※ 本文是否可提供臺大同學轉作其他非營利用途？（須保留原作者 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問題的定義」永遠只
會得到「多項式時間內可以求解的問題」這類官腔說法(?)，但「多項式時間」
甚至「問題」這些概念都是可以用圖靈機的語言好好定義的。另外，演算法課
會教你怎麼解題，而這堂課則會討論到哪些問題「不能被解」(例如著名的停機
問題)，這部分我覺得也很有趣。
總之，學完這堂課可能會對「電腦/計算」的抽象本質有更深刻的理解(?)