計算機科學與技術方法論2

1、第二章 計算學科中的科學問題智能與分布計算實驗室()1主要內(nèi)容科學問題的定義和特征計算學科各主領域的基本問題計算學科中的典型問題（非數(shù)值計算）哥尼斯堡七橋問題“梵天塔”問題P類問題與NP類問題哲學家共餐問題GoTo語句問題人工智能中的若干哲學問題（圖靈測試、西爾勒的“中文屋子”、計算機中的博弈問題） 科學問題的定義科學問題是指一定時代的科學認識主體，在已完成的科學知識和科學實踐的基礎上，提出的需要解決且有可能解決的問題。它包含一定的求解目標和應答域，但尚無確定的答案。能否在所從事的工作中提出關鍵和重要的科學問題，對我們每個人來說都是一個挑戰(zhàn)?？茖W問題的主要特征時代性：每一個時代都有它自己的科學

2、問題混沌性：渴望對新知識的追求，追求開始的時候是模糊不清的?？山鉀Q性?？勺儺愋裕耗芤隽硗饩哂锌山鉀Q性的科學問題可待解性：絕非永遠不可解決。1、離散結(jié)構(gòu)：離散結(jié)構(gòu)是計算機科學的基礎內(nèi)容。包括集合論、數(shù)理邏輯、代數(shù)系統(tǒng)、圖論和組合數(shù)學等重要內(nèi)容。強有力的數(shù)學工具“能行性” 的根本問題決定了計算機本身的結(jié)構(gòu)和它處理的對象都是離散型的。一、計算學科各主領域的基本問題(P23-P27)2、程序設計基礎包括：程序設計結(jié)構(gòu)、算法、問題求解、數(shù)據(jù)結(jié)構(gòu)等?；締栴}包括：（1）對給定的問題，如何進行有效的描述并給出算法？（2）如何正確選擇數(shù)據(jù)結(jié)構(gòu)？（3）如何進行設計、編碼、測試和調(diào)試程序？3 算法與復雜性包括：

3、算法復雜性分析、算法策略、分布式并行算法、可計算理論、 P類問題與NP類問題、自動機理論、密碼算法、幾何算法等。基本問題： 對于給定的問題類，最好的算法是什么？時間、空間復雜性分析。 訪問數(shù)據(jù)的最好方法是什么？ 算法最好和最壞情況如何？ 算法的平均性能如何？ 算法的通用性如何？算法的時間復雜度（ Time complexity ）時間復雜度：time complexity對算法運行所需要的時間的度量算法執(zhí)行的步驟數(shù)目（非時間單位秒，效率的度量）非精確的、數(shù)量級的；空間復雜度：space complexity我們常用大O表示法表示時間復雜度，注意它是某一個算法的時間復雜度。這里的“O”表示量級

4、(order) 比如說“二分檢索是 O(logn)的”,也就是說它需要“通過logn量級的步驟去檢索一個規(guī)模為n的數(shù)組”記法 O ( f(n) )表示當 n增大時，運行時間至多將以正比于 f(n)的速度增長。 例1. 交換i和j的內(nèi)容 sum=0； （一次） for(i=1;i=n;i+) （n次 ） for(j=1;j=n;j+) （n2次 ） sum+； （n2次 ）例2 a=0; b=1; for (i=1;iL1) Lim L(r)=+ r0 自相似，無窮遞歸 維數(shù)公式：Koch 雪花, N=4,S=1/3D= =1.2619log 4log (1 1/3)D= log Nlog (1

5、/s)10 智能系統(tǒng)包括約束可滿足性問題、知識表示和推理、agent、自然語言處理、機器學習與神經(jīng)網(wǎng)絡、人工智能規(guī)劃系統(tǒng)和機器人學等。11信息管理包括：信息模型和信息系統(tǒng)、數(shù)據(jù)庫系統(tǒng)數(shù)據(jù)建模、關系數(shù)據(jù)庫及設計、數(shù)據(jù)庫查詢語言、分布式數(shù)據(jù)庫、數(shù)據(jù)挖掘、信息存儲于檢索 、多媒體信息及系統(tǒng)、數(shù)字圖書館、電子商務、電子政務、ERP系統(tǒng)等。12、軟件工程軟件工程是一門關于如何有效構(gòu)建滿足用戶需求的軟件系統(tǒng)所需的理論、知識和實踐的學科。包括軟件過程、軟件需求和規(guī)格說明、軟件設計、驗證演化、軟件項目管理、軟件開發(fā)工具和環(huán)境、軟構(gòu)件、軟件可靠性等。13社會和職業(yè)問題計算學科本身基本的文化、社會背景、法律和道德

6、、計算的歷史、知識產(chǎn)權、隱私保護、計算機犯罪、經(jīng)濟問題、哲學框架等。14、科學計算包括數(shù)值分析、運籌學、模擬和仿真、高性能計算等?；締栴}：（1）如何精確地以有限的離散過程近似表示連續(xù)和無限的離散過程？（2）如何處理這種近似產(chǎn)生的錯誤？（3）給定某一類方程在某精確度水平上能以多快的速度求解？（4）如何實現(xiàn)方程的符號操作，如積分、微分以及到最小項的歸約？（5）如何把這些問題的答案包含到一個有效的、可靠的、高質(zhì)量的數(shù)學軟件包中？反映計算學科某一方面本質(zhì)特性的典型實例二、計算學科中的典型問題 （非數(shù)值計算）P27-411 哥尼斯堡(Konigsberg)七橋問題17世紀的東普魯士有一座哥尼斯堡城，城

7、中有一座奈佛夫島，普雷格爾河的兩條支流環(huán)繞其旁，并將整個城市分成北區(qū)、東區(qū)、南區(qū)和島區(qū)4個區(qū)域，全城共有7座橋?qū)?個城區(qū)相連起來。 人們常通過這7座橋到各城區(qū)游玩，于是產(chǎn)生了一個有趣的數(shù)學難題：尋找走遍這7座橋，且只許走過每座橋一次，最后又回到原出發(fā)點的路徑。該問題就是著名的“哥尼斯堡七橋問題”。1、Konigsberg 七橋問題 問題描述 L. Euler：從一點出發(fā)不重復地走遍七橋，最后又回到 原點是不可能的 一般化處理：對給定的任意一個河道圖與任意多座橋， 判定可能不可能每座橋恰好走過一次 三條判定規(guī)則（P29） 為圖論的形成奠定基礎ACBD哈密爾頓回路問題在圖論中還有一個很著名的“哈密

8、爾頓回路問題”。該問題是愛爾蘭著名學者威廉哈密爾頓爵士（W.R.Hamilton）在1859年提出的一個數(shù)學問題。其大意是：在任一給定的圖中，能不能找到這樣的路徑，即從一點出發(fā)不重復地走過所有的結(jié)點（不必通過圖中每一條邊），最后又回到原出發(fā)點。D C B A 對于前面的例子來說，如果是求哈密爾頓回路，就是遍歷A、B、C、D四個點，最后又回到原出發(fā)點。對于 “哈密爾頓回路問題”至今仍未找到滿足問題的充分必要條件。圖論的形成和發(fā)展歐拉的論文為圖論的形成奠定了基礎。圖論已廣泛地應用于計算學科運籌學信息論控制論等學科圖論已成為我們對現(xiàn)實問題進行抽象的一個強有力的數(shù)學工具。圖論在計算學科中的作用越來越大

9、，圖論本身也得到了充分的發(fā)展。相傳印度教的天神梵天在創(chuàng)造地球這一世界時，建了一座神廟，神廟里豎有三根寶石柱子，柱子由一個銅座支撐。梵天將64個直徑大小不一的金盤子，按照從大到小的順序依次套放在第一根柱子上，形成一座金塔（如圖2.3所示），即所謂的梵天塔（又稱漢諾塔）。天神讓廟里的僧侶們將第一根柱子上的64個盤子借助第二根柱子全部移到第三根柱子上，即將整個塔遷移，同時定下3條規(guī)則：2、Hanoi塔問題2、Hanoi塔問題問題: 將第一根柱子上的64盤子借助于第二根柱子全部移動第 三根柱子上。約束 : (1) 每次只能移動一個 (2) 只能在三根柱子上來回移動，不能放在它處 (3) 在移動過程中，

10、三根柱子上的盤子必須始終保持大在 下、小在上。123CBA解題過程（3個圓盤問題）123123123123123123123123算法：C語言描述hanoi(int n,char left,char middle,char right) if(n=1) move(1,one,_,three); else hanoi(n-1,left,right,middle); move(1,left,_,right); hanoi(n-1,middle,left,right); 解: 采用遞歸的思想：將一個較大的問題歸約為一個或多個子問題的求解，子問題比原問題簡單，且結(jié)構(gòu)與原問題相同。 h(n)=2h(n-

11、1)+1 =2(2h(n-2)+1)+1=22h(n-2)+2+1 =23h(n-3)+22+2+1 =2nh(0)+2n-1+ +22+2+1 =2n-1+ +22+2+1=2n-1 264-1=184467445 1次/秒，264-1/31536000(秒)=5849億年(世界末日) 264-1/1000萬次=58490年 能行問題 o(2n) P=？NP問題3、P類問題與NP類問題算法復雜性包括算法的空間以及時間兩方面的復雜性問題，梵天塔問題主要講的是算法的時間復雜性。能否空間換時間？3、P類問題與NP類問題（1）問題的引入求婚 問題求出48 770 428 433 377 171 （1

12、7位數(shù)）的一個真因子。 算法1：從2開始逐個除，一秒一個，86400 答案：223 092 827。算法2：最小的真因子不會超過9位，全民動員串行與并行，時間與空間，折衷O(10 ) 指數(shù)級 2n 旅行商（貨郎擔）問題（Traveling Salesman Problem，TSP）經(jīng)且只經(jīng)每個城市一次，回到出發(fā)點，路程(費用)最短(少)BDAC254246旅行商問題與組合爆炸問題我們?nèi)粼O城市數(shù)目為n時，那么組合路徑數(shù)則為（n1）！ 0 ( (n1) ! )順序算法和并行算法順序算法-時間復雜性大；并行算法-空間復雜性大。直覺上，順序算法解決不了的問題完全可以用并行算法來解決，是這樣嗎？（2）阿

13、爾達定律（并行）加速比的局限SP1f 1 fP對難解性問題而言，降低算法復雜度的數(shù)量級是關鍵！ 設f為求解某個問題的計算存在的必須串行執(zhí)行操作占整個計算的百分比，p為處理器的數(shù)目，Sp為并行計算機系統(tǒng)最大的加速能力，則：（3）P=？NP 將所有可以在多項式時間內(nèi)求解的問題稱為P類問題。 將所有在多項式時間內(nèi)可以驗證的問題稱為NP類問題。 P NP P=？NP 懸而未決的最大問題 NP完全問題中尋找多項式時間算法，從未成功 P NP又無法證明 NP問題族中的任何一個NP問題存在多項式時間復雜度算法時，則所有這些NP問題都是多項式時間可解的，這些問題被稱為NP完全性問題。多達數(shù)千個的NP完全性問題

14、。有代表性的有：哈密爾頓回路問題、旅行商問題（也稱貨郎擔問題）、劃分問題、帶優(yōu)先級次序的處理機調(diào)度問題、頂點覆蓋問題等。NP完全性問題例：可滿足性問題 判定一個布爾公式是否可滿足的 SAT = 是可滿足的布爾公式 庫克結(jié)論 SAT P，當且僅當 P = NPNP完全性問題 公鑰密碼系統(tǒng) RSA 加密密鑰公開，解密密鑰私有 很難從加密密鑰求其解密密鑰（NP完全問題） 例：三月二十八日早晨七點不發(fā)起總攻 計算復雜性理論應用密碼學 三月二十八日早晨七點不發(fā)起總攻4、哲學家共餐問題5個哲學家圍坐在一張圓桌旁，每個人的面前擺有一碗面條，碗的兩旁各擺有一只筷子。一個哲學專家的生活進程： (1) 思考問題

15、(2) 左手拿筷 （等待的可能） (3) 右手拿筷 （等待的可能） (4) 進餐 (5) 放右筷 (6) 放左筷 (7) 返回 (1) 問題：如何協(xié)調(diào)5人的生活進程，使得每一人最終都可進餐； 餓死例： (1) 同時拿起左手筷全等待 (2) 同時放、同時拿的循環(huán) 反應程序并發(fā)執(zhí)行時進程同步的兩個問題：死鎖(Deadlock)與饑餓(Starvation) n個進程與m個共享資源的問題 5、GoTo語句問題以及程序設計方法學任何程序的邏輯結(jié)構(gòu)都可以用3種最基本的結(jié)構(gòu)順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)來表示。GOTO語句1968年，E.W.Dijkstra：“GoTo語句是有害的”。 結(jié)論：濫用GoTo語

16、句是有害的，完全禁止也不明智。 GoTo語句問題的爭論導致程序設計方法學的產(chǎn)生。三 人工智能中的若干哲學問題圖靈測試西爾勒的“中文屋子”計算機中的博弈問題1 圖靈測試 人類思維的本質(zhì)尚未真正了解 人工智能并無實質(zhì)性 突破 如果在C、X、Y的游戲中作出的錯誤判斷與在計算機、C、Y的游戲中作出的錯誤判斷次數(shù)相同，那么，機器是能夠思維的。（非結(jié)構(gòu)，而是從功能角度上）XYC男（A）女（B）計算機提問者2、J.R.Searle 的 “中文屋子”美國哲學家約翰西爾勒（J.R.Searle）將有關人工智能的研究劃分為強人工智能（Strong Artificial Intelligence，簡稱強AI）和弱人

17、工智能（Soft Artificial Intelligence，簡稱弱AI）兩個派別。 Soft Artificial Intelligence：計算機是一個工具 Strong Artificial Intelligence：不僅是一個工具，而且具有意識。 “中文屋子”反駁強人工智能SAI觀點 Searle 真的懂中文嗎？ 形式化的計算機僅有語法，沒有語義 人在計算能力上超過機器是不現(xiàn)實的 機器永遠也不可能代替人腦3博弈樹搜索（信息科學導論 P283-286）國際象棋、西洋跳棋與圍棋、中國象棋一樣都屬于雙人完備博弈。所謂雙人完備博弈就是兩位選手對壘，輪流走步，其中一方完全知道另一方已經(jīng)走過的棋步以及未來可能的走步，對弈的結(jié)果要么是一方贏（另一方輸），要么是和局。對于任何一種雙人完備博弈，都可以用一個博弈樹（與或樹）來描述，并通過博弈樹搜索策略尋找最佳解。博弈樹類似于問題求解搜索