正規語言概論 – 交大修課心得

課程資料

正規語言概論

開課:黃廷祿老師

修課年度:100資工系

這門課的課題是基礎的計算理論,研究什麼是電腦的能力和極限。介紹各種計算模型,例如 DFA, NFA, PDA, Turing machines 等等,以及其相對應的正規語言,如 regular languages, context free languages, Turing-decidable languages 等等。也會探討問題間的 Reduction 以及問題的 Complexity。使用的課本是《Introduction to the Theory of Computation》,更多相關議題可參考:〈正規語言概論〉

上課方式

上課是用老師自己編的講義作為投影片講解,有時也會配合課本的頁面。老師上課時常會點同學回答,如果有同學打瞌睡他也會熱心的叫醒大家。老師會記人的名字,筆者就曾被點名回答題目。有時老師的穿著頗為正式,下課時如果問老師問題,他會不耐其煩的細心講解。作業通常是先在上課時宣佈,其後再公佈於課程網頁上。他偶而會在上課時突擊小考。

他曾說資工有很多課會消失於時代的演進之中,但這堂課是歷久不衰的。

好像是因為有同學懷疑課本的文法,所以老師有一次和我們談談學習英文的重要性,還跟我們說學校的圖書館有 iPad 可以出借,介紹了可以在其上使用的 Merriam-Webster 英英字典(有真人發音),以及 New York Times 等讀物。

順帶一提,筆者也有用過《Longman Dictionary of Contemporary English》以及《Collins COBUILD Advanced Learner’s English Dictionary》,這三者都是非常優秀的英英字典,除了紙本外也都附有 PC 版光碟。關於英英字典也可參考:〈辭典選用的基本觀念〉〈哪本辭典的定義最好?〉

考試作業

這堂課的負擔其實沒有很重,通常是數個禮拜老師才會在上課時宣佈習題。習題內容為課本的練習題,每次都只有一兩題,很快就會寫完,有時老師也會自己出題。

基本上是不點名,只有一次發了問卷調查作為點名,不過因為上課時有突擊小考,加上作業都在上課先宣佈的關係,建議還是不要蹺課比較好。

突擊小考的內容多半是剛剛才講過的內容,所以上課專心能有回報。考題不難,通常只有一題,若對課本有一定的熟悉度,應能很快寫完。

除此之外,還有期中考和期末考。老師會在事前公佈考古題,從考古題看來,以前的考試型態似乎有不少證明題。不過這次的期中考意外的沒出證明題,而且題型偏向簡單,多數人都考的不錯。期末考出了幾題證明,不過也滿基本的,考古題感覺難很多。

考試題型分別為是非題、選擇題,及最後的簡答、計算與證明題。所有的考試都是 open book,可以自由查閱課本、講義,或任何自帶紙本參考資料。也因此考的題目都會有變化,不會跟考古題一樣。

結語

這門課使用的課本其實內容不多,而且由於較為理論與數學,可以邊看邊思考,閱讀起來並不枯燥,筆者暑假時利用通勤的時間,把課本看完了一遍,覺得幫助頗大。《Intro. to the Theory of Computation》這本書真的寫得不錯,算是在資工教科書中,十分易讀的課本之一。

由於老師出的練習題實在太少,令人感覺不踏實,所以筆者也將課本裡附有答案的習題寫過了一遍。老師並不會出一些刁難的問題,基本上只要細讀課本與講義,考試和作業應該都能把握。

廣告

2 thoughts on “正規語言概論 – 交大修課心得

    • 您好,這個應該是看個人情況有所不同,不過其實印象中這門課跟資工其他課的關聯度沒有很大就是,唯一可能可以算的上是有關的先修課程應該只有「離散數學」。理論上修過其他資工的課並不會比較聽的懂這堂課。

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 /  變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 /  變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 /  變更 )

w

連結到 %s