計(jì)算機(jī)科學(xué)基礎(chǔ)-第1章-計(jì)算思維導(dǎo)論

1、計(jì)算機(jī)科學(xué)基礎(chǔ),授課教師：林春薔,lcq@cuit.edu.cn QQ:14358983（教務(wù)處?教務(wù)管理? 教師課件）,課程介紹,《計(jì)算機(jī)科學(xué)基礎(chǔ)》是網(wǎng)絡(luò)工程專業(yè)、物聯(lián)網(wǎng)工程專業(yè)、信息安全專業(yè)和信息對(duì)抗技術(shù)專業(yè)本科生的必修課程。本課程主要對(duì)計(jì)算機(jī)科學(xué)基礎(chǔ)知識(shí)進(jìn)行介紹，要求學(xué)生了解計(jì)算機(jī)科學(xué)基礎(chǔ)相關(guān)概念和知識(shí)，掌握計(jì)算機(jī)的基本操作及辦公軟件的應(yīng)用，拓寬學(xué)生的計(jì)算機(jī)科學(xué)領(lǐng)域知識(shí)面。本課程是最先開設(shè)的計(jì)算機(jī)科學(xué)基礎(chǔ)知識(shí)課程，為后續(xù)《

2、C語言程序設(shè)計(jì)》、《數(shù)據(jù)結(jié)構(gòu)》、《計(jì)算機(jī)網(wǎng)絡(luò)》、《操作系統(tǒng)原理》、《網(wǎng)絡(luò)攻擊與防御》等計(jì)算機(jī)課程的學(xué)習(xí)提供必要的計(jì)算機(jī)基礎(chǔ)知識(shí)。,培養(yǎng)目標(biāo),通過《計(jì)算機(jī)科學(xué)基礎(chǔ)》課程，學(xué)生應(yīng)該了解計(jì)算思維、計(jì)算理論、算法、程序設(shè)計(jì)、計(jì)算機(jī)數(shù)據(jù)表示、操作系統(tǒng)、計(jì)算機(jī)網(wǎng)絡(luò)和計(jì)算機(jī)信息安全等計(jì)算機(jī)科學(xué)基礎(chǔ)概念知識(shí)，掌握Windows操作系統(tǒng)、Word、PowerPoint、Excel和虛擬機(jī)的使用。學(xué)生在了解了計(jì)算機(jī)科學(xué)基礎(chǔ)知識(shí)及概念的基礎(chǔ)上，通過學(xué)習(xí)，能對(duì)

3、問題進(jìn)行思考，對(duì)未知概念進(jìn)行資料查詢，對(duì)未知應(yīng)用軟件能初步使用，為將來學(xué)習(xí)其它計(jì)算機(jī)知識(shí)提供基本的學(xué)習(xí)方法。,課程簡介,總學(xué)時(shí)：40（其中20學(xué)時(shí)授課，20學(xué)時(shí)上機(jī)）授課內(nèi)容：1、計(jì)算機(jī)思維導(dǎo)論2、思維理論3、算法基礎(chǔ)4、程序設(shè)計(jì)語言5、數(shù)據(jù)表示及邏輯基礎(chǔ)6、操作系統(tǒng),課程簡介,7、計(jì)算機(jī)網(wǎng)絡(luò)8、計(jì)算機(jī)信息安全上機(jī)內(nèi)容：1、操作系統(tǒng)及命令行 （4學(xué)時(shí)）2、Word2007 （6學(xué)時(shí)）3、Excel2007 （4學(xué)

4、時(shí)）4、PowerPoint2007（4學(xué)時(shí)）5、測(cè)試（2學(xué)時(shí)）,成績?cè)u(píng)定,平時(shí)+實(shí)驗(yàn)：50%期末考試（閉卷）：50%,第1章 計(jì)算思維導(dǎo)論,主要內(nèi)容,1.1 科學(xué)與計(jì)算科學(xué)一、科學(xué)的概念二、計(jì)算科學(xué)與計(jì)算學(xué)科三、計(jì)算機(jī)科學(xué)與計(jì)算機(jī)學(xué)科 1.2 計(jì)算思維的概念,一、科學(xué)的概念 達(dá)爾文對(duì)科學(xué)定義：科學(xué)就是整理事實(shí)，從中發(fā)現(xiàn)規(guī)律并做出結(jié)論。,1.1 科學(xué)與計(jì)算科學(xué),達(dá)爾文的定義指出了科學(xué)的內(nèi)涵，即事實(shí)與規(guī)律?？茖W(xué)要

5、發(fā)現(xiàn)人所未知的事實(shí)，并以此為依據(jù)，實(shí)事求是。至于規(guī)律是指客觀事物之間內(nèi)在的本質(zhì)的必然聯(lián)系。,愛因斯坦認(rèn)為：設(shè)法將人們雜亂無章的感覺經(jīng)驗(yàn)加以整理，使之符合邏輯一致的思想系統(tǒng)，就叫科學(xué)。,科學(xué)作為一種存在的事物和完整的事物，是人類認(rèn)知的事物中最客觀的。但科學(xué)在形成過程中，作為追求的目的，卻如同人類的其他認(rèn)知一樣，是主觀的也是受心理制約的。,（續(xù)）,美國《韋伯斯特新世界詞典》對(duì)科學(xué)定義：科學(xué)是從確定研究對(duì)象的性質(zhì)和規(guī)律這一目的出發(fā)，通過觀察、

6、調(diào)查和實(shí)驗(yàn)得到的系統(tǒng)知識(shí)。 中國《辭?！穼?duì)科學(xué)定義：科學(xué)是運(yùn)用范疇、定理和定律等思維形式反映現(xiàn)實(shí)世界各種現(xiàn)象的本質(zhì)和運(yùn)動(dòng)規(guī)律的知識(shí)體系。,科學(xué)的定義：反映現(xiàn)實(shí)世界中各種現(xiàn)象及其客觀規(guī)律的知識(shí)體系。科學(xué)作為人類知識(shí)的最高形式，已成為人類社會(huì)普遍的文化理念。,（續(xù)）,科學(xué)的種類：,廣義的科學(xué)概念是自然科學(xué)、人文科學(xué)和社會(huì)科學(xué)等所有學(xué)科的總稱，狹義的科學(xué)概念則專指自然科學(xué)，有時(shí)甚至直指基礎(chǔ)理論科學(xué)。,（續(xù)）,如何界定自然科學(xué)？物理學(xué)，

7、化學(xué)，……,計(jì)算科學(xué)？數(shù)學(xué)？,（續(xù)）,主要內(nèi)容,1.1 科學(xué)與計(jì)算科學(xué)一、科學(xué)的概念二、計(jì)算科學(xué)與計(jì)算學(xué)科三、計(jì)算機(jī)科學(xué)與計(jì)算機(jī)學(xué)科 1.2 計(jì)算思維的概念,,美國能源部報(bào)告認(rèn)為：高端計(jì)算目前已經(jīng)與理論研究、實(shí)驗(yàn)手段一起，成為獲得科學(xué)發(fā)現(xiàn)的三大支柱。因此，理論科學(xué)、實(shí)驗(yàn)科學(xué)和計(jì)算科學(xué)是推動(dòng)人類文明進(jìn)步和科技發(fā)展的重要途徑。,1.1 科學(xué)與計(jì)算科學(xué),1.1 科學(xué)與計(jì)算科學(xué),計(jì)算科學(xué)/Computing Science：應(yīng)用高性

8、能計(jì)算能力預(yù)測(cè)和了解實(shí)際世界物質(zhì)運(yùn)動(dòng)或復(fù)雜現(xiàn)象演化規(guī)律的科學(xué)，它包括數(shù)值模擬、工程仿真、高效計(jì)算機(jī)系統(tǒng)和應(yīng)用軟件等。(計(jì)算機(jī)視角),二、計(jì)算科學(xué)與計(jì)算學(xué)科 計(jì)算科學(xué)/Computational Science：一種與數(shù)學(xué)模型構(gòu)建、定量分析方法以及利用計(jì)算機(jī)來分析和解決科學(xué)問題的研究領(lǐng)域。(計(jì)算視角),1993：高性能計(jì)算與通信--HPCC計(jì)劃 1996：加速戰(zhàn)略計(jì)算創(chuàng)新--ASCI計(jì)劃 2002：高性能計(jì)算系統(tǒng)-

9、-HPCS計(jì)劃,1.1 科學(xué)與計(jì)算科學(xué),2005：計(jì)算科學(xué)--確保美國的競爭力報(bào)告建議：應(yīng)將計(jì)算科學(xué)長期置于國家科學(xué)與技術(shù)領(lǐng)域中心的領(lǐng)導(dǎo)地位。 計(jì)算科學(xué)是運(yùn)用高級(jí)計(jì)算能力來理解和處理復(fù)雜問題的學(xué)科，已經(jīng)成為對(duì)科學(xué)領(lǐng)導(dǎo)力、經(jīng)濟(jì)競爭力以及國家安全都至關(guān)重要的一門科學(xué)。 我們相信計(jì)算科學(xué)是21世紀(jì)最重要的技術(shù)領(lǐng)域之一，因?yàn)樗鼘?duì)整個(gè)社會(huì)的進(jìn)步都是十分重要的。計(jì)算科學(xué)為研究者提供了一個(gè)獨(dú)特的窗口，他們可以通過它來研究那些不切實(shí)際或

10、很難解決的問題，為高經(jīng)濟(jì)效益提供高級(jí)工業(yè)方法，如高效設(shè)計(jì)比價(jià)格昂貴又費(fèi)時(shí)的風(fēng)洞試驗(yàn)更有效的機(jī)翼計(jì)算試驗(yàn)。,計(jì)算學(xué)科/Computational Discipline:利用計(jì)算科學(xué)對(duì)其他學(xué)科中的問題進(jìn)行計(jì)算機(jī)模擬或者其他形式的計(jì)算而形成的諸如計(jì)算物理、計(jì)算化學(xué)等學(xué)科統(tǒng)稱為計(jì)算學(xué)科。(計(jì)算視角),1.1 科學(xué)與計(jì)算科學(xué),計(jì)算學(xué)科/Computing Discipline:是對(duì)描述和變換信息的算法過程進(jìn)行系統(tǒng)的研究，它包括算法過程的理論、分析

11、、設(shè)計(jì)、效率分析、實(shí)現(xiàn)和應(yīng)用等。(計(jì)算機(jī)視角),學(xué)科：指高校中講授或研究知識(shí)的分科。,,計(jì)算學(xué)科是在數(shù)學(xué)和電子科學(xué)基礎(chǔ)上發(fā)展起來的一門新興學(xué)科，它既是一門理論性很強(qiáng)的學(xué)科，又是一門實(shí)踐性很強(qiáng)的學(xué)科。,1.1 科學(xué)與計(jì)算科學(xué),主要內(nèi)容,1.1 科學(xué)與計(jì)算科學(xué)一、科學(xué)的概念二、計(jì)算科學(xué)與計(jì)算學(xué)科三、計(jì)算機(jī)科學(xué)與計(jì)算機(jī)學(xué)科 1.2 計(jì)算思維的概念,三、計(jì)算機(jī)科學(xué)與計(jì)算機(jī)學(xué)科,1.1 科學(xué)與計(jì)算科學(xué),計(jì)算機(jī)科學(xué)/Computer S

12、cience：研究計(jì)算機(jī)及其周圍各種現(xiàn)象和規(guī)律的科學(xué)。 分類：理論計(jì)算機(jī)科學(xué)、應(yīng)用計(jì)算機(jī)科學(xué)。,計(jì)算機(jī)學(xué)科/Computer Discipline：即計(jì)算機(jī)科學(xué)與技術(shù)，它是研究計(jì)算機(jī)的設(shè)計(jì)與制造和利用計(jì)算機(jī)進(jìn)行信息獲取、表示、儲(chǔ)存、處理、控制等的理論、原則、方法和技術(shù)的學(xué)科。 計(jì)算機(jī)科學(xué)側(cè)重研究現(xiàn)象與揭示規(guī)律。計(jì)算機(jī)技術(shù)側(cè)重研制計(jì)算機(jī)及使用計(jì)算機(jī)進(jìn)行信息處理的方法和技術(shù)手段。,主要內(nèi)容,1.1 科學(xué)與計(jì)算科學(xué)一、科學(xué)

13、的概念二、計(jì)算科學(xué)與計(jì)算學(xué)科三、計(jì)算機(jī)科學(xué)與計(jì)算機(jī)學(xué)科 1.2 計(jì)算思維的概念,一、計(jì)算思維的定義 計(jì)算思維(Computational Thinking，CT) 周以真認(rèn)為：計(jì)算思維是運(yùn)用計(jì)算機(jī)科學(xué)的基礎(chǔ)概念去求解問題、設(shè)計(jì)系統(tǒng)和理解人類行為的涵蓋了計(jì)算機(jī)科學(xué)之廣度的一系列思維活動(dòng)。,1.2 計(jì)算思維的概念,針對(duì)上述定義解釋如下： ①求解問題中的計(jì)算思維 利用計(jì)算手段求解問題的過程是：首先要把實(shí)

14、際的應(yīng)用問題轉(zhuǎn)換為數(shù)學(xué)問題，可能是一組偏微分方程，其次將偏微分方程離散為一組代數(shù)方程組，然后建立模型、設(shè)計(jì)算法和編程實(shí)現(xiàn)，最后在實(shí)際的計(jì)算機(jī)中運(yùn)行并求解。 前兩步是計(jì)算思維中的抽象，后兩步是計(jì)算思維中的自動(dòng)化。,1.2 計(jì)算思維的概念,②設(shè)計(jì)系統(tǒng)中的計(jì)算思維 R.Karp認(rèn)為：任何自然系統(tǒng)和社會(huì)系統(tǒng)都可視為一個(gè)動(dòng)態(tài)演化系統(tǒng)，演化伴隨著物質(zhì)、能量和信息的交換，這種交換可以映射為符號(hào)變換，使之能用計(jì)算機(jī)進(jìn)行離散的符號(hào)處理。

15、 當(dāng)動(dòng)態(tài)演化系統(tǒng)抽象為離散符號(hào)系統(tǒng)后，就可以采用形式化的規(guī)范描述，建立模型、設(shè)計(jì)算法和開發(fā)軟件來揭示演化的規(guī)律，實(shí)時(shí)控制系統(tǒng)的演化并自動(dòng)執(zhí)行。,1.2 計(jì)算思維的概念,③理解人類行為中的計(jì)算思維 王飛躍認(rèn)為(中科院)：計(jì)算思維是基于可計(jì)算的手段，以定量化的方式進(jìn)行的思維過程。計(jì)算思維就是應(yīng)對(duì)信息時(shí)代新的社會(huì)動(dòng)力學(xué)和人類動(dòng)力學(xué)所要求的思維。在人類的物理世界、精神世界和人工世界等三個(gè)世界中，計(jì)算思維是建設(shè)人工世界需要的主要思維

16、方式。 利用計(jì)算手段來研究人類的行為，可視為社會(huì)計(jì)算，即通過各種信息技術(shù)手段，設(shè)計(jì)、實(shí)施和評(píng)估人與環(huán)境之間的交互。,1.2 計(jì)算思維的概念,二、計(jì)算思維的詳細(xì)描述,計(jì)算思維是通過約簡、嵌入、轉(zhuǎn)化和仿真等方法，把一個(gè)看來困難的問題重新闡釋成一個(gè)人們知道怎樣解決的問題。計(jì)算思維是一種遞歸思維，是一種并行處理，是一種把代碼譯成數(shù)據(jù)又能把數(shù)據(jù)譯成代碼。計(jì)算思維是一種采用抽象和分解來控制龐雜的任務(wù)或進(jìn)行巨大復(fù)雜系統(tǒng)設(shè)計(jì)的方法，是一種基

17、于關(guān)注點(diǎn)分離的方法。,1.2 計(jì)算思維的概念,計(jì)算思維是一種選擇合適的方式去陳述一個(gè)問題，或?qū)σ粋€(gè)問題的相關(guān)方面建模并使其易于處理的思維方法。計(jì)算思維是按照預(yù)防、保護(hù)及通過冗余、容錯(cuò)和糾錯(cuò)方式，從最壞情況進(jìn)行系統(tǒng)恢復(fù)的一種思維方法。計(jì)算思維是利用啟發(fā)式推理尋求解答，也即在不確定情況下的規(guī)劃、學(xué)習(xí)和調(diào)度的思維方法。計(jì)算思維是利用海量數(shù)據(jù)來加快計(jì)算，在時(shí)間和空間之間，在處理能力和存儲(chǔ)容量之間進(jìn)行折中的思維方法。,1.2 計(jì)算思維的概念

18、,三、計(jì)算思維的特征,1.2 計(jì)算思維的概念,1.概念化，不是程序化 計(jì)算機(jī)科學(xué)不是計(jì)算機(jī)編程。像計(jì)算機(jī)科學(xué)家那樣去思維意味著遠(yuǎn)遠(yuǎn)不僅限于計(jì)算機(jī)編程，還要求能夠在抽象的多個(gè)層次上思維。計(jì)算機(jī)科學(xué)不只是關(guān)注計(jì)算機(jī)，就像音樂產(chǎn)業(yè)不只是關(guān)注麥克風(fēng)一樣。 2.根本的，不是刻板的技能 計(jì)算思維是一種根本技能，是每一個(gè)人為了在現(xiàn)代社會(huì)中發(fā)揮職能所必須掌握的?？贪宓募寄芤馕吨唵蔚臋C(jī)械重復(fù)。,3.是人的，不是計(jì)算機(jī)的思維

19、 計(jì)算思維是人類求解問題的一條途徑，但決非要使人類像計(jì)算機(jī)那樣地思考。計(jì)算機(jī)枯燥且沉悶，人類聰穎且富有想象力。是人類賦予計(jì)算機(jī)激情。計(jì)算機(jī)賦予人類強(qiáng)大的計(jì)算能力，人類應(yīng)該好好的利用這種力量去解決各種需要大量計(jì)算的問題。 4.是思想，不是人造物 不只是將生產(chǎn)的軟硬件等人造物到處呈現(xiàn)給我們的生活，更重要的是計(jì)算概念，它被人們用來求解問題、管理日常生活，以及與他人進(jìn)行交流和互動(dòng)。,1.2 計(jì)算思維的概念,5.數(shù)學(xué)和工

20、程思維的互補(bǔ)與融合 計(jì)算機(jī)科學(xué)在本質(zhì)上源自數(shù)學(xué)思維，它的形式化基礎(chǔ)建筑于數(shù)學(xué)之上。計(jì)算機(jī)科學(xué)又從本質(zhì)上源自工程思維，因?yàn)槲覀兘ㄔ斓氖悄軌蚺c現(xiàn)實(shí)世界互動(dòng)的系統(tǒng)。所以設(shè)計(jì)思維是數(shù)學(xué)和工程思維的互補(bǔ)與融合。 6.面向所有的人，所有地方 當(dāng)計(jì)算思維真正融入人類活動(dòng)的整體時(shí)，它作為一個(gè)問題解決的有效工具，人人都應(yīng)當(dāng)掌握，處處都會(huì)被使用。,1.2 計(jì)算思維的概念,四、計(jì)算思維的本質(zhì) 抽象(Abstract)、自動(dòng)化(

21、Automation)。 它反映了計(jì)算的根本問題，即什么能被有效的自動(dòng)進(jìn)行。,1.2 計(jì)算思維的概念,計(jì)算是抽象的自動(dòng)執(zhí)行，自動(dòng)化需要某種計(jì)算機(jī)去解釋抽象。 從操作層面上講，計(jì)算就是如何尋找一臺(tái)計(jì)算機(jī)去求解問題，隱含地說就是要確定合適的抽象，選擇合適的計(jì)算機(jī)去解釋執(zhí)行該抽象，后者就是自動(dòng)化。,五、計(jì)算思維與計(jì)算機(jī)的關(guān)系,1.2 計(jì)算思維的概念,計(jì)算思維雖然具有計(jì)算機(jī)的許多特征，但是計(jì)算思維本身并不是計(jì)算機(jī)的專屬。實(shí)際上，

22、即使沒有計(jì)算機(jī)，計(jì)算思維也會(huì)逐步發(fā)展，甚至有些內(nèi)容與計(jì)算機(jī)沒有關(guān)系。但是，正是由于計(jì)算機(jī)的出現(xiàn)，給計(jì)算思維的發(fā)展帶來了根本性的變化。,,一、生物學(xué) 計(jì)算機(jī)科學(xué)許多領(lǐng)域滲透到生物信息學(xué)中的應(yīng)用研究，包括數(shù)據(jù)庫、數(shù)據(jù)挖掘、人工智能、算法、圖形學(xué)、軟件工程、并行計(jì)算和網(wǎng)絡(luò)技術(shù)等都被用于生物計(jì)算的研究。,計(jì)算思維的應(yīng)用領(lǐng)域,從各種生物的DNA數(shù)據(jù)中挖掘DNA序列自身規(guī)律和DNA序列進(jìn)化規(guī)律，可以幫助人們從分子層次上認(rèn)識(shí)生命的本質(zhì)及其進(jìn)化

23、規(guī)律 DNA序列實(shí)際上是一種用四種字母表達(dá)的“語言”。,二、腦科學(xué) 腦科學(xué)是研究人腦結(jié)構(gòu)與功能的綜合性學(xué)科它以揭示人腦高級(jí)意識(shí)功能為宗旨，與心理學(xué)、人工智能、認(rèn)知科學(xué)和創(chuàng)造學(xué)等有著交叉滲透。,計(jì)算思維的應(yīng)用領(lǐng)域,美國神經(jīng)生理學(xué)家羅杰·斯佩里進(jìn)行了裂腦實(shí)驗(yàn)，提出大腦兩半球功能分工理論。他認(rèn)為：大腦左右半球完全可以以不同的方式進(jìn)行思維活動(dòng)，左腦側(cè)重于抽象思維，如邏輯抽象、演繹推理和語言表達(dá)等；右腦側(cè)重于形象思維，如直

24、覺情感、想象創(chuàng)新等。,三、化學(xué) 計(jì)算機(jī)科學(xué)在化學(xué)中的應(yīng)用包括：化學(xué)中的數(shù)值計(jì)算、化學(xué)模擬、化學(xué)中的模式識(shí)別、化學(xué)數(shù)據(jù)庫及檢索、化學(xué)專家系統(tǒng)等。,計(jì)算思維的應(yīng)用領(lǐng)域,基于非結(jié)構(gòu)網(wǎng)格和分區(qū)并行算法，為求解多組化學(xué)反應(yīng)流動(dòng)守恒方程組開發(fā)了單程序多數(shù)據(jù)流形式的并行程序，對(duì)己有的預(yù)混可燃?xì)怏w中高速飛行的彈丸的爆轟現(xiàn)象進(jìn)行了有效的數(shù)值模擬。,四、經(jīng)濟(jì)學(xué) 計(jì)算博弈論正在改變?nèi)藗兊乃季S方式。 囚徒困境是博弈論專家設(shè)計(jì)的典型示例，

25、但是囚徒困境博弈模型可以用來描述兩家企業(yè)的價(jià)格大戰(zhàn)等許多經(jīng)濟(jì)現(xiàn)象。,計(jì)算思維的應(yīng)用領(lǐng)域,五、藝術(shù) 計(jì)算機(jī)藝術(shù)是科學(xué)與藝術(shù)相結(jié)合的一門新興的交叉學(xué)科，它包括繪畫、音樂、舞蹈、影視、廣告、書法模擬、服裝設(shè)計(jì)、圖案設(shè)計(jì)、產(chǎn)品和建筑造型設(shè)計(jì)以及電子出版物等眾多領(lǐng)域。,計(jì)算思維的應(yīng)用領(lǐng)域,六、其他領(lǐng)域,計(jì)算思維的應(yīng)用領(lǐng)域,工程學(xué)(電子、土木、機(jī)械、航空航天等)： 計(jì)算高階項(xiàng)可以提高精度,進(jìn)而降低重量、減少浪費(fèi)并節(jié)省制造成本；波音7

26、77飛機(jī)完全是采用計(jì)算機(jī)模擬測(cè)試的，沒有經(jīng)過風(fēng)洞測(cè)試。社會(huì)科學(xué)： 社交網(wǎng)絡(luò)是MySpace和YouTube等發(fā)展壯大的原因之一；統(tǒng)計(jì)機(jī)器學(xué)習(xí)被用于推薦和聲譽(yù)服務(wù)系統(tǒng),例如Netflix和聯(lián)名信用卡等。,地質(zhì)學(xué)、天文學(xué)、數(shù)學(xué)、醫(yī)學(xué)、法律、娛樂、體育等,計(jì)算學(xué)科的典型問題,一、排序問題 排序是把給定數(shù)據(jù)集合中的元素按照一定的標(biāo)準(zhǔn)來安排先后次序的過程。,選擇排序算法：對(duì)給定的一個(gè)數(shù)據(jù)表，算法從第一個(gè)元素開始掃描整個(gè)列表，找到

27、最小或最大的元素，并將其與第一個(gè)位置的元素交換。然后算法從第二個(gè)位置的元素開始掃描剩下的列表，找到次小或次大的元素，并將其與第二個(gè)位置的元素交換。如此循環(huán)，直到所有的元素都被排好序?yàn)橹埂?選擇排序算法是由一個(gè)雙層循環(huán)控制，算法時(shí)間復(fù)雜度是O(n2),部分排序算法的時(shí)間效率比較 (單位：毫秒),計(jì)算學(xué)科的典型問題,每一種排序算法對(duì)時(shí)間的效率和空間的要求不盡相同，沒有哪一種是絕對(duì)最優(yōu)的，在實(shí)用時(shí)需要根據(jù)不同情況適當(dāng)選用，也可多種方法結(jié)

28、合使用。,二、漢諾塔問題,計(jì)算學(xué)科的典型問題,印度古老傳說：在世界中心貝拿勒斯的圣廟里，一塊黃銅板上插著三根寶石針A、B和C。印度教的主神梵天在創(chuàng)造世界時(shí)，在其中一根針上從下到上地穿好了由大到小的64片金片。,不論白天黑夜，總有一個(gè)僧侶在按下面的法則移動(dòng)這些金片：一次只移動(dòng)一片，不管在哪根針上，小片必須在大片上面。僧侶們預(yù)言，當(dāng)所有金片移到另外一根針上時(shí)，世界將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。,不管這個(gè)傳說的可信度有

29、多大，如果僅考慮把64片金片，由一根針上移到另一根針上，并且始終保持上小下大的順序。這需要多少次移動(dòng)呢？這里需要使用遞歸算法。 假設(shè)有n片，移動(dòng)次數(shù)是f(n) 顯然f(1)=1，f(2)=3，f(3)=7，且f(k+1)=2*f(k)+1 不難證明f(n)=2^n-1 當(dāng)n=64時(shí)，f(64)=2^64-1=18446744073709551615次 如果每秒鐘移動(dòng)一次，共需多長時(shí)間呢？

30、一年有31536000秒，則18446744073709551615/31536000=5849億年,計(jì)算學(xué)科的典型問題,三、國王的婚姻,計(jì)算學(xué)科的典型問題,國王：艾述(喜愛數(shù)學(xué)) 宰相：孔喚石(數(shù)學(xué)家) 公主：秋碧貞楠(鄰國)公主：求出48770428644836899的一個(gè)真因子國王：2,3,4,┅,30000多數(shù)據(jù)(一天)公主：驗(yàn)證一下，223092871宰相：將全國百姓按自然數(shù)的順序編號(hào)，百姓用自己的編號(hào)去除公主的數(shù)

31、，誰除盡來領(lǐng)賞。,童話說明：①國王本人計(jì)算(串行算法，時(shí)間復(fù)雜性) ②全國百姓計(jì)算(并行算法，空間復(fù)雜性),四、旅行商問題（旅行推銷員問題、貨郎擔(dān)問題） 旅行商問題(TSP)的描述：一位商人去n個(gè)城市推銷貨物，所有城市走一遍后，再回到起點(diǎn)，問如何事先確定好一條最短的路線，使其旅行的費(fèi)用最少。,計(jì)算學(xué)科的典型問題,路徑ABCDA的總距離是：4+2+4+2=12路徑ABDCA的總距離是：4+6+4+6=20路

32、徑ACBDA的總距離是：6+2+6+2=16路徑ACDBA的總距離是：6+4+6+4=20路徑ADCBA的總距離是：2+4+2+4=12路徑ADBCA的總距離是：2+6+2+6=16,城市數(shù)目為4時(shí)，組合路徑數(shù)為6 城市數(shù)目為n時(shí)，組合路徑數(shù)為(n-1)! 當(dāng)城市數(shù)目不多時(shí)要找到最短距離的路線并不難，但隨著城市數(shù)目的不斷增大，組合路線數(shù)將呈指數(shù)級(jí)數(shù)規(guī)律急劇增長，以至到達(dá)無法計(jì)算的地步，這就是所謂的組合爆炸問題。,計(jì)

33、算學(xué)科的典型問題,假如城市的數(shù)目增為20個(gè)，組合路徑數(shù)則為(20-1)！≈1.216×1017 若計(jì)算機(jī)以每秒檢索1000萬條路線的速度計(jì)算，也需要花上386年的時(shí)間。,本章小結(jié),科學(xué)的定義和種類理論科學(xué)、實(shí)驗(yàn)科學(xué)、計(jì)算科學(xué)計(jì)算科學(xué)和計(jì)算學(xué)科(不同視角)計(jì)算機(jī)科學(xué)與計(jì)算機(jī)學(xué)科(不同視角),計(jì)算思維的定義、詳細(xì)描述、特征和本質(zhì) 計(jì)算思維與計(jì)算機(jī)的關(guān)系 計(jì)算思維的應(yīng)用領(lǐng)域 （生物學(xué)、腦科學(xué)、化學(xué)、經(jīng)濟(jì)學(xué)、藝

34、術(shù)、工程學(xué)、社會(huì)科學(xué)等） 計(jì)算學(xué)科的典型問題 （通過排序問題、漢諾塔問題、國王的婚姻、旅行商問題來說明人所固有的能力與局限性、計(jì)算機(jī)的計(jì)算能力與局限性，以及問題到底有多復(fù)雜）,本章小結(jié),課后：,通過互聯(lián)網(wǎng)搜索周以真(Jeannette M. Wing)教授的《計(jì)算思維》/ 《Computational Thinking》一文(中文與英文版本)，并認(rèn)真閱讀。了解周以真教授的簡歷。觀看視屏：尼古拉 特斯拉,END,參考文獻(xiàn),《計(jì)算