《离散数学及其应用教育部重点试验室工作总结报告福州大学》由会员分享，可在线阅读，更多相关《离散数学及其应用教育部重点试验室工作总结报告福州大学（5页珍藏版）》请在金锄头文库上搜索。
1、离散数学及其应用教育部重点实验室工作总结报告（2011年3月18日）实验室名称： 离散数学及其应用教育部重点实验室 主管部门： 福建省教育厅依托单位： 福州大学实验室概况: 在迅速发展的计算机科学技术及信息技术等领域，离散数学是重要的基础学科和支撑学科，它的发展和应用是影响一个国家科学技术发展水平的重要因素。以福州大学“离散数学与理论计算机科学研究中心”为依托的离散数学及其应用教育部重点实验室于2007年7月获教育部批准立项建设。目前，实验室共有固定研究人员27人，其中教授16人，副教授4人。实验室由马志明院士担任学术委员会主任，范更华教授担任实验室主任。实验室位于福州大学铜盘校区。2007年
2、11月完成了实验室装修一期工程；2009年3月完成了二期装修工程，达到 “环境优美、设备一流”。按国际研究所标准建设基础设施，为每位研究人员及来访学者提供40平米宽敞办公室及一流科研设备。为每位研究生提供一个工作位及台式电脑。已建成无线网覆盖实验室3000平米的科研、办公场所。重视网络建设，保证网络高速畅通。订购相关专业的国外数据库及原版图书，已基本建成一流的专业图书资料室。一、 实验室现有三个研究方向：图论与组合数学、大规模集成电路设计中的数学方法、优化理论与算法。二、 在本年度，实验室主任范更华教授获全国优秀科技工作者。实验室在研科研项目国家973计划课题1项，国家自然科学基金7项，其中重
3、点项目1项，面上项目6项，新增国家973计划课题1项，为1. 大规模集成电路物理设计中关键应用数学理论和方法（2011CB808003），范更华 新增国家自然科学基金3项，其中面上项目2项，青年项目1项，分别是：1. 超大规模集成电路多目标划分的算法研究（61070020），朱文兴，国家基金面上项目。2. 近景摄影测量中的自动图像分割技术（11071270），王美清，国家基金面上项目。3. 几类图染色问题的研究（11001055），侯建锋，国家基金青年项目。实验室在2010年8月顺利完成了国家重点基础研究发展计划（973计划）课题“大规模集成电路设计中的图论与代数方法（2006CB805904
4、）”。课题实施期间，课题组共发表研究论文133篇，其中被SCI收录104篇；由于出色完成了该课题，我们将继续承担新一轮的973课题：大规模集成电路物理设计中关键应用数学理论和方法（2011年1月至2015年12月）。三、 实验室不仅是高水平科学研究中心，也是高层次人才培养基地。实验室以应用数学、计算机应用技术省级重点学科，国家集成电路人才培养基地，离散数学“211工程”建设重点学科，应用数学博士点以及两个一级学科硕士点（数学、计算机科学与技术）为支撑，形成具有一定规模的离散数学高层次人才培养体系。实验室将充分利用自身的条件，围绕主攻方向，提升开放层次，促进学术交流与合作，使实验室整体研究水平达
5、到国内领先水平，某些研究方向达到国际先进水平，为国家及福建地方建设做出突出贡献。本年度培养博士研究生2名，硕士研究生21名。四、 年度科研成果实验室在各个研究问题方面开展了深入地研究工作，在课题研究中取得了一些很好的研究结果。本年度课题组研究成员在国内外重要专业刊物上发表SCI收录论文27篇， EI收录论文6篇，具体研究成果如下：（1）图论与组合研究工作关于连通图支撑树的计数问题，给出了连通图支撑树个数的紧的上界，并且考虑的连通度为k的图的支撑树的个数，同时给出了连通图支撑树的个数和图色数之间的关系，其结果发表在Applied Mathematics Letters上。一个图的Laplacia
6、n谱半径是指该图Laplacian矩阵的最大特征值，对于图n个顶点，最大度为，直径为D的非正则图，Shi给出了该图的Laplacian谱半径的上界，我们改进了该上界，并且证明了该上界给出了在某些情况是紧的，同时，给出了不含三角形图的Laplacian谱半径的上界。对于连通二部图，给出了Laplacian谱半径紧的上界和下界，从而改进了Shi的结果。在图染色领域，考虑了图的列表染色问题，给出了考虑图列表染色的新的思路，并且用该思路证明了某些形式的完全k部图是(2, 2)-total weight choosable，并证明了除了一条边外的所有完全二部图都是(1, 2)-total weight
7、choosable。研究了稀疏图和平面图的列表全染色问题，证明了如果平面图的最大度不超过8，则其列表全色数不超过11；如果平面图最大度至少是8，且不含5-圈，则其列表全色数等于最大度加一；如果图的最大度是4，并且最大平均度不超过3，则其列表全色数是5，该项成果发表在Information Processing Letters上。考虑了有向图博弈染色，给出了有向图博弈色数以及弱的博弈色数的定义，证明每个定向平面图的博弈色数不超过9，每个定向外平面图的博弈色数不超过4，同时研究了有向图强博弈染色，证明了每个定向平面图的强博弈色数不超过16。考虑的外平面图的无圈边染色问题，完全确定了外平面图无圈边色
8、数的上界，其结果发表在Journal of Graph Theory上。在化学图论方面，一个图的能量是指该图所有特征值绝对值的和，一个图的能量小于图的顶点数，称该图是hypoenergetic，我们研究了图的能量，构造了顶点数为4n+2的树T，使得T是hypoenergetic，从而验证了Gutman等人在2008年提出的猜想，该文发表在Applied Mathematics Letters上。同时考虑的图的能量和Estrada指标之间的关系，给出了图Estrada指标紧的上界。（2）VLSI中的图论与优化算法研究工作为了开展大规模集成电路设计领域的研究工作，实验室于2010年建立了一个150
9、m2的大规模集成电路设计EDA实验室，拥有16个研究工作位，装备国产熊猫EDA系统软件16台套，对所有实验室研究成员和研究生开放使用。布局是大规模集成电路电路设计重要环节，决定了超大规模集成电路芯片的性能，尺寸，产量和可靠性，我们给出了基于粒子群优化算法新的智能决策，利用该决策可以超大规模集成电路较快的获得一个可行的电路物理布局。同时在遗传算法的变异和交叉的原则中引入了粒子群优化算法，可以使得该算法脱离局部最优和实现更好的多样性。实验通过采用MCNC和GSRC基准测试表明，该算法是有效的。同时该算法可以避免局部最小，并有很好的收敛性。实验结果表明所提出的方法可以大大帮助集成电路设计中的布局决策
10、，其结果发表在Soft Comput.上。从计算的角度来看，超大规模集成电路布局规划是一个NP-困难问题。我们给出了非分层和模块VLSI布图规划问题的一个混合演化算法（HGA），该算法使用一个有效的遗传搜索方法来探索搜索空间和一种有效的局部搜索方法，利用信息在搜索区域。MCNC基准的实验结果表明该算法是有效的。同时，借助于进化算法和模拟退火算法的概念，给出了另外一种混合演化算法，实验表明该算法也是有效的。（3）优化理论与算法我们提出了一个高效求解三维装箱问题（Three Dimensional Container Loading Problem 3D-CLP）的混合模拟退火算法；研究了极大可满
11、足性问题的局部搜索算法，提出了用单纯形法产生“初始概率”(每个变量取1的概率)，用“初始概率”对局部搜索算法中变量的初始随机指派进行适当的约束；研究了箱约束非线性整数规划问题，提出了该问题的离散动态凸化算法，同时还证明了算法的收敛性；对非线性约束连续全局优化问题，我们构造一个结合罚函数的辅助函数，构造了解非线性约束连续全局优化的一个动态凸化算法，该算法避免了传统罚函数法中罚参数选取困难的问题。五、 学术交流为推动福建省数学教育和研究活动开展，在范更华教授的大力倡导下，协同福建省数学会，于2010年10月16日至17日召开福建省首届数学大会，1100多名来自全省各地高校和中学的数学教师参会。为了
12、使基层农村学校数学教师有机会参加会议，在省政府、省教育厅等部门的大力支持下，会议为300名工作在乡镇学校的教师提供了交通、住宿等经费支持。会议期间，“院士与中学教师互动座谈会”和“专家讲座”等专项活动交流和讨论热烈，这种面对面的交流让来自中小学的数学教师受益匪浅、耳目一新，为广大基层学校特别是农村学校教师提供了良好的学习机会，有效地调动了全省中学教师参与数学研究的积极性，对提升福建省数学教育水平起到了积极的推动作用。2010年5月，实验室协同中国运筹学会，召开中国运筹学会第八届三次常务理事会。在本年度，共有10余位国内外知名学者到校访问，并作报告和进行合作研究，其中包含入选者，浙江师范大学教授朱绪鼎，香港浸会大学数学系主任朱力行，加拿大Simon Fraser大学教授Pavol Hell等。
