※ 本文是否可提供臺大同學轉作其他非營利用途？（須保留原作者 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/m.aspx?n=bbs/NTUcourse/M.1598164945.A.5CE.html