※ 本文是否可提供台大同学转作其他非营利用途？（须保留原作者 ID）
（是／否／其他条件）：
是
哪一学年度修课：
107-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 Push-down automata
Lesson 7 CFG = PDA
Midterm exam
Lesson 8 Turing machines and decidable languages
Lesson 9 Variants of Turing machines
Lesson 10 Universal Turing machines and Halting problem
Lesson 11 Reducibility, part I
Lesson 12 Reducibility, part II
Lesson 13 Time and space complexity
Lesson 14 NP-complete and PSPACE-complete languages
Final exam
期中考和期末考前各放一次温书假
Ω 私心推荐指数(以五分计) ★★★★★
★ ★ ★ ★ ★
η 上课用书(影印讲义或是指定教科书)
课本是Introduction to the Theory of Computation by M. Sipser
老师有自制讲义，基本上顺着课本脉络，稍微精简一点
μ 上课方式(投影片、团体讨论、老师教学风格)
纯板书 英文授课
每个礼拜上完一份讲义
老师相当关心大家能不能理解，常常停下来问"any questions?"，但通常没什么回应
然后老师就会"If you have no questions, I have a question"自己接下去讲
σ 评分方式(给分甜吗？是扎实分？)
homework 40%
midterm 30%
final 30%
作业本来有四次，因为放假的关系，作业三跟作业四合并成一份，占分20%
应该算扎实甜，我期中75，期末100，作业全拿，最后A+
ρ 考题型式、作业方式
每次作业约五六题，前两题难度简易，后面会越来越困难，通常需要写不少证明
作业可以手写或者印出来，在课堂上交
考试考三个小时，型式和作业相同，也是大概五六题，难度较作业略低一点
认真写作业对考试帮助蛮大的，有时候会考出类似的概念
ω 其它(是否注重出席率？如果为外系选修，需先有什么基础较好吗？老师个性？
加签习惯？严禁迟到等…)
完全不看出席率
加签应该是全签，今年似乎有蛮多隔壁班的同学与外系生，所以有点挤，常常抢不到位置orz
这门课从严格的数学定义出发，透过抽象模型，一步一步带着大家理解计算的本质，各种复杂度型
别，最后推向计算能力的极限。刚开始听可能有点不知所以，但往后走的某个时刻就会豁然开朗，
，出现新的观点来看待事物，并且明白先前的定义跟符号到底有什么意义。
老师会亲自改作业跟考卷，他相当注重引用的出处，抓抄袭也十分仔细，曾经不只一次的来信提醒
，还说自己"extremely unhappy"，第一次作业最后关于myhill-nerode theorem的证明，就有不少
同学因此被扣分。老师曾经在课堂上说过，他能体谅大家辛苦，只要努力把自己的东西表达清楚，
不会太为难人。上课有问题随时可以打断，他会很乐意解答XD，如果害羞或是不太敢讲英文，也可
以询问热心又nice的助教。
老师的英文有一点点口音，但完全不影响听力，比较要注意的是他音量小，语速颇快，板书也不太
整齐，所以一恍神就要花很大功夫把漏洞补起来。我期中考后不小心发呆几次，就跟不上了，连带
著到课率大幅下降，在这里特别感谢几位互助的战友，期末考前帮我把进度补起来。要是老师能别
个麦克风上课就更好了。
Ψ 总结
好课 Tony is good