英国算法与复杂性COMP36111Algorithms and Complexity课程介绍

算法与复杂性

COMP36111

Algorithms and Complexity

学习目标

课程内容：

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

课程大纲：

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

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

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

- 图灵机和可计算性。

- 计算复杂度的度量。

- 分离定理。

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

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

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

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

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

- 拉德纳定理。

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

学习成果：

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

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

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

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

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

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

展开全部

英国算法与复杂性课程辅导

课程课件讲解

同步海外各大院校学习进度+原版课件，PPT课件知识点讲解，包含但不限于作业讲解、考试突击辅导、论文essay辅导等，提高GPA，解决课业难题。
作业知识点讲解

作业题目讲解,topic+outline讲解，作业题难点知识点、答题思路指导。
考前冲刺辅导

帮助学生考前快速冲刺，考前直击重点/作答技巧，重点难点梳理+讲解，预测exam考点，更有独家学习资料与干货分享。
挂科appeal

学术不端、论文低分重复度高申诉appeal、考试作弊挂科听证会申诉，全程申诉老师陪同指导，高质量申诉信写作，听证会材料搜集整理，抓住申诉机遇。

免费获得学习规划方案

已有 1129 位留学生获得学习规划方案

英国

*已对您的信息加密，保障信息安全