※ 本文是否可提供台大同学转作其他非营利用途？（须保留原作者 ID） （是／否／其他条件）：是 哪一学年度修课： 108-1 ψ 授课教师 (若为多人合授请写开课教师，以方便收录) 陈伟松 a.k.a. Tony Tan，今年单/双班都是他教 λ 开课系所与授课对象 (是否为必修或通识课 / 内容是否与某些背景相关) 资工系大三必修 δ 课程大概内容 这堂课介绍了各种自动机和图灵机。自动机是一种会吃字串吐出 yes/no 的 东西；而图灵机除了 yes/no 之外还会输出一个字串。一个自动机/图灵机 对应的形式语言，指的则是会被输出 yes 的那些字串们。图灵机在做的事 情很像演算法，或者说它本质上就是一个演算法，也是先有图灵机的抽象概 念之後才发展出电脑的，所以这堂课的东西可以说是电脑科学的源头(?) Part1: Regular Languages (DFA, NFA, regex 跟三者间的等价) Part2: Context-free Languages (CFG, PDA 跟两者间的等价) Part3: Decidable and Undecidable Languages (图灵机与相关理论) Part4: Basic Complexity Classes (P, NP, P_space, NP_space...) Ω 私心推荐指数(以五分计) ★★★★★ ★★★★☆ 个人没有特别喜欢 Tony 的上课模式(下面会说理由)，因此给四颗。 η 上课用书(影印讲义或是指定教科书) Tony 的个人网页上有上课讲义。 μ 上课方式(投影片、团体讨论、老师教学风格) 老师用英文上课，但速度不快绝对跟得上。板书当然也是英文。 第一堂课我觉得上课讲的跟讲义一模一样，就没再去上过课了。 後来才知道上课其实会补充讲义外的东西..... 期中跟期末考前都有一周是 reading week，不会上课但可以去问问题。期中 考的 reading week 好像没人问，所以教授就开始讲题目，其中包括出在期中 考中的 Bonus 题。(虽然最後没加分就是了) σ 评分方式(给分甜吗？是紮实分？) 作业 4 次，每次 10% 期中考 30% 期末考 30% 主观感受给分算甜。 ρ 考题型式、作业方式 作业跟考试题目差不多，都会有基本题 (例如给定形式语言写出对应的自动机) 和证明题。证明题通常只需要上课讲的概念就能想到，当然相对於构造题而言 仍然比较难，在考试时会是高分关键。 ω 其它(是否注重出席率？如果为外系选修，需先有什麽基础较好吗？老师个性？ 加签习惯？严禁迟到等…) 教授不点名，不过自己读讲义感觉会有点吃力，写作业时有大腿抱会舒服很多。 本质上这是一堂很数学的课，教授第一周甚至特别讲了一些基本的数学名词跟 符号定义当先备知识。 另外加签应该没有特别的限制。 Ψ 总结 上面有提到我不是非常喜欢 Tony 的上课模式，有两个理由。首先是他的上课 进度对我来说偏慢，我个人觉得每个 part 介绍的内容有点少 (当然其他人不 一定这样觉得)；第二点纯粹是我不太习惯英文上课。 不过我还是觉得这堂课很棒，并且会想要推荐给对图灵机、P=NP 问题这些东西 有兴趣的人，尤其是期中考後的部分。毕竟在网路上查「P问题的定义」永远只 会得到「多项式时间内可以求解的问题」这类官腔说法(?)，但「多项式时间」 甚至「问题」这些概念都是可以用图灵机的语言好好定义的。另外，演算法课 会教你怎麽解题，而这堂课则会讨论到哪些问题「不能被解」(例如着名的停机 问题)，这部分我觉得也很有趣。 总之，学完这堂课可能会对「电脑/计算」的抽象本质有更深刻的理解(?) --

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