※ 本文是否可提供台大同学转作其他非营利用途？（须保留原作者 ID）
（是／否／其他条件）：是
哪一学年度修课：
108-1
ψ 授课教师 (若为多人合授请写开课教师，以方便收录)
陈伟松 a.k.a. Tony Tan，今年单/双班都是他教
λ 开课系所与授课对象 (是否为必修或通识课 / 内容是否与某些背景相关)
资工系大三必修
δ 课程大概内容
这堂课介绍了各种自动机和图灵机。自动机是一种会吃字串吐出 yes/no 的
东西；而图灵机除了 yes/no 之外还会输出一个字串。一个自动机/图灵机
对应的形式语言，指的则是会被输出 yes 的那些字串们。图灵机在做的事
情很像算法，或者说它本质上就是一个算法，也是先有图灵机的抽象概
念之后才发展出电脑的，所以这堂课的东西可以说是电脑科学的源头(?)
Part1: Regular Languages (DFA, NFA, regex 跟三者间的等价)
Part2: Context-free Languages (CFG, PDA 跟两者间的等价)
Part3: Decidable and Undecidable Languages (图灵机与相关理论)
Part4: Basic Complexity Classes (P, NP, P_space, NP_space...)
Ω 私心推荐指数(以五分计) ★★★★★
★★★★☆
个人没有特别喜欢 Tony 的上课模式(下面会说理由)，因此给四颗。
η 上课用书(影印讲义或是指定教科书)
Tony 的个人网页上有上课讲义。
μ 上课方式(投影片、团体讨论、老师教学风格)
老师用英文上课，但速度不快绝对跟得上。板书当然也是英文。
第一堂课我觉得上课讲的跟讲义一模一样，就没再去上过课了。
后来才知道上课其实会补充讲义外的东西.....
期中跟期末考前都有一周是 reading week，不会上课但可以去问问题。期中
考的 reading week 好像没人问，所以教授就开始讲题目，其中包括出在期中
考中的 Bonus 题。(虽然最后没加分就是了)
σ 评分方式(给分甜吗？是扎实分？)
作业 4 次，每次 10%
期中考 30%
期末考 30%
主观感受给分算甜。
ρ 考题型式、作业方式
作业跟考试题目差不多，都会有基本题 (例如给定形式语言写出对应的自动机)
和证明题。证明题通常只需要上课讲的概念就能想到，当然相对于构造题而言
仍然比较难，在考试时会是高分关键。
ω 其它(是否注重出席率？如果为外系选修，需先有什么基础较好吗？老师个性？
加签习惯？严禁迟到等…)
教授不点名，不过自己读讲义感觉会有点吃力，写作业时有大腿抱会舒服很多。
本质上这是一堂很数学的课，教授第一周甚至特别讲了一些基本的数学名词跟
符号定义当先备知识。
另外加签应该没有特别的限制。
Ψ 总结
上面有提到我不是非常喜欢 Tony 的上课模式，有两个理由。首先是他的上课
进度对我来说偏慢，我个人觉得每个 part 介绍的内容有点少 (当然其他人不
一定这样觉得)；第二点纯粹是我不太习惯英文上课。
不过我还是觉得这堂课很棒，并且会想要推荐给对图灵机、P=NP 问题这些东西
有兴趣的人，尤其是期中考后的部分。毕竟在网络上查“P问题的定义”永远只
会得到“多项式时间内可以求解的问题”这类官腔说法(?)，但“多项式时间”
甚至“问题”这些概念都是可以用图灵机的语言好好定义的。另外，算法课
会教你怎么解题，而这堂课则会讨论到哪些问题“不能被解”(例如著名的停机
问题)，这部分我觉得也很有趣。
总之，学完这堂课可能会对“电脑/计算”的抽象本质有更深刻的理解(?)