形式语言与计算复杂性(黄文超) 2021春  课程号:COMP6106P01
2021春  课程号:COMP6106P01
10.0(1人评价)
  • 课程难度:困难
  • 作业多少:中等
  • 给分好坏:一般
  • 收获大小:很多
选课类别:基础 教学类型:理论课
课程类别:研究生课程 开课单位:计算机科学与技术系
课程层次:硕士 学分:2
简介

本课程为计算理论的入门,为学生在计算机科学领域的后续工作和研究奠定理论基础。课程涵盖了计算模型、可计算性和计算复杂度相关内容,分别介绍如何以数学方式定义计算,哪些问题是计算机可计算的,可计算问题中计算机解决的效率如何。主要授课内容包括:

  • 形式化计算模型: 介绍自动机(DFA/NFA)、正则语言(Regular Language)、上下文无关语言(CFL)、图灵机(Turing Machine)等计算模型。
  • 可计算理论:可判定性(Decidability)、归约(Reduction)等概念
  • 计算复杂度:时间复杂度、P versus NP, NP-completeness, 不可计算性(Intractability)等。

最后更新:

点评 写点评
ABCDE 2021春

说明:我没有选修这门课,但前前后后旁听了一半多的课时,所以下面的评价主要针对课程本身,关于考试和给分的具体情况请其他同学补充。


这门课是2020研究生新版培养方案中新开设的,计算机软件与理论专业的基础课,40课时,2学分。这学期的上课时间是15-18周,每周两次课,每次上一个上午,实际授课28课时。

(补充说明一下,为什么到期末才开课呢?据黄老师说,由于是第一次开课,且课程难度较大,学院大部分老师不愿意上,上学期期末教学秘书才找到黄老师,最后黄老师不得已接下了这门课,所以这学期前面一大半时间都在准备。)

这门课使用的教材是Sipser 的 Introduction to the Theory of Computation, Third Edition,在课程主页上有电子版。对应的中译本是《计算理论导引》(原书第3版)。

课程内容主要包括三个部分:自动机理论(计算的模型)、可计算性理论(哪些问题可计算?哪些问题不可计算?)、计算复杂性理论(哪些问题是难的?哪些问题是容易的?)。

  • 第1章 绪论
  • 第2章 Automata and Languages
    • 2.1 Regular Languages
    • 2.2 Context-free Languages
  • 第3章 Computability Theory
    • 3.1 The Church-Turing Thesis
    • 3.2 Decidability
    • 3.3 Reducibility
  • 第4章 Complexity Theory
    • 4.1 Time Complexity

实际上课程中的很多内容大家在其他课程中多少接触过一些,但这门课是对这些知识的一个系统的讲解,每一个定理都会经过严格地证明。

黄老师在第一次课就说,这是一门数学课,难度是比较大的,经常提醒大家要及时预习和复习,保证充足睡眠。虽然是第一次开课,但看得出来,黄老师是在很用心地对待这门课,课件制作得很精良(可以称得上是赏心悦目),并且每讲完一处比较难的地方会停下来问大家听懂了没有,大部分同学都听懂了才会继续讲,否则会停下来和大家讨论,或再讲一遍。这也是我给10分的原因。

课程的考核方式是半开卷(可带一张手写A4纸)。据黄老师第一节课所说,80%的题目与作业相关,剩下的20%是压轴题,会考课程中所讲到的一个证明。

由于是第一次开课,难免有一些不足。首先就是上课时间,这门课期末才开课,大部分同学都在考试,所以压力是比较大的(不过从明年开始就会和其他课程一样从学期开始就上课)。另外,可以看得出黄老师在尽力把内容讲明白,但因为是第一次上课,很多地方显得不太熟练,偶尔也会有一些小错误。但我相信后面会上得越来越好!


最后还想多说几句,我们为什么要学习计算理论?这里引用南京大学尹一通老师在豆瓣上给《计算理论导引》所写的书评(链接)中的一段话,与大家共勉:

然而,尽管我对这本书和这门学问都很推崇,我对于学习计算理论的必要性却并不坚定。我自己喜欢这些,可我该如何向别人解释学习它是必要的?

Sipser在前言中也试图说明这个问题:"After all, isn't theory arcane, boring, and worst of all, irrelevant?"
他很认真的试图从几个方面说服学生,计算理论是“有用”的,但我总觉得这些说服很徒劳:书中的三个部分,对于搞研究的人来说,前两个领域已经或走到头了或不再是主流研究趣味了,只有复杂度尚活跃,但也只是个理论方向之一;而对于那些有志于业界工作的学生,后两个部分几乎永远不会在工作中用到,而只有第一部分的自动机,可能会用到一点点正则表达式。

看来,从“有用”这个方向去为计算理论辩护,难免会遭遇尴尬和勉强。

我能想到的理由就只剩两个:
(一)这些是计算机科学的根本,没有它们计算机科学不能算作是个正经学问,因此,一个自称计算机科学专业的人,应当知道这些。
(二)这些是美好的,值得在短暂的人生中去经历去见识。

我觉得这已是足够的理由了。

感谢黄文超老师,让我在科大计算机学院听到这样一门优质的课程。推荐大家明年来选!

4 0

黄文超

教师主页: 戳这里

其他老师的「形式语言与计算复杂性」课

黄文超老师的其他课

形式化方法导引 10.0 (5) 2021春
操作系统 7.8 (5) 2020秋 2019秋...
现代密码学理论与实践 5.2 (9) 2020秋 2019秋...
操作系统 2017秋