课程号:00135050
课程名称:理论计算机科学基础
开课学期:春
学分: 3
先修课程: 数理逻辑
基本目的:本课程的教学目标是使学生掌握可计算性的基本概念、基本计算模型、计算模型之间的等价关系以及计算复杂性理论的初步知识,通过理论学习使学生理解理论计算机科学的基本思想,扩展学生思维,增强学生理论与工程实践相结合的能力。
内容提要:
一、预备知识(1学时)
数论函数、字函数、计算理论的发展历史、Church-Turing论题简介
二、程序设计语言S (1学时) 程序设计语言S、可计算函数、宏指令
三、原始递归函数 (6学时)
原始递归函数、原始递归谓词、迭代运算、有界量词、极小化运算、配对函数、Gӧdel数、原始递归运算、Ackermann函数(简介)、字函数的可计算性
四、通用程序(4学时)
程序的代码、通用性定理、停机问题、递归集与递归可枚举集
五、Turing机(6学时)
Turing机的基本模型、Turing机的各种变形(五元Turing机、单向无穷带Turing机、多带Turing机、离线Turing机)、非确定性Turing机、Turing机与可计算性、Turing机接受的语言、通用Turing机(简介)
六、过程与文法(4学时)
半Thue过程、用半Turing过程模拟Turing机、文法、递归可枚举集与部分可计算函数、递归函数类与可计算函数类的等同性、Church-Turing论题
七、不可判定的问题(3学时)
判定问题、可判定性、半可判定性、归约、Turing机的停机问题、字问题和Post对应问题(简介)、有关文法的不可判定问题
八、形式语言与自动机(8学时)
Chomsky谱系、有穷自动机、有穷自动机与正则文法的等价性、正则表达式(简介)、关于正则语言的泵引理、上下文无关文法、 Chomsky范式、Bar-Hillel泵引理、 下推自动机、上下文无关文法与下推自动机的等价性、确定型下推自动机(简介)、上下文有关文法(简介)
九、时间复杂性与空间复杂性(4学时)
Turing机的运行时间和工作空间、计算复杂性类、空间可构造性、Savitch定理、复杂性类的真包含关系
十、NP完全性(6学时)
Cook-Karp论题、 P 与NP、多项式时间变换、 NP完全性、 Cook定理、若干NP完全问题(简介)、coNP
十一、PSPACE类和P类(3学时)
PSPACE完全性、带量词的布尔公式的可满足问题、广义地理学问题、带幂运算的正则表达式的全体性(简介)、对数空间变换、L类、NL类、P完全性
十二、随机算法与随机复杂性类简介(2学时)
近似算法、随机算法、概率Turing机、随机复杂性类
教学方式:每周授课3学时
教材与参考书:1. 张立昂:《可计算性与计算复杂性导引》,第2版,williamhill体育在线平台出版社,2004.
2.Michael Sipser: Introduction to the Theory of Computation, second edition(影印本), 机械工业出版社,2006.中译本: 唐常杰,陈鹏,向勇,刘齐宏 译: 《计算理论导引》,机械工业出版社,2007.
学生成绩评定方法:作业30%,期中考试20%,期末考试50%。 课程修订负责人:夏壁灿