理论计算机科学导引 ¶

课程学习内容 ¶

课程主要内容为计算理论的基础知识，包括：

• 语言、自动机与正则表达式
  • 课程基本概念、常用记号、语言的定义
  • 确定性和非确定性的有限自动机（DFA 和 NFA）
  • DFA 和 NFA 的等价性，NFA 转 DFA 的方法
  • 正则语言的定义，正则语言和 FA 的等价性，互相转换的方法
  • 正则语言封闭运算，泵定理 (pumping theorem)，如何证明不正则
  • DFA 的状态最小化方法
• 上下文无关语言 (Context-Free Language, CFL)
  • 上下文无关语法 (CFG) 的定义，CFG 和 CFL 的关系
  • Chomsky 范式 (CNF)，转换 CNF 的方法
  • 下推自动机 (pushdown automata, PDA)，PDA 和 CFG 等价性
  • CFL 封闭运算，泵定理，如何证明不是 CFL
• 图灵机 (Turing Machine, TM) 基础
  • TM 定义、TM 构建、TM 的功能（判定 / 半判定语言，计算函数），递归函数
  • 变种图灵机、非确定性图灵机与标准确定性图灵机 (STM) 的等价性
• 不可判定性 (Undecidability)
  • Church-Turing 论题
  • 可判定问题的图灵机构建方法与规约
  • 停机问题，及可由停机问题规约出的其他问题的不可判定性证明
  • Rice 定理与通用的可 / 不可判定或半判定的证明方法
  • 程序的自输出问题与 Recursion 定理、语言的枚举和字典序枚举（略讲）
• 函数的可计算性
  • 原始递归函数定义、μ 递归函数定义、μ 递归函数与可计算函数的等价性
• 复杂度理论
  • 时间复杂度，P、NP、NP 完全问题的定义及与图灵机关系
  • SAT/3-SAT 问题、Clique 问题、Vertex Cover 问题属于 NP 完全问题的证明
  • 空间复杂度，PSPACE、NPSPACE、EXP 问题的定义与关系
  • Savitch's Theorem 与 Hierarchy Theorem

为了向大家说明这门课内容看似少实际多、补天困难，我刻意把内容介绍写成了复习提纲的形式。

先修要求 ¶

• 离散数学理论基础
• 高级数据结构与算法分析

有了这两门课的基础一些知识可以更容易理解，当然就算你这两门课学了个寂寞也没关系，跟着课听问题不大。

任课教师 ¶

21 级图灵的计算理论课改为由毛宇尘老师教授。（20 级是只有金小刚老师教授）

毛哥讲课十分清晰有逻辑，跟住老师一定可以学懂这门课的内容，毛哥全程使用 iPad 手写投屏（不过课后不会发布讲义，需要自己跟住记笔记），概念都会手写、证明过程也会一步一步推导。当然毛哥也有一些奇怪的要求，比如不允许前排同学使用电脑，所谓防止屏幕影响其他同学听课（不过一学期上下来这样效果确实还不错）。

因为这门课只有图灵一个班，所以讲课内容、作业、小测、考试都由毛哥自己发挥，内容相比《计算理论》有一定拓展。作业比较偏向理论与证明，更多考察是否真的掌握了这些知识，而非只是知道做题方法，当然小测和考试也都是这个风格，只要掌握了课上讲的东西，是肯定能写出东西的。除此之外会有三次讨论的内容，说是讨论其实就是开放性且占分数的少量作业，好好完成就可以。

课程教材 ¶

21 级无教材，全靠毛哥手写讲义。20 级曾用教材如下：

《计算理论基础》Elements of the Theory of Computation

有中文版，但有一些小错误，英文版笔者未发现错误。中文版部分地方没有照抄英文版，做出了一些修改，经过笔者和一位 dl 的合力验证英文版部分地方确实太拗口，中文版做出了一些更易于理解的修改，所以需要批判性阅读。

Introduction to the Theory of Computation. Michael Sipser 亦是一本不错的参考教材。

分数构成 ¶

• 作业（0%）
  • 不占分数，也不会要求上交，每周会发一些题然后下一周发布答案，作业可以很好地了解老师的出题风格，因此对小测和考试的帮助还是很大的
• 小测（20%）
  • 21 级进行了两次小测，虽然考验的是是否理解了课上的内容但难度并不算低，不过最后会开根号乘十来调分
• 讨论（20%）
  • 21 级讨论有 3 次，一次是开放性的问题（问一个语言是不是正则的），一次是自学课外的定理（Ogden's Lemma）来证明，还有一次是写一个输出自身的程序，课上会抽同学起来讲，这部分的给分比较慷慨，只要认真完成了应该都能拿到满分
• 期末考试（60%）
  • 期末考试的难度不会很大，如果平时跟上的话复习的东西也没有很多，如毛哥所说，“历年卷是没有用的”，因此主要参考的就是小测和作业的题目

参考资料 ¶

• TonyCrane 的课程笔记：https://note.tonycrane.cc/cs/tcs/toc/
• HobbitQia 的课程笔记：https://note.hobbitqia.cc/TCS/
• ZhouTimeMachine 的笔记（20 级的 jxg 版本）

学习建议 ¶

计院很少有毛哥这种能把理论课讲得非常流畅的老师，需要好好珍惜，课上跟住老师这门课可以说完全不成问题。而且毛哥给分也可以说非常慷慨，和之前的金小刚完全形成了鲜明对比（x）。同时考试也没有套路题，不需要靠历年卷，只要弄懂课上内容加上看一看作业和小测题就足够了。有任何问题也都可以在课后去找毛哥问，每次都会非常清晰地给出解答。