求解np难度问题的现代方法-华中科技大学研究生院

求解np难度问题的现代方法-华中科技大学研究生院 附件5(计算机 学院(系、所)全英 研究生课程简介(中文) 课程名称:求解NP难度问题的现代方法 课程代码:210.813 课程类型:, 博士专修课程 ? 硕士专修课程 考核方式: 全英文考试 教学方式: 全英文讲授 适用专业: 计算机 适用层次:? 硕士 , 博士 开课学期: 秋季 总学时: 32 学分:2 先修课程要求:可计算性与计算复杂性理论 或 算法与分析 课程组教师姓名 职 称 专 业 年 龄 学术方向 计算机软件与理论 何琨(负责人) 副教授 40 算法设计与分析 计算机软件与理论 许如初 副教授 56 算法设计与分析 课程负责教师留学经历及学术专长简介: 何琨，研究领域为NP难度问题的现实求解。对若干典型的NP难度问题如Packing问题、Scheduling问题等进行了系统、深入的研究，取得了一系列具有国际影响的创新性成果。2011.9-2012.8在美国斯坦福大学留学访问，访问期间的方向为组合优化。 许如初，研究领域为NP难度问题的现实求解。对若干典型的NP难度问题如Packing问题、团簇问题等进行了系统、深入的研究，取得了一系列具有国际影响的创新性成果。 课程教学目标: 结合教师在科研中遇到的具体困难问题，采用研讨的方式，使学生了解和把 握教师本人和当前国际上流行的求解NP难度问题的一些有代性的方法，包括 它们的思想来源、方法和具体技术。 课程大纲:(章节目录) 第一章 算法中智慧的来源 ?1.1 拟物思想 ?1.2 拟人思想 ?1.3 其他思想 第二章 求解NP难度问题的拟物方法 ?2.1求解圆形Packing问题的拟物算法 ?2.2 求解SAT问题的拟物算法 ?2.3 求解Covering问题的拟物算法 第三章 求解NP难度问题的拟人方法 ?3.1 求解矩形Packing问题的拟人算法 ?3.2 求解SAT问题的拟人算法 ?3.3 求解Covering问题的拟人算法 第四章 求解NP难度问题的拟物拟人方法 ?4.1 求解Packing问题的拟物拟人算法 ?4.2 求解SAT问题的拟物拟人算法 ?4.3 求解Covering问题的拟物拟人算法 第五章 与其它现代求解方法的结合 ?5.1 与遗传进化方法的结合 ?5.2 与模拟退火方法的结合 ?5.3 与其他搜索方法的结合 全英文教材: 1. Colin R Reeves, Modern Heuristic Techniques for Combinational Problems, McGraw-Hill Book Company Europe, London, New York, 1995. 2. 任课教师发表的相关英文论文. 主要参考书: ,.黄文奇, 许如初著, 近世计算理论导引——NP难度问题背景前景及其求解 算法研究, 科学出版社, 北京, 2004.