跳转至

1771911126

理论计算机科学导引

本课程与计算机学院开设的另一门讲解理论计算机科学的课程“计算理论”在某些内容上有不小的区别；具体表现为，对计算复杂度理论的分析内容更多。且每年的教材、课程内容都有一些变化。

课程学习内容

课程主要内容为计算理论的基础知识，研究脉络是这几个问题：

  • 问题怎么描述？（对应编码）
  • 如何计算问题？（对应各种计算模型，例如电路、自动机与图灵机）
  • 所有问题都可以被计算吗？（对应可计算性）
  • 对于可计算的问题，计算它们需要多少资源？（对应复杂度理论，函数复杂类）

具体大纲如下：

  • 编码与电路
    • 课程基本概念、常用记号、可数与不可数集合
    • 如何对问题进行编码，编码与可数的关系
    • 利用最初步的计算模型（布尔电路和对应的程序）进行计算，并研究其规模
  • 语言与自动机
    • 介绍语言与函数的对应关系
    • 确定性和非确定性的有穷自动机（DFA 和 NFA）
    • DFA 和 NFA 的等价性与互相转换的过程
    • 正则语言的定义，正则语言和 FA 的等价性，互相转换的方法
    • 正则语言封闭运算，泵定理 (pumping theorem) 及其应用
    • 下推自动机 (PDA) 相比普通 FA 的增强
    • 上下文无关语法 (CFG) 的定义，CFG 和 PDA 的等价性，互相转换的方法
  • 图灵机 (Turing Machine, TM)
    • TM 的定义与基本概念、计算过程
    • 图灵完备性 (Turing Completeness)，NAND-TM/RAM 程序
    • 通用图灵机 UTM 的构造与工作原理
    • 函数可计算性
      • Church-Turing 论题
      • 停机问题
      • 归约，如何利用归约证明某些问题的不可计算性
      • 利用 Rice Theorem 证明不可计算性
      • Recursion Theorem 和 Godel 不完备性定理
  • 复杂度理论
    • 时间复杂度，空间复杂度
      • Time Hierarchy Theorem
      • 多项式时间归约的定义
    • 函数复杂类及其之间的关系：P、NP（采用“多项式时间内可验证性”作为定义）、EXP、P/poly etc.
      • NP-Hard、NP-Complete 的定义
    • 各复杂类的具体例子：SAT/3-SAT 问题、01 EQUATION 问题、SUBSET SUM 问题等，其之间的归约关系
      • Cook-Levin 定理
  • 概率图灵机与随机算法（这部分是新加的）
    • 概率图灵机的定义
    • BPP 类的定义及其性质
    • 伪随机数生成器

这门课内容多、补天困难，作为一门 2 学分的课程，内容艰涩且难以速成，一定不能掉以轻心。

先修要求

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

有了这两门课的基础一些知识可以更容易理解，例如说 ADS 中的复杂度分析和复杂类函数会在这里以更本质的形象再次出现。

任课教师

21 级开始，TCS 改为由毛宇尘老师教授（20 级是只有金小刚老师教授）。很有可能之后都由毛宇尘老师教授了。

毛宇尘可以说是新式古法上课，全程使用 iPad 手写概念与证明过程并投屏，没有任何 Slides 和讲义参考，并且不允许除最后一排外的同学使用电脑，这也就要求在课后花很多时间消化内容，或是对着智云 / 教材反复学习概念。

这门课只有图灵一个班，所以讲课内容、作业、小测、考试都由毛哥自己发挥，内容相比计算理论有很大拓展。作业比较偏向理论与证明，更多考察是否真的掌握了这些知识，而非只是知道做题方法；小测和考试也都是这个风格，只要掌握了课上讲的东西，是肯定能写出东西的。

课程教材

23 级的教材是 Boaz Barak 的 Introduction to Theoretical Computer Science

20 级曾用教材如下：

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

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

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

分数构成

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

参考资料

前人们的笔记：

和“计算理论”重合的部分，也可在 CC98 等地方搜索计算理论的相关资料参考。

回忆卷

学习建议

在换新教材后，课程内容的难点更加偏向复杂度理论，然而这部分内容并没有在 23 级考试中占据特别大的比重。图灵机之前的内容相对容易理解一些，需要对每个概念都掌握扎实（例如 22 级期末考了一道用双栈 PDA 模拟图灵机，23 级考了一道同时跑 PDA 和 DFA 的题目，这都要求你对这些基本概念有清晰的理解），要掌握正则 / 非正则的判断和证明（怎么画 / 构造 FA），CFL 的判断和证明（怎么构造 CFG/PDA，虽然很多情况下写 CFG 会更方便，但是有些时候很难想，需要用 PDA）。在图灵机及之后的内容逐渐抽象，理解难度也会增加，重点是对（多项式时间）归约的掌握，要熟练掌握用莱斯定理和归约来证明不可计算性的问题（至少车轱辘话要会写 [ac01]）。

每次作业批改结束 / 小测结束后助教都会发布答案，一定要对着看看懂。平时作业和小测的题目是复习考试的最好资料，考试题目风格也和这些题目比较接近，但是第一眼看到容易使人发懵，弄懂课上内容加上看一看作业和小测题会有很大的帮助。有任何问题也都可以在课后去找毛哥问，每次都会非常清晰地给出解答。