※ 本文是否可提供台大同学转作其他非营利用途？（须保留原作者 ID）
（是／否／其他条件）：
是
哪一学年度修课：
106-1
ψ 授课教师 (若为多人合授请写开课教师，以方便收录)
陈伟松 Tony Tan
λ 开课系所与授课对象 (是否为必修或通识课 / 内容是否与某些背景相关)
资工系 大三必修
δ 课程大概内容
Lesson 1. Preliminaries
Lesson 2. Deterministic finite state automata
Lesson 3. Nondeterministic finite state automata
Lesson 4. Regular expressions
Lesson 5. Context-free languages
Lesson 6. Pumping lemma and push-down automata
Lesson 7. CFG = PDA
Midterm
Lesson 8. Turing machines and decidable languages
Lesson 9. Variants of Turing machines
Lesson 10. Universal Turing machines and Halting problem
Lesson 11. Reducibility
Lesson 12. Time and space complexity
Lesson 13. NP-complete problems
Lesson 14. NLog- and PSPACE-complete problems
Ω 私心推荐指数(以五分计) ★★★★★
★ ★ ★ ★ ★
η 上课用书(影印讲义或是指定教科书)
老师讲义
不过脉络是照Introduction to Computation Theory
μ 上课方式(投影片、团体讨论、老师教学风格)
课前公布Note，然后两个半小时板书
老师上课会在白板上直接推导，然后时不时停下来问同学ok hah?
σ 评分方式(给分甜吗？是扎实分？)
I don't know
ρ 考题型式、作业方式
四次作业，每次作业四到五题，难度不一
期中期末考，分别五题，大概都是两题送分，两题简易，一题进阶的形式
ω 其它(是否注重出席率？如果为外系选修，需先有什么基础较好吗？老师个性？
加签习惯？严禁迟到等…)
全签，不管出席率，不太需要基础
老师满注意与学生互动的情形，不过满常发生讲的太快，学生连要问什么问题都不
知道的情况(QQ)
Ψ 总结
老师人不错，助教人帅又nice，期末考当天TA Hour还超时加班三个小时，根本佛心。
期中期末考的难度其实满不错的，如果只是想要混分，应该很容易就可以及格，如果
想要获得高分一点，就要多想久一点。然后，因为考试时间充裕(3 hr)，又只有五题
其实满适合给人思考，突破自己的极限。