2011年年报告-福州大学离散数学与理论计算机科学研究中心.docVIP

离散数学及其应用教育部重点实验室工作总结报告 （2012年2月10日） 实验室名称： 离散数学及其应用教育部重点实验室 主管部门： 福建省教育厅 依托单位： 福州大学 实验室概况: 在迅速发展的计算机科学技术及信息技术等领域，离散数学是重要的基础学科和支撑学科，它的发展和应用是影响一个国家科学技术发展水平的重要因素。以福州大学“离散数学与理论计算机科学研究中心”为依托的离散数学及其应用教育部重点实验室于2007年7月获教育部批准立项建设。目前，实验室共有固定研究人员人，其中教授1人，副教授人。实验室由马志明院士担任学术委员会主任，范更华教授担任实验室主任。“环境优美、设备一流”。按国际研究所标准建设基础设施，为每位研究人员及来访学者提供40平米宽敞办公室及一流科研设备。为每位研究生提供一个工作位及台式电脑。已建成无线网覆盖实验室3000平米的科研、办公场所。重视网络建设，保证网络高速畅通。订购相关专业的国外数据库及原版图书，已基本建成一流的专业图书资料室。 实验室现有个研究方向：图论与组合数学、大规模集成电路设计中的数学方法、优化理论与算法，刘月。 图的Ramsey理论中的随机方法，林启忠。 Volterra 方程与高维分数阶扩散方程的理论与数值研究，李娴娟。 新增教育部重点项目1项：动态拓扑下WSN任务调度中多目标优化问题的算法研究，郭文忠。 实验室成员侯建锋博士获福建省自然科学基金杰青项目资助。 实验室不仅是高水平科学研究中心，也是高层次人才培养基地。实验室以应用数学、计算机应用技术省级重点学科，国家集成电路人才培养基地，离散数学“211工程”建设重点学科，应用数学博士点以及两个一级学科硕士点（数学、计算机科学与技术）为支撑，形成具有一定规模的离散数学高层次人才培养体系。实验室将充分利用自身的条件，围绕主攻方向，提升开放层次，促进学术交流与合作，使实验室整体研究水平达到国内领先水平，某些研究方向达到国际先进水平，为国家及福建地方建设做出突出贡献。 年度科研成果 实验室在各个研究问题方面开展了深入地研究工作，在课题研究中取得了一些很好的研究结果。本年度课题组研究成员在国内外重要专业刊物上发表研究SCI收录论文28篇， EI收录论文7篇。主要科研成果如下： （1）VLSI中的图论与优化算法研究工作 在大规模集成电路设计理论研究方面，课题组在开展拟定研究工作的同时, 进一步加强与集成电路设计研发和研究机构的合作，先后派出课题组成员和博士研究生共计9人次到北京华大电子了解我国目前唯一的集成电路设计工具“九天”EDA的研发进展，并针对该项研发所提出的多项实际研究问题，从理论和实际两个方面都提出了解决方案。在北京华大九天公司正在着力开发的自动化对称布线软件研发中，由于当前国内外对对称布线的系统研究非常少, 在实际布线过程中如果存在线网需要对称布线都是采用手工布线, 而且手工布线也只能解决布线层和已布线网比较少的情况, 还经常出现找不到问题的解的情况。课题组得到了H-V模型下对称布线问题等价于在有效连通图中找所有引脚对应的点的一棵斯坦纳树并提出一个解决对称布线算法。本方法适合无网格且水平和垂直布线层交替出现的模型。此方法经过修改还得到一层既可以水平布线又可以垂直布线的模型下关于对称布线问题的方法。这项研究为自动化对称布线软件的开发提供了一个方法和理论保障；布线在超大规模集成电路布局面积中是一个关键性问题。Szymanski证明找一个通道布线的最小宽度是NP-困难的。课题组研究证明了通道对应的图CCG的一个最少平行团覆盖等价于一个垂直限制无圈且不添加新的空列和狗腿到网格上的二层曼哈顿模型通道布线的一个最优解。根据这个结论我们还给出了一个解决二层曼哈顿模型通道布线的一个启发式算法。为华大九天公司开发的自动化布线软件中自动化通道布线软件的开发提供了一个可行的解决方案；我们使用图论的方法对David Szeszler的2层具有Manhattan模型的通道布线的算法进行改进，并给了一个新的算法，这个算法比以前的算法所用层数更少，该项研究可用在华大九天公司正在开发的布线工具通道宽度的估计。 研究并设计出器件匹配问题的一种自动匹配方法（MatchingLiu算法），该算法已用C程序实现。通过华大九天公司的评估，认为该算法快速、有效，可以帮助弥补公司新一代IC设计平台Aether的自动匹配工具的空白。 研究了超大规模集成电路标准单元的布局问题。布局是超大规模集成电路物理设计的关键步骤，影响了芯片的可布线性、性能和功耗。我们研发了一个标准单元布局器，其中包含了多层全局布局和详细布局两个阶段。在全局布局阶段，我们用非线性规划方法和最优聚类技术对电路聚类，在解聚类阶段用迭