※ 本文是否可提供台大同学转作其他非营利用途？（须保留原作者 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 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 36.225.223.33 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/NTUcourse/M.1548407877.A.BBF.html ※ 编辑: timestoneman (36.225.223.33), 01/25/2019 17:21:54