大學計算機課件：第七章 關于計算

大學計算機基礎第一章基于計算機的問題求解

第二章計算機信息數(shù)字化基礎

第三章計算機的工作原理與硬件體系結構第四章計算機軟件平臺第五章計算機網(wǎng)絡平臺第六章數(shù)據(jù)處理與數(shù)據(jù)庫第七章關于計算第八章算法與程序設計第九章實用軟件

第十章計算機科學前沿技術

7.1計算的本質(zhì)

7.2關于計算學科

7.3普適計算及其應用

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

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

設m和n是兩個正整數(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)閞，重復上述步驟.//變換參7.1計算的本質(zhì)7.1.3計算復雜性1.三大數(shù)學難題世界近代三大數(shù)學難題即“三大數(shù)學猜想”費馬猜想、四色猜想和哥德巴赫猜想。以上三個問題的共同點就是：題面簡單易懂，但內(nèi)涵深邃無比，困擾了一代代的數(shù)學家。這就是計算復雜性的問題。7.1計算的本質(zhì)7.1.3計算復雜性2.可計算問題的可解性對于數(shù)學和計算機應用學科來說，平常我們關心的是計算機需要花多長時間去解決一個問題，即：可計算且能在有限時間有解。換言之，這個問題有多復雜？可計算未必能有有完全解。因為這里的可計算問題僅僅是來自于理論思維上的可計算，圖靈機模型中的“有限步驟”是一個過于寬松的限制，它甚至包括了需要計算好幾百年才能完成的那些問題。實際上對可計算問題可否實際計算還需要判斷其復雜性。如果一個問題的最好算法需要100年才能夠完成計算過程，那你認為這個問題是可計算的嗎？為什么？？7.1計算的本質(zhì)7.1.3計算復雜性3.計算復雜性20世紀70年代，庫克（StephenCook）將可計算問題進一步分為實際可解和實際不可解：一個問題是實際可計算的當且僅當它能夠在圖靈機上經(jīng)過多項式步驟得到正確結果。這就是著名的庫克論題，它界定了計算機的實際計算能力限度。超過這個限度的問題一般被認為是難解問題。其中一個典型的難解問題示例是漢諾塔問題。

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

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

7.1計算的本質(zhì)

7.2關于計算學科

7.3普適計算及其應用

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

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

7.1計算的本質(zhì)

7.2關于計算學科

7.3普適計算及其應用

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