《计算理论》课程教学大纲

更新:2019-04-23 17:00:51 阅读:人次

一、课程名称(中英文)

中文名称:计算理论

英文名称:Theory of Computation

二、课程性质

专业方向课选修,双语教学

三、学时与学分

总学时:32(理论学时:32学时)

学分:2

四、先修课程

离散数学、算法设计与分析

五、授课对象

本课程面向计算机科学与技术实验班(ACM班)学生开设

六、教学内容与学时安排

(一)形式语言理论介绍(Formal Language Theory)

本章的主要知识点包括 有限状态自动机与正则表达式,自动机中非确定性,下推自动机与上下文无关语言。

本章课堂教学学时4学时,建议学生课后学习4学时。

(二)图灵机介绍

本章的主要知识点包括确定性图灵机,Church Turing Hypothesis,确定性图灵机的变种,非确定性图灵机以及通用图灵机。

本章课堂教学学时3学时,建议学生课后学习4学时。

(三)可计算理论介绍

本章的主要知识点包括可数与不可数集合,判定与不可判定语言以及对角化证明方法。

本章课堂教学学时2学时,建议学生课后学习4学时。

(四)复杂性度量介绍

本章的主要知识点包括确定性时间复杂度,非确定性时间复杂度,空间复杂度以及时间和空间分层定理。

本章课堂教学学时2学时,建议学生课后学习4学时。

(五)P、NP完全与多项式层级

本章的主要知识点包括多项式时间归约,对数空间归约,P、NP与NP-完全,Cook-Levin定理以及3SAT问题,coNP,EXPTIME、NEXPTIME与多项式层级(Polynomial Hierarchy)。

本章课堂教学学时4学时,建议学生课后学习6学时。

(六)空间复杂性

本章的主要知识点包括PSPACE完全,Savitch证明,L、NL与对数空间归约。

本章课堂教学学时2学时,建议学生课后学习4学时。

(七)并行计算复杂性

本章的主要知识点包括P-完全,Log-depth电路,NC类,NC类与并行计算的关系,NC并行计算示例。

本章课堂教学学时2学时,建议学生课后学习4学时。

(八)随机复杂性

本章的主要知识点包括RP,BPP, ZPP,概率图灵机示例与概率判定树。

本章课堂教学学时3学时,建议学生课后学习4学时。

(九)计数复杂性初步

本章的主要知识点包括#P概念,#P完全问题举例(Counting Cycle Covers,Counting Bipartite Matchings月Permanent计算)。

本章课堂教学学时2学时,建议学生课后学习4学时。

(十)交互证明

本章的主要知识点包括零知识证明,Arthur-Merlin Games,以及IP=PSPACE证明。

本章课堂教学学时4学时,建议学生课后学习6学时。

(十一)不可近似性(近似难度)介绍

本章的主要知识点包括PCP定理介绍、MAX-SAT问题的近似难度分析以及Hardness Amplification。

本章课堂教学学时4学时,建议学生课后学习6学时。

七、教学参考书及文献

教学参考书:

1.Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach, Cambridge University Press, 2009.

2.Michael Sipser. Introduction to the Theory of Computation, 3rd edition, Cengage Learning, 2012.

3.Oded Goldreich. Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008.

4.John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation (3rd Edition), Addison-Wesley Longman Publishing, 2006.

5.David Harel. Computers Ltd.: What They Really Can't Do, Oxford University Press, 2000.

6.张立昂.可计算性与计算复杂性导引(第3版),北京大学出版社,2011.

八、课程成绩评定与记载

课程成绩=课后作业(30%)+终结性考试(70%)

终结性考试形式:闭卷

《计算理论》课程组:何琨,华强胜,金燕