年报告离散数学福州大学由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“福州大学离散数学”。
离散数学及其应用教育部重点实验室工作总结报告（2014年1月28日）
实验室名称： 离散数学及其应用教育部重点实验室 主管部门： 福建省教育厅 依托单位： 福州大学
实验室概况: 在迅速发展的计算机科学技术及信息技术等领域，离散数学是重要的基础学科和支撑学科，它的发展和应用是影响一个国家科学技术发展水平的重要因素。以福州大学“离散数学与理论计算机科学研究中心”为依托的离散数学及其应用教育部重点实验室于2007年7月获教育部批准立项建设。目前，实验室共有固定研究人员27人，其中教授16人，副教授4人。实验室由马志明院士担任学术委员会主任，范更华教授担任实验室主任。实验室位于福州大学铜盘校区。2007年11月完成了实验室装修一期工程；2009年3月完成了二期装修工程，达到 “环境优美、设备一流”。按国际研究所标准建设基础设施，为每位研究人员及来访学者提供40平米宽敞办公室及一流科研设备。为每位研究生提供一个工作位及台式电脑。已建成无线网覆盖实验室3000平米的科研、办公场所。重视网络建设，保证网络高速畅通。订购相关专业的国外数据库及原版图书，已基本建成一流的专业图书资料室。
一、实验室现有三个研究方向：图论与组合数学、大规模集成电路设计中的数学方法、优化理论与算法。
二、本年度实验室在研科研项目国家973计划课题1项，国家自然科学基金13项，其中重点项目1项，面上项目4项，青年项目8项。教育部重点项目1项，高等学校博士学科点专项科研基金1项。新增国家自然科学基金4项，均为青年项目，分别是： 1.图的完美匹配计数及其相关问题的研究（11301085），林峰根。2.变密度粘性流体动力学中非线性瑞利-泰勒不稳定性的数学理论研究（11301083），江飞。3.保持全局形状和视觉舒适度的2D和3D媒体适应方法（61300102），牛玉贞。
4.不相交QoS路径与斯坦纳网络的近似算法研究（61300025），郭龙坤。
实验室成员于元隆博士获福建省“闽江学者奖励计划”项目资助，郭文忠博士获福建省自然科学基金杰青项目资助。
实验室成员陈国龙教授和郭文忠博士主持的“内网安全监控平台研制及其产业化”获福建省科技进步二等奖，该项研究针对日益严重的内网安全问题，深入分析内网所面临的各种安全威胁，从身份认证、网络接入控制、数据保护、移动存储设备监控以及网络访问监控等关键问题入手开展内网安全关键技术的创新开发，具体如下：(1)研发了基于USB 安全锁、手掌静脉识别、用户名与密码的统一身份认证平台，采用多因子身份认证方式，解决内网用户身份的合法性和真实性验证问题。(2)研发了一种高安全性的内网安全综合管理的网络接入控制方案，通过内网安全综合管理系统、统一身份认证平台、802.1x 交换机和Radius 服务器之间的联动实现对网络接入终端的身份验证和接入安全控制。(3)研发了一种基于微过滤器模型及内嵌加密标识的数据动态加解密技术的数据保护技术。(4)研发了基于新一代WFP 模型的网络数据包监控和过滤引擎，设计了一种融合防病毒和入侵检测功能的多功能综合网关。
实验室成员朱文兴教授主持的“连续全局优化和非线性整数规划的算法研究”获福建省自然科学奖三等奖。
三、实验室不仅是高水平科学研究中心，也是高层次人才培养基地。实验室以应用数学、计算机应用技术省级重点学科，国家集成电路人才培养基地，离散数学“211工程”建设重点学科，应用数学博士点以及两个一级学科硕士点（数学、计算机科学与技术）为支撑，形成具有一定规模的离散数学高层次人才培养体系。实验室将充分利用自身的条件，围绕主攻方向，提升开放层次，促进学术交流与合作，使实验室整体研究水平达到国内领先水平，某些研究方向达到国际先进水平，为国家及福建地方建设做出突出贡献。本年度培养博士研究生3名，硕士研究生23名。
四、年度科研成果
实验室在各个研究问题方面开展了深入地研究工作，在课题研究中取得了一些很好的研究结果。本年度课题组研究成员在国内外重要专业刊物上发表SCI收录论文36篇，EI收录4篇，主要研究成果如下：
（1）VLSI中的图论与优化算法研究工作
1、设计并实现了超大规模集成电路混合单元布局问题的一个新的布局流程，主要思想是用版图规划算法指导电路单元的布局。该布局流程包含4个步骤：1）在多级框架下，利用递归划分技术对电路单元聚类；2）对每层的模块用版图规划算法布局；3）用局部移动技术确定宏单元的精确位置；4）当宏单元的位置确定后，用标准单元布局算法确定标准单元的具体位置。与当前最好的混合单元布局器相比，对IBM mixed-size benchmark circuits和modern mixed-size(MMS)placement benchmarks，我们的布局器在合理的计算时间内能得到最好的平均半周长线长。经过分析发现，我们的布局器的划分和模块形成阶段（即聚类阶段）占用了总的计算时间的2/5，所以划分和模块形成阶段是我们的布局器的主要瓶颈，需要进一步研究。
2、由于图划分问题在布局问题中有直接的应用，我们研究赋权图的最大二等分问题，该问题是NP困难问题。我们构造了该问题的一个memetic算法，其中包括一个快速的局部搜索过程，一个的交叉算子和种群修改策略。这些策略能在全局搜索和局部搜索之间取得平衡。利用文献中的大量有800-10000个顶点的标准测试实例对我们所构造的算法进行测试，我们的算法能取得所测试例子的比当前最好结果更好的解。与著名的circut算法相比，我们的算法在割值方面的提高幅度在0.02% 到4.15%之间。从而实验表明了我们的memetic算法可以在可接受的计算时间内获得高质量的解。
3、研究了超大规模集成电路划分问题的动态凸化算法。利用辅助函数，把集成电路划分问题等价变换为有约束非线性整数规划问题，并构造了动态凸化算法这一全局搜索算法。我们修改了集成电路划分的FM算法，使适合我们的整数规划问题。理论分析和实际计算表明，我们的算法可以成功跳出离散局部极小解。在ACM/SIGDA和ISPD98的测试实例集上的测试表明，我们的局部搜索算法得到的结果比FM算法优58%以上。为解决大规模集成电路划分问题，我们把所构造的算法集成到多级划分框架MLPart中，在同一测试实例集上的测试表明，算法所得到的结果比MLPart优3-7%。
4、划分与超大规模集成电路紧密相关，我们研究了图的max-k-cut问题，把该问题转化为非线性整数规划问题。改进了集成电路划分的FM算法，构造了该问题的一个局部搜索算法。为跳出局部极大解，我们构造了一个辅助函数，理论分析和实验表明，对该函数的局部搜索，可以找到更好的局部极大解。对k=2的情况，用大量的标准实例计算实验表明，算法不仅可以求到当今其它基于局部搜索的算法不能找到的解，而且效率较优。对k≧2的情况，算法也是稳定的，且可以与国际上最新的算法比较。
5、研究了从超大规模集成电路全局布局中提取的非线性规划问题，其目标函数是对半周长线长的基于L1范数的近似，是两个凸函数的和，约束是密度函数约束，是一系列Lipschitz连续非凸函数构成的不等式。该问题对交替方向法来说是新问题，我们构造了基于临近点的交替方向法，在适当条件下证明了算法收敛于问题的KKT点。在实现的时候，我们对临近点参数采用自适应策略。把所构造的算法嵌入到NTUplacer中，用IBM的标准测试实例测试，对18个例子所获得的半周长线长均比NTUplacer3的短，其中例子IBM01的要短3.21%，IBM08的要短6.97%。与其他的最新的布局工具相比，我们的算法在18个例子中多数占优势。该算法的优点是计算效果好，但是算法的计算时间太长，需要在以后的研究中加以克服。
6、研究了超大规模集成电路标准单元布局问题的ell-1模优化模型。我们把半周长线长目标函数用ell-1模近似，把单元重叠函数用非光滑函数近似，然后用非光滑共轭次梯度法求解所得到的非光滑优化模型，进而构造了一个标准单元布局的多级框架。该框架包含聚类阶段和解聚类阶段。在聚类阶段中，我们改进了best-choice电路聚类算法，以实现电路的全局视图。在解聚类阶段中，用我们所构造的非光滑优化技术对全局布局问题逐级求解，其中对目标线长和密度约束需要做仔细的平衡。我们用IBM standard cell benchmark circuits 和 Peko suites的测试例子测试所构造的布局工具，初步实验表明该工具能在合理的时间内获得高质量的布局效果，而且在时间和解的质量上与当前主流的布局工具相比，有很大的优越性。
7、总体布线是超大规模集成电路物理设计中极为重要的一个环节。针对此问题，我们在研究中引入了非曼哈顿结构，继而在非曼哈顿结构的基础上开展了总体布线中布线树的相关构造工作，包括：1）超大规模集成电路中绕障X结构Steiner树问题已经被证明是一个NP完全问题，而且对于超大规模集成电路中的非曼哈顿结构布线问题有着非常重要的意义。本课题提出了一种有效的绕障X结构Steiner树算法。研究成果发表在国际会议《IEEE ICNC2013》。本课题在绕障X结构Steiner树的基础上进一步考虑多层结构，基于粒子群优化方法提出了多层绕障X结构Steiner最小树算法；2）超大规模集成电路中性能驱动非曼顿结构Steiner树是VLSI布线中非常重要的布线树模型。本课题设计一个基于多目标离散粒子群优化算法的性能驱动Steiner树构造算法。
（2）图论与组合研究工作
课题组开展了关于超图的张量谱理论的研究工作，并对于图与超图的划分问题相关的谱与张量谱方法等问题进行了系统研究，取得了多项有意义的结果。
1.著名的Erdős–Sós猜想是说如果图G的平均度大于k-1，则G存在k条边的任意树，对于该猜想的成果较少，研究方法较单一，我们对该猜想进行了深入研究，利用新的思路证明了如果图G的平均度大于k-1，则G存在k条边的任意蜘蛛，其中k≥(n+5)/2，其结果为研究Erdős–Sós猜想提供了新的思路。
2.图的无符号Laplace矩阵的研究是图谱理论研究的重点问题，我们将图的无符号Laplace矩阵推广到无符号，从而研究一致超图谱的性质，给出了超图的无符号Laplace张量谱理论的一些基本性质，特别是，偶一致超图无符号Laplace张量的最小和最大的Z-特征值的研究，并研究了与这两个Z-特征值有关的超图的边割和边连通性。
3.给出了偶一致超图无符号Laplace张量的H-特征值，并证明了H-特征值的一些基本性质，对取到最小和最大无符号Laplace张量的H-特征值的偶一致超图进行了刻画，同时，研究了H-特征值与一致超图的割，最小度，最大度的关系。同时，利用最小和最大无符号Laplace张量的H-特征值给出了一致超图边割和边连通度的上下界。
4.研究了平面图的无圈边染色问题，给出了平面图无圈边色数的上界，该上界改进了《SIAM J.Discrete Math.》上的结果。同时考虑了围长为5的平面图的无圈边染色，给出了这类图无圈边色数的紧的上界，同时证明了，如果该类图的最大度至少是4，则其无圈边色数等于最大度，该结果改进了原有一系列结果。
五、学术交流
2013年5月，实验室和福州大学数学与计算机学院，主办了“图与超图谱理论国际研讨会议”，本次国际学术会议是首次在国内召开的有关图与超图谱理论的专题研讨会，会议主席为香港理工大学祁力群教授和厦门大学张福基教授，执行主席为福州大学常安教授。共有来自美国、荷兰、澳大利亚、南非、中国香港地区和国内北京大学、清华大学、上海交通大学高校的60多位学者和博、硕士研究生参加了此次研讨会议，其中包括北京大学张恭庆院士、美国威斯康辛大学Richard Brualdi教授（University of Wisconsin-Madison）、宾夕法尼亚州立大学Winnie Li教授（Pennsylvania State University）、荷兰Tilburg 大学Willem Haemers教授（Tilburg University）、同济大学邵嘉裕教授等多位国内外知名学者。福州大学副校长、离散数学及其应用教育部重点实验室主任范更华教授在会议开幕式上代表福州大学致辞欢迎并介绍了福州大学概况。
在为期4天的研讨会期间，共有31位与会国内外学者做了图与超图谱理论研究领域最新研究成果的学术报告，包括20个40分钟会 6 议邀请报告：11个20分钟会议报告。这些报告内容涉及图的谱理论、张量谱理论、超图的张量表示及其谱理论，以及与图与超图谱理论相关的应用问题研究等。另外，会议在5月30日下午专门安排了半天的3个专题报告，由香港理工大学祁力群教授等系统介绍了关于张量特征值理论和超图张量特征值问题的基础知识和研究进展情况。本次会议为图与超图谱理论研究领域的国内外专家学者开展学术交流和合作研究提供了一次难得机会，与会者一致认为这是一次高水平的学术研讨会，会议报告和讲座体现和代表了国内外相关研究的先进水平和本领域国内外研究现状和趋势，将对于国内相关研究领域的科学研究和发展起到积极的促进作用，并有助于开拓与会研究生的视野和研究水平的提高，促进青年研究人才的培养。本次会议得到了教育部高校数学中心资助！
2013年12月，实验室主办了“2013 International Conference on Cloud Computing and Big Data(CloudCom-Asia)”国际学术研讨会，共有100多位学者和博、硕士研究生参加了此次研讨会议。2013年3月，实验室联合国家自然科学基金委，召开了数学天元基金“问题驱动的应用数学研究”研讨会，5月，在实验室召开了973计划项目“信息及相关领域重大需求的应用数学研究”交流会。在本年度，共有10余位国内外知名学者到校访问，并作报告和进行合作研究，其中包含美国伊利诺伊大学教授Douglas West，美国乔治亚理工大学教授郁星星，美国乔治亚州立大学教授陈冠涛，山东大学教授吴建良等。
