课程号：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版，北京大学出版社，2004.
2.Michael Sipser: Introduction to the Theory of Computation, second edition（影印本）, 机械工业出版社，2006.中译本: 唐常杰，陈鹏，向勇，刘齐宏 译： 《计算理论导引》，机械工业出版社，2007.
学生成绩评定方法：作业30％，期中考试20％，期末考试50％。 课程修订负责人：夏壁灿