[評價] 108-1 陳偉松自動機與形式語言

看板NTUcourse作者nonamefour (nonamefour0210)時間5年前 (2020/01/24 01:02)推噓8(8推 0噓 1→)

留言9則, 8人參與討論串1/2 (看更多)

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

推

joey11121

01/24 09:05, 5年前 , 1^F

01/24 09:05, 1^F

推

tryptochan

01/24 11:26, 5年前 , 2^F

01/24 11:26, 2^F

推

microuzi9797

01/24 13:11, 5年前 , 3^F

01/24 13:11, 3^F