1
课程详述
COURSE SPECIFICATION
以下课程信息可能根据实际授课需要或在课程检讨之后产生变动。如对课程有任何疑问，请
联系授课教师。
The course information as follows may be subject to change, either during the session because of unforeseen
circumstances, or following review of the course at the end of the session. Queries about the course should be
directed to the course instructor.
1.
课程名称 Course Title
计算理论 The Theory of Computation
2.
授课院系
Originating Department
计算机科学与工程系 Department of Computer Science and Engineering
3.
课程编号
Course Code
CS327
4.
课程学分 Credit Value
2
5.
课程类别
Course Type
专业选修课 Major Elective Courses
6.
授课学期
Semester
秋季 Fall
7.
授课语言
Teaching Language
中英双语 English & Chinese
8.
授课教师、所属学系、联系方
式（如属团队授课，请列明其
他授课教师）
Instructor(s), Affiliation&
Contact
（For team teaching, please list
all instructors）
程京德，教学教授，计算机科学与工程系，chengjd@sustech.edu.cn
Jingde Cheng, Teaching Professor, Department of Computer Science and Engineering,
chengjd@sustech.edu.cn
9.
实验员/助教、所属学系、联系
方式
Tutor/TA(s), Contact
待公布 To be announced
10.
选课人数限额(可不填)
Maximum Enrolment
（Optional）
2
11.
授课方式
Delivery Method
讲授
Lecure
s
习题/辅导/讨论
Tutorials
实验/实习
Lab/Practical
其它(请具体注明)
Other（Please specify）
总学时
Total
学时数
Credit Hours
32
0
0
0
32
12.
先修课程、其它学习要求
Pre-requisites or Other
Academic Requirements
CS101B 计算机导论 B Introduction to Computer Science B
CS104 数理逻辑导论 Introduction to Mathematical Logic
13.
后续课程、其它学习规划
Courses for which this course
is a pre-requisite
计算机科学、智能科学所有理论课程 All theoretical courses for Computer Science,
Intelligent Sciences
14.
其它要求修读本课程的学系
Cross-listing Dept.
数学系 Department of Mathematics
教学大纲及教学日历 SYLLABUS
15.
教学目标 Course Objectives
“计算理论”研究计算的本质以及计算的各种性质，是计算机科学、智能科学、及人工智能的核心理论基础。“计算理
论”课程的教学目标为：（1）关于可计算性理论，通过严格定义的计算模型让学生知道什么是计算，什么是原理上能够
计算的，什么是原理上不能计算的。（2） 关于计算复杂性理论，让学生知道计算模型对计算复杂性的影响，计算的时间
复杂性及空间复杂性，计算难易程度的分类。（3）关于计算理论在工程实践中的应用，让学生知道各类经典算法的计算
复杂性。
“The theory of computation” studies the nature of computation and various properties of computation. It is the core
theoretical foundation of Computer Science, Intelligent Science, and Artificial Intelligence. The teaching objectives of the
course "The Theory of Computation" are: (1) On the computability theory, through strictly defined computation models
let students know what computation is, what can and cannot be computed in principle. (2) On the computational
complexity theory, let students know the influence of computation model on computational complexity, the computational
time complexity, the computational space complexity, and the classification of computational difficulty. (3) On
applications of the theory of computation in engineering practices, let students know the computational complexity of
various classical algorithms.
16.
预达学习成果 Learning Outcomes
“计算理论”课程的预达学习效果为：（1）学生能够在遇到任何问题时凭借在本课程学习到的知识辨别出该问题是否是
可计算（可判定）的。（2）学生能够在遇到任何可计算（可判定）的问题时凭借在本课程学习到的知识分析评估出该问
题属于哪一计算复杂性类。（3）学生能够基于本课程学习到的知识进一步学习和研究计算理论前沿课题。
The learning outcomes of the course "The Theory of Computation" are as follows: (1) When students encounter any
problem, they can use the knowledge learned in this course to identify whether the problem is computable (decidable)
or not. (2) When students encounter any computable (decidable) problem, they can analyze and evaluate which
computational complexity class the problem belongs to by virtue of the knowledge learned in this course. (3) Students
can further study and investigate advanced problems in the theory of computation.
17.
课程内容及教学日历 （如授课语言以英文为主，则课程内容介绍可以用英文；如团队教学或模块教学，教学日历须注明
主讲人）
Course Contents (in Parts/Chapters/Sections/Weeks. Please notify name of instructor for course section(s), if
this is a team teaching or module course.)
3
32 hours in total. 2 hours lecture for each week. Corresponding to the following sections：
1. Guidance and Mathematical Preliminaries
2. Enumerability and Diagonalization
3. Finite Automata and Regular Languages
4. Context-Free Languages
5. Computation: Turing Machines
6. Computation: Turing-Decidability
7. Computation: Turing-Reducibility
8. Computation: Recursive Functions
9. Computation: Recursive Sets and Relations
10. Equivalent Definitions of Computability
11. Advanced Topics in Computability Theory
12. Computational Complexity
13. Time Complexity
14. Space Complexity
15. Intractability
16. Advanced Topics in Complexity Theory
共计 32 小时，每周两小时理论课，对应以下章节：
1. 导引与数学预备知识
2. 可枚举性与对角线方法
3. 有穷自动机与正则语言
4. 上下文无关语言
5. 计算：图灵机
6. 计算：图灵可判定性
7. 计算：图灵可归约性
8. 计算：递归函数
9. 计算：递归集和关系
10. 可计算性的等价定义
11. 可计算性理论的高级专题
12. 计算复杂性
13. 时间复杂性
14. 空间复杂性
15. 难解性
16. 计算复杂性理论高级专题
18.
教材及其它参考资料 Textbook and Supplementary Readings
4
M. Sipser, “Introduction to the Theory of Computation,” Cengage Learning, 2013 (3rd Edition).
G. S. Boolos, J. P. Burgess, and R. C. Jeffrey, “Computability and Logic,” 2007 (5th Edition).
P. Linz, “An Introduction to Formal Languages and Automata,” Jones & Bartlett Learning, 2017 (6th Edition).
R. Weber, “Computability Theory,” AMS, 2012.
J. C. Martin, “Introduction to Languages and the Theory of Computation,” McGraw-Hill, 2011 (4th Edition).
S. Homer and A. L. Selman, “Computability and Complexity Theory,” Springer, 2011 (2nd Edition).
M. Fernandez, “Models of Computation -- An Introduction to Computability Theory,” Springer, 2009.
J. E. Hopcroft, R. Motwani, and J. D. Ullman, “Introduction to Automata Theory, Languages, and Computation,”
2007 (3rd Edition).
课程评估 ASSESSMENT
19.
评估形式
Type of
Assessment
评估时间
Time
占考试总成绩百分比
% of final
score
违纪处罚
Penalty
备注
Notes
出勤 Attendance
课堂表现
Class
Performance
小测验
Quiz
课程项目 Projects
平时作业
Assignments
50%
期中考试
Mid-Term Test
期末考试
Final Exam
50%
期末报告
Final
Presentation
其它（可根据需要
改写以上评估方
式）
Others (The
above may be
modified as
necessary)
20.
记分方式 GRADING SYSTEM
A. 十三级等级制 Letter Grading
B. 二级记分制（通过/不通过） Pass/Fail Grading
课程审批 REVIEW AND APPROVAL
21.
本课程设置已经过以下责任人/委员会审议通过
This Course has been approved by the following person or committee of authority
