計(jì)算機(jī)科學(xué)與技術(shù)方法論2

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

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

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

4、(order) 比如說(shuō)“二分檢索是 O(logn)的”,也就是說(shuō)它需要“通過(guò)logn量級(jí)的步驟去檢索一個(gè)規(guī)模為n的數(shù)組”記法 O ( f(n) )表示當(dāng) n增大時(shí)，運(yùn)行時(shí)間至多將以正比于 f(n)的速度增長(zhǎng)。 例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 自相似，無(wú)窮遞歸 維數(shù)公式：Koch 雪花, N=4,S=1/3D= =1.2619log 4log (1 1/3)D= log Nlog (1

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

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

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

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

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

10、三根柱子上的盤子必須始終保持大在 下、小在上。123CBA解題過(guò)程（3個(gè)圓盤問(wèn)題）123123123123123123123123算法：C語(yǔ)言描述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); 解: 采用遞歸的思想：將一個(gè)較大的問(wèn)題歸約為一個(gè)或多個(gè)子問(wèn)題的求解，子問(wèn)題比原問(wèn)題簡(jiǎn)單，且結(jié)構(gòu)與原問(wèn)題相同。 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萬(wàn)次=58490年 能行問(wèn)題 o(2n) P=？NP問(wèn)題3、P類問(wèn)題與NP類問(wèn)題算法復(fù)雜性包括算法的空間以及時(shí)間兩方面的復(fù)雜性問(wèn)題，梵天塔問(wèn)題主要講的是算法的時(shí)間復(fù)雜性。能否空間換時(shí)間？3、P類問(wèn)題與NP類問(wèn)題（1）問(wèn)題的引入求婚 問(wèn)題求出48 770 428 433 377 171 （1

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

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

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

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

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

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