※ 本文是否可提供台大同学转作其他非营利用途？（须保留原作者 ID） （是／否／其他条件）：是 哪一学年度修课： 105-1 ψ 授课教师 (若为多人合授请写开课教师，以方便收录) 陈伟松 λ 开课系所与授课对象 (是否为必修或通识课 / 内容是否与某些背景相关) 资工系大三必修 δ 课程大概内容 Part A Lesson 1. Preliminaries ---------------------------------------------------- Part B Lesson 2. Deterministic finite state automata Lesson 3. Nondeterministic finite state automata Lesson 4. Regular expressions ---------------------------------------------------- Part C Lesson 5. Context-free languages Lesson 6. Pumping lemma and push-down automata Lesson 7. CFG = PDA -----------------期中考（范围BC）-------------------- Part D 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 E Lesson 12. Time and space complexity Lesson 13. NP-complete problems -----------------期末考范围全部---------------------- Ω 私心推荐指数(以五分计) ★★★★★ ★★★★ η 上课用书(影印讲义或是指定教科书) Introduction to the Theory of Computation by M. Sipser. μ 上课方式(投影片、团体讨论、老师教学风格) 英文授课 老师会将每个礼拜的上课讲义上传到课程网站（比较简略） 上课老师会先讲一个观念，然後有类似的东西会问同学要怎麽证明之类的 让大家有再思考，考试前会留一周reading week σ 评分方式(给分甜吗？是紮实分？) hw*5 一份10% 期中考 25% 期末考 25% 考卷改得很松，最後没有调分。 ρ 考题型式、作业方式 每次作业大约5题 考试跟作业很像 期中考有五题，後面几题是证明题 期末考有四题，一个part出一题，考很基本的东西 ω 其它(是否注重出席率？如果为外系选修，需先有什麽基础较好吗？老师个性？ 加签习惯？严禁迟到等…) 这是一门理论课，所以老师特别注重写证明的方式 有寄一封信写说A+跟A的差别大概是差在证明写的完整度上面 加签好像没有限制，因为这学期两个班都是他教的， 如果外系想要加签，最好要有离散数学Relation的基础，还要会写证明。 交作业时间到了老师会准备两个箱子放到他的办公室外面， 作业跟考卷都是老师亲自批改。 还有hw5好像因为有蛮多人写 coNP algorithm 这个词老师蛮不开心的 因为老师说这个词是NONSENCE，他上课也没有提到，所以寄信跟大家说这件事情 每个礼拜的预定进度讲完就会下课，我记得有一次大概11:30就下课了。 Ψ 总结 这是一门计算理论入门的课，如果非必修只是像要看看的话，可以不要修其实 因为就是理论证明这样。如果对计算理论有兴趣想要专研的话，这门课入门 压力不大。 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 115.82.208.80 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/NTUcourse/M.1485528144.A.CE7.html