算法与复杂性COMP36111

课程内容：

本课程是对计算复杂性理论的独立介绍。除了对基本算法和数学符号有所了解之外，无需其他先决条件。教学将完全采用传统授课方式，辅以规定的课程教材。课程旨在使学生熟悉计算复杂性理论的基本概念和技术。

课程大纲：

- 有向图：拓扑排序和塔让算法。

- 无向图：并集查找、Grzegorczyk层次、并集查找的复杂度。

- 流网络：最优流、二维匹配、最小成本最大流。

- 图灵机和可计算性。

- 计算复杂度的度量。

- 分离定理。

- 命题逻辑和复杂度：SAT、k-SAT、Horn-SAT和QBF-SAT（第一部分）。

- 困难和简化：库克定理。

- 图论问题：三色问题、哈密顿电路和欧拉电路、TSP。

- 萨维奇定理和伊默曼-塞莱普塞尼定理。

- 命题逻辑与复杂性：SAT、k-SAT、Horn-SAT和QBF-SAT（第二部分）。

- 拉德纳定理。

- 其他内容：一阶逻辑与复杂性：决策问题。

学习成果：

通过本课程的学习，学生将能够：

1、理解与图灵计算模型相关的常见复杂度类别的标准层级。

2、理解（问题）简化与计算难度的概念，并熟悉确定较低复杂度界限的技术——特别是NPTime-hardness。

3、熟悉复杂度理论中最重要、最核心的定理（库克定理、拉德纳定理、萨维奇定理、伊莫曼-塞莱普塞尼定理）。

4、查阅并理解复杂度理论方面的科学文献。

5、分析一系列问题的计算复杂度。