计算理论
课程编码：480177081202D4005
英文名称：Theory of Computing
课时：20
学分：1.00
课程属性：研讨课
主讲教师：张涌
教学目的要求
"计算理论是计算机科学的核心课程。通过学习计算理论，我
们可以理解什么问题是可计算的，什么问题是不可计算的；解决
问题需要多少时间，多少空间；如何平衡算法质量和效率等计算
机领域中的最根本问题。"
预修课程
离散数学，算法设计与分析
大纲内容
第一章 形式语言理论 2.0学时 张涌
第1节 形式语言理论
第二章 图灵机 2.0学时 张涌
第1节 图灵机
第三章 可计算理论 2.0学时 张涌
第1节 可计算理论
第四章 复杂性理论 2.0学时 张涌
第1节 复杂性理论
第五章 NP完全与多项式层级 2.0学时 张涌
第1节 NP完全与多项式层级
第六章 空间复杂性 2.0学时 张涌
第1节 空间复杂性
第七章 并行计算复杂性 2.0学时 张涌
第1节 并行计算复杂性
第八章 随机复杂性 2.0学时 张涌
第1节 随机复杂性
第九章 计数复杂性 2.0学时 张涌
第1节 计数复杂性
第十章 交互证明 2.0学时 张涌
第1节 交互证明
教材信息
1、
Introduction to the Theory of Computation
Michael Sipser
2012
Cengage Learning
参考书
1、
"计算复杂性导论
堵丁柱，葛可一，王洁
2022
高等教育出版社
2、
Computational Complexity: A
Modern Approach
Sanjeev Arora, Boaz Barak
2009
Cambridge University Press
3、
Computational Complexity: A Conceptual
Perspective
Oded Goldreich
2008
Cambridge University Press
4、
Computational
Complexity"
Christos Papadimitriou
1994
Addison-Wesley
课程教师信息
张涌，男，2007年博士毕业于复旦大学计算机系，现为中国科学院深圳先进技术研究院研究员。2014-2023年担任深圳先进技术研究院硕士/博士研究生高级算法、在线算法、算法博弈论、计算理论等课程的授课教师。