大學(xué)計(jì)算機(jī)課件：第七章 關(guān)于計(jì)算

大學(xué)計(jì)算機(jī)基礎(chǔ)第一章基于計(jì)算機(jī)的問題求解

第二章計(jì)算機(jī)信息數(shù)字化基礎(chǔ)

第三章計(jì)算機(jī)的工作原理與硬件體系結(jié)構(gòu)第四章計(jì)算機(jī)軟件平臺(tái)第五章計(jì)算機(jī)網(wǎng)絡(luò)平臺(tái)第六章數(shù)據(jù)處理與數(shù)據(jù)庫第七章關(guān)于計(jì)算第八章算法與程序設(shè)計(jì)第九章實(shí)用軟件

第十章計(jì)算機(jī)科學(xué)前沿技術(shù)

7.1計(jì)算的本質(zhì)

7.2關(guān)于計(jì)算學(xué)科

7.3普適計(jì)算及其應(yīng)用

第7章關(guān)于計(jì)算7.1計(jì)算的本質(zhì)7.1.1什么是計(jì)算1.關(guān)于計(jì)算

計(jì)算是構(gòu)建在一套公理體系上的、不斷向上演化的規(guī)則。比如我們?nèi)粘５乃膭t運(yùn)算，它的公理體系應(yīng)該是由三部分組成：數(shù)字、基本運(yùn)算符、組合規(guī)則。那么，抽象地描述計(jì)算應(yīng)該是：基于規(guī)則的符號(hào)集合的變換過程，即：從一個(gè)按規(guī)則組織的符號(hào)集合開始，再按照既定的規(guī)則一步步地改變這些符號(hào)集合，經(jīng)過有限步驟之后得到一個(gè)確定的結(jié)果。計(jì)算思維是人的，而不是計(jì)算機(jī)的思維7.1計(jì)算的本質(zhì)7.1.1什么是計(jì)算2.計(jì)算的分類1.計(jì)算理論的研究，側(cè)重于從數(shù)學(xué)角度證明表達(dá)能力和正確性，比較典型的圖靈機(jī)、lambda演算、pi演算這些都屬于這個(gè)范疇；2.計(jì)算模型的研究，側(cè)重于對(duì)真實(shí)系統(tǒng)的建模和刻畫，比如馮諾伊曼模型、BSP模型、LogP模型等等。在計(jì)算這個(gè)問題上的兩種范式7.1計(jì)算的本質(zhì)7.1.1什么是計(jì)算3.計(jì)算的本質(zhì)以計(jì)算機(jī)下棋為例來說明：一個(gè)簡單的井子棋盤如圖7-1所示，計(jì)算機(jī)的計(jì)算主要是建立在一個(gè)狀態(tài)空間樹(博奕樹)的搜索方式上。圖7-1井子棋示意圖圖7-2計(jì)算解釋器7.1計(jì)算的本質(zhì)7.1.1什么是計(jì)算3.計(jì)算的本質(zhì)不同的解釋器對(duì)應(yīng)著不同的計(jì)算模型，比如我們常說的符號(hào)計(jì)算和數(shù)值計(jì)算，其實(shí)就是指我們輸入的數(shù)據(jù)是數(shù)值或是符號(hào)，然后各自對(duì)應(yīng)一個(gè)自己的解釋器，通過不同的計(jì)算模型得出各自需要的結(jié)果。它們是不同的計(jì)算模型，但是本質(zhì)都是相同的：計(jì)算過程符號(hào)化。計(jì)算的本質(zhì)就是通過演化產(chǎn)生新的信息7.1計(jì)算的本質(zhì)7.1.2可計(jì)算與不可計(jì)算1.什么問題不可計(jì)算圖靈論題一個(gè)可計(jì)算問題是“當(dāng)且僅當(dāng)它在圖靈機(jī)上經(jīng)過有限步驟之后可以得到正確的結(jié)果”根據(jù)這一論題，通常人們把所面臨的問題分為可計(jì)算問題與不可計(jì)算問題兩大類7.1計(jì)算的本質(zhì)7.1.2可計(jì)算與不可計(jì)算1.什么問題不可計(jì)算通常人們把所面臨的問題分為可計(jì)算問題與不可計(jì)算問題兩大類。那么什么問題不可計(jì)算？例如，一直被關(guān)注的圖靈“停機(jī)問題”就是不可計(jì)算的，因?yàn)樗麩o法用數(shù)學(xué)的方式證明，這是不可計(jì)算的典型問題。事實(shí)上，如果該問題可計(jì)算，那么編譯程序就可以在運(yùn)行程序之前判斷該程序是否存在死循環(huán)。而實(shí)際中死循環(huán)程序和一個(gè)只是“運(yùn)行很慢”的程序是無法得以明確區(qū)分的。證明一個(gè)問題不可計(jì)算：證明它如果可以計(jì)算，那么停機(jī)問題就可以計(jì)算7.1計(jì)算的本質(zhì)7.1.2可計(jì)算與不可計(jì)算2.問題的可計(jì)算判斷無論是數(shù)學(xué)還是工程，解決問題的過程就是問題狀態(tài)發(fā)生變化的過程。如果我們以參數(shù)形式來描述問題狀態(tài)，那么解決問題的過程就可以看作是一個(gè)參數(shù)變化的過程，如表7-1所示。這個(gè)過程中如果輸入?yún)?shù)和輸出參數(shù)的對(duì)應(yīng)關(guān)系是明確的，則說明這個(gè)過程是能行的，也就是說這個(gè)問題是可計(jì)算的。過程時(shí)間問題狀態(tài)參數(shù)形式開始初始狀態(tài)輸入?yún)?shù)結(jié)束結(jié)果狀態(tài)輸出結(jié)果表7-1解決問題的參數(shù)變化過程7.1計(jì)算的本質(zhì)7.1.2可計(jì)算與不可計(jì)算2.問題的可計(jì)算判斷例7-1

設(shè)m和n是兩個(gè)正整數(shù)，且m>n。求m和n的最大公因子的歐幾里得算法，可以通過下列過程表示:步驟1：以n除m得余數(shù)r.//求余數(shù)步驟2.若r=0,則輸出答案n，過程終止;否則轉(zhuǎn)到步驟3.//判斷余數(shù)是否為0步驟3.把m的值變?yōu)閚,n的值變?yōu)閞，重復(fù)上述步驟.//變換參7.1計(jì)算的本質(zhì)7.1.3計(jì)算復(fù)雜性1.三大數(shù)學(xué)難題世界近代三大數(shù)學(xué)難題即“三大數(shù)學(xué)猜想”費(fèi)馬猜想、四色猜想和哥德巴赫猜想。以上三個(gè)問題的共同點(diǎn)就是：題面簡單易懂，但內(nèi)涵深邃無比，困擾了一代代的數(shù)學(xué)家。這就是計(jì)算復(fù)雜性的問題。7.1計(jì)算的本質(zhì)7.1.3計(jì)算復(fù)雜性2.可計(jì)算問題的可解性對(duì)于數(shù)學(xué)和計(jì)算機(jī)應(yīng)用學(xué)科來說，平常我們關(guān)心的是計(jì)算機(jī)需要花多長時(shí)間去解決一個(gè)問題，即：可計(jì)算且能在有限時(shí)間有解。換言之，這個(gè)問題有多復(fù)雜？可計(jì)算未必能有有完全解。因?yàn)檫@里的可計(jì)算問題僅僅是來自于理論思維上的可計(jì)算，圖靈機(jī)模型中的“有限步驟”是一個(gè)過于寬松的限制，它甚至包括了需要計(jì)算好幾百年才能完成的那些問題。實(shí)際上對(duì)可計(jì)算問題可否實(shí)際計(jì)算還需要判斷其復(fù)雜性。如果一個(gè)問題的最好算法需要100年才能夠完成計(jì)算過程，那你認(rèn)為這個(gè)問題是可計(jì)算的嗎？為什么？？7.1計(jì)算的本質(zhì)7.1.3計(jì)算復(fù)雜性3.計(jì)算復(fù)雜性20世紀(jì)70年代，庫克（StephenCook）將可計(jì)算問題進(jìn)一步分為實(shí)際可解和實(shí)際不可解：一個(gè)問題是實(shí)際可計(jì)算的當(dāng)且僅當(dāng)它能夠在圖靈機(jī)上經(jīng)過多項(xiàng)式步驟得到正確結(jié)果。這就是著名的庫克論題，它界定了計(jì)算機(jī)的實(shí)際計(jì)算能力限度。超過這個(gè)限度的問題一般被認(rèn)為是難解問題。其中一個(gè)典型的難解問題示例是漢諾塔問題。

圖7-3漢諾塔問題7.1計(jì)算的本質(zhì)[練習(xí)與思考7-1]

嘗試設(shè)計(jì)一個(gè)計(jì)算過程，確定你今年的年齡是否是素?cái)?shù)?？紤]一下你的解決方法的效率。這個(gè)問題是一個(gè)難解的問題嗎？為什么？

7.1計(jì)算的本質(zhì)

7.2關(guān)于計(jì)算學(xué)科

7.3普適計(jì)算及其應(yīng)用

第7章關(guān)于計(jì)算7.2關(guān)于計(jì)算學(xué)科7.2.1計(jì)算學(xué)科的根本問題凡是與“能行性”有關(guān)的討論，所處理的大都是離散型問題，即很難處理連續(xù)型對(duì)象的問題。能行性這個(gè)計(jì)算學(xué)科的根本問題，決定了計(jì)算機(jī)本身的結(jié)構(gòu)和它處理的對(duì)象都是離散型的。甚至許多連續(xù)型的問題也必須在轉(zhuǎn)化為離散型問題以后才能被計(jì)算機(jī)處理。例如計(jì)算定積分就是把它變成離散量再用分段求和的方法來處理的。計(jì)算學(xué)科的根本問題討論的是“能行性”的相關(guān)內(nèi)容。7.2關(guān)于計(jì)算學(xué)科7.2.2計(jì)算學(xué)科與計(jì)算機(jī)學(xué)科的區(qū)別傳統(tǒng)的計(jì)算機(jī)學(xué)科是指與計(jì)算機(jī)相關(guān)的科學(xué)與技術(shù)，是研究計(jì)算機(jī)的設(shè)計(jì)、制造，以及用其進(jìn)行信息獲取、表示、存儲(chǔ)、處理控制等的理論、原則、方法和技術(shù)的學(xué)科，應(yīng)該包括科學(xué)和技術(shù)兩方面。計(jì)算機(jī)科學(xué)側(cè)重研究現(xiàn)象、揭示規(guī)律；而計(jì)算機(jī)技術(shù)則側(cè)重于研制計(jì)算機(jī)以及研究使用計(jì)算機(jī)進(jìn)行處理的方法和手段。7.2關(guān)于計(jì)算學(xué)科7.2.3計(jì)算學(xué)科環(huán)境—理論、抽象與設(shè)計(jì)1.理論特征化研究的對(duì)象（定義）；假設(shè)它們之間可能的聯(lián)系（定理）；判斷它們聯(lián)系的真實(shí)性（證據(jù)）；解釋結(jié)果。理論過程發(fā)展的四個(gè)步驟7.2關(guān)于計(jì)算學(xué)科7.2.3計(jì)算學(xué)科環(huán)境—理論、抽象與設(shè)計(jì)2.抽象特征化研究的對(duì)象（定義）；假設(shè)它們之間可能的聯(lián)系（定理）；判斷它們聯(lián)系的真實(shí)性（證據(jù)）；解釋結(jié)果。理論過程發(fā)展的四個(gè)步驟7.2關(guān)于計(jì)算學(xué)科7.2.3計(jì)算學(xué)科環(huán)境—理論、抽象與設(shè)計(jì)3.設(shè)計(jì)方法?陳述需求；?建立規(guī)格陳述說明；?設(shè)計(jì)構(gòu)建系統(tǒng)；?對(duì)系統(tǒng)的測(cè)試與分析系統(tǒng)。設(shè)計(jì)方法的四個(gè)步驟7.2關(guān)于計(jì)算學(xué)科[練習(xí)與思考7-2]

1)請(qǐng)查找一下你所學(xué)的專業(yè)課中與計(jì)算機(jī)學(xué)科相關(guān)的課程有哪些？具體在什么方面會(huì)用到？用計(jì)算、程序還是軟件？舉例說明。2)請(qǐng)查找一下國外在你專業(yè)方面排名前十名的高校中，他們?cè)谡n程設(shè)置上，就計(jì)算機(jī)科學(xué)與你專業(yè)的融合方面有哪些不同？說說自己的認(rèn)識(shí)。

7.1計(jì)算的本質(zhì)

7.2關(guān)于計(jì)算學(xué)科

7.3普適計(jì)算及其應(yīng)用

第7章關(guān)于計(jì)算7.3普適計(jì)算及其應(yīng)用7.3.1普適計(jì)算的特點(diǎn)普適計(jì)算的創(chuàng)始人MarkWeiser說：“只有當(dāng)機(jī)器進(jìn)入人們生活環(huán)境而不是強(qiáng)迫人們進(jìn)入機(jī)器世界時(shí)，機(jī)器的使用才能像林中漫步一樣新鮮有趣。”所以普適計(jì)算追求的是：人們能夠在任何時(shí)間、任何地點(diǎn)、以任何方式進(jìn)行信息的獲取與處理。7.3普適計(jì)算及其應(yīng)用7.3.2普適計(jì)算的研究內(nèi)容普適計(jì)算需要從多個(gè)方面進(jìn)行突破研究，最終構(gòu)建一個(gè)普適計(jì)算的體系結(jié)構(gòu)。這些方面包括：?普適計(jì)算設(shè)備。?普適網(wǎng)絡(luò)。?系統(tǒng)軟件。?人機(jī)交互和覺察上下文。7.3普適計(jì)算及其應(yīng)用7.3.3一個(gè)普適計(jì)算應(yīng)用實(shí)例在美國華盛頓湖的東岸，有一幢名為Bighouse的大房子，又被稱作