| 课程编号： |
H333-20 |
| 课程名称： |
组合最优化 Combinatorial
Optimization |
|
开课学校、学院、专业： |
华东理工大学理学院 |
| 上课地点： |
华东理工大学 |
|
教学方式： |
授课 |
|
考试方式： |
笔试 |
|
适合专业： |
应用数学,计算机相关专业 |
|
总学时和学分： |
开课学时54 |
| 课程作用与任务： |
组合最优化研究离散现象中所出现的优化问题、性质与算法，在工程技术、经济管理、计算机技术等方面有广泛应用。本课程学习组合最优化的常见算法和算法复杂性的基本理论，为应用数学专业优化理论方向的硕士研究生从事学位论文工作打下基础，使计算机相关专业的硕士研究生了解算法分析的理论。 |
| 先修课程： |
线性代数 |
| 教学内容与学时分配： |
一、线性规划的原始对偶算法 3学时
二、最大流问题的原始对偶算法 3学时
最大流最小截定理，Ford-Fulkerson标号算法，算法的有限性问题
三、最短路算法 3学时
四、最小费用流的原始对偶算法 3学时
圈算法，迭加算法与运输问题的联系
五、算法与复杂性 3学时
可计算性，算法的时间界，算法分析，多项式时间算法
六、最大流问题的有效算法 6学时
图的搜索，标号算法的病症，最大流的改进算法
七、匹配算法 6学时
匹配，二部图的匹配算法，非二部图的匹配算法
八、指派问题的匈牙利方法 3学时
九、支撑树与拟阵 6学时
最小支撑树问题的多项式时间算法，Greedy算法，拟阵
十、NP完备问题 6学时
最优化问题的三种提法，P类和NP 类，Cook定理
十一、再论NP完备性 3学时
拟多项式时间算法，强NP完备性，非确定性图灵机
十二、近似算法 6学时
点覆盖、货郎问题与背包问题的近似算法，一些否定的结果
十三、分支定界和动态规划 3学时 |
| 参考文献： |
1.C.H. Papadimitriou,
K. Steiglitz著.刘振宏，蔡茂诚译.
组合最优化：算法和复杂性. 北京：清华大学出版社，1988
2.M.R.Garey, D.S. Johnson著. 张立昂，沈泓，毕源章译. 计算机和难解性：NP完全性理论引导. 北京：科学出版社，1987
编制人：俞文鱼此 ，刘朝晖
审核人：何志庆 |
