1、第一章 計(jì)算與計(jì)算機(jī)科學(xué)引論1，什么是計(jì)算、什么是計(jì)算科學(xué)？一、概念： Mathematical Theory of ComputationZ.Manna： “什么是計(jì)算？我相信，世界上沒有兩個(gè)計(jì)算機(jī)科學(xué)家會(huì)就這一概念給出相同的定義?！币粋€(gè)也許是最容易理解的定義： 計(jì)算科學(xué)是使用數(shù)學(xué)語(yǔ)言對(duì)信息進(jìn)行描述與處理的系統(tǒng)理論應(yīng)用的科學(xué)。計(jì)算不等于數(shù)學(xué)，但數(shù)學(xué)確源于計(jì)算。計(jì)算科學(xué)不等于信息科學(xué)，但信息科學(xué)必須基于計(jì)算科學(xué)。二、內(nèi)容 1，基礎(chǔ)構(gòu)造性數(shù)學(xué)（數(shù)理邏輯、代數(shù)系統(tǒng)、圖論、集合論）歷史：數(shù)學(xué)的三次飛躍。解析幾何：由于笛卡爾坐標(biāo)系的發(fā)明, 把數(shù)與形聯(lián)系在一起；微積分：將數(shù)學(xué)引人無(wú)窮小分域；群論：代數(shù)系

2、統(tǒng)的整體結(jié)構(gòu)研究。數(shù)學(xué)基礎(chǔ)問題： 集合論悖論（B.Russell） 定義集合 S=x | x S） 數(shù)學(xué)公理體系的相容性。*特別關(guān)于“無(wú)矛盾與完備證明”以及“無(wú)窮總體的存在與真實(shí)性”的討論導(dǎo)致三個(gè)數(shù)學(xué)派別的明確形成。數(shù)學(xué)的邏輯主義學(xué)派 B.Russell 核 A.N.Whitehead 為代表，認(rèn)為數(shù)學(xué)從邏輯推導(dǎo)而來(lái)，是邏輯的擴(kuò)展。數(shù)學(xué)與邏輯是一個(gè)主題，邏輯先于數(shù)學(xué)。也就是說，數(shù)學(xué)可以不通過外加入新的概念而純邏輯得到。羅素的數(shù)學(xué)原理。D.Hilbert，認(rèn)為數(shù)學(xué)是形式系統(tǒng)。每一個(gè)數(shù)學(xué)分支有自己的概念、公理和推導(dǎo)定理的法則以及自己的定理。把數(shù)學(xué)演繹系統(tǒng)通過形式的邏輯推理方式建立數(shù)學(xué)分支，而產(chǎn)生的

3、數(shù)學(xué)分支將不存在悖論。數(shù)學(xué)的形式主義學(xué)派數(shù)學(xué)的直覺主義學(xué)派 十九世紀(jì)末，由對(duì)數(shù)系與幾何的嚴(yán)密化，代表人物 L.E.J.Brouwer。強(qiáng)調(diào)數(shù)學(xué)先于邏輯，而邏輯是從數(shù)學(xué)思維中總結(jié)出來(lái)的規(guī)律。主張數(shù)學(xué)中所有概念和證明都必須是構(gòu)造性的，排中律只有在有限論域中是正確的，對(duì)無(wú)窮論域就不一定正確。一個(gè)數(shù)學(xué)名題除了正、反兩面之外，還有一種可能不可解。對(duì)數(shù)學(xué) 證明中普遍使用的反證法，直覺主義學(xué)派只限于證明否定命題。三種數(shù)學(xué)學(xué)派都在現(xiàn)代數(shù)學(xué)中存在且各有利弊。 從直覺主義學(xué)派的觀點(diǎn)產(chǎn)生的構(gòu)造性數(shù)學(xué)是計(jì)算科學(xué)的基礎(chǔ)。計(jì)算必須建立在可構(gòu)造的邏輯推理基礎(chǔ)上。2，計(jì)算的數(shù)學(xué)理論計(jì)算理論、高等邏輯、形式語(yǔ)言與自動(dòng)機(jī)、形式語(yǔ)

4、義學(xué)、Petri網(wǎng)論、通信順序進(jìn)程（CSP）、通信系統(tǒng)演算、演算、進(jìn)程代數(shù)（PA）、分布式事件代數(shù)（DEA）等。計(jì)算理論可計(jì)算性理論：抽象的計(jì)算模型及其性質(zhì)，可計(jì)算 函數(shù)以及之間關(guān)系；算法理論：抽象模型上的算法設(shè)計(jì)與算法復(fù)雜度；計(jì)算復(fù)雜性：算法復(fù)雜性，可計(jì)算函數(shù)的復(fù)雜性。高等邏輯模型論：形式語(yǔ)言及其解釋之間的關(guān)系；非經(jīng)典邏輯：時(shí)序邏輯、模態(tài)邏輯、概率邏輯、非單調(diào)邏輯、歸納邏輯、模糊邏輯。形式語(yǔ)言與自動(dòng)機(jī)理論 形式語(yǔ)言理論是用數(shù)學(xué)方法研究語(yǔ)言的語(yǔ)法（詞法與文法），研究語(yǔ)言的構(gòu)造性結(jié)構(gòu)的學(xué)問； 自動(dòng)機(jī)理論，主要研究各種能自動(dòng)處理符號(hào)的數(shù)學(xué)機(jī)器； 當(dāng)將自動(dòng)機(jī)看成是一種符號(hào)接受器或識(shí)別器的時(shí)候，文法與

5、自動(dòng)機(jī)可以證明是等價(jià)的。形式語(yǔ)言學(xué) 用數(shù)學(xué)方法研究語(yǔ)言的語(yǔ)義或語(yǔ)言的含義。特別是研究程序設(shè)計(jì)語(yǔ)言的語(yǔ)義。例：操作語(yǔ)義、指稱語(yǔ)義、公理語(yǔ)義和代數(shù)語(yǔ)義。 3, 計(jì)算機(jī)組成原理、器件與體系結(jié)構(gòu) 根據(jù)計(jì)算模型研究計(jì)算機(jī)的工作原理，并按照器件、設(shè)備、工藝條件設(shè)計(jì)，制造具體的計(jì)算機(jī)。 由于硬件的極限，當(dāng)前重在分布式網(wǎng)絡(luò)計(jì)算機(jī)系統(tǒng)和并行計(jì)算機(jī)系統(tǒng)。同時(shí)產(chǎn)生了對(duì)解問題的分布式算法與并行算法?？勺兘Y(jié)構(gòu)與開放式系統(tǒng)是有希望的方向。 算法基礎(chǔ)、程序設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫(kù)基礎(chǔ)、微機(jī)原理與接口技術(shù)。算法基礎(chǔ)是研究數(shù)值算法與非數(shù)值算法的基本設(shè)計(jì)方法與分析。數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)表示與存儲(chǔ)的方法、抽象的邏輯結(jié)構(gòu)以其上定義的各

6、種基本操作。 4, 計(jì)算機(jī)應(yīng)用基礎(chǔ) 微機(jī)接口技術(shù)研究計(jì)算機(jī)之間及與外部設(shè)備儀器之間的數(shù)據(jù)連接問題。 5， 計(jì)算機(jī)應(yīng)用技術(shù) 數(shù)值計(jì)算、信號(hào)處理技術(shù)、圖形學(xué)與圖象處理技術(shù)、網(wǎng)絡(luò)技術(shù)、多媒體技術(shù)、計(jì)算可視化與虛擬現(xiàn)實(shí)技術(shù)、人工智能技術(shù)、輔助設(shè)計(jì)、測(cè)試、制造、教學(xué)等輔助技術(shù)等。6， 軟件基礎(chǔ) 高級(jí)語(yǔ)言、數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計(jì)、編譯原理、數(shù)據(jù)庫(kù)原理、操作系統(tǒng)原理、軟件工程。2， 計(jì)算機(jī)原理一、歷史1623年: Wilhelm Schikard 在給開普勒的信中提出了加 法器、乘法器和記錄中間結(jié)果機(jī)構(gòu)等三步分組成 的機(jī)械式計(jì)算機(jī)的設(shè)想。1642年：法國(guó)人B.Pascal基于齒輪技術(shù)制造了一臺(tái)能夠進(jìn) 行加法和乘

7、法運(yùn)算的計(jì)算器,以后成為手搖計(jì)算 機(jī)的原理. Pascal 語(yǔ)言是為紀(jì)念他而起名的.1672年：G.W.Leibniz提出了不用連續(xù)相加而進(jìn)行機(jī)械乘 法的思想,并制成樣機(jī),成為手搖計(jì)算機(jī)例子.同 時(shí)提出二進(jìn)制計(jì)算在機(jī)械計(jì)算中作用. 一百年后,C.Thomas 研制成機(jī)械計(jì)算器并批量生產(chǎn).18世紀(jì)：英國(guó)數(shù)學(xué)家C.Babbage提出了用程序控制計(jì)算的思想,并且用齒輪式寄存器、運(yùn)算裝置和專門控制操作順序的結(jié)構(gòu)組成的通用數(shù)字計(jì)算機(jī)的設(shè)計(jì)方案，1972年在美國(guó)明尼蘇達(dá)大學(xué)建立了巴貝治信息處理研究所。 19世紀(jì)：英國(guó)G.Bool系統(tǒng)研究了邏輯思維的一般規(guī)律,將形式邏輯歸結(jié)為一種代數(shù)運(yùn)算Boll代數(shù)，成為現(xiàn)

8、代計(jì)算機(jī)的理論基礎(chǔ)。 20世紀(jì)初：希爾伯特提出“希爾伯特計(jì)劃”，認(rèn)為數(shù)學(xué)可以從少數(shù)幾條公理出發(fā)推理產(chǎn)生所有數(shù)學(xué)定理及其證明。但是哥德爾定理使這一計(jì)劃破滅；具有一定復(fù)雜程度的完備的數(shù)學(xué)系統(tǒng)是不存在的。 同時(shí)，丘奇、波斯特、圖靈從不同角度考察什么樣的數(shù)學(xué)問題是機(jī)械可解的？ 1936年，丘奇發(fā)表了關(guān)于遞歸函數(shù)的論文，給出可計(jì)算函數(shù)的概念，從可計(jì)算函數(shù)的結(jié)構(gòu)與構(gòu)造出發(fā)討論計(jì)算的概念；而圖靈從理想化的數(shù)學(xué)機(jī)器的改造來(lái)研究計(jì)算，以過程形式比較準(zhǔn)確地刻畫了計(jì)算的概念。2，存儲(chǔ)程序式計(jì)算機(jī)的基本結(jié)構(gòu)與工作原理 圖靈機(jī)提供了存儲(chǔ)數(shù)據(jù)與程序的功能，從而在馮.諾依夏的設(shè)計(jì)下，完成現(xiàn)代計(jì)算機(jī)的工作原理。 控制器控制器

9、 存儲(chǔ)器 輸入輸出控制部件 反饋信息 輸入輸出設(shè)備 反饋信息(1)輸入設(shè)備 計(jì)算機(jī)與外部交互部件，用于輸入，基本數(shù)據(jù)以二進(jìn)制，優(yōu)點(diǎn)在于只需要兩件穩(wěn)定狀態(tài)以供計(jì)算，比多種穩(wěn)定狀態(tài)的多進(jìn)制易于實(shí)現(xiàn)；缺點(diǎn)是字長(zhǎng)變得很長(zhǎng)。（2）存儲(chǔ)器 數(shù)據(jù)與信息的存儲(chǔ)部件，每個(gè)存儲(chǔ)單元編有地址。內(nèi)存儲(chǔ)器直接讀取數(shù)據(jù)，存取速度快，但停電后信息消失。 外存儲(chǔ)器不能直接讀取，速度慢，但可以永久保留信息。（3）運(yùn)算器 運(yùn)算器是計(jì)算機(jī)對(duì)數(shù)據(jù)或信息進(jìn)行技術(shù)運(yùn)算或邏輯運(yùn)算的主要部件，由很多邏輯電路組成，包括寄存器，加法器，移位器和一些控制電路。（4）輸出設(shè)備 計(jì)算機(jī)與外部交互部件，用于數(shù)據(jù)輸出，形成數(shù)字、字符、圖形、圖象聲音等等。

10、 （5） 控制器 計(jì)算機(jī)的中樞，控制整個(gè)計(jì)算機(jī)各部分由序工作，由時(shí)序電路和邏輯電路組成，通過輸出電壓與脈沖信號(hào)來(lái)實(shí)現(xiàn)對(duì)計(jì)算機(jī)的控制。 運(yùn)算器與控制器整合成一個(gè)中央處理器或CPU；輸入輸出與外存儲(chǔ)器為外部設(shè)備，內(nèi)存儲(chǔ)器為內(nèi)存部件。3，Boolean代數(shù) 1854年George Boole在The Laws of Thought一書中第一次給出了邏輯的推理規(guī)則。1938年Claude Shannon 揭示出如何用邏輯的基本規(guī)則設(shè)計(jì)電路數(shù)字邏輯電路，從而形成今天的Boole代數(shù)。 一個(gè)布爾函數(shù)對(duì)每個(gè)輸入集合均給出確定的輸出值，而電路的操作結(jié)果由布爾函數(shù)定義。而布爾函數(shù)只是給出輸入輸出值，必須有確定的

11、算法用布爾代數(shù)的基本運(yùn)算改造出布爾表達(dá)式來(lái)表示布爾函數(shù)。一、布爾函數(shù)1，布爾運(yùn)動(dòng)： 在集合0，1上定義三種布爾運(yùn)算，一元運(yùn)算布爾補(bǔ)一；兩個(gè)二元運(yùn)算，布爾和V，+，OR ； 1+1=1 ， 1+0=1 ， 0+1=1 ， 0+0=0布爾積 ， AND。 11=1 ， 1 0=1 ， 0 1=1 ， 0 0=0若補(bǔ)對(duì)應(yīng)邏輯算子 ，而0F（假），1T（真），則布爾運(yùn)算對(duì)應(yīng)到邏輯推理。2，布爾表達(dá)式與布爾函數(shù)B0，1，稱從B中取值的變?cè)獮椴紶栕冊(cè)度布爾函數(shù)（Boolean function of degree n）：BnB。其中Bn=（x，x2，xn）|xiB， 1in。布爾表達(dá)式（遞歸定義）：1

12、） 0，1，x1，xn 是布爾表達(dá)式；2） 若E1，E2是布爾表達(dá)式則 3，布爾代數(shù)中恒等式4，布爾代數(shù)：定義：集合B上有兩個(gè)二元運(yùn)算，及元素0，1，以及一個(gè)一元運(yùn)算，且對(duì) x，y，z B：5，布爾函數(shù)表示： 顯然小項(xiàng)值為 1 每個(gè)變?cè)禐?。問題：給定一個(gè)布爾函數(shù)（函數(shù)值表），怎樣找到表示這個(gè)布爾函數(shù)的布爾表達(dá)式？有沒有最小的算子集合可表示所有布爾函數(shù)？xyzFG1111000011001100101010100010000001000100 xyzx+y111100001100110010101010111111000101010101010100從而用布爾和的布爾積表示一個(gè)布爾函數(shù)稱函數(shù)

13、的合取范式或和之積展開式。二、邏輯門電路 根據(jù)布爾代數(shù)的規(guī)則可以設(shè)計(jì)成電路，所有復(fù)雜的運(yùn)算由簡(jiǎn)單的邏輯電路組合實(shí)現(xiàn)。三種基本元件（電路）： 反相器 或門 與門 x 0 0 x+y 0 x+yxyxy例加法器： 不考慮以前的進(jìn)位，輸入x，y為 0，1，輸出 s （和位），c（進(jìn)位），則稱半加器；則輸入、輸出表與電路如下：輸入輸出xysc1100101001101001輸入x，y及進(jìn)位ci，輸出 s， ci+1如表輸入輸出xycisci+11111000011001100101010101001011011101000第二章 計(jì)算模型與形式語(yǔ)言計(jì)算模型：形式語(yǔ)言文法、有限狀態(tài)機(jī)、圖靈機(jī)。由于計(jì)算是

14、可以用語(yǔ)言來(lái)描述的，因此語(yǔ)言的文法象一臺(tái)計(jì)算機(jī)一樣給出結(jié)論。1， 形式語(yǔ)言 在語(yǔ)言的翻譯過程中產(chǎn)生了語(yǔ)言的抽象形式：形式語(yǔ)言。短語(yǔ)結(jié)構(gòu)文法 定義1，字母表（也稱字匯表）V是一個(gè)有限非空集，其元素為符號(hào)。V上的一個(gè)詞或句子是指V中元素組成的有限長(zhǎng)度的字符串?？沾菦]有字符的串（不是空集），記為。V上所有詞的集合記為V*，V上的語(yǔ)言是V*的一個(gè)子集。 定義2， 一個(gè)短語(yǔ)結(jié)構(gòu)文法G=（V，T，S，P）由四部分組成：字母表（或詞匯表）V，由V的所有終結(jié)符組成的V的子集T，V的初始符S，和產(chǎn)生式集合P。集合V-T=N稱為非終結(jié)字符集，P中的每個(gè)產(chǎn)生式的左邊必須至少包含一個(gè)非終結(jié)符。 語(yǔ)言有子字表V及詞匯

15、表及所有短語(yǔ)語(yǔ)句的集合。例如漢字“句”“子”，及英語(yǔ)字母表。如果終結(jié)符是所有英文字母，而所有漢字為非終結(jié)符，則由產(chǎn)生式最后得到的是英文。例如生成式產(chǎn)生。句子名詞動(dòng)詞，則這些漢字還可以通過生成式代換成英文。 例1，設(shè)G=（V，T，S，P），其中V=a，b，A，B，S，T=a，b，S是初始符，Ps=Aba，ABB，Bab，Abb，構(gòu)成短語(yǔ)文法結(jié)構(gòu)。 定義3，設(shè)G=（V，T，S，P），是一個(gè)短語(yǔ)結(jié)構(gòu)文法，w0=lz0r， w=lz1r是V中串。若z0z1是G的一個(gè)產(chǎn)生式，則稱w0w1稱直接派生。如果V上串w0， w1 ， wn（n0）滿足： w0w1 ， w1w2 ， wn-1wn ，則稱由w0可派

16、生，記為w0*wn。由w0到wn 的序列稱為派生。 例2，在例1的文法中，ABB，Bab，可以派生：ABa Aaba BBaba Bababa abababa 定義4，設(shè)G=（V，T，S，P），是一個(gè)短語(yǔ)結(jié)構(gòu)文法由G生成的語(yǔ)言是初始符S能夠派生的所有終結(jié)符串構(gòu)成的集合，記為L(zhǎng)（G）： L（G）=wT*|S*w 習(xí)題1：設(shè)G是一個(gè)文法，其字母表V=S，A，a，b，終結(jié)符集T=a，b，初始符為S，產(chǎn)生式為P=SaA，Sb，Aaa，求這文法生成的語(yǔ)言 L（G）。 習(xí)題2：設(shè)G是一個(gè)文法，字母表V=S，0，1，終結(jié)符 T=0，1，初始符為S，產(chǎn)生式為P=S11S，S0，求這文法的語(yǔ)言 L（G）。 例3

17、：給出生成集合0n1n| n=0，1，2， 的一個(gè)短語(yǔ)結(jié)構(gòu)文法，G=（V，T，S，P），V=0，1，S終結(jié)符集T=0，1，初始符為S，產(chǎn)生式為S0S1，S 。 例4：給出生成集合0m1n| m和n均為非負(fù)整數(shù) 的一個(gè)短語(yǔ)結(jié)構(gòu)文法解：可以構(gòu)造兩個(gè)文法G1，G2來(lái)生成這個(gè)集合。 G1：V=S，0，1，終結(jié)符集T=0，1 產(chǎn)生式 S0S，SS1，S 。 G2：V=S，A，0，1，終結(jié)符集T=0，1 產(chǎn)生式 S0S，S1A，S1，A1A，A1和S 。 例5：生成集合0n1n2n | n=0，1，2， 。一個(gè)文法G=（V，T，S，P），其中V=0，1，2，S，A，B ，終結(jié)符T=0，1，2，初始符為S，

18、產(chǎn)生式為 S0SAB，S ，BAAB，OA01，1A11，1B12，2B22 二、短語(yǔ)結(jié)構(gòu)文法類型 諾姆：齊姆斯基（Avram Noam Chomsky）的文法分類，不同文法也就定義了不同的語(yǔ)言，對(duì)應(yīng)于不同計(jì)算模型能識(shí)別的語(yǔ)言。0型文法：沒有限制產(chǎn)生式。1型文法只有兩種產(chǎn)生式：a，w1w2，L（w2L（w1）； b，w1 。 1型文法是一種O型文法，對(duì)文法lw1rlw2r也稱1型文法，此時(shí)必須有相同的包 lr 。也稱上下相關(guān)文法。2型文法只有產(chǎn)生式：w1w2 且：w1=A 且：w2 =aB或 w 2=a0 其中A，B是非終結(jié)字符而a是終結(jié)符?；蛘撸?w1 =S，w2 = 0 3型文法全是2型文

19、法。例6，G 2文法是正則文法。例7，由S0S1, S從而是上下文無(wú)關(guān)文法, 但不是3型。例8，是上下文相關(guān)文法但不是2型文法。 2,有限狀態(tài)機(jī)包括一個(gè)有限的狀態(tài)集合(含初試態(tài))，一個(gè)輸入字母表和一個(gè)轉(zhuǎn)移函數(shù)（對(duì)每個(gè)狀態(tài)和輸入指定下一個(gè)狀態(tài)）。自動(dòng)售貨機(jī)、整數(shù)加法器及許多計(jì)算機(jī)部件的數(shù)學(xué)模型。 一、帶輸出有限狀態(tài)機(jī)狀態(tài)下 一 個(gè) 狀 態(tài)輸 出輸 入5 10 25 O R輸 入5 10 25 O Rs0s1s2s3s4s5s6s1 s2 s5 s0 s0 s2 s3 s6 s1 s1 s3 s4 s6 s2 s2 s4 s5 s6 s3 s3 s5 s6 s6 s4 s4s6 s6 s6 s5

20、s5s6 s6 s6 s0 s0n n n n nn n n n nn n 5 n nn n 10 n nn n 15 n nn 5 20 n n 10 25 OJ AJ 定義1：有限狀態(tài)機(jī)M=（S，I，O，f，g， s0 ）由如下部分組成：有限狀態(tài)集S，有限輸入字母表I，有限輸出字母表O，轉(zhuǎn)移函數(shù)。：每個(gè)狀態(tài)及輸入對(duì)指定一個(gè)新狀態(tài)，輸出函數(shù)g：每個(gè)狀態(tài)和輸入對(duì)指定一個(gè)輸出，一個(gè)初始狀態(tài)。例1，一個(gè)有限狀態(tài)機(jī)，其中S=S0 ， S1， S2， S3，I=a，1且O=0，1。f 與g的值由表給出。也可以用狀態(tài)圖表示：狀態(tài)fg輸入1輸出1s0s1s2s3s1s3s1s2s0s0s2s1110001

21、10例2，試構(gòu)造一個(gè)有限狀態(tài)機(jī)，使其利用整數(shù)二進(jìn)制展開式將兩個(gè)整數(shù)相加。 解：初始位令是0（xn，yn）=（0，0）。S0前進(jìn)位0，S1前進(jìn)位1；兩位輸入（第一個(gè)數(shù)，第二個(gè)數(shù)），只有四種：00，01，10，11。轉(zhuǎn)移與輸出根據(jù)下面兩因素構(gòu)造的輸入所表示的兩個(gè)二進(jìn)制數(shù)之和；另一個(gè)是狀態(tài)S0，S1表示的進(jìn)位情況。 此機(jī)器的狀態(tài)圖：二、不帶輸出的有限狀態(tài)機(jī) 有限狀態(tài)機(jī)最重要的應(yīng)用是語(yǔ)言識(shí)別，這在設(shè)計(jì)編譯器時(shí)有實(shí)際用途。帶輸出的有限狀態(tài)機(jī)可以識(shí)別語(yǔ)言，但可以專門設(shè)計(jì)不帶輸出的有限狀態(tài)機(jī)以供識(shí)別語(yǔ)言。 定義1，設(shè)V是一個(gè)字母表（或詞匯表），A，B是V*的子系。A和B的連接是所有形如xy的串構(gòu)成的集合，記

22、AB，其中xA，yB。 例1， A=0，11，B=1，10，110， 則 AB=01，010，0110，111，1110，11110， BA=10，111，100，1011，1100，11011 注意 ABBA！ 定義2，設(shè)A是V*的子集。A的克萊因閉包是A中任意多個(gè)串的連接組成的集合，記為A*： 定義3，有限狀態(tài)自動(dòng)機(jī)M=（S，I，f，s0，F(xiàn)）：有限狀態(tài)集合S，有限輸入字母表I，轉(zhuǎn)移函數(shù) f ，初始狀態(tài)S0，由終結(jié)狀態(tài)構(gòu)成的S的子集F。 有限自動(dòng)機(jī)也可以用狀態(tài)圖表示，終結(jié)符用雙圈表示。 例2，構(gòu)造有限自動(dòng)機(jī)M=（S，I，f，s0，F(xiàn)）的狀態(tài)圖，其中 S=（ s0 ， s1， s2， s3）

23、，I=0，1，F(xiàn)=（ s0 ， s1）狀態(tài)f輸入 01s0s1s2s3s0 s0 s0 s2s1 s2 s0 s1 看這自動(dòng)機(jī)可識(shí)別的語(yǔ)言終結(jié)符只有 s0 ， s3，可將s0 變?yōu)閟0的只有串，0，00，0n ；將 s0 s3 ： 0n 10后跟任意x，從而語(yǔ)言： L= 0n ，0n 10 x | n=0，1，x 是任意串了。 如果狀態(tài)的轉(zhuǎn)移是不確定的，也就是不是唯一的轉(zhuǎn)移，稱非確定型的有限狀態(tài)自動(dòng)機(jī)。 定義4，非確定型有限狀態(tài)自動(dòng)機(jī)M=（S，I，f，S0，F(xiàn)）由以下五部分組成：一個(gè)狀態(tài)的集合S，一個(gè)輸入字母表I，一個(gè)轉(zhuǎn)移函數(shù)f（f 為每個(gè)狀態(tài)和輸入對(duì)指派一個(gè)狀態(tài)集合），一個(gè)初始狀態(tài)S0和一個(gè)

24、由終結(jié)狀態(tài)構(gòu)成的S的子集F。 例4，一個(gè)非確立性有限狀態(tài)自動(dòng)機(jī)的狀態(tài)表與狀態(tài)圖：狀態(tài)f 01輸入s0s1s2s3 s4s01 s2 s3 s3 s3s1 s4s4 s3 非確定性自動(dòng)機(jī)所確定的語(yǔ)言，就是這個(gè)機(jī)所識(shí)別的所有串的集合。 上述自動(dòng)機(jī)所能識(shí)別的集合： 1），S0是終結(jié)字符，可見所有On可識(shí)別； 2）S4是終結(jié)字符，從S0到S4的所有可能串：0n01，0n11 從而可識(shí)別的語(yǔ)言L=0n，0n01，0n11 | n0 定理1，如果語(yǔ)言L可以由非確定型的有限自動(dòng)機(jī)M0識(shí)別，也可以由一個(gè)確定型有限自動(dòng)機(jī)M1識(shí)別。三、 語(yǔ)言的識(shí)別 以下嚴(yán)格敘述：定義1，集合I上的正則表達(dá)式的遞歸定義如下： 符號(hào)

25、是一個(gè)正則表達(dá)式； 符號(hào)是一個(gè)正則表達(dá)式； 若xI，符號(hào)x是一個(gè)正則表達(dá)式； 當(dāng)A，B是正則表達(dá)式時(shí)，符號(hào)（AB），（AB）和A*都是正則表達(dá)式。這里A*式A代表的集合的克萊因閉包。 克萊因在1956年首先證明了：一個(gè)集合能夠被一個(gè)有限狀態(tài)自動(dòng)機(jī)識(shí)別當(dāng)且僅當(dāng)這個(gè)集合是這樣得到的：以任意順序通過對(duì)空集、空串和單字符串的連接，并或克萊因閉包構(gòu)造出來(lái)。以這種方法構(gòu)造出來(lái)的集合稱為正則集合。 例 以下正則表達(dá)式表示的集合 10*：1 后任意多個(gè) 0 （10*）：10的任意多次復(fù)制（包括空串） 0 01：串 0 或 01 0（0 1）*：以 0 開頭的任意 0 和 1 生成的串。 （0*1）*：不以 0

26、 結(jié)尾的任意串。 克萊因定理：一個(gè)集合是正則的，當(dāng)且僅當(dāng)它可由一個(gè)有限狀態(tài)自動(dòng)機(jī)識(shí)別。 定理：一個(gè)集合可以由正則文法生成，當(dāng)且僅當(dāng)它是一個(gè)正則集合。 每個(gè)正則表達(dá)式表示一個(gè)由下列規(guī)則指出的集合： 表示空集； 表示集合 ； x表示由單個(gè)符號(hào)x贊成的串； （AB）表示A和B表示的集合的連接； （AB）表示A和B代表的集合的并。正則表達(dá)式表示的集合稱為正則集合。 3圖靈機(jī) 帶有存貯功能的計(jì)算模型，更強(qiáng)大的計(jì)算功能。一、圖靈機(jī)： 定義1，圖靈機(jī)T=（S，I，f，S0）：有限狀態(tài)集S，含有空白符B的字母表I，從SIR，L的部分函數(shù) f 及初始狀態(tài)S0。所謂部分函數(shù) f 是對(duì)定義域內(nèi)有些有定義，有些無(wú)定義

27、。 當(dāng)控制頭讀當(dāng)前符號(hào)x，處于狀態(tài)S，且部分函數(shù) f在（x，S）處由f（S，x）=（S，x，d）定義，則控制頭 1，進(jìn)入狀態(tài) S； 2，當(dāng)前格中檫取x1寫上x； 3，若d=R 則圖靈機(jī)的運(yùn)行方法是給出一個(gè)正元組 （S，x，S，x，d）的有序集合。B 1 1 0 1 B 0 1 BS0S1S2S1 S3 二、識(shí)別集合（語(yǔ)言） 定義2，設(shè)V是字母表I的子集。T=S，I，f，S0識(shí)別V*中帶x當(dāng)且僅當(dāng)：若將x 寫在帶上，T從初始位置開始運(yùn)行，則T能在一個(gè)終結(jié)狀態(tài)停機(jī)。稱T能識(shí)別V*的子集A，若x能被T識(shí)別當(dāng)且僅當(dāng)xA。 注意：1，識(shí)別xV* ，可以使用不在V中但在I中符號(hào)； 2，所謂不能識(shí)別xV*，

28、指x放在帶子上，運(yùn)行不停機(jī)或停機(jī)而不在終結(jié)狀態(tài)終結(jié)狀態(tài)是指在五元組中不是第一個(gè)的狀態(tài)。 例：求一個(gè)圖靈機(jī)，使之能識(shí)別第二位是1的二進(jìn)制串構(gòu)成的集合，即正則集合（01）|（01）* 解：從左邊非空白格開始運(yùn)行，向右移動(dòng)并判斷第二符號(hào)是否是1。若是則進(jìn)入終結(jié)狀態(tài)；若不是1則或不停止或停機(jī)于非終結(jié)狀態(tài)。該第一符用兩個(gè)五元組（S0，O，S1，0，R）或（S0，I，S1，1，R），后進(jìn)入S1 。下一步是兩個(gè)五元組（S1，O，S2，0，R）或（S1，I，S3，1，R）。由于當(dāng)?shù)诙?hào)是0時(shí)S2不應(yīng)是終結(jié)狀態(tài)，從而進(jìn)一步進(jìn)入五元組：（S2，0，S2，R），而S3定義為終結(jié)狀態(tài)。此外，空串及只有1位的串不當(dāng)識(shí)

29、別，從而加入五元組（S0，B，S2，0，R）和（S1，B，S2，0，R） 以上7個(gè)五元組產(chǎn)生了圖靈機(jī)識(shí)別完成任務(wù)。習(xí)題：求識(shí)別集合0n1n|n1的圖靈機(jī)。 用輔助符號(hào)M作為標(biāo)記可識(shí)別這種非正則集合的語(yǔ)言。令V=0，1，I=0，1，M，B。只識(shí)別V*中串，終結(jié)態(tài)為S6。用M替核串中最左邊的0與最右邊1，左右移動(dòng)，能在一個(gè)終止?fàn)顟B(tài)終止當(dāng)且僅當(dāng)：這串的構(gòu)成是一列0后跟一列相同個(gè)數(shù)1。五元組：（S0，O，S1，M，R），（S1，0，S1，0，R），（S1，1，S1，1，R），（S1，M1，S2，M，L），（S1，B，S2，B，L），（S2，1，S3，M，L），（S3，1，S3，1，L），（S3，O，S

30、4，0，L），（S3，M，S5，M，R），（S4，O，S4，0，L），（S4，M，S0，M，R），（S5，M，S6，M，R）。請(qǐng)說明每個(gè)五元組的功能且如何能識(shí)別該集合？三、計(jì)算函數(shù)： 例：構(gòu)造一個(gè)圖靈機(jī)將兩個(gè)非負(fù)整數(shù)相加。解：f（n1,n2）= n1+ n2 ， n1表示成 n1+1個(gè)1，n2表示成 n2 +1個(gè)1，元素對(duì)（ n1,n2 ）表示成n1+1個(gè)1后跟*再n2+1個(gè)1作為輸入，而輸出當(dāng)是n1+n2+1個(gè)1。以下五元組可實(shí)現(xiàn)（S0，1，S1，B，R）,（S1，*，S3，B，R),（S1，1，S2，B，R）,（S2，1，S2，1，R）,（S2，*，S3，1，R）。事實(shí)上一般的計(jì)算是用多帶

31、圖靈機(jī)實(shí)現(xiàn)的,但是多帶與單帶圖靈機(jī)可計(jì)算的函數(shù)是相同的:由圖靈機(jī)可計(jì)算的函數(shù)稱為可計(jì)算函數(shù).圖靈機(jī)有許多種變形,但是它們的計(jì)算能力是一樣的. 丘奇圖靈機(jī)論題：對(duì)于任何有效算法的問題，都存在解該問題的圖靈機(jī)。這不是定理，因?yàn)椤翱捎行Ы鉀Q的問題”無(wú)法嚴(yán)格形式化定義，而圖靈機(jī)是可以形式化定義的。第三章 計(jì)算復(fù)雜度理論計(jì)算機(jī)計(jì)算理論要解決以下三個(gè)問題： 可計(jì)算性問題； 計(jì)算復(fù)雜性問題 計(jì)算實(shí)現(xiàn)。一、問題 1， 計(jì)算復(fù)雜性基本概念 問題由兩部分組成： 條件及其中參數(shù)的一般性描述；對(duì)需求回答的問題的特征說明。 問題的例子：是對(duì)問題中參數(shù)給定具體值描述。 例，旅行商問題是指一個(gè)城市的有限系 C=C1， C2

32、， Cm和每?jī)蓚€(gè)城市間距離d（ Ci， Cj）。解是對(duì)城市的一個(gè)排序： 這里(C(1), C(2), C(m)是1,2,m的某個(gè)排序,使該排序?yàn)橐韵潞瘮?shù)取最小值:而例子:C=(C1,C2 ,C3,C4), d(C1, C2)=10, d(C1，C3)=5, d(C1,C4)=9, d(C2，C3)=6, d(C2，C4)=9, d(C3，C4)3二、算法 算法（algori thm）是指可用來(lái)求解某一問題的，適用于所有例子的，帶有一般性的過程。 算法定義：一個(gè)算法是一個(gè)有窮規(guī)則的集合，這些規(guī)則確定一個(gè)解決某一特定類型問題的運(yùn)算序列。這些規(guī)則或運(yùn)算序列滿足： 1， 有窮性：算法必須總是在執(zhí)行有窮

33、步之后結(jié)束。 2， 確定性：算法的每一個(gè)步驟必須是確切地定義的。 3， 輸入：算法有零個(gè)或多個(gè)輸入。 4， 輸出：算法有一個(gè)或多個(gè)輸出 5， 能行性：算法中的運(yùn)算操作必須是基本的或可精 確實(shí)現(xiàn)的。 程序是一種事先編制好了具有特殊功能的指令序列。 程序=數(shù)據(jù)結(jié)構(gòu)+算法。 算法的有效性決定于所需資源：運(yùn)行時(shí)間與內(nèi)存空間。 其中運(yùn)行時(shí)間一般用基本操作的次數(shù)表示。 問題大小是指一個(gè)問題的確定的例子的大小的描述它所須的信息量。 當(dāng)表示適當(dāng)時(shí)，例子大小的值當(dāng)與問題求解難度成正比。 這里適當(dāng)是指一個(gè)好的編碼策略：可解碼性與簡(jiǎn)潔性。 例：字母表 C，1，0，1，2，9 中表示一個(gè)具體的旅行商問題：“C1C2C

34、3 C4/10/5/9/6/9/3”輸入長(zhǎng)度為32，這個(gè)例子大小為32。三、多項(xiàng)式時(shí)間算法與指數(shù)時(shí)間算法 時(shí)間復(fù)雜性：對(duì)某一問題和任一可能的輸入長(zhǎng)度n，稱所給算法求解該問題的所有大小為n 的例子所需時(shí)間的最大值為該算法對(duì)輸入長(zhǎng)度n 的時(shí)間復(fù)雜度。 多項(xiàng)式時(shí)間算法：對(duì)以輸入長(zhǎng)度 n 為變量的多項(xiàng)式函數(shù) P（n），使其時(shí)間復(fù)雜性函數(shù)為 0（pcn）的算法。 指數(shù)時(shí)間算法：是指任何其時(shí)間復(fù)雜性函數(shù)不不能用多項(xiàng)式函數(shù)界定的算法。2， 問題復(fù)雜性分類判定問題：任何一個(gè)問題可以化成兩類統(tǒng)一的問題：可行性檢驗(yàn)問題和判定問題。 一個(gè)判定問題可以由所有例子的集合 D與符合問題條件的子集Y D組成。 例：旅行商問

35、題中 C=C1，CI，Cm ,Ci，CjC 之間距離d（Ci，Cj）Z+ 及界 BZ+。問題：C 中存在一個(gè)總長(zhǎng)不超過 B 的，通過所有城市的旅行路線嗎？即，是否存在 C 的序 使得 一個(gè)判定問題可以由所有例子的集合 D與符合問題條件的子集Y D組成。三、P 類問題 以確定性單帶 Turing 機(jī) DTM 為計(jì)算模型，則一個(gè)DTM 程序M ： a）帶中所用字符的一個(gè)有限集合，它應(yīng)包括輸入字符表子集和一個(gè)特別的空白符號(hào) b-。 b）一個(gè)有限狀態(tài)集Q，包括初始狀態(tài) q0 和兩個(gè)特有的停機(jī)狀態(tài)qY，qN。 C）一個(gè)轉(zhuǎn)移函數(shù):(Q-Qy,qN)QL, 當(dāng)一個(gè)帶有輸入字符表的DTM程序M接受x*M 作用

36、于輸入 x 時(shí)停機(jī)于狀態(tài) qY. 則 M 所識(shí)別的語(yǔ)言: LM=x|x*: M 接受 x 當(dāng)一個(gè)M對(duì)定義于其輸入字符表上的所有可能字符串均停機(jī)時(shí),我們才稱其為一個(gè)算法.相應(yīng)地: 稱一個(gè)DTM程序M在編碼策略e之下求解判定問題,若M對(duì)定義于其輸入字符表上所有輸入字符串均停機(jī)且LM=L,e. 時(shí)間復(fù)雜度函數(shù)：對(duì)于一個(gè)對(duì)所有輸入x*均停機(jī)的DTM程序M，定義其時(shí)間復(fù)雜性函數(shù)TM：Z+Z+ 為： TM（n）=maxm：存在一個(gè)x*，|x|=n，使得M對(duì)輸入x 的計(jì)算需要時(shí)間m 若存在一個(gè)多項(xiàng)式P，使對(duì)所有 nZ+ 有 TM(n)P(n)，則稱次序M為一個(gè)多項(xiàng)式時(shí)間DTM 程序. P類的第一類重要語(yǔ)言正

37、式定義: P=L：存在一個(gè)多項(xiàng)式時(shí)間 DTM 程序 M，使L=LM。此時(shí)不再?gòu)?qiáng)調(diào)編碼策略，因?yàn)樗鼈冎g可以是等價(jià)的。 若存在一個(gè)多項(xiàng)式P，使對(duì)所有 nZ+ 有 TM(n)P(n)，則稱次序M為一個(gè)多項(xiàng)式時(shí)間DTM 程序. 多項(xiàng)式時(shí)間可解的P類問題是在已知可解的條件下，通過 Turing 機(jī)可以達(dá)到停止?fàn)顟B(tài)qY。但是一般的問題并不知道是否可解，而且并無(wú)解法策略，而上述問題幾乎類似于多項(xiàng)式時(shí)間可驗(yàn)證問題而非可解。因?yàn)闉榱苏页鼋獾哪硞€(gè)猜測(cè)花去的時(shí)間也許不是多項(xiàng)式級(jí)的。四、NP 類問題 設(shè)計(jì)另一假想機(jī)：非確定性單帶 Turing 機(jī) NDTM，即在Turing 機(jī)模式上加一個(gè)猜想模塊，猜想頭將可以從-

38、1開始改寫格中數(shù)據(jù)，而且可以無(wú)窮地猜想，于是計(jì)算變成兩部分：猜想階段與檢驗(yàn)階段： -5 4 3 2 1 0 1 2 3 4 5 猜想模塊有限狀態(tài)控制器猜想頭讀寫頭 一般來(lái)說，對(duì)于一個(gè)輸入x，NDTM 的程序 M可能做無(wú)窮多個(gè)可能的計(jì)算，如果有一個(gè)可能計(jì)算（由猜想決定）停機(jī)于qr，則x稱 M可接受的。 如果這樣定義的 NDTM 程序 M 可接受計(jì)算的語(yǔ)言，則從 q0 到 qr所用時(shí)間為多項(xiàng)式所界，則定義了NP類語(yǔ)言： NP=L：存在一個(gè)多項(xiàng)式時(shí)間 NDTM 程序 M，使LM=L。顯然我們也可以不計(jì)編碼策略。 顯然 PNP 定理：若問題NP，則存在多項(xiàng)式P 使可以用一個(gè)時(shí)間復(fù)雜性為O(2P(n)

39、的確定性算法求解. 對(duì)于一個(gè)長(zhǎng)度為 n 的輸入,通過 A 的確定性計(jì)算的檢驗(yàn)其Kq(n)個(gè)可解猜測(cè)子符串中每一個(gè),直到停止或運(yùn)行完 q(n) 步,可以肯定判斷該輸入是否是一個(gè)可接受輸入,從而對(duì)于判“是”與“非”來(lái)說,這里的一個(gè)確定性算法. 從而每個(gè)長(zhǎng)度為 n 的可被 A接受的輸入，必存在字符集上長(zhǎng)度最當(dāng)為 q（n）的某個(gè)猜想字符串，使算法 A的檢驗(yàn)階段在不多于q(n)步內(nèi)回答“是”.從而若 |=K, 則所需考慮的可能猜測(cè)的數(shù)目最多Kq(n).這里長(zhǎng)度小于 q(n)的猜想字符串可以用 b 填充為 q(n)長(zhǎng). 證明:設(shè) A 為求解的一個(gè)多項(xiàng)式不確定算法,多項(xiàng)式 q(n)界定其復(fù)雜度.而 q 可在

40、多項(xiàng)式時(shí)間內(nèi)被計(jì)算其值 q(n),即可計(jì)算出 C1,C2 使 q(n)=C1nC2。 試圖找 NP 中一類與 P 問題有顯著不同的一類問題，從而去證明 PNP ，這就是導(dǎo)致了 NP 完全性問題 （NPC）的出現(xiàn)。 上述定理說明，在非確定性 Turing 機(jī)上時(shí)間復(fù)雜度為q(n)Kq(n)的問題相當(dāng)。直觀上認(rèn)為一定有問題是前者可解而后者不可解之問題，或人們一般認(rèn)為 P 是 NP 的真子集。 已知 PNP，但P 是 NP的真子集嗎？或者有 P=NP？這就是著名的數(shù)學(xué)難題 “P=NP？” 從而該算法的時(shí)間復(fù)雜度為q(n)K Kq(n)上界.有q(n)可被2Q所界而K 可寫成2的冪,從而存在一個(gè)多項(xiàng)式

41、P使上界寫成OC2P(w). 從語(yǔ)言L1 1*到另一語(yǔ)言 L2 2*的多項(xiàng)式變換是指滿足下面兩個(gè)條件的函數(shù) f：1* 2* ： 1， 存在計(jì)算f 的一個(gè)多項(xiàng)式時(shí)間 DTM 程序。 2，對(duì)所有 x2* ，xL1f（x） L2。一、多項(xiàng)式變換 3， NP 完全問題“NP完全的”定義: 一個(gè)語(yǔ)言 L (判定問題) 為NP 完全的(NPC),如果 LNP(NP),且對(duì)所有別的語(yǔ)言LP(判定問題NP），均有LL（ ） 從問題角度看，從判定問題 2 的多項(xiàng)式變換是函數(shù) f：D1 D2 滿足： 1， f 可由多項(xiàng)式時(shí)間算法去計(jì)算。 2， 對(duì)所有的 I D1 ，IY1 f(I)Y2 記為 L1L2 或 12

42、因此為證明一個(gè)問題是NP完全的，必須證明NP中每個(gè)問題均可多項(xiàng)式地變換到它。 可滿足性問題：給定布爾變量的一個(gè)集合 U=u1，u2，um，U 的一個(gè)真值分配是映射 t：U T，F(xiàn)，且若 t（ ui）=T，則稱 ui 取真值，否則 t（ui）=F 稱取假。定義在 U 上的一個(gè)子句ui是由一些布爾變量（或它的補(bǔ)）通過邏輯“或”而連接起來(lái)的布爾表示式。若存在對(duì)布爾變量 U 的一組真賦值，使該子句 ui 取值為真，即 ui 中至少有一個(gè)單元取真值，則稱 ui 被滿足。而子句的集合 C 是由所有包含的子句通過邏輯“與”連接組成。稱該集合是可滿足的，若存在布爾變量集之一組賦值，使 C 中的每一個(gè)子句均取真值。 但是，NP 問題完全存在嗎？1971年 Cook 證明了第一個(gè) NP 完全問題，可滿足性問題，稱為 Cook 定理。 Cook 定理：可滿足性問題是 NP 完全的。 從 Cook 開創(chuàng)性工作至今，已經(jīng)發(fā)現(xiàn)，證明了數(shù)千個(gè) NP 完全問題，并總結(jié)出一些證明方法。 二、NP 困難問題 多項(xiàng)式時(shí)間圖靈歸約（Polynomial time Turing reduction）設(shè)1和2