大學(xué)計算機(jī)基礎(chǔ)（第六版）課件 01計算思維導(dǎo)論

第1章計算思維導(dǎo)論01計算與計算思維02計算理論03數(shù)與計算工具04計算與信息社會Contents目錄01計算與計算思維計算就是一種思考過程或執(zhí)行過程。計算的特點：①計算要有可用的數(shù)據(jù)；②在一定的時間內(nèi)完成計算，故要有速度；③計算是個過程；④要有適合和科學(xué)的方法（算術(shù)、規(guī)則、變換、算法、策略等）；⑤計算過程和結(jié)果要有精度；⑥計算對錯都要有結(jié)果。計算的含義計算需要硬件與軟件算籌和算盤都屬于硬件，而擺法和算盤的使用規(guī)則就是它們的軟件，它們的計算功能是加、減、乘、除、開方等運(yùn)算，這就是計數(shù)與計算。計數(shù)與計算邏輯（Logic）：本質(zhì)是尋找事物的相對關(guān)系，并用已知推斷未知數(shù)理邏輯：德國人萊布尼茨邏輯代數(shù)：愛爾蘭的數(shù)學(xué)教授布爾邏輯與計算算法是對特定問題求解步驟和方案的一種描述或解法算法是一組確定的、有效的、有限的解決問題的步驟6-5=1和6+（-5）=1的區(qū)別：前者是算數(shù)，后者為算法算法可分為數(shù)值計算類、非數(shù)值計算類算法的過程正好就是可以在計算機(jī)上執(zhí)行的過程計算：計算的過程就是執(zhí)行算法的過程算法與計算科學(xué)思維（ScientificThinking）：人腦對科學(xué)信息的加工活動，它是主體對客體理性的、邏輯的、系統(tǒng)的認(rèn)識過程?？茖W(xué)思維必須遵守的基本原則：在邏輯上要求嚴(yán)密的邏輯性，達(dá)到歸納和演繹的統(tǒng)一；在方法上要求辯證的分析和綜合兩種思維方法；在體系上要求實現(xiàn)邏輯與歷史的一致，達(dá)到理論與實踐具體的、歷史的統(tǒng)一?？茖W(xué)思維理論思維（TheoreticalThinking）又稱邏輯思維，對應(yīng)于理論科學(xué)實踐思維（ExperimentalThinking）又稱實證思維，對應(yīng)于實踐科學(xué)計算思維（ComputationalThinking）對應(yīng)于計算機(jī)科學(xué)科學(xué)思維的分類計算思維的精髓是運(yùn)用計算機(jī)科學(xué)的思想與方法分析問題、行為理解、系統(tǒng)建模與設(shè)計實現(xiàn)計算機(jī)科學(xué)成為計算思維的基礎(chǔ)計算機(jī)的出現(xiàn)強(qiáng)化了計算思維的意義和作用計算思維的概念人與環(huán)境人與人環(huán)境與人行為理解的社會性什么是“行為理解”？計算思維定義、本質(zhì)和特征科學(xué)思維美國學(xué)者周以真（JeannetteMWing）教授2006年提出：計算思維是運(yùn)用計算機(jī)科學(xué)的基礎(chǔ)概念進(jìn)行問題求解、系統(tǒng)設(shè)計以及人類行為的理解等涵蓋計算機(jī)科學(xué)之廣度的一系列思維活動計算思維的三大部分：問題求解、系統(tǒng)設(shè)計和工程組織（人類行為理解）本質(zhì)：抽象（Abstract）和自動化（Automation）；特征：能行性，構(gòu)造性和確定性計算思維的概念計算思維的實踐基礎(chǔ)為計算系統(tǒng)（機(jī)器）與程序，當(dāng)程序被加載到計算系統(tǒng)（機(jī)器）中之后，它會被自動執(zhí)行。這種思維方式就是要將現(xiàn)實信息進(jìn)行符號化。計算思維的實踐環(huán)境是指應(yīng)用計算系統(tǒng)（機(jī)器）與程序的通用領(lǐng)域，是將計算思維轉(zhuǎn)化成物理環(huán)境的過程?！榜T?諾依曼計算機(jī)”“個人計算環(huán)境”“并行與分布式計算環(huán)境”“云計算環(huán)境”計算思維的實踐計算系統(tǒng)（機(jī)器）程序遞歸0和1

計算思維的實踐基礎(chǔ)02計算理論計算模型是指用于刻畫計算概念的抽象形式系統(tǒng)或數(shù)學(xué)系統(tǒng)。計算模型控制器讀/寫頭紙帶讀/寫頭紙帶（a）模型圖（b）概念圖y=5/20;z=x+y;F=b1

b2…………狀態(tài)x狀態(tài)n初始條件變量狀態(tài)0圖靈機(jī)模型和概念示意圖可計算性理論是研究計算的一般性質(zhì)的數(shù)學(xué)理論，也稱算法理論和能行性理論?？捎嬎阈跃哂腥缦聨讉€特征確定性有限性設(shè)備無關(guān)性可用算術(shù)運(yùn)算可計算性計算復(fù)雜性是指利用計算機(jī)求解問題的難易程度計算復(fù)雜性的度量標(biāo)準(zhǔn)時間復(fù)雜度常數(shù)、對數(shù)階、線性階、線性對數(shù)階、平方階、立方階、k次方階、指數(shù)階

空間復(fù)雜度人們對算法空間復(fù)雜度分析的重視程度要小于時間復(fù)雜度的分析計算復(fù)雜性P問題是指問題可以在內(nèi)的多項式時間內(nèi)解決

P問題成為了區(qū)分問題是否可以被計算機(jī)求解的一個重要標(biāo)志NP問題是指算法時間復(fù)雜度不能使用確定的多項式來表示可計算與計算復(fù)雜性理論可知，一個問題理論上是否能行，取決于其可算性，而現(xiàn)實是否能行，則取決于其計算復(fù)雜性。P問題與NP問題印度古老傳說。三根柱子，最終64個盤子在其中一根柱子上從下到上由大到小的地穿好。按照下面的法則移動這些盤子：①一次只移動一個盤子，且只能在柱子上來回移動②不管在哪根柱子上，盤子必須在大片上面。漢諾塔求解當(dāng)n=64時，假如每秒鐘移動一次，共需要多長時間呢？5,849億年以上，時間復(fù)雜度不可行問題。問題的抽象問題的映射設(shè)計問題求解算法問題求解的實現(xiàn)求解問題過程數(shù)學(xué)模型已成為處理各種實際問題的重要工具建立數(shù)學(xué)模型的一般步驟①模型準(zhǔn)備階段②模型假設(shè)階段③模型構(gòu)成階段④模型確定階段問題抽象的思維過程問題的映射是將客觀世界的問題求解映射到計算機(jī)中求解開發(fā)軟件進(jìn)行問題求解的過程實現(xiàn)問題域→建立模型→編程實現(xiàn)→到計算機(jī)世界執(zhí)行求解的過程。問題的映射過程①將算法作用于特定的輸入集或問題描述時，可導(dǎo)致有限步動作構(gòu)成的動作序列。②該動作序列具有唯一的初始動作。③序列中的每一動作具有一個或多個后繼動作。④序列或者終止于某一個動作，或者終止于某一個陳述。設(shè)計問題求解算法編寫求解算法的程序程序調(diào)試或測試完成相關(guān)文檔問題求解的實現(xiàn)循環(huán)（行）in=5個數(shù)兩兩比較循環(huán)（列）j比較次數(shù)（n–i）i：由1到4（n-1）第1輪初始排序數(shù)據(jù)表[563478219]j=1到44次第2輪第1輪兩兩比較4次后結(jié)果[3456219]78j=1到33次第3輪第2輪兩兩比較3次后結(jié)果[34219]5678j=1到22次第4輪第3輪兩兩比較2次后結(jié)果[219]345678j=11次

第4輪兩兩比較1次后結(jié)果[9]21345678

最后排序結(jié)果表[921345678]

數(shù)據(jù)有序排列——排序算法冒泡排序算法過程求出n=48770428433377171的一個真因子，一天之內(nèi)交卷一人計算：順序求解多人同時計算：并行計算并行處理技術(shù)的形式①時間并行，指時間重疊②空間并行，指資源重復(fù)③時間并行和空間并行，指時間重疊和資源重復(fù)的綜合應(yīng)用。國王婚姻問題——并行計算假設(shè)給定4個城市A、B、C、D相互連接，間距已知。由以下路徑的總距離可以求出來：①路徑ABCDA的總距離是：4.5+2.5+4.5+2.5=14.0②路徑ABDCA的總距離是：4.5+6.0+4.5+5.5=20.5③路徑ACBDA的總距離是：5.5+2.5+6.0+2.5=16.5④路徑ACDBA的總距離是：5.5+4.5+6.0+4.5=20.5⑤路徑ADBCA的總距離是：2.5+6.0+2.5+5.5=16.5⑥路徑ADCBA的總距離是：2.5+4.5+2.5+4.5=14.0最優(yōu)化方法用于研究各種有組織系統(tǒng)的管理問題及其生產(chǎn)經(jīng)營活動，對所研究的系統(tǒng)，求得一個合理運(yùn)用人力、物力和財力的最佳方案，發(fā)揮和提高系統(tǒng)的效能及效益，最終達(dá)到系統(tǒng)的最優(yōu)目標(biāo)。旅行商問題——最優(yōu)化思想ABCD4.52.54.55.56.02.503數(shù)與計算工具傳統(tǒng)的計算工具算籌是世界上最古老的計算工具之一算籌在算板上按照需要排列形成籌式，同樣的籌，所在的位置不同，表示的數(shù)也不同，這是十進(jìn)制的思想算籌空表示0橫排式：多位數(shù)：縱排式：數(shù)字：（a）算籌布袋

（b）算籌計數(shù)算盤是中國古代偉大發(fā)明之一珠算有完整、成熟的運(yùn)算口訣，算盤是方便、實用的器械算盤計算尺由上下兩條相對固定的尺身，中間一條可以移動的滑尺和可在尺上滑動的游標(biāo)三部分組成計算尺除了對數(shù)刻度，還可以有其他數(shù)學(xué)函數(shù)刻度，如常用的三角函數(shù)、乘方、開方等，來實現(xiàn)復(fù)雜的運(yùn)算計算尺A尺刻度1.26B尺刻度1A尺刻度4.30B尺刻度3.38A尺log(1.26)B尺log(3.38)傳統(tǒng)的計算工具的計算能力和數(shù)據(jù)分析能力有限計算的自動化：1642年，法國科學(xué)家帕斯卡發(fā)明了加法器計算機(jī)的雛形查爾斯·巴貝奇（CharlesBabbage，1792—1871年）差分機(jī)設(shè)計閃爍出了程序控制的靈光差分機(jī)（a）查爾斯·巴貝奇

（b）1822年設(shè)計的差分機(jī)分析機(jī)：“存儲庫”和“運(yùn)算室”奧歐古斯塔·愛達(dá)（AugustaAdaByron，1815—1852年）巴貝奇的分析機(jī)的設(shè)想可以說是現(xiàn)代通用計算機(jī)的雛形，同現(xiàn)代計算機(jī)一樣可以編程分析機(jī)1834年設(shè)計的分析機(jī)機(jī)械式計算機(jī)器：1642年，法國科學(xué)家布萊斯·帕斯卡（BlaisePascal）乘法器：1674年，德國著名數(shù)學(xué)家萊布尼茨（GottfriedWilhelmLeibniz）手搖計算器：中國機(jī)械式計算器（a）中國制造的飛魚牌機(jī)械式計算器

（b）國外制造的機(jī)械式計算器電子式計算器：采用集成電路的便攜式電子式計算器既可以是硬件，也可以是開發(fā)出的軟件計算器電子式計算器（a）硬件電子式計算器

（b）軟件電子式計算器語言的發(fā)展中，逐漸有了數(shù)的概念最早的數(shù)的概念是“有”和“無”隨著問題的復(fù)雜，把“有”逐步分解，產(chǎn)生數(shù)的概念數(shù)的起源原始的結(jié)繩計數(shù)計數(shù)、符號和數(shù)量阿拉伯?dāng)?shù)字由1、2、3、4、5、6、7、8、9、0十個符號組成，采用十進(jìn)制計數(shù)法，筆畫簡單，書寫方便20世紀(jì)初阿拉伯?dāng)?shù)字才在中國逐漸推廣使用。阿拉伯?dāng)?shù)字中國人于公元前14世紀(jì)，發(fā)明了十進(jìn)計數(shù)制，到了商朝，中國人就已經(jīng)能夠用0～9十個數(shù)字來表示任意大的自然數(shù)十進(jìn)制在計算機(jī)科學(xué)和計算技術(shù)的發(fā)展中起了非常重要的作用中國人發(fā)明十進(jìn)制計算機(jī)之父：馮·諾依曼（JohnvonNeumann，1903—1957年）EDVAC（ElectronicDiscreteVariableAutomaticCalculator，離散變量自動電子計算機(jī)）：1945年馮·諾依曼的兩大設(shè)計思想二進(jìn)制：在電子計算機(jī)中采用二進(jìn)制計算機(jī)采用“存儲程序和程序控制”工作原理通用電子計算機(jī)ENIAC：1946年ENIAC計算機(jī)ABC計算機(jī)：約翰·阿塔納索夫（JohnVincentAtanasoff，1904—1995年）ABC計算機(jī)的電路系統(tǒng)中裝有300個電子真空管執(zhí)行數(shù)字計算與邏輯運(yùn)算，機(jī)器使用電容器來進(jìn)行數(shù)值處理，數(shù)據(jù)輸入采用打孔讀卡辦法，還采用了二進(jìn)制ABC計算機(jī)現(xiàn)代計算機(jī)的發(fā)展時代年份器件軟件應(yīng)用一1946—1956電子管、運(yùn)算速度每秒幾萬次二進(jìn)制機(jī)器語言、匯編語言科學(xué)計算二1957—1964晶體管、運(yùn)算速度每秒300萬次高級語言數(shù)據(jù)處理工業(yè)控制三1965—1969集成電路、運(yùn)算速度每秒4000萬次操作系統(tǒng)文字處理圖形處理四1970年至今大規(guī)模和超大規(guī)模集成電路、運(yùn)算速度每秒幾億次數(shù)據(jù)庫、網(wǎng)絡(luò)等社會的各個領(lǐng)域五1980年至今各種光學(xué)器件、光纖通信技術(shù)以及智能輔助設(shè)計系統(tǒng)智能化程序設(shè)計及系統(tǒng)、知識庫系統(tǒng)所有領(lǐng)域六2000年至今超導(dǎo)、神經(jīng)網(wǎng)絡(luò)、生物輔助設(shè)計所有領(lǐng)域二進(jìn)制：1679年，德國杰出的數(shù)學(xué)家萊布尼茨發(fā)明一種計算法，用兩個數(shù)“0”和“1”代替原來的十位數(shù)二進(jìn)制的特點：①只有兩個數(shù)字“0”和“1”，從物理上講更容易實現(xiàn)計數(shù)和存儲，即數(shù)的表示和存儲更容易②計算簡單，對二進(jìn)制進(jìn)行算術(shù)運(yùn)算的規(guī)則比十進(jìn)制簡單得多計算機(jī)采用晶體管實現(xiàn)二進(jìn)制，其功能也就是：變換、邏輯運(yùn)算和加法運(yùn)算二進(jìn)制萊布尼茨的邏輯原理①所有的觀念或概念都是由非常小數(shù)目的簡單觀念復(fù)合而成的，它們形成了人類思維的方式②復(fù)雜的觀念來自這些簡單觀念的組合布爾代數(shù)：1847年，英國數(shù)學(xué)家布爾發(fā)表了《邏輯的數(shù)學(xué)分析》數(shù)理邏輯布爾認(rèn)為：邏輯中的各種命題能夠使用數(shù)學(xué)符號來代表，并能依據(jù)規(guī)則推導(dǎo)出適當(dāng)?shù)慕Y(jié)論兩個邏輯值［“真（True）”“假（False）”］３種邏輯關(guān)系［“與（And）”“或（Or）”的二元運(yùn)算，和“非（Not）”的一元運(yùn)算］基礎(chǔ)上的集合運(yùn)算和邏輯運(yùn)算克勞德·艾爾伍德·香農(nóng)（ClaudeElwoodShannon，1916—2001年）：把布爾代數(shù)的“真（True）”與“假（False）”和電路系統(tǒng)的“開”與“關(guān)”對應(yīng)起來，用1和0表示布爾代數(shù)1956年8月25日我國第一個計算技術(shù)研究機(jī)構(gòu)─中國科學(xué)院計算技術(shù)研究所籌備委員會成立，著名數(shù)學(xué)家華羅庚任主任。2001年中國雙院士、北京大學(xué)王選教授作為漢字激光照排系統(tǒng)的創(chuàng)始人和技術(shù)負(fù)責(zé)人獲得國家最高科學(xué)技術(shù)獎?，F(xiàn)代計算機(jī)在中國的發(fā)展年份計算機(jī)1958小型通用數(shù)字電子管計算機(jī)（103型）1964大型通用電子管計算機(jī)1964全晶體管計算機(jī)1971集成電路計算機(jī)目前，我國自主開發(fā)的“銀河”、“曙光”、“深騰”、“神威”和“天河”等系列高性能計算機(jī)，取得了令人矚目的成果。巨型機(jī)和超級計算機(jī)的研制、開發(fā)和利用代表著一個國家的經(jīng)濟(jì)實力和科學(xué)研究水平。以“聯(lián)想”、“清華同方”、“方正”、“浪潮”等為代表的我國計算機(jī)制造業(yè)也非常發(fā)達(dá)，已成為世界計算機(jī)主要制造中心之一。微型機(jī)的研制、開發(fā)和廣泛應(yīng)用，標(biāo)志著一個國家科學(xué)技術(shù)普及的程度?，F(xiàn)代計算機(jī)在中國的發(fā)展現(xiàn)代計算機(jī)在中國的發(fā)展云超級計算機(jī)加快新藥研發(fā)速度讓天氣預(yù)報更精準(zhǔn)超級計算機(jī)在中國的發(fā)展04計算與信息社會互聯(lián)網(wǎng)+是計算機(jī)系統(tǒng)網(wǎng)絡(luò)化技術(shù)與其他技術(shù)相結(jié)合的產(chǎn)物，是信息社會與知識社會推動下由互聯(lián)網(wǎng)發(fā)展產(chǎn)生的新業(yè)態(tài)。“互聯(lián)網(wǎng)+”就是“互聯(lián)網(wǎng)+各個行業(yè)”，但這并不是簡單的兩者相加，而是利用信息通信技術(shù)以及互聯(lián)網(wǎng)平臺，讓互聯(lián)網(wǎng)與傳統(tǒng)行業(yè)進(jìn)行深度融合，創(chuàng)造新的發(fā)展生態(tài)?；ヂ?lián)網(wǎng)+技術(shù)的應(yīng)用范圍為互聯(lián)網(wǎng)與其他傳統(tǒng)產(chǎn)業(yè)，應(yīng)用手段則是通過互聯(lián)網(wǎng)與傳統(tǒng)產(chǎn)業(yè)進(jìn)行聯(lián)合和深入融合的方式進(jìn)行?；ヂ?lián)網(wǎng)+作為一個整體概念，是指通過傳統(tǒng)的計算機(jī)網(wǎng)絡(luò)化技術(shù)完成產(chǎn)業(yè)升級?；ヂ?lián)網(wǎng)+行業(yè)融合創(chuàng)新驅(qū)動重塑結(jié)構(gòu)尊重人性開放生態(tài)連接一切互聯(lián)網(wǎng)+的特征（1）運(yùn)算速度快（2）存儲容量大，保存時間長（3）計算精確度高（4）邏輯判斷能力（5）自動工作的能力計算機(jī)的特點（1）科學(xué)和工程計算領(lǐng)域（2）數(shù)據(jù)處理領(lǐng)域（3）辦公自動化領(lǐng)域（也稱信息管理）（4）電子商務(wù)領(lǐng)域（5）自動控制領(lǐng)域（6）計算機(jī)輔助領(lǐng)域

（7）人工智能領(lǐng)域（8）計算機(jī)網(wǎng)絡(luò)領(lǐng)域計算機(jī)系統(tǒng)的應(yīng)用微型化大型化網(wǎng)絡(luò)化智能化計算機(jī)系統(tǒng)的發(fā)展信息同物質(zhì)、能源一樣重要，是人類生存和社會發(fā)展的三大基本資源之一。信息（Information）是自然界、人類社會和人類思維活動中普遍存在的一切物質(zhì)和事物的屬性。廣義地說，信息就是人類的一切生存活動和自然存在所傳達(dá)出來的信號和消息。美國科學(xué)家香農(nóng)1948年發(fā)表了著名的《通信的數(shù)學(xué)原理》一文，使得信息論從此誕生，香農(nóng)也因此成為信息論的奠基人。信息的概念數(shù)據(jù)（Data）是指客觀世界中記錄下來的各種各樣的物理符號及其組合，是信息的具體表現(xiàn)形式，反映了信息的內(nèi)容。數(shù)據(jù)是信息的載體，數(shù)據(jù)中包含著信息。例如，數(shù)值、文字、聲音、圖形、圖像、視頻等都是可識別的不同形式的數(shù)據(jù)信息是指數(shù)據(jù)中有用的知識，需要去挖掘，即處理加工。信息既是各種事物的變化和特征的反映，又是事物之間相互作用和聯(lián)系的表征。信息與數(shù)據(jù)當(dāng)數(shù)據(jù)以某種形式經(jīng)過處理、描述或與其他數(shù)據(jù)比較時，才能成為信息，而知識是指人類的認(rèn)識成果。如規(guī)則等，表現(xiàn)為判斷、推理、決策等包括事實、信息的描述或在教育和實踐中獲得的技能。可以是關(guān)于理論的，也可以是關(guān)