Chapter1信息與計算科學(xué)

1、計算科學(xué)導(dǎo)論華僑大學(xué)計算機科學(xué)系教授陳鍛生 博士課程目標(biāo)與主要內(nèi)容課程目標(biāo)與主要內(nèi)容課程目標(biāo)課程目標(biāo): n理解理解計算計算在在問題求解問題求解中所能起的作用；中所能起的作用；n接觸信息技術(shù)的基礎(chǔ)知識，接觸信息技術(shù)的基礎(chǔ)知識，n培養(yǎng)學(xué)習(xí)計算機及計算思維的專業(yè)技能的興趣，包括動手編程，為培養(yǎng)學(xué)習(xí)計算機及計算思維的專業(yè)技能的興趣，包括動手編程，為深入學(xué)習(xí)計算機專業(yè)課程打下良好基礎(chǔ)。深入學(xué)習(xí)計算機專業(yè)課程打下良好基礎(chǔ)。主要內(nèi)容主要內(nèi)容n信息與計算科學(xué)信息與計算科學(xué)n計算機系統(tǒng)計算機系統(tǒng)n多媒體技術(shù)基礎(chǔ)多媒體技術(shù)基礎(chǔ)n程序數(shù)據(jù)的結(jié)構(gòu)、組織與管理程序數(shù)據(jù)的結(jié)構(gòu)、組織與管理n數(shù)據(jù)庫技術(shù)基礎(chǔ)數(shù)據(jù)庫技術(shù)基礎(chǔ)n計

2、算機網(wǎng)絡(luò)與應(yīng)用計算機網(wǎng)絡(luò)與應(yīng)用n信息系統(tǒng)安全與社會責(zé)任信息系統(tǒng)安全與社會責(zé)任n大部分教學(xué)材料在書上，n有的相關(guān)解釋在課堂，而不在書上主要參考資源:n大學(xué)信息技術(shù)基礎(chǔ)省計算機教學(xué)指導(dǎo)委員會n計算機科學(xué)引論（影印版）（含CD-ROM光盤一張）. （美）奧利里編著. 高等教育出版社。￥39，可當(dāng)做專業(yè)英語學(xué)nZelle, John. Python Programming: An Introduction to Computer Science. Wilsonville, OR: Franklin, Beedle & Associates, 2003. MITnWebnhttp:/ 第一章信息

3、與計算科學(xué)信息與計算科學(xué)n本章要點本章要點探索信息的真諦探索信息的真諦信息技術(shù)與信息科學(xué)信息技術(shù)與信息科學(xué)計算與計算科學(xué)計算與計算科學(xué)計算機的信息表示與編碼計算機的信息表示與編碼計算機的邏輯運算與邏輯門電路計算機的邏輯運算與邏輯門電路1.1 1.1 探索信息的真諦探索信息的真諦什么是信息 ? ? 現(xiàn)代“信息”的概念，已經(jīng)與半導(dǎo)體技術(shù)、微電子技術(shù)、計算機技術(shù)、通訊技術(shù)、網(wǎng)絡(luò)技術(shù)、多媒體技術(shù)、信息服務(wù)業(yè)、信息產(chǎn)業(yè)、信息經(jīng)濟、信息化社會、信息管理、信息論等含義緊密地聯(lián)系在一起。維納(N. Wiener), 1894年11月26日生于密蘇里州的哥倫比亞，1964年3月18日去世。美國數(shù)學(xué)家，控制論的創(chuàng)

4、始人。“信息信息就是就是差異差異”,是是我們在我們在適應(yīng)外部世界，并使這種適適應(yīng)外部世界，并使這種適應(yīng)反作用于外部世界的過程應(yīng)反作用于外部世界的過程中，同外部世界進行交換的中，同外部世界進行交換的內(nèi)容的名稱。內(nèi)容的名稱。要有效的生活要有效的生活,就必須有足夠的信息就必須有足夠的信息.1.1 探索信息的真諦香農(nóng)香農(nóng)（C. E. Shannon) 1916年4月30日出生于美國密歇根州，2001年2月26日去世。美國數(shù)學(xué)家、信息論的創(chuàng)始人。信息信息是能夠減少或消除不確定性的東西。(1948)信息是有秩序的量度，是人們對事物了解的不確定性的消除或減少。熵返回目錄返回目錄香農(nóng)的研究成果標(biāo)志著信息論（香

5、農(nóng)的研究成果標(biāo)志著信息論（Information Information TheoryTheory）的誕生。）的誕生。 信息論的三個發(fā)展階段：信息論的三個發(fā)展階段：階段階段意義意義研究重點研究重點狹義信息論狹義信息論基礎(chǔ)基礎(chǔ)用數(shù)學(xué)方法研究信息，提用數(shù)學(xué)方法研究信息，提出通信模型出通信模型一般信息論一般信息論發(fā)展發(fā)展注重信號被噪聲干擾時的注重信號被噪聲干擾時的處理問題處理問題廣義信息論廣義信息論豐富豐富拓展拓展注重信息的內(nèi)容，研究范注重信息的內(nèi)容，研究范圍遠遠超出通信領(lǐng)域圍遠遠超出通信領(lǐng)域香農(nóng)對信息的定義香農(nóng)對信息的定義 信息是有秩序的量度，是人們對事物了解信息是有秩序的量度，是人們對事物了解的

6、不確定性的消除或減少。信息是對組織程度的不確定性的消除或減少。信息是對組織程度的一種測度，信息能使物質(zhì)系統(tǒng)有序性增強，的一種測度，信息能使物質(zhì)系統(tǒng)有序性增強，減少破壞、混亂和噪音。減少破壞、混亂和噪音。 通信系統(tǒng)模型：通信系統(tǒng)模型：信源信源信道信道編碼編碼信宿信宿解碼解碼信息信息信息信息信號信號信號信號干擾干擾信道：在物理線路上信道：在物理線路上劃分的邏輯通道。劃分的邏輯通道。香農(nóng)將香農(nóng)將“熵熵”的概念引入信息領(lǐng)域。一的概念引入信息領(lǐng)域。一個系統(tǒng)的熵就是它的無組織程度的度量。而個系統(tǒng)的熵就是它的無組織程度的度量。而一個系統(tǒng)中的一個系統(tǒng)中的信息量是它的組織化程度的度信息量是它的組織化程度的度量量

7、，這說明信息與熵恰好是一個相反的量，這說明信息與熵恰好是一個相反的量，信息是負熵。信息是負熵。信息的度量信息的度量l 自信息量及其計算自信息量及其計算若某若某事件事件的基本空間可能出現(xiàn)的元素分別為的基本空間可能出現(xiàn)的元素分別為x x1 1，x x2 2x xm m；且每一個可能值的概率為：；且每一個可能值的概率為： P P（X= xX= xi i）p p i i= =1,2,1,2,m,m 則定義一個隨機事件則定義一個隨機事件x x所含的信息量稱為所含的信息量稱為x x的自信的自信息量：息量：I I( (x x) )loglog（1 1/ /p p( (x x) )）log plog p( (

8、x x) ) 其中其中I I( (x x) )代表代表x x的自信息量，的自信息量，p p( (x x) )為事件為事件x x出出現(xiàn)的概率現(xiàn)的概率, ,當(dāng)?shù)讛?shù)為當(dāng)?shù)讛?shù)為2 2時，信息的計量單位為比特時，信息的計量單位為比特（bitbit）。）。 n 事件的分類事件的分類n 必然事件必然事件：在一定條件下必然要發(fā)生的事件：在一定條件下必然要發(fā)生的事件 如如: :星期一過后是星期二星期一過后是星期二 ，其發(fā)生的概率為，其發(fā)生的概率為1 1；n 不可能事件不可能事件：在一定條件下必然不會發(fā)生的事：在一定條件下必然不會發(fā)生的事件件 如如: :太陽從西邊升起太陽從西邊升起 ，其發(fā)生的概率為，其發(fā)生的概率

9、為0 0；n 隨機事件隨機事件：在相同條件下，可能發(fā)生也可能不：在相同條件下，可能發(fā)生也可能不發(fā)生的事件，其概率介于發(fā)生的事件，其概率介于0 0到到1 1之間。之間。例例1 1：假設(shè)我們想由甲地告訴乙地關(guān)于甲地的：假設(shè)我們想由甲地告訴乙地關(guān)于甲地的狀態(tài)，如甲地共有狀態(tài)，如甲地共有8 8種狀態(tài)，每種狀態(tài)發(fā)生的種狀態(tài)，每種狀態(tài)發(fā)生的概率是相等的，即概率是相等的，即1/81/8。如果甲告訴乙，甲處。如果甲告訴乙，甲處于第于第i i種狀態(tài)，這時甲傳給乙的信息量是多少？種狀態(tài)，這時甲傳給乙的信息量是多少？信息量信息量 I I-log-log2 2(1/8)(1/8)3 (bit)3 (bit)l信息熵及

10、其計算信息熵及其計算 信息熵：定義平均信息量來作為信息總體的信息熵：定義平均信息量來作為信息總體的測度。測度。設(shè)設(shè)X X為一離散隨機變量，在集合為一離散隨機變量，在集合 x x1 1，x x2 2x xn n 中取值，其概率分布為中取值，其概率分布為 P X= xP X= xi i p pi i i=1,2, i=1,2,n ,n 則定義則定義: :稱稱H(X)H(X)為離散變量為離散變量X X的信息熵。的信息熵。 niiiniiippppXH11log1log)(11 niip例例2 2：某信源有：某信源有8 8種相互獨立的狀態(tài)，其發(fā)生種相互獨立的狀態(tài)，其發(fā)生概率分別是概率分別是1/4,0,

11、0,1/4,0,0,0,1/2,1/4,0,0,1/4,0,0,0,1/2,這時信這時信源傳給信宿的信息熵是多少？源傳給信宿的信息熵是多少？信息熵信息熵 )21(21)41(41)41(41222LogLogLogH = 1.5(bit)= 1.5(bit)香農(nóng)信息論的局限性香農(nóng)信息論的局限性香農(nóng)對信息的定義的出發(fā)點是假定事香農(nóng)對信息的定義的出發(fā)點是假定事物狀態(tài)可以用一個以經(jīng)典集合論為基礎(chǔ)的物狀態(tài)可以用一個以經(jīng)典集合論為基礎(chǔ)的概率模型來描述。然而實際存在的某些事概率模型來描述。然而實際存在的某些事物運動狀態(tài)要尋找一個合適的概率模型往物運動狀態(tài)要尋找一個合適的概率模型往往是非常困難的。這個定義和

12、度量缺少考往是非常困難的。這個定義和度量缺少考慮收信者的主觀性和信息的具體內(nèi)容。慮收信者的主觀性和信息的具體內(nèi)容。數(shù)據(jù)、消息、信號與信息的區(qū)別數(shù)據(jù)、消息、信號與信息的區(qū)別l數(shù)據(jù)是對客觀實體的一種描述形式，是信息的載數(shù)據(jù)是對客觀實體的一種描述形式，是信息的載體。數(shù)據(jù)是未加工的信息，信息是經(jīng)過加工的數(shù)體。數(shù)據(jù)是未加工的信息，信息是經(jīng)過加工的數(shù)據(jù)，將數(shù)據(jù)加工為數(shù)據(jù)的過程稱為信息加工或處據(jù)，將數(shù)據(jù)加工為數(shù)據(jù)的過程稱為信息加工或處理。理。l消息：在通信過程中，信息總是經(jīng)過編碼消息：在通信過程中，信息總是經(jīng)過編碼( (符號化符號化) )成為消息以后，才能經(jīng)由媒介傳播的，而信息的成為消息以后，才能經(jīng)由媒介傳

13、播的，而信息的接收者收到信息后，總是要經(jīng)過譯碼接收者收到信息后，總是要經(jīng)過譯碼( (解讀解讀) )才獲才獲取其中的信息。取其中的信息。l信號是數(shù)據(jù)的電磁或光脈沖編碼。信號可以分為信號是數(shù)據(jù)的電磁或光脈沖編碼。信號可以分為模擬信號和數(shù)字信號。模擬信號和數(shù)字信號。 信息信息n就是差異。(Longo,1975) 評述此指信息量，而量與質(zhì)是相關(guān)的，沒有差異就沒有結(jié)構(gòu)，也就沒有信息。因而信息量是結(jié)構(gòu)的差異。n是集合的變異度 (Ashby,1956) n(狹義)是收信者事先不知道的報道n(廣義)是對各種事物的存在方式、運動狀態(tài)和相互聯(lián)系特征的一種表達和陳述,是自然界,人類社會和人類思維活動普遍存在的一切物

14、質(zhì)和事物的屬性。n（標(biāo)準(zhǔn)化）信息是事物及其屬性標(biāo)識的集合信息是事物及其屬性標(biāo)識的集合n確定性的增加n信息就是信息，信息是物質(zhì)、能量、信息的標(biāo)示。 評述n在諸多信息定義當(dāng)中，維納的定義是很重要的。其重要性就在他指出構(gòu)成系統(tǒng)要有三個要素，即物質(zhì)、能量和信息。 物質(zhì)、能量和信息分別從不同側(cè)面反映了系統(tǒng)三象性質(zhì)缺一不可但又相互聯(lián)系。 1.21.2 信息技術(shù)與信息科學(xué)信息技術(shù)與信息科學(xué) 1.2.1 1.2.1 信息技術(shù)的發(fā)展與定義信息技術(shù)的發(fā)展與定義 信息技術(shù)是人類開發(fā)和利用信息資源信息技術(shù)是人類開發(fā)和利用信息資源的所有手段的總和；的所有手段的總和； 信息技術(shù)既包括有關(guān)信息的產(chǎn)生、收信息技術(shù)既包括有關(guān)信

15、息的產(chǎn)生、收集、表示、檢測、處理和存儲等方面的技集、表示、檢測、處理和存儲等方面的技術(shù)，也包括有關(guān)信息的傳遞、變換、顯示、術(shù)，也包括有關(guān)信息的傳遞、變換、顯示、識別、提取、控制和利用等方面的技術(shù)。識別、提取、控制和利用等方面的技術(shù)。迄今為止，人類社會已經(jīng)發(fā)生過四次信息技術(shù)革命：迄今為止，人類社會已經(jīng)發(fā)生過四次信息技術(shù)革命： 第一次革命第一次革命是人類創(chuàng)造了語言和文字，接著現(xiàn)出了是人類創(chuàng)造了語言和文字，接著現(xiàn)出了文獻。文獻。 第二次革命第二次革命是造紙和印刷術(shù)的出現(xiàn)。是造紙和印刷術(shù)的出現(xiàn)。 第三次革命第三次革命是電報、電話、電視及其他通訊技術(shù)的是電報、電話、電視及其他通訊技術(shù)的發(fā)明和應(yīng)用。發(fā)明和

16、應(yīng)用。 第四次革命第四次革命是電子計算機和現(xiàn)代通訊技術(shù)在信息工是電子計算機和現(xiàn)代通訊技術(shù)在信息工作中的應(yīng)用。作中的應(yīng)用。 目前正在進行目前正在進行第五次第五次信息技術(shù)革命，第五次是計信息技術(shù)革命，第五次是計算機及計算機網(wǎng)絡(luò)與通信衛(wèi)星、光纖等等現(xiàn)代通訊技算機及計算機網(wǎng)絡(luò)與通信衛(wèi)星、光纖等等現(xiàn)代通訊技術(shù)的結(jié)合術(shù)的結(jié)合.1.2 信息技術(shù)與信息科學(xué) 1.2.2 1.2.2 信息技術(shù)信息技術(shù)主要包括主要包括計算機技術(shù)計算機技術(shù)（人的思維器官處理信息和決策的功能的擴人的思維器官處理信息和決策的功能的擴展展）、）、微電子技術(shù)微電子技術(shù)（擴展了人對信息的存儲和使用能力擴展了人對信息的存儲和使用能力）; ;通信

17、技術(shù)通信技術(shù)（擴展人的神經(jīng)系統(tǒng)傳遞信息的功能擴展人的神經(jīng)系統(tǒng)傳遞信息的功能），），以及以及傳感技術(shù)傳感技術(shù)（擴展人的感覺器官收集信息的功能擴展人的感覺器官收集信息的功能）和）和 控制技術(shù)控制技術(shù)。1.21.2 信息技術(shù)與信息科學(xué)信息技術(shù)與信息科學(xué) 信息技術(shù)對人類信息器官的擴展信息技術(shù)對人類信息器官的擴展: :人體的信息人體的信息器官器官人體的信息人體的信息器官器官擴展信息器官功能的信擴展信息器官功能的信息技術(shù)息技術(shù)感覺器官感覺器官獲取信息獲取信息傳感技術(shù)傳感技術(shù)神經(jīng)器官神經(jīng)器官傳遞信息傳遞信息通信技術(shù)通信技術(shù)思維器官思維器官加工加工/再生產(chǎn)再生產(chǎn)信息信息計算機與智能技術(shù)計算機與智能技術(shù)效應(yīng)器官

18、效應(yīng)器官使用信息使用信息控制技術(shù)控制技術(shù)擴展擴展人類(頭腦、軀體、神經(jīng)、五官等)某器官的能力。旨在改造自然。n哪種更關(guān)鍵？關(guān)鍵還是思路、算法。而會聚技術(shù)(NBIC)旨在提升提升人類自身能力，大科學(xué)，以人為本。n會聚技術(shù)與人類以往所有技術(shù)不同之處是把提升人類自身能力作為其最終目標(biāo)。n以往的技術(shù)，主要通過擴展人類某器官的能力，來更好地改造世界，讓自然界為人類服務(wù)。實現(xiàn)人類自身和社會的進步。 1.21.2 信息技術(shù)與信息科學(xué)信息技術(shù)與信息科學(xué) .3 信息科學(xué)信息科學(xué) 主要研究信息的產(chǎn)生，獲取，存儲，傳輸，處理及主要研究信息的產(chǎn)生，獲取，存儲，傳輸，處理及其應(yīng)用。其應(yīng)用。是研究信息及其

19、運動規(guī)律、擴展人的信息功是研究信息及其運動規(guī)律、擴展人的信息功能能( (特別是智力功能為主要研究目標(biāo)特別是智力功能為主要研究目標(biāo)) )的新興、邊緣、的新興、邊緣、綜合性學(xué)科。綜合性學(xué)科。 信息科學(xué)的崛起，是信息現(xiàn)象日趨復(fù)雜化、信息爆炸性增長、信息科學(xué)的崛起，是信息現(xiàn)象日趨復(fù)雜化、信息爆炸性增長、知識重要性增加、信息技術(shù)飛速發(fā)展等因素相互作用的結(jié)果。是知識重要性增加、信息技術(shù)飛速發(fā)展等因素相互作用的結(jié)果。是信息時代的必然產(chǎn)物。信息時代的必然產(chǎn)物。 信息科學(xué)是以信息科學(xué)是以信息信息為基本研究對象，傳統(tǒng)科學(xué)都為基本研究對象，傳統(tǒng)科學(xué)都是以物質(zhì)和能量為主要研究對象，這是信息科學(xué)有別是以物質(zhì)和能量為主要

20、研究對象，這是信息科學(xué)有別于一切傳統(tǒng)科學(xué)最基本的特征。于一切傳統(tǒng)科學(xué)最基本的特征。返回目錄返回目錄信息科學(xué)n在國家自然科學(xué)基金委“十一五”發(fā)展規(guī)劃中曾指出：信息科學(xué)是研究信息的產(chǎn)生、獲取、存儲、顯示、處理、傳輸和利用的科學(xué)。n信息科學(xué)應(yīng)該是研究信息的產(chǎn)生、獲取、存儲、表示、處理、傳輸、利用及其相互關(guān)系的科學(xué).n信息科學(xué)是研究信息和信息活動（產(chǎn)生、獲取、存儲、表示、處理、傳輸、利用）的規(guī)律、原理、相互關(guān)系以及技術(shù)實現(xiàn)的科學(xué)。信息科學(xué)發(fā)展戰(zhàn)略研究中提出了15個優(yōu)先發(fā)展的領(lǐng)域及其研究目標(biāo)包括1、后摩爾時代的新型器件，納米級集成電路，微納光子器件與光電集成，太赫茲與新型紅外、毫米波器件，高分辨率探測成

21、像，強場與超強場激光技術(shù)，7、低功耗艾級超級計算機系統(tǒng)，多機器人協(xié)調(diào)與仿生機器人，傳感網(wǎng)絡(luò)基礎(chǔ)，B4G移動通信理論與技術(shù)，11、網(wǎng)絡(luò)數(shù)據(jù)挖掘與理解，互聯(lián)網(wǎng)計算（云計算），賽博空間安全，復(fù)雜控制理論與技術(shù)，復(fù)雜系統(tǒng)與復(fù)雜網(wǎng)絡(luò)。5個重大交叉學(xué)科領(lǐng)域n生命信息檢測與解讀n量子計算與量子調(diào)控n基于光電子的精密測量n空間信息網(wǎng)絡(luò)基礎(chǔ)n面向社會發(fā)展的群智計算。社會計算（管理科學(xué)？）1.3 計算與計算科學(xué)計算與計算科學(xué)n1.3.1 探索計算(computing)之源n計算：即符號串的變換。n算法：求解某類問題的通用法則或方法，即符號串變換的規(guī)則。2500年前古希臘數(shù)學(xué)家哲學(xué)家畢達哥拉斯名言：“凡物皆數(shù)凡物皆

22、數(shù)”?！靶闹杏袛?shù)”。 學(xué)科=科學(xué)？數(shù)學(xué)描述？ 圖靈機計算模型控制器1000011111111.3.2 計算模型與圖靈(Alan Turing)機。 圖靈機是一種抽象計算模型，用來精確定義可計算函數(shù)。圖靈機由一個控制器，一條可以無限延伸的帶子和一個在帶子上左右移動的讀寫頭組成。這個概念如此簡單的機器，理論上卻可以計算任何直觀可計算函數(shù)。圖靈在設(shè)計了上述模型后提出，凡是可計算的函數(shù)都可用這樣的機器來實現(xiàn)，這就是著名的圖靈論題（1934）。圖靈機為現(xiàn)代計算機的出現(xiàn)提供了重要的依據(jù)：帶子存儲存儲設(shè)備命令相當(dāng)于一組預(yù)先設(shè)計、存儲好的程序程序控制器決定讀寫頭的每一步操作 1.3 計算與計算科學(xué)計算與計算科

23、學(xué)1.3.3 圖靈測試 圖靈試驗的方法：被測試的有一個人，另一個是聲稱自己有人類智力的機器。測試時，測試人與被測試人是分開的，測試人只有通過一些裝置（如鍵盤）向被測試人問一些問題，這些問題隨便是什么問題都可以。 問過一些問題后，如果測試人能夠正確地分出誰是人誰是機器，那機器就沒有通過圖靈測試，如果測試人沒有分出誰是機器誰是人，那這個機器就是有人類智能的。 圖靈試驗對智能問題從行為主義的角度給出了定義 圖靈為這項測試親自擬定了幾個示范性問題：問： 請給我寫出有關(guān)“第四號橋”主題的十四行詩。答：不要問我這道題，我從來不會寫詩。問：34957加70764等于多少？答：（停30秒后）105721問：你

24、會下國際象棋嗎？答：是的。問：我在我的K1處有棋子K；你僅在K6處有棋子K，在R1處有棋子R?，F(xiàn)在輪到你走，你應(yīng)該下那步棋？答：（停15秒鐘后）棋子R走到R8處，將軍！圖靈指出：“如果機器在某些現(xiàn)實的條件下，能夠非常好地模仿人回答問題，以至提問者在相當(dāng)長時間里誤認它不是機器，那么機器就可以被認為是能夠思維的?！睆谋砻嫔峡?，要使機器回答按一定范圍提出的問題似乎沒有什么困難，可以通過編制特殊的程序來實現(xiàn)。然而，如果提問者并不遵循常規(guī)標(biāo)準(zhǔn)，編制回答的程序是極其困難的事情。例如，提問與回答呈現(xiàn)出下列狀況：問：你會下國際象棋嗎？答：是的。問：你會下國際象棋嗎？答：是的。問：請再次回答，你會下國際象棋嗎？

25、答：是的。你多半會想到，面前的這位是一部笨機器。 如果提問與回答呈現(xiàn)出另一種狀態(tài)：問： 你會下國際象棋嗎？答：是的。問：你會下國際象棋嗎？答：是的，我不是已經(jīng)說過了嗎？問：請再次回答，你會下國際象棋嗎？答：你煩不煩，干嘛老提同樣的問題。那么，你面前的這位，大概是人而不是機器。 n上述兩種對話的區(qū)別在于，第一種可明顯地感到回答者是從知識庫里提取簡單的答案，第二種則具有分析綜合的能力，回答者知道觀察者在反復(fù)提出同樣的問題。n“圖靈測試”沒有規(guī)定問題的范圍和提問的標(biāo)準(zhǔn)，如果想要制造出能通過試驗的機器，以我們現(xiàn)在的技術(shù)水平，必須在電腦中儲存人類所有可以想到的問題，儲存對這些問題的所有合乎常理的回答，并

26、且還需要理智地作出選擇。 阿蘭圖靈(Alan Turing，1912-1954 )劍橋大學(xué) “論數(shù)字計算在決斷難題中的應(yīng)用(1936)”返回目錄返回目錄ACM(美國計算機學(xué)會)1966年起設(shè)立圖靈獎。圖靈獎美國計算機學(xué)會（ACM）的年度“圖靈獎”，自從1966年設(shè)立以來，一直是世界計算機科學(xué)領(lǐng)域的最高榮譽，相當(dāng)于計算機科學(xué)界的諾貝爾獎。圖靈獎已經(jīng)被先后授予給了47位計算機科學(xué)界的杰出人物，其中包括關(guān)系數(shù)據(jù)庫理論的開創(chuàng)者Edgar Codd、程序語言和算法理論的知名科學(xué)家Dijkstra、UNIX操作系統(tǒng)的開創(chuàng)者Dennis Ritchie、面向?qū)ο蟪绦蛟O(shè)計理論的奠基人以及蘋果個人電腦基于鼠標(biāo)的

27、GUI界面（也就是WINDOWS圖形界面的最原始來源）的首創(chuàng)者Alan Kay、Fortran語言的設(shè)計者John Backus、IBM-RISC體系結(jié)構(gòu)的創(chuàng)立者John Cocke等大名鼎鼎的計算機科學(xué)家。n這個以圖靈的名字命名的大獎，代表著60年來世界計算機科學(xué)的重大進步和創(chuàng)新，代表著計算機科學(xué)和相關(guān)技術(shù)產(chǎn)業(yè)的一次次質(zhì)的飛躍，同時，也代表著計算機科學(xué)界對圖靈的崇高敬意。n1950年圖靈認為50年后能作出像人一樣能思考的機器,目前60年過去了,還沒有成功,甚至還沒有像人一樣能看,聽的機器.1.3.4 計算科學(xué)(Computing Science)計算科學(xué)計算科學(xué)對描述和變換信息的過程，包括對

28、其理論、分析、設(shè)計、效率、實現(xiàn)和應(yīng)用等進行系統(tǒng)的研究。包括對算法和可計算性的研究，到根據(jù)可計算硬件和軟件的實際實現(xiàn)問題的研究，范圍極廣，但基本問題是：什么能被有效的自動進行？什么能被有效的自動進行？計算機科學(xué)(Computer Science存在性？)與技術(shù)計算機體系結(jié)構(gòu)計算機軟件與理論計算機應(yīng)用技術(shù) 軟件工程、信息管理、網(wǎng)絡(luò)工程、信息技術(shù)等n計算科學(xué)的最核心任務(wù)是算法算法研究摘自2005年總統(tǒng)信息技術(shù)顧問委員會計算科學(xué)確保美國的競爭力計算科學(xué)確保美國的競爭力. 美國總統(tǒng)報告計算科學(xué)計算科學(xué)是一個快速發(fā)展的多學(xué)科領(lǐng)域，它采用高是一個快速發(fā)展的多學(xué)科領(lǐng)域，它采用高級計算能力來理解和解決復(fù)雜問題。

29、計算科學(xué)融級計算能力來理解和解決復(fù)雜問題。計算科學(xué)融合了三種要素：合了三種要素：n算法(數(shù)值或非數(shù)值的)和建模與仿真軟件：為解決科學(xué)（如生物、物理和社會）工程和人文學(xué)科問題。n計算機與信息科學(xué)：為解決計算需求所發(fā)展和優(yōu)化的高級系統(tǒng)硬件、軟件、聯(lián)網(wǎng)和數(shù)據(jù)管理組件。n計算基礎(chǔ)設(shè)施：支持科學(xué)與工程問題的解決和發(fā)展計算機與信息科學(xué)。算法實例：求兩個正整數(shù)的最大公約數(shù)的Euclidean算法1.設(shè)M=較大的數(shù)，N=較小的數(shù)2.R=M/N的余數(shù)(將整除的余數(shù)賦給R)3.如果R非零，則M=N(將N值賦給M)，N=R (將R值賦給N),并返回2；否則，最大公約數(shù)就是當(dāng)前N值.尋找算法實際上就是尋找問題的解決方

30、案。WinXP是算法嗎？計算機科學(xué)算法的科學(xué)算法過程可以解決什么問題？如何更簡單地找出算法？描述和交互算法的技術(shù)如何改進？如何應(yīng)用我們算法的知識和技術(shù)來制造更好的機器？任何分析和比較不同算法的特性？所有這些問題的一般性主題就是算法的研究。所有這些問題的一般性主題就是算法的研究。計算機科學(xué)的新思維n算法研究已經(jīng)從什么功能可以計算之類的轉(zhuǎn)向如何用計算機,比如大型網(wǎng)絡(luò)結(jié)構(gòu)海量數(shù)據(jù)信息與檢索.（高級的應(yīng)用大都涉及智能）（高級的應(yīng)用大都涉及智能）n課程變化: 你會碰到這類問題: random graphs, giant component, phase transition, spectral anal

31、ysis,small world phenomenaProbability and Statistics從高維的有噪聲的數(shù)據(jù)中提取信息例:n選讀學(xué)校n選購汽車n選科研課題nWikipedia/Encyclopedian特快專遞/實時航班云圖http:/ Law），2.阿姆達爾定律（Amdals Law）3.局部性法則（Principle of Locality）大部分重要的系統(tǒng)性能問題都與這三個規(guī)律有關(guān).摩爾定律:英特爾(Intel)創(chuàng)始人之一戈登摩爾(Gordon Moore)n集成電路上可容納的晶體管數(shù)目，約每隔18個月便會增加一倍(性能也將提升一倍).n微處理器的性能每隔18個月提高一倍

32、，而價格下降一半。 n用一個美元所能買到的電腦性能，每隔18個月翻兩番。 阿姆達爾定律(Amdahl law)n阿姆達爾曾致力于并行處理系統(tǒng)的研究。對于固定負載情況下描述并行處理效果的加速比s，阿姆達爾經(jīng)過深入研究給出了如下公式： nS=1/(a+(1-a)/n) 其中，a為串行計算部分所占比例，n為并行處理結(jié)點個數(shù)。這樣，當(dāng)a=0時，最大加速比s=n；當(dāng)a=1時，最小加速比s=1；當(dāng)n時，極限加速比s 1a，這也就是加速比的上限。例如，若串行代碼占整個代碼的25，則并行處理的總體性能不可能超過4。這一公式已被學(xué)術(shù)界所接受，并被稱做“阿姆達爾定律” 。局部性法則（Principle of Locality）n好的程序經(jīng)常呈現(xiàn)出良好的局部性.即經(jīng)常用到最近用過的數(shù)據(jù)附近的數(shù)據(jù)項,或用到最近引用過自己的那些數(shù)據(jù).這種傾向稱為局部性法則,對軟硬件系統(tǒng)的性能和設(shè)計有很大影響.n分為時間局部性和空間局部性.1.4 計算機的信息表示與編碼計算機的信息表示與編碼n1.4.1 信息在計算機中的表示信息在計算機中的表示n二進制