計(jì)算理論與計(jì)算模型ppt課件.ppt

《計(jì)算理論與計(jì)算模型ppt課件.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、計(jì)算思維與計(jì)算機(jī)文化第二章計(jì)算理論與計(jì)算模型計(jì)算理論與計(jì)算模型主要內(nèi)容2.1計(jì)算的幾種視角2.2計(jì)算理論2.3計(jì)算模型計(jì)算機(jī)能夠解決所有的問題嗎？計(jì)算機(jī)能夠解決什么樣的問題？什么問題是可計(jì)算的？如何判定一個(gè)問題是可計(jì)算的？2.1計(jì)算的幾種視角計(jì)數(shù)與計(jì)算中國古代計(jì)算工具：最初的計(jì)算工具——手指digit——手指，整數(shù)易得的計(jì)數(shù)工具——石頭、木棍、繩結(jié)calculus——計(jì)算，微積分，結(jié)石公園前四世紀(jì)戰(zhàn)國時(shí)期，《周易·系辭下》上古結(jié)繩而治，后世圣人易之以書契5算籌：中國古代普遍采用的一種計(jì)算工具。不僅可以計(jì)數(shù)，還可以進(jìn)行加、減、乘、除等算數(shù)運(yùn)算。出土的西漢時(shí)

2、期的算籌6算籌的擺放有兩種方式，橫式和縱式。豎橫1500年前的《孫子算經(jīng)》“凡算之法，先識其位，一縱十橫，百立千僵，千十相望，萬百相當(dāng)?！奔礄M式和縱式要間隔排放。7比如計(jì)算3748+289從左向右算=40378比如計(jì)算4231-789從左向右算=3442南北朝時(shí)期的數(shù)學(xué)家祖沖之借助算籌，將圓周率的值計(jì)算到小數(shù)點(diǎn)后第7位。之后國際上又進(jìn)行了許多有效的計(jì)算，人工計(jì)算達(dá)到了808位。1949年美國科學(xué)家，利用ENIAC將計(jì)算到2037位。10算籌存在著縱橫記數(shù)、占用地方面積大、運(yùn)籌的數(shù)字較大容易出現(xiàn)失誤等缺點(diǎn)。唐朝后，另一種計(jì)算工具走上了歷史舞臺，這就是算盤。

3、算盤用帶孔的珠子代替了竹棍，有檔位限制，不易亂，又有計(jì)算口訣，學(xué)的快，準(zhǔn)確性高，所以很快就普及了。2.邏輯與計(jì)算邏輯是研究推理的學(xué)科，研究形式體系，作為其組成部分的命題演算和謂詞演算等在計(jì)算機(jī)學(xué)科中作用巨大，影響很深。推理與計(jì)算是相通的，數(shù)理邏輯的許多研究成果都可以用于計(jì)算科學(xué)，數(shù)理邏輯給出的思維過程可以通過計(jì)算機(jī)來實(shí)現(xiàn)。3.算法與計(jì)算問題求解是計(jì)算，求解算法的每一步也是計(jì)算，計(jì)算的過程是算法，算法又由計(jì)算步驟組成。算法是計(jì)算機(jī)科學(xué)中最重要的內(nèi)容，計(jì)算機(jī)科學(xué)就是算法科學(xué)。2.2計(jì)算理論1.可計(jì)算性理論（ComputabilityTheory）可計(jì)算理論是

4、研究計(jì)算的可行性和算法的理論，又稱算法理論。（1）可計(jì)算理論的發(fā)展“計(jì)算”是解決問題的最基本手段，計(jì)算的過程就是執(zhí)行算法的過程。隨著計(jì)算機(jī)科學(xué)與技術(shù)的發(fā)展，“計(jì)算”的內(nèi)涵與外延均發(fā)生了巨大的變化，涉及到了社會發(fā)展的各個(gè)領(lǐng)域。“計(jì)算”離不開計(jì)算的規(guī)則與方法（算法），正確的計(jì)算規(guī)則建立與可行的計(jì)算方法設(shè)計(jì)是正確地解決問題的關(guān)鍵所在?？捎?jì)算性理論的研究分為兩個(gè)方面：通過建立計(jì)算的數(shù)學(xué)模型，研究哪些算法問題是可計(jì)算的（可行的），哪些算法問題是不可計(jì)算的（不可行的）。另一主要內(nèi)容就是計(jì)算復(fù)雜性理論，研究一個(gè)問題怎樣才能被有效的解決（算法的復(fù)雜度）。在20世紀(jì)以前，

5、人們普遍認(rèn)為，所有的問題都是有算法的，人們關(guān)于計(jì)算問題的研究就是找出解決各類問題的算法來。隨著時(shí)間的遷移，人們發(fā)現(xiàn)有許多問題雖然經(jīng)過長期的研究仍然找不到算法，于是人們開始懷疑，是否對有些問題來說根本就不存在算法，即它們是不可計(jì)算的。那么什么是可計(jì)算，什么又是不可計(jì)算的呢？（2）可計(jì)算性定義如果存在一個(gè)機(jī)械過程，對給定的一個(gè)輸入，能在有限步驟內(nèi)給出答案，那么這個(gè)問題就是可計(jì)算性的。計(jì)算機(jī)科學(xué)的定義：凡可用某種程序設(shè)計(jì)語言描述的問題都是可計(jì)算性的。圖靈通過精確地描述給出了“可計(jì)算性”的形式定義，他提出一類直觀而合理的抽象機(jī)，就是圖靈機(jī)。（3）計(jì)算性理論的主要

6、內(nèi)容到了20世紀(jì)30年代，一些著名的數(shù)學(xué)家和邏輯學(xué)家從不同的角度分別給出了“可計(jì)算性”概念的確切定義，為計(jì)算科學(xué)的研究與發(fā)展奠定了重要基礎(chǔ)。其中包括丘奇的λ-轉(zhuǎn)換演算，哥德爾的一般遞歸性概念，圖靈（Turing）的可計(jì)算性概念等。經(jīng)證明，這些形式上完全不同的概念都是等價(jià)的，而其中圖靈提出來的“圖靈機(jī)”模型直觀形象，于是很快得到了大家的普遍接受。圖靈機(jī)圖靈機(jī)是一種在理論計(jì)算機(jī)科學(xué)中廣泛采用的抽象計(jì)算機(jī)，由阿蘭.圖靈1936年提出的。核心：可用一個(gè)圖靈機(jī)來計(jì)算其值的函數(shù)是可計(jì)算函數(shù)，找不到圖靈機(jī)來計(jì)算其值的函數(shù)是不可計(jì)算函數(shù)?？梢宰C明，存在一個(gè)圖靈機(jī)U，它可

7、以模擬任何其他的圖靈機(jī).這就是通用圖靈機(jī)，這正是后來存儲程序的通用數(shù)字計(jì)算機(jī)的理論模型。正是因?yàn)閳D靈奠定的理論基礎(chǔ)，人們才有可能發(fā)明20世紀(jì)以來甚至是人類有史以來最偉大的發(fā)明：計(jì)算機(jī)。1912年出生，演算能力突出1931年，進(jìn)劍橋大學(xué)學(xué)數(shù)學(xué)1936年，提出圖靈機(jī)模型1938年，獲普靈斯頓大學(xué)博士學(xué)位1939年，英國外交部通信處1950年，發(fā)表論文“計(jì)算機(jī)和智能”，提出圖靈測試1951年，成為英皇家學(xué)會院士1954年，不幸去世圖靈機(jī)有以下四個(gè)部分組成：無限長的紙帶可移動(dòng)的讀寫頭狀態(tài)存儲器(開始結(jié)束)規(guī)則表（程序）圖靈用機(jī)器來模擬人用紙筆進(jìn)行數(shù)學(xué)運(yùn)算的過程，

8、兩種簡單的動(dòng)作：在紙上寫上或擦除某個(gè)符號；把注意力從紙的一個(gè)位置移動(dòng)到另一個(gè)位置