大學計算機基礎之計算機思維基礎教學課件

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

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

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

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

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

--理論研究

--實驗研究

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

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

科學是以觀察或實驗為依據(jù)的，經(jīng)驗的描述自然現(xiàn)象近幾百年：

派生出理論的

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

派生出計算的

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

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

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

1.計算思維概念的引入

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

-BPC（擴大計算參與面）

-CPATH（大學計算教育振興途徑）

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

-CE21（21世紀計算科學教育）

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

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

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

計算---Computation

通信---Communication

協(xié)作---Coordination

記憶---Recollection

自動化-Automation

評估---Evaluation

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

計算---Co例1計算函數(shù)f(x)區(qū)間[a,b]上的積分。在高等數(shù)學中，計算積分是使用牛頓—萊布尼茲公式，即首先求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服務窗口排隊（1）問題只有一個服務窗口，有三個服務顧客，分別需要服務時間為：

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

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

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

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

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

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

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

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

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

（1）可計算性

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

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

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

B塔作為輔助，中間過渡的塔。例漢諾塔問題【問題描述】相傳古印度的僧侶在進行一種被稱為【分析】這個移動過程很復雜與煩瑣，但規(guī)律性卻很強。使用遞歸調用技術來解決這個移動過程，先得找到一個遞歸調用模型。想要得到漢諾塔問題的簡單解法，著眼點應該是移動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ū)別僅在于各塔的作用有所不同。這樣，原問題被轉換為與原問題相同性質的、規(guī)模小一些的新問題。即：HANOI(N,A,B,C)

可轉化為

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

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

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

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

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

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

2）化學模擬3）化學中的模式識別

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

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