※ 本文是否可提供台大同学转作其他非营利用途？（须保留原作者 ID）
（是／否／其他条件）：是
哪一学年度修课：109-1
ψ 授课教师 (若为多人合授请写开课教师，以方便收录)
陈伟松教授 (Tony Tan)
λ 开课系所与授课对象 (是否为必修或通识课 / 内容是否与某些背景相关)
资讯系大三必修
δ 课程大概内容
Lesson 0. Preliminaries
Lesson 1. Finite state automata
Lesson 2. Pumping lemma and regular expressions
Lesson 3. Context-free grammars
Lesson 4. Push-down automata
Lesson 5. Equivalence between CFL and PDA
===== Midterm Exam =====
Lesson 6. Turing machines and deciadable languages
Lesson 7. Turing machines and the notion of algorithm
Lesson 8. Universal Turing machines and halting problem
Lesson 9. Reducibility
Lesson 10. Non-deterministic Turing machines
Lesson 11. Basic complexity classes
Lesson 12. NP-complete languages
===== Final Exam =====
Ω 私心推荐指数(以五分计) ★★★★★
不排斥证明题：★★★ + 0.75 ★

推推

推

推