大學(xué)計算機基礎(chǔ)之計算機思維基礎(chǔ)教學(xué)課件

大學(xué)計算機基礎(chǔ)第八章計算思維基礎(chǔ)大學(xué)計算機基礎(chǔ)第八章計算思維基礎(chǔ)第八章計算思維基礎(chǔ)主要內(nèi)容8.1計算科學(xué)與計算學(xué)科8.2計算思維的概念8.3計算思維的內(nèi)涵8.4計算思維的應(yīng)用第八章計算思維基礎(chǔ)主要內(nèi)容思維本身讓人沉醉……計算思維除了給計算機技術(shù)帶來變革，它還讓人們在探索的過程中體驗和諧、對稱、完備、簡潔等美學(xué)屬性?？茖W(xué)的美不遜于藝術(shù)的美。思維本身讓人沉醉……科學(xué)的概念8.1計算科學(xué)與計算學(xué)科達爾文“科學(xué)就是整理事實，從中發(fā)現(xiàn)規(guī)律，作出結(jié)論?！笨茖W(xué)是運用范疇、定理和定律等思維形式反映現(xiàn)實世界中各種現(xiàn)象的本質(zhì)和運動規(guī)律的知識體系?！皊cience”來源于拉丁文”scientia”,意為“知識與學(xué)問”。詞源科學(xué)的概念8.1計算科學(xué)與計算學(xué)科達爾文“科學(xué)就是整理事實2.科學(xué)的分類廣義科學(xué)自然科學(xué)：以自然界為主要研究對象，運用實證、理性和臻美等方法，解釋自然的奧秘。人文科學(xué)：以人類為主要研究對象，，運用實地考察、詮釋和啟示等方法，認識人、人性和人生的意義，提升人的精神素質(zhì)和思想境界。社會科學(xué)：以社會領(lǐng)域為主要研究對象，運用調(diào)查、統(tǒng)計和歸納等方法，把握社會規(guī)律，解決社會問題，促進社會進步。狹義科學(xué)自然科學(xué)（有時也指基礎(chǔ)理論科學(xué)）

8.1計算科學(xué)與計算學(xué)科2.科學(xué)的分類8.1計算科學(xué)與計算學(xué)科科學(xué)思維及其分類1）科學(xué)思維科學(xué)思維（ScientificThinking)是指經(jīng)過感性階段獲取的大量材料通過整理和改造，形成概念、判斷和推理，以便反映事物的本質(zhì)和規(guī)律?？茖W(xué)思維是大腦對科學(xué)信息的加工活動?？茖W(xué)思維涵蓋內(nèi)容：

--思維要與客觀實際相符

--要求遵循形式邏輯的規(guī)律和規(guī)則

--思維要具有創(chuàng)新性科學(xué)研究的方法：

--理論研究

--實驗研究

--計算研究理論科學(xué)、實驗科學(xué)和計算科學(xué)是推動人類文明進步和科技發(fā)展的主要途徑。8.1計算科學(xué)與計算學(xué)科科學(xué)思維及其分類8.1計算科學(xué)與計算學(xué)科2）科學(xué)思維的分類對應(yīng)的三大科學(xué)研究的思維是理論思維、實驗思維和計算思維。理論思維：又稱推理思維，以推理和演繹為特征，以數(shù)學(xué)學(xué)科為代表。實驗思維：又稱實證思維，以觀察和總結(jié)自然規(guī)律為特征，以物理學(xué)科為代表。計算思維：又稱構(gòu)造思維，以設(shè)計和構(gòu)造為特征，以計算機學(xué)科為代表。

計算思維就是思維過程或功能的計算模擬方法論，其研究的目的是提供適當(dāng)?shù)姆椒ǎ谷藗兘柚F(xiàn)代和將來的計算機，逐步實現(xiàn)人工智能的較高目標。諸如：模式識別、決策、優(yōu)化和自控等算法都屬于計算思維的范疇。三大思維都是人類科學(xué)思維方式中固有的部分。其中，理論思維強調(diào)推理，實驗思維強調(diào)歸納，計算思維希望能自動求解。他們以不同的方式推動著科學(xué)的發(fā)展和人類文明的進步。8.1計算科學(xué)與計算學(xué)科2）科學(xué)思維的分類8.1計算科學(xué)與計算學(xué)科幾千年前：

科學(xué)是以觀察或?qū)嶒灋橐罁?jù)的，經(jīng)驗的描述自然現(xiàn)象近幾百年：

派生出理論的

使用模型進行一般化推理近幾十年：

派生出計算的

用計算機輔助分析復(fù)雜現(xiàn)象

采集數(shù)據(jù)——軟件處理——結(jié)果分析和統(tǒng)計8幾千年前：

科學(xué)是以觀察或?qū)嶒灋橐罁?jù)的，經(jīng)驗的描述8計算科學(xué)理論科學(xué)實驗科學(xué)測試理論提出理論解釋結(jié)果制作模型提出模型建模過程提出實驗數(shù)據(jù)分析驅(qū)動裝置大型計算模型驗證數(shù)據(jù)生產(chǎn)解釋結(jié)果生產(chǎn)模型精確計算驗證理論生產(chǎn)數(shù)據(jù)提出理論3）理論科學(xué)、實驗科學(xué)和計算科學(xué)的研究關(guān)系計算科學(xué)理論科學(xué)實驗科學(xué)測試理論提出理論解釋結(jié)果制作模型提出計算科學(xué)與計算學(xué)科計算科學(xué)計算科學(xué)（ComputingScience）是應(yīng)用高性能計算能力預(yù)測和了解客觀世界物質(zhì)運動或復(fù)雜現(xiàn)象演化規(guī)律的科學(xué)，它包括數(shù)值模擬、過程仿真、高效計算機系統(tǒng)和應(yīng)用軟件等。-計算學(xué)科計算學(xué)科（ComputingDiscipline）是對描述和變化信息的算法過程進行系統(tǒng)的研究，它包括算法過程理論、分析、設(shè)計、效率分析、實現(xiàn)和應(yīng)用等。計算學(xué)科的根本問題是“什么能被（有效地）自動進行”。計算科學(xué)與計算學(xué)科人要成功融入社會所必備的思維能力，是由其解決問題時所能獲得工具或過程決定的工業(yè)社會了解物理特性，思考如何用原料生成新事物組裝線自動化草圖制造工藝美術(shù)11計算思維簡介人要成功融入社會所必備的思維能力，是由其解決問題時所能獲得工信息社會為了問題求解，如何利用技術(shù)定位和使用信息電信、Email、信息空間網(wǎng)絡(luò)、LAN、Modem、blogWYSIWYG(WhatYouSeeIsWhatYouGet)、文件、圖標、光標芯片、RFID(射頻識別)、USB……12計算思維簡介信息社會12計算思維簡介超越信息社會利用數(shù)據(jù)和構(gòu)想解決問題超越使用工具和信息，進而創(chuàng)造工具和信息需要抽象、數(shù)據(jù)處理等技能，和大量計算機科學(xué)概念的支持這就是“計算思維”……人類思維與計算機能力的綜合……在21世紀，將是每個人所必備的基本技能讀、寫、算術(shù)13計算思維簡介超越信息社會13計算思維簡介計算思維舉例在排好序的花名冊中查找某個人線性搜索、二分查找在銀行窗口、超市排隊任務(wù)調(diào)度的性能分析將小孩一天要上的課的課本放入書包預(yù)取與緩沖送小孩去參加各種興趣班貨郎擔(dān)問題(旅行商問題）14計算思維簡介準備晚餐并行處理清理衣柜替換——留下需要的、丟掉不用并且占地方的幫小孩收納玩具Hash——按類型分別收納、按形狀、按材質(zhì)……各種算術(shù)運算方法計算思維舉例14計算思維簡介準備晚餐

1.計算思維概念的引入

2006年美國國家科學(xué)基金會（NSF）組織了計算教育與科學(xué)領(lǐng)域以及其他相關(guān)領(lǐng)域的專家，對“大學(xué)第一年計算機課程的構(gòu)建”、“多學(xué)科的融合”等問題進行研討。NSF先后啟動了旨在振興美國計算教育的四項國家計劃：

-BPC（擴大計算參與面）

-CPATH（大學(xué)計算教育振興途徑）

-CDI（計算使能的科學(xué)發(fā)現(xiàn)和技術(shù)創(chuàng)新）

-CE21（21世紀計算科學(xué)教育）

目的是提高K-14（中小學(xué)和大學(xué)一、二年級）老師與學(xué)生的計算思維能力。8.2計算思維概述1.計算思維概念的引入8.2計算思維概述

計算思維概念的定義周以真定義：計算思維（ComputationalThinking，CT）是運用計算機科學(xué)的基礎(chǔ)概念進行問題求解、系統(tǒng)設(shè)計、和理解人類行為等涵蓋計算機科學(xué)廣度的一系列思維活動。目的是培養(yǎng)學(xué)生像擁有閱讀、寫作和算術(shù)（3R）基本技能一樣擁有計算思維技能，并能自覺地應(yīng)用于日常的學(xué)習(xí)、研究與將來的工作中，要像計算機科學(xué)家那樣思考問題。周以真：原美國卡內(nèi)基·梅隆大學(xué)教授，2013年任微軟全球資深副總裁、負責(zé)微軟研究院全球各核心研究機構(gòu)及學(xué)術(shù)合作部。2006年對計算思維進行了清晰、系統(tǒng)的闡述，使計算思維的概念得到人們的極大關(guān)注。2.計算思維定義計算思維概念的定義周以真：原美國卡內(nèi)基·梅隆大學(xué)教授，202023/7/31172011年，國際教育技術(shù)協(xié)會(ISTE)和計算機科學(xué)教師協(xié)會(CSTA)給計算思維下了一個操作性的定義：

計算思維是一個問題解決的過程，該過程包括：①制定問題，并能夠利用計算機和其他工具來幫助解決該問題；②符合邏輯地組織和分析數(shù)據(jù)；③通過抽象（如模型、仿真等）再現(xiàn)數(shù)據(jù)；④通過算法（一系列有序的步驟）支持自動化的解決方案；⑤識別、分析和實施可能的解決方案，并整合這些最有效的方案和資源；⑥將該問題的求解過程進行推廣并移植到更廣泛的應(yīng)用中。2.計算思維定義2023/7/27172011年，國際教育技術(shù)協(xié)會(J.M.Wing,“ComputationalThinking,”CACMViewpoint,March2006,pp.33-35.Paperoff/~wing/J.M.Wing,“ComputationalThinP.J.Denning觀點ACM前主席P.J.Denning觀點Denning認為：計算原理可以總結(jié)為7類。

計算---Computation

通信---Communication

協(xié)作---Coordination

記憶---Recollection

自動化-Automation

評估---Evaluation

設(shè)計---Design7類原理：計算機理的功能角度Computation：meaningandlimitsofcomputationCommunication：reliabledatatransmissionCoordination：cooperationamongnetworkedentitiesRecollection：storageandretrievalofinformationAutomation：meaningandlimitsofautomationEvaluation：performancepredictionandcapacityplanningDesign：buildingreliablesoftwaresystems4類核心實踐ProgrammingSystemsandsystemsthinkingModeling,validating,testing,andmeasuringInnovatingP.J.Denning觀點Denning認為：計算原理可以總結(jié)為7類。

計算---Co例1計算函數(shù)f(x)區(qū)間[a,b]上的積分。在高等數(shù)學(xué)中，計算積分是使用牛頓—萊布尼茲公式，即首先求f(x)的原函數(shù)F(x),然后計算F(x)，解決這個問題不用黎曼積分的原因是計算量太大。在計算機中，計算積分的方法是使用黎曼積分，即對區(qū)間[a,b]進行n等分，然后計算各小矩形的面積。這里不用牛頓—萊布尼茲公式的原因有兩個：一是不同的f(x)求原函數(shù)的方法是不同的；二是并不是所有的f(x)都能找到原函數(shù)F(x).計算思維示例ab例1計算函數(shù)f(x)區(qū)間[a,b]上的積分。計算思維示例a例2：計算函數(shù)n的階乘f(n)=n!在計算機中，采用兩種方法：1）遞歸法：將計算f(n)的問題分解為計算一個較小的問題f(n-1),再將計算f(n-1)的問題分解為計算一個更小的問題f(n-2)……，直至分解到f(1)=1為止，然后從f(1)逐步計算到f(n)。

遞推—回代2）迭代法：f(1)=1，根據(jù)f(1)計算f(2)……最后根據(jù)f(n-1)計算f(n)。例2：計算函數(shù)n的階乘f(n)=n!例3服務(wù)窗口排隊（1）問題只有一個服務(wù)窗口，有三個服務(wù)顧客，分別需要服務(wù)時間為：

C1:12min；C2:5min；C3:3min（2）引發(fā)思考如何評價不同方案不同情況服務(wù)順序如何決定？到達時間不同、有不同的服務(wù)優(yōu)先級、服務(wù)允許被中斷（3）“討論”出服務(wù)排隊的核心方法先來先服務(wù)（FCFS)短任務(wù)優(yōu)先（SJF)最短剩余時間優(yōu)先（SRTF)優(yōu)先級調(diào)度（HPF)時間片輪轉(zhuǎn)（RR)例3服務(wù)窗口排隊（1）問題在日常生活中，當(dāng)小學(xué)生早晨去上學(xué)時，他把當(dāng)天所需要的東西放進書包，這就是“預(yù)置”；當(dāng)有人丟了東西，你建議他沿著走過的路線去尋找，這就叫“回退”；你永遠不知道下一步會怎樣，只能根據(jù)過去經(jīng)驗和當(dāng)前情況來決定現(xiàn)在的行為。人生就是“在線算法”；在超市付費時，應(yīng)當(dāng)去排哪一個隊呢？這就是“多服務(wù)器系統(tǒng)”；為什么停電時電話仍然可以使用呢？這就是“失敗的無關(guān)性”和”設(shè)計的冗余性“?！扒鐜в陚恪埃憋枎ю嚰Z”，就是一種“預(yù)立”。計算思維的理解……在日常生活中，當(dāng)小學(xué)生早晨去上學(xué)時，他把當(dāng)天所需要的東西放進計算思維的本質(zhì)：抽象（Abstraction）和自動化（Automation）。計算思維的本質(zhì)反映了計算的根本問題，即什么能被有效地自動進行。計算是抽象地自動進行，自動化需要某種計算機去解釋現(xiàn)象。從操作層面上講，計算就是如何尋找一臺計算機去求解問題，選擇合適的抽象，選擇合適的計算機去解釋執(zhí)行抽象，后者就是自動化。計算思維中的抽象完全超越物理的時空觀，并完全用符號來表示。其中，數(shù)字抽象只是一類特例。自動化就是機械地一步一步自動執(zhí)行，其基礎(chǔ)和前提是抽象。

案例：18世紀著名古典數(shù)學(xué)問題——哥尼斯堡七橋問題。3.計算思維的本質(zhì)計算思維的本質(zhì)：抽象（Abstraction）和自動化（Au26哥尼斯堡城地處東普魯士，位于普雷格爾河的兩岸及河中心的兩個島上，城市各部分由七座橋與兩岸連結(jié)起來。多年來，當(dāng)?shù)氐木用窨傆幸粋€愿望：從家里出去散步，能否通過每座橋恰好一次，再返回家中？但是任何人也沒有找到這樣一條理想的路徑。哥尼斯堡普萊格爾河抽象案例：18世紀著名古典數(shù)學(xué)問題——哥尼斯堡七橋問題。

26哥尼斯堡城地處東普魯士，位于普雷格爾河的兩岸及河中心的兩27

1736年，瑞士數(shù)學(xué)家歐拉(Euler)解決問題的方法是把陸地抽象為一個點，用連接兩個點的線段表示橋梁，將該問題抽象成點與線的連接圖的數(shù)學(xué)問題。實際問題的獨特之處是把一個實際問題抽象成合適的“數(shù)學(xué)模型”。這就是計算思維中的抽象。271736年，瑞士數(shù)學(xué)家歐拉(Euler)解決問題的4.計算思維的特征（1）計算機思維是人類求解問題的一條途徑，是屬于人的思維方式，不是計算機的思維方式。

計算機之所以能夠求解問題，是因為人將計算思維的思想賦予了計算機，計算機才能夠進行如迭代、遞歸等計算。（2）計算思維的過程可以由人執(zhí)行，也可以由計算機執(zhí)行。

這些計算人和計算機都可以做，只不過人的速度慢而已。借助于超算能力的計算機，人類就可以去解決那些在計算時代之前不敢嘗試的問題，實現(xiàn)只有想不到的，沒有做不到的境界。4.計算思維的特征（3）計算思維是思想，不是人造物。

計算思維不是硬件，而是計算這一概念用于求解問題、管理日常生活以及與他人交流和互動的思想。（4）計算思維是概念化，不是程序化。

計算機科學(xué)并不僅僅是計算機編程，像計算機科學(xué)家那樣去思維意味著遠不止能為計算機編程，還要求能夠在抽象的多個層次上思維。（3）計算思維是思想，不是人造物。1.計算思維的基本問題

計算思維是研究計算的思維，研究計算思維的基本問題是要了解哪些問題是可計算的，哪些問題是不可計算的，以及計算的復(fù)雜性如何度量。

（1）可計算性

一個問題是可計算的是指可以使用計算機在有限步驟內(nèi)完成計算。

圖靈論題給出可計算性的定義：一個問題是可計算的，當(dāng)且僅當(dāng)它在圖靈機上經(jīng)過有限步驟之后可以得到正確的結(jié)果。

8.3計算思維的內(nèi)涵1.計算思維的基本問題8.3計算思維的內(nèi)涵（2）計算復(fù)雜性計算復(fù)雜性就是指用計算機求解問題的難易程度，通常可用時間復(fù)雜度和空間復(fù)雜度來衡量。計算復(fù)雜性理論是用數(shù)學(xué)方法研究各類問題的計算復(fù)雜性學(xué)科。它研究各種可計算問題在計算過程中時間和空間的耗費情況，以及在不同計算模型下，使用不同類型的資源和不同數(shù)量的資源時，各類問題復(fù)雜性的本質(zhì)特性和相互關(guān)系。（2）計算復(fù)雜性例漢諾塔問題【問題描述】相傳古印度的僧侶在進行一種被稱為漢諾塔的游戲，如圖所示。條件是：每次只能移動一個盤；每次移動都不允許大盤移到小盤之上；

B塔作為輔助，中間過渡的塔。例漢諾塔問題【問題描述】相傳古印度的僧侶在進行一種被稱為【分析】這個移動過程很復(fù)雜與煩瑣，但規(guī)律性卻很強。使用遞歸調(diào)用技術(shù)來解決這個移動過程，先得找到一個遞歸調(diào)用模型。想要得到漢諾塔問題的簡單解法，著眼點應(yīng)該是移動A塔最底部的大盤，而不是其頂部的小盤?？紤]N個盤的一般情況。漢諾塔問題初始狀態(tài)N-1N【分析】漢諾塔問題初始狀態(tài)N-1N例

漢諾塔問題第一步：A塔上的N-1盤移至B塔漢諾塔的分解操作：N-1N例漢諾塔問題第一步：A塔上的N-1盤移至B塔漢諾塔的分解例

漢諾塔問題第二步：A塔上的N盤移至C塔漢諾塔的分解操作：N-1N例漢諾塔問題第二步：A塔上的N盤移至C塔漢諾塔的分解操作例

漢諾塔問題第三步：B塔上的N-1盤移至C塔漢諾塔的分解操作：N-1N例漢諾塔問題第三步：B塔上的N-1盤移至C塔漢諾塔的分解我們看到，步驟2只需移動一次就可以完成；步驟1與3的操作則完全相同，唯一區(qū)別僅在于各塔的作用有所不同。這樣，原問題被轉(zhuǎn)換為與原問題相同性質(zhì)的、規(guī)模小一些的新問題。即：HANOI(N,A,B,C)

可轉(zhuǎn)化為

HANOI(N-1,A,C,B)與HANOI(N-1,B,A,C)

其中HANOI中的參數(shù)分別表示需移動的盤數(shù)、起始塔、臨時塔與終止塔，這種轉(zhuǎn)換直至轉(zhuǎn)入的盤數(shù)為0為止，因為這時已無盤可移了，這就是需要找的遞歸調(diào)用模型。例

漢諾塔問題我們看到，步驟2只需移動一次就可以完成；步驟1與3的操作則完可以采用遞歸的方法，進行求解。問題：當(dāng)n=64時，即有移動64個盤子時，需要移動多少次盤子？耗費多少時間呢？h(n)=2×h(n-1)+1=2×[2×h(n-2)+1]+1=22×h(n-2)+1]+2+1……=2n×h(0)+2n-1+……+22+2+1=2n-1+……+22+2+1=2n-1=264-1=18446744073709551615假定移動一個盤子1秒，僧侶要花費5849億年的時間。假定計算機每秒可移動1000萬個盤子，也需要花費約58490年的時間。理論上可以計算的問題，實際上并不一定能行?？梢圆捎眠f歸的方法，進行求解。理論上可以計算的問題，實際上并2.計算思維的核心概念分類關(guān)注點核心概念計算可計算性和計算復(fù)雜性計算模型、可計算性、計算復(fù)雜性抽象關(guān)注對象的本質(zhì)特征抽象、抽象層次、概念模型、實現(xiàn)模型自動化信息處理的算法設(shè)計算法、程序，迭代、遞歸，啟發(fā)式策略、隨機策略，智能設(shè)計可靠和可信系統(tǒng)的構(gòu)建分解、復(fù)合、折中，可靠性、安全性、重用性評估復(fù)雜系統(tǒng)的性能評價評價指標與基準、瓶頸、冗余、容錯、性能仿真通信不同過程和對象間的可靠信息傳遞信息及其表示、信息量（熵）、編碼與解碼、信息壓縮、信息加密、校驗與糾錯、協(xié)議協(xié)作多個自主計算實體間的有效配合和時序控制同步、并發(fā)、并行、事件、服務(wù)記憶信息的表示、存儲和檢索數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)組織、檢索與索引、局部性與緩存2.計算思維的核心概念分類關(guān)注點核心概念計算可計算性和計算1.生物學(xué)計算生物學(xué)是指開發(fā)和應(yīng)用數(shù)據(jù)分析及理論的方法、數(shù)學(xué)建模、計算機仿真技術(shù)等。用于生物學(xué)、行為學(xué)、和社會群體系統(tǒng)研究的一門學(xué)科。由于生物學(xué)數(shù)據(jù)量和復(fù)雜性不斷增長，每14個月基因研究產(chǎn)生的數(shù)據(jù)就會翻一番，僅依靠觀察和實驗已難以應(yīng)付。必須依靠大規(guī)模計算技術(shù)，從海量信息中提取有用的數(shù)據(jù)。有生物序列的片段拼接、序列對接、基因識別、蛋白質(zhì)結(jié)構(gòu)預(yù)測、生物數(shù)據(jù)庫等。8.4計算思維的應(yīng)用1.生物學(xué)8.4計算思維的應(yīng)用2.腦科學(xué)-模擬大腦像計算機腦科學(xué)是研究人腦結(jié)構(gòu)與功能的綜合性學(xué)科，以揭示人腦高級意識功能為宗旨，與教育學(xué)、心理學(xué)、人工智能、認知學(xué)科以及創(chuàng)造學(xué)等學(xué)科有緊密聯(lián)系和交叉滲透。-通過機器學(xué)習(xí)分析腦成像通過分析腦成像技術(shù)（fMRI）

，對大腦的研究便可擴展至記憶、注意力、決定等。在某些情況下，腦成像技術(shù)甚至能夠識別研究對象所見到的圖像或者閱讀的詞語。-從患者身上提取皮膚細胞，轉(zhuǎn)成干細胞，再將干細胞分裂成所需要的神經(jīng)元，最后得到大腦細胞，首次在細胞水平上觀察精神分裂患者的腦細胞。2.腦科學(xué)-模擬大腦像計算機-從患者身上提取皮膚細胞3.計算化學(xué)

計算化學(xué)是根據(jù)基本的物理化學(xué)理論，以大量數(shù)值運算方式來探討化學(xué)系統(tǒng)的性質(zhì)。主要以分子模擬為工具實現(xiàn)各種核心化學(xué)的計算問題，架起了理論化學(xué)與實驗化學(xué)之間的橋梁。主要有如下研究方向：

1）化學(xué)中的數(shù)值計算

2）化學(xué)模擬3）化學(xué)中的模式識別

4）化學(xué)數(shù)據(jù)庫及檢索

5）化學(xué)專家系統(tǒng)3.計算化學(xué)4.