本文尚在草稿狀態(tài)，很難在短期內(nèi)完成寫作。發(fā)布出來(lái)旨在為初學(xué)者提供一些指引：書籍、資料、簡(jiǎn)介、歷史還有我在不同年代的吐槽。請(qǐng)?jiān)徫野淹虏垡沧鳛橹改系囊徊糠?，必不可少的部分?-作者
教材
Introduction to the Theory of Computation ( ITOC ),
作者: Michael Sipser
出版社: Course Technology
出版年: 2012-6-27
ISBN: 9781133187790
主要內(nèi)容
ITOC主講三大內(nèi)容：
- 什么是計(jì)算；
- 什么可計(jì)算；
- 如何度量計(jì)算的效率。
大致上來(lái)說，首先我們需要一種準(zhǔn)確的表達(dá)法來(lái)說明到底計(jì)算本質(zhì)上是什么。不同的科學(xué)家抽象出不同的計(jì)算模型，于是我們必須考查這些模型的表達(dá)能力(第一部分：什么是計(jì)算)。其次，我們發(fā)現(xiàn)計(jì)算是有局限的，不是什么問題都能計(jì)算，那到底什么是可計(jì)算的問題呢？有什么問題是不可計(jì)算的呢（或稱為“不存在算法”）？（第二部分：什么可計(jì)算）如果某些問題是可解的，存在某種算法可以解決這個(gè)問題，那么這種算法的效率如何度量呢？我們需要一種通用的標(biāo)準(zhǔn)度量，並建立相關(guān)理論（第三部分：復(fù)雜性理論）。
需要強(qiáng)調(diào)的是，ITOCv3是本科教材，用于高年級(jí)的本科教學(xué)。
第0章 引論
0.1 自動(dòng)機(jī)、可計(jì)算性、復(fù)雜性
0.2 數(shù)學(xué)表示與術(shù)語(yǔ)
0.3 定義、定理與證明
0.4 證明的類型
第1章 正則語(yǔ)言
Language（語(yǔ)言），對(duì)計(jì)算問題的高度抽象表達(dá)。整本書的重點(diǎn)是“計(jì)算“，如果能體會(huì)出在描述計(jì)算理論時(shí)語(yǔ)言的定義所產(chǎn)生的巨大作用，則理解就上了一個(gè)臺(tái)階。只是，第一章并不能產(chǎn)生這么大的效用，需持續(xù)關(guān)注。
1.1 有限自動(dòng)機(jī)
概念：FA、語(yǔ)言、正則語(yǔ)言、正則操作
定理：正則語(yǔ)言類在正則操作（并、交、串聯(lián)）下封閉；
1.2 非確定性
重點(diǎn)：體會(huì)計(jì)算的非確定性
難點(diǎn)：DFA與NFA的等價(jià)
對(duì)非確定性的兩種解讀：
- 并行執(zhí)行；
- 總是猜對(duì)執(zhí)行路徑。哪一種更好？
問題：為什么我們需要“不確定性“？
1.3 正則表達(dá)
1.4 非正則語(yǔ)言
要點(diǎn)：自動(dòng)機(jī)的計(jì)算局限性
難點(diǎn)：Pumping Lemma及其應(yīng)用
第2章 上下文無(wú)關(guān)語(yǔ)言
2.1 上下文無(wú)關(guān)文法
重點(diǎn)：歧義性
問題1：為什么把能以不同方式生成的字符串稱為歧義？
問題2：為什么需要“最左派生“這個(gè)定義？
2.2 下推自動(dòng)機(jī)
問題0：下推自動(dòng)機(jī)（PDA）比有限自動(dòng)機(jī)的能力更強(qiáng)，主要體現(xiàn)在哪里？為什么PDA能力會(huì)更強(qiáng)呢？
問題1：在Lemma 2.21的證明中，如何確?？杀黄ヅ涞拇畐一定會(huì)被匹配？
回答：構(gòu)造算法是非確定性算法。重點(diǎn)體會(huì)非確定性選擇的含義。
問題2：在Lemma 2.27的證明中，如果p不可達(dá)q，那么的構(gòu)造是否還合法（會(huì)出現(xiàn)不合法的情況）？
回答：暫無(wú)
2.3 非上下文無(wú)關(guān)語(yǔ)言
2.4 （忽略）
第3章 丘奇-圖靈論題
本章的主要內(nèi)容是介紹圖靈機(jī)及其相關(guān)概念，旨在進(jìn)一步刻畫計(jì)算（算法）的本質(zhì)。重點(diǎn)區(qū)分兩個(gè)概念：圖靈可判定與圖靈可識(shí)別。從算法的角度看，前者要求計(jì)算在有限步之后結(jié)束，而后者沒有。明白了這種區(qū)別，對(duì)計(jì)算機(jī)的有限計(jì)算將會(huì)有更深入的理解。
3.1圖靈機(jī)
一種計(jì)算模型，定義繁瑣，但并無(wú)理解難點(diǎn)。
3.2 圖靈機(jī)的各種變種
3.3 算法的定義
第4章 判定性
4.1 可判定語(yǔ)言
4.2 停機(jī)問題
重點(diǎn)：對(duì)角線法、停機(jī)問題不可判定的證明
關(guān)于停機(jī)問題的一種充滿詩(shī)意的證明
5 可歸約性
這一章的重點(diǎn)是理解歸約的本質(zhì)、過程與應(yīng)用。
5.1 語(yǔ)言理論中的不可判定問題
針對(duì)RL與CFL的若干語(yǔ)言形成的判定性問題進(jìn)行證明。
5.2 一個(gè)簡(jiǎn)單的不可判定問題：PCP問題
只是一個(gè)證明！PCP問題的描述很簡(jiǎn)單，其不可判定性倒是頗令人感到意外。這里除了一個(gè)結(jié)論，一個(gè)冗長(zhǎng)的證明外，內(nèi)容不多。
5.3 不可判定問題的形式化定義：映射可歸約性
重點(diǎn)：Mapping Reducibility的定義
第6章 計(jì)算理論的高級(jí)專題
6.1. 遞歸定理
遞歸定理展示“程序自我復(fù)制是可能的”這樣一個(gè)簡(jiǎn)單而令人吃驚的結(jié)論。
The Quine Page，里面收集了大量不同語(yǔ)言寫成的Quine程序：自己輸出自己源代碼的程序。
待續(xù)
參考書
- Introduction to Automata Theory, Languages, and Computation (IALC), John E. Hopcroft, Rajeev Motwani, Jeffrey D Ullman，Addison Wesley, 2006-7-15. (不能不說的另一本鼎鼎有名的ITOC book。)
- CS-581: Theory of Computation. (By Harry Porter -D)
- A free book of ITOC (another ITOC).
- MIT 18. 404J,Sipser 授課視頻
選課建議
首先，這是一門為有志氣有思想不怕困難的同學(xué)開設(shè)的課程。其次，這是一門比較困難的理論課程，需要大量的閱讀與思考。第三，學(xué)這門課很難立即給你帶來(lái)那種讓同學(xué)們羨慕的實(shí)踐技能、那些傳說中大公司招人所需的技能，但是它能給你帶來(lái)思想上的重大轉(zhuǎn)變（如果你認(rèn)真學(xué)的話）。第四，如果你對(duì)理論不感興趣，請(qǐng)不要選，盡管我知道所謂“不喜歡理論”的人通常不知道什么是理論。最后，如果你選擇了讀研，我建議你選，因?yàn)槟氵x擇讀研就隱含地意味你必須面對(duì)理論，也許你不同意我這個(gè)看法也沒關(guān)系。
ITOC 在某學(xué)院的本科開課歷史
- 2014年秋季，2012級(jí)網(wǎng)絡(luò)工程專業(yè)首次授課；
- 2015年秋季，2013級(jí)網(wǎng)絡(luò)工程專業(yè)第二次授課；
- 2016年秋季，2014級(jí)因故停開
- 2017年秋季，2015級(jí)因故停開
- 2018年秋季，2016級(jí)待定
...... - 2023年春季，2022級(jí)（大一新生）開課?。?！
以下廢話
我年輕的時(shí)候曾經(jīng)吐槽說：
TOC是科普，無(wú)論是全職師奶還是IT民工都可以讀之且獲得樂趣，何況一眾非常有可能是擁有211重點(diǎn)大學(xué)雙一流學(xué)科本科學(xué)位的全職師奶或者IT民工。
閱讀TOC不需要高IQ，不要總是拿自己的IQ忽悠自己和他人。
TOC是思維的訓(xùn)練，文化的熏陶，你們不缺少知識(shí)、不缺少信息，缺的是熏陶。
TOC是巨人出沒的領(lǐng)域，你不走入巨人的領(lǐng)地，怎么能站到巨人的肩膀上呢？
2017年7月整理
2023年3月整理
