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