※ 本文是否可提供台大同学转作其他非营利用途？（须保留原作者 ID )
（是／否／其他条件）：否
哪一学年度修课： 111-1
ψ 授课教师 (若为多人合授请写开课教师，以方便收录)
林智仁
λ 开课系所与授课对象 (是否为必修或通识课 / 内容是否与某些背景相关)
资讯工程学系大三必修
δ 课程大概内容
- Chapter 1
Deterministic finite automata
Nondeterministic finite automata
Regular expressions
Pumping lemma
- Chapter 2
Context-free grammars
Chomsky normal form
Pushdown automata
Deterministic pushdown automata
- Chapter 3
Turing machines
Multitape Turing machines
Nondeterministic Turing machines
Hilbert's problems
- Chapter 4
Decidability
Halting problem
- Chapter 7
Big-O notation
Time complexity
Languages in P
Languages in NP
Ω 私心推荐指数(以五分计)
★★★★★ 五颗
η 上课用书(影印讲义或是指定教科书)
Michael Sipser, Introduction to the Theory of Computation, 3rd edition
μ 上课方式(投影片、团体讨论、老师教学风格)
每周在Webex直播上课，不点名。上课方式为播放预录的影片，老师再稍微加以解释。影片和投影片在课程网站上都可以找到，因此不一定要跟课，可以根据自己的学习习惯来选择同步或异步:D
另外，课程全程都用英文进行，包括上课、作业和考试的撰写。
σ 评分方式(给分甜吗？是扎实分？)
30%作业（6次）
70%考试（3次）
3次考试的权重在期初不公开，我根据最后公告的成绩来算，分布大概是26%、39%、35%
最后等第也是从不公开的机制换算而成
大家的成绩都会被放在课程网页上（汗
给分我认为蛮甜的，目测约有一半的人都拿A-（含）以上，而有认真读的的话基本上不会被当，除非有缺考或考出个位数的成绩。
ρ 考题型式、作业方式
作业都是课本后的习题，不会太难，不过作业的难度很容易让人低估了考试。
三次考试题目都出得很活，大部分都要想过，甚至带入情境、文意理解一下才能作答，但题目也会引导你一步步地思考。以这种死板死板（？）的学科来说实在是难能可贵^^
不过这学期是采线上考试（Open book），或许因此才将题目如此精心设计，来防止大家在网络上爆搜解答吧。
ω 其它(是否注重出席率？如果为外系选修，需先有什么基础较好吗？老师个性？
加签习惯？严禁迟到等…)
这学期是一类加签，上系统登记就可以修了。
Ψ 总结
整堂课比较偏导论性质，经典的问题都有带到；但在某些观念上只有用例题的方式带过，如果想要彻底深入各种观念的人可能得靠自己读课本了。但作为系上必修课来说，我认为这样的份量反而拿捏得恰到好处:D