※ 本文是否可提供台大同学转作其他非营利用途？（须保留原作者 ID） （是／否／其他条件）：是 哪一学年度修课：108-1 ψ 授课教师 (若为多人合授请写开课教师，以方便收录) 陈伟松 教授 λ 开课系所与授课对象 (是否为必修或通识课 / 内容是否与某些背景相关) 资工系 大三必修 δ 课程大概内容 Part 0: Preliminaries Lesson 0. Preliminaries Part 1: Regular languages Lesson 1.a. Finite state automata Lesson 1.b. Pumping lemma and regular expressions Lesson 1.c. Review Part 2: Context-free languages Lesson 2.a. Context-free grammars and pumping lemma Lesson 2.b. Push-down automata Lesson 2.b. Push-down automata Lesson 2.c. Review ---- Midterm ---- Part 3: Decidable and undecidable languages Lesson 3.a. Turing machines and decidable languages Lesson 3.b. Variants of Turing machines Lesson 3.c. Universal Turing machines and halting problems Lesson 3.d. Reducibility Part 4: Basic complexity theory Lesson 4.a. Basic complexity classes Lesson 4.b. NP-complete languages ---- Final ---- (以上复制自课程网页 https://0rz.tw/S74Gq ) 基本上算是计算理论的入门课程，会以严谨的数学定义各种自动机 (偷nonamefour的解释：自动机是一种会吃字串吐出 yes/no 的东西) 并介绍它所能决定的语言(字串集合)。 Ω 私心推荐指数(以五分计) ★★★★★ η 上课用书(影印讲义或是指定教科书) 无(课程网页有推荐用书，但上课不会用到) μ 上课方式(投影片、团体讨论、老师教学风格) 板书(白板，淡到快不见的那种) 有提供handouts的pdf/tex档，但不会完全照着上面教， 有些上课有提到的不一定有放在上面 纯英文上课，坐太後面的话有点小声(?) 但英文速度偏慢，不会听不懂 整体课程进度也偏慢，但教授讲话很ㄎㄧㄤ所以不会无聊 (参见 #1VEKVl_r (NTUcourse)) σ 评分方式(给分甜吗？是紮实分？) 作业 40% 除了Preliminaries外每个Part各一次(10%) Midterm 30% Final 30% 24.74% A+ 应该甜(吧 ρ 考题型式、作业方式 作业跟考试方式差不多，前几题都是基本概念，有听懂一定会写。 後面会有证明题，通常不会太难，但需要思考，有人可以讨论会比较好。 ω 其它(是否注重出席率？如果为外系选修，需先有什麽基础较好吗？老师个性？ 加签习惯？严禁迟到等…) 不点名，不过听课对理解很有帮助，讲义相对不易阅读(而且会少一些东西) 基础的话就简单的集合论和熟悉数学定义、证明的过程(吧 外系应该是全签 另外课间的下课会改为课中告一段落时一次下课15分， 然後印象中会提早下课(吗? Ψ 总结 推推 个人觉得这个主题蛮有趣的，也推Tony上课风格w --

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