※ [本文轉錄自 neoneon 信箱] 作者: [email protected] ("愛宕有機奈米負離子貓") 標題: [心得] 正規語言概論 時間: Sun Jul 10 08:26:23 2016 作者: yukuro (魔法師mystery) 看板: NCTU-Teacher 標題: [心得] 正規語言概論 時間: 2011/01/26 Wed 00:00:50 （按Ctrl+v 預覽，稍微修一下版面，可讓你這篇文章更專業喔^^） ⊕課名⊕ 正規語言概論(英文授課) ▲教授▲ 黃廷祿 ★修課年度★（請加註開課單位 如:大三通識、XX系選修、XX所） 大三資工組必修 ￡教了什麼￡（課程大概內容。或是額外學會了什麼東西。） 1. Finite State Automata and its property(also its theorem) (i) DFA/NFA (ii) Regular expression (iii) Equivalence : DFA/NFA, RE/NFA(DFA) (iv) Pumping lemma (v) The closure property of regular langauge (vi) Myhill Nerode's Theorem and minimize the Finite state automata 2. Context-free grammer (i) CFG and Chomsky Normal Form (ii) Push down automata (iii) CYK algorithm (iv) Inherent Ambiguity proved by Odgen's lemma (v) Decision problem about CFL 3. Turing machine (i) Turing Thesis (ii) What is Turing-recognizable? and What is (Turing-)decidable? What is "emunerate the language"? 4. Decidable and Undecidable 這要看課本,他會開始證明和引用很多很多定理,來說明許多以上automata的 decidable 和 undecidable 性質 另外還有Halting problem 和diagnalization method 最後會有Co-Turing recognizable這個名詞的出現,再連到一個decidable language is Turing-recognizble and Co-Turing recognizable. 5. Reduction, computable function, mapping reducible 延續第四章,著重在如何利用reduction的技巧,來證明undecidable 還有Post Correspondence Problem(PCP) 6. Computational Complexity and P/NP problem(包含NP-complete) 這個看課本就知道... 從以上看來,教的東西還不少(千萬不要被課本的厚度所騙!!) ◆上課方式◆（投影片、團體討論、老師教學風格） 1.老師用補充的講義為主,偶爾會回到課本來說明,另外老師從一開始就強調: 離散數學的Diagnalization method很重要,所以如果聽到,千萬不要當作耳邊風!! 2.另外,從一開始你會感受到這門課不友善的地方,就是一直下定義,給定理,證明. (老師很喜歡導定理喔!) 而且,老師在前兩章的內容,教了還蠻多的內容,而且很多都不在(Sipser)課本上, 很多內容可能是從其他書上擷取過來的,前兩章會用這種方式教,所以講義的內容 一定要弄懂!!而且這裡會突然生出很多以前沒用過的符號,所以要專心才能讀懂 3.以上是前兩章的運作,但到第三章~第七章就會比較緩慢,老師會很用心和你解釋 decidable, emunerable, Turing-recoginizable的意涵,還有再講定理的時候, 會盡量用比較口語的方式講,證明為什麼要這樣寫和證明的意思是什麼 另外,還會補充一些習題的解答,和提醒一些容易犯錯的部分 4. 在最後約2個禮拜,會進入Time Complexity的部分,但這個部分全部都是定義定理. 會定義一些名詞,導很多定理.如果在3~5章基礎不好的話,應該會看不懂 ▼考試作業▼ 兩次大考,各40%, 作業+小考20% 第一次作業是設計一些DFA/NFA,這部分學生會比較有機會拿高分 第二次作業,大多數會變很低分. 為什麼呢? 因為全都是證明題!! 一般學生都不想去 作證明吧,而老師是很嚴謹的人,所以大多數人寫得證明,老師都不會太滿意 第三次和第四次作業,也都是證明 考試是採Open book,可帶任何的紙本(講義或書籍或筆記),不可帶電子的,但還是要認真看 ,才能應付考試喔!(免得腦筋轉不過來) 而題型是,是非題+證明或問答題 第一次考20題是非(40%), 30%證明(其中一題可直接抄講義), 30% 基本的Push down automata 設計 第二次考35題(70%)是非,10%問答,20%證明 ￥其他￥（是否注重出席率or嚴禁遲到？需要的基礎？） 離散的 logic 和 set 的部分非常重要 老師後來不喜歡學生蹺課,有一次小考說:為鼓勵出席,只要出席就滿分,但小考 最重要的是上課專心聽,不會考太難的 ￠最後想說的話￠ 如果你的老師用的課本是Sipser的話,那麼這門課就一半以上都是證明了,絕對逃不掉. (Note:黃廷祿老師和陳穎平老師都用這一本) 而楊武老師的班級是用Linz的 An introduction to Formal Language and Automata,這本比較強調Automata和Grammer 的設計想法和實例,所以基本上對初學者來講,是比較好讀的,而Sipser的Introduction to theory of Computaion,就不強調automata和grammer的設計,而是強調這些東西運作的 "性質", 所以是以證明為主.當然,後面不用說了,計算理論和複雜度理論,本來就是由 定義和定理構成的,所以這門課不管修到誰的,都是一大挑戰. Note:千萬不要以為楊武老師的課會比其他老師難,這很難說= = ＆誰適合修這門課＆ 如果是修黃老師的,一定要對定義,定理和導定理,有深厚的興趣和一定的能力,不然會修得 很辛苦.不過如果是這樣的學生,應該會很喜歡和黃老師討論問題,喜歡他上課說明的觀點. -- ※ Origin: 交大次世代(bs2.to) ◆ From: 218-173-157-90.dynamic.hinet.net 作者從 218-173-157-90.dynamic.hinet.net 修改文章於 2011/01/26 Wed 00:06:33 推 gxlkhhc：推薦這篇文章 01/26 00:11 推 rockmanray：滿喜歡廷祿葛格的上課方式，基本上老師都會深入淺出 01/26 00:12 推 rockmanray：不過舉例好壞大概一半一半，老師本身滿有理想 01/26 00:13 推 rockmanray：雖然一把年紀了XD 另外這門課其實需要一些基礎 01/26 00:15 推 rockmanray：就如同原po所說的：離散等等 所以其實要額外再複習一些 01/26 00:16 推 advanding100：推薦這篇文章 01/26 01:18 推 nowar100：推黃老師 這種定理推導課 我也上過老師另一門的數理邏輯 01/26 01:33 → nowar100：如果願意好好跟不排斥的話 其實跟老師腳步走我覺得很有趣 01/26 01:34 推 dogsbear：寫的很清楚 01/26 01:37 推 kougousei：推薦這篇文章 01/26 03:28 推 foxs91092：推薦黃老師 老師上課很清楚，相當嚴謹 01/26 13:34 推 foxs91092：而且老師教學相當認真，有問題都可以去跟老師討論 01/26 13:35 推 yukuro：其實我也很好奇,別的老師怎麼上的,感覺上上法很多 01/26 15:40 → yukuro：因為這方面大概有幾種可能:著重在Language 或是automata 01/26 15:41 → yukuro：是一種上法,而著重在計算理論,也是一種上法 01/26 15:41 → yukuro：所以希望其他人也多分享 01/26 15:42 推 ken77921：推薦這個老師 01/26 22:59 推 sword：整堂課充滿各種數學定理證明 跟著老師學得很充實(′‧ω‧) 01/27 17:39 推 sword：不要需要點數學基礎...最少要回憶起大一離散 01/27 17:40 推 icnivad：老師教地好啊~~^^ 01/31 19:08

※ 發信站: 批踢踢實業坊(ptt.cc) ※ 轉錄者: neoneon (106.105.175.48), 07/11/2016 23:46:20