※ 本文是否可提供臺大同學轉作其他非營利用途？（須保留原作者 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 ★