第1章 計算思維

第一章計算科學(xué)與計算思維教學(xué)目標了解科學(xué)、計算、計算科學(xué)與計算學(xué)科、思維與計算思維的基本概念了解計算學(xué)科與其它學(xué)科之間的關(guān)系了解計算思維的作用，學(xué)會計算思維的基本方法，掌握其基本技能了解運用計算機求解問題的基本思路和一般過程知識要點計算、可計算性以及計算學(xué)科的概念思維、計算思維進行問題求解的一般過程計算思維在人類社會的經(jīng)濟、科技等各領(lǐng)域發(fā)展中的作用和對人的能力發(fā)展的影響計算科學(xué)研究與應(yīng)用（普適計算、網(wǎng)格計算和云計算、人工智能、物聯(lián)網(wǎng)等）重點！舉案引思1、皇帝會答應(yīng)大臣的請賞？古代皇帝和他的大臣下象棋，大臣贏了?；实蹎柎蟪迹骸澳阆胍玫绞裁椽勝p？”大臣向皇帝說：“微臣不敢奢求，只要皇上按棋盤的格子數(shù)，依次給予1粒黃豆，2粒黃豆，4粒黃豆，8粒黃豆，16粒黃豆，…….按此規(guī)律(每次給出黃豆的數(shù)目是前一次給出黃豆數(shù)目的2倍)給64次就無比地感謝皇上了”。請問皇帝會答應(yīng)這個大臣的請賞嗎？你能很快(10秒內(nèi))給出答案嗎？2、到底誰說真話？張三說:李四在說謊;李四說:王五在說謊;王五說:張三和李四都在說謊。已知三人中只有一人說真話。舉案引思3、如圖1-1所示，從哪一點出發(fā)開始旅行既能游覽每一個景點(A-J表示景點，連線表示通路)，又不走重復(fù)路線？1.1什么是思維，思維有哪些種類，思維對人的能力的影響1、思維的概念：思維是人腦對現(xiàn)實事物的概括、加工，最終揭示其本質(zhì)特征和內(nèi)在規(guī)律的活動；人腦對信息的加工處理包括分析、抽象、綜合、概括等。思維是人的高級心理活動，認識事物的高級形式；是人和動物的根本區(qū)別之一，是人的重要本質(zhì)所在。人類文明，人化的世界，重要源泉是人的思維。

2、思維的作用：思維對于知識具有本原作用。思維是人類獲得知識的途徑，加工知識的機器。3、思維的分類：思維分類方法思維的形式從思維的進程方向可分為橫向思維、縱向思維、發(fā)散思維、收斂思維從思維的抽象程度可分為直觀行動思維(操作思維、實踐思維)、形象思維、抽象思維(邏輯思維或理論思維)從思維的形成與應(yīng)用領(lǐng)域可分為日常思維、科學(xué)思維科學(xué)思維是指形成并運用于科學(xué)認識活動的人腦，借助信息符號對感性認識材料,經(jīng)過整理、歸納、加工處理，形成概念、分析、判斷和推理，揭示事物的本質(zhì)和內(nèi)在規(guī)律的思維活動。簡而言之，科學(xué)思維就是人們認識自然界、社會和人類意識的本質(zhì)和客觀規(guī)律性的高級思維活動。特點是比日常思維更具理性、客觀性、嚴謹性、系統(tǒng)性與科學(xué)性?？茖W(xué)思維的分類理論思維實證思維計算思維對事物的感性認識資料，經(jīng)過抽象、概括，形成描述事物本質(zhì)的概念，主要以推理和演繹的方法，探尋概念之間相互聯(lián)系的一種思維活動。理論源于數(shù)學(xué)，理論思維支撐著所有的學(xué)科領(lǐng)域。通過觀察和實驗的手段，揭示自然規(guī)律法則的一種思維方法。特征是觀察、整理、歸納、對比和驗證。人們往往要借助于某些特定的設(shè)備、工具，通過實驗，獲取資料，以便分析研究。例如星球運行規(guī)律與萬有引力的發(fā)現(xiàn)，設(shè)備性能的物理測量、化學(xué)的分解與化合、生物的解剖等實驗，就是認識事物本質(zhì)和變化規(guī)律的有效手段和思維方法。又叫構(gòu)造思維，是指從具體的算法設(shè)計規(guī)范入手，通過算法過程的構(gòu)造與實施，來解決給定問題的一種思維方法。目前被廣泛接受的計算思維概念是2006年美籍華裔計算機科學(xué)家周以真教授首次明確提出的定義：計算思維就是運用計算機科學(xué)的基礎(chǔ)概念去求解問題、設(shè)計系統(tǒng)和理解人類行為的涵蓋了計算機科學(xué)之廣度的一系列思維活動。1.2計算思維的本質(zhì)、特征，及其對人能力的影響1、本質(zhì):抽象(Abstract)和自動化(Automation)

2、特征:是概念化，不是程序化計算機科學(xué)不是計算機編程。像計算機科學(xué)家那樣去思維，意味著遠遠不是只能為計算機編程，還要求能夠在抽象的多個層次上思維。計算機科學(xué)不只是關(guān)于計算機，就像音樂產(chǎn)業(yè)不只是關(guān)于鋼琴一樣。

是根本的，不是刻板的技能是人的，不是計算機的思維是思想，不是人造品是數(shù)學(xué)思維和工程思維的互補與融合面向所有的人，所有地方關(guān)注依舊亟待理解和解決的智力上及有挑戰(zhàn)性并且引人入勝的科學(xué)問題。3、計算思維品質(zhì)對人的能力影響作用問題抽象層次的能力是衡量人的思維品質(zhì)的重要方面。根據(jù)求解問題的需要，在分析問題的過程中，人們可以對問題進行多層次的抽象，將注意力集中在感興趣的抽象層次或關(guān)系相對密切的上下層，拋棄那些不感興趣的(不重要的)層次或細節(jié)，使問題分析相對簡單，以控制問題解決的復(fù)雜性。抽象的概念是由具體概念依其“共性”而產(chǎn)生的，把具體概念的諸多個性排出，集中描述其共性，就會產(chǎn)生一個抽象性的概念。人的大腦思維方法和思維品質(zhì)的差異決定著：同一問題解決辦法和處理方式各不相同。其付出的代價與取得效果甚至可能天壤之別。4、計算思維的應(yīng)用領(lǐng)域計算思維是每個人應(yīng)當具備的基本技能，也是創(chuàng)新人才的基本要求和專業(yè)素質(zhì)，每個人都應(yīng)當學(xué)習和應(yīng)用計算思維。正如印刷出版促進了閱讀、寫作和算術(shù)的傳播一樣，計算和計算機也促進著計算思維的傳播。迄今為止，計算思維不僅滲透到每個人的生活，而且對生物信息學(xué)、生物計算、專家系統(tǒng)、經(jīng)濟學(xué)等學(xué)科領(lǐng)域產(chǎn)生了重大影響，在科技創(chuàng)新與教育教學(xué)中起著非常重要的作用。計算思維領(lǐng)域提出的新思想、新方法不斷地促進自然科學(xué)、工程技術(shù)和社會經(jīng)濟等領(lǐng)域產(chǎn)生革命性的發(fā)展。典型的應(yīng)用領(lǐng)域有：生物信息學(xué)仿生計算

專家系統(tǒng)

數(shù)值計算

工程、模型模擬

統(tǒng)計模式識別

虛擬現(xiàn)實

1.3科學(xué)與計算科學(xué)科學(xué)是反映現(xiàn)實世界中各種現(xiàn)象的本質(zhì)和運動規(guī)律的知識體系?！翱茖W(xué)”在現(xiàn)實生活中，被人們普遍簡單樸實而又模糊地認為就是“真實的”、“客觀的”意思。1、科學(xué)的分類

分類方式劃分的類型按照研究對象的不同自然科學(xué)、社會科學(xué)、思維科學(xué)按照人類目標的不同廣義科學(xué)、狹義科學(xué)按照人類對自然規(guī)律利用的直接程度自然科學(xué)、實驗科學(xué)按照與實踐聯(lián)系的不同理論科學(xué)、技術(shù)科學(xué)、應(yīng)用科學(xué)按照研究手段和方法的不同理論科學(xué)、實驗科學(xué)、計算科學(xué)2、計算科學(xué)與計算學(xué)科

從計算的角度來看，計算科學(xué)（ComputationalScience）又稱之為科學(xué)計算，是一種與數(shù)學(xué)建模、定量分析方法和采用計算機進行分析、解決科學(xué)問題的研究領(lǐng)域。從計算機的角度來說，計算科學(xué)(ComputingScience)是應(yīng)用高性能計算能力預(yù)測和了解客觀世界物質(zhì)運動或復(fù)雜現(xiàn)象演化規(guī)律的科學(xué)，它包括數(shù)值模擬、工程仿真、高效計算機系統(tǒng)和應(yīng)用軟件等。3、學(xué)科

一是指學(xué)術(shù)的分類；指一定科學(xué)領(lǐng)域或一門科學(xué)的分支。如自然科學(xué)中的物理學(xué)、化學(xué)；社會科學(xué)中的法學(xué)、社會學(xué)等。二是“教學(xué)科目”的簡稱，也稱“科目”。教學(xué)中按邏輯程序組織的一定知識和技能范圍的單位。如中小學(xué)的數(shù)學(xué)、物理、語文、音樂等；高等學(xué)校中講授或研究知識的分科。

從計算的角度來說，利用計算科學(xué)對其它學(xué)科的問題進行計算機模擬或者其它形式的計算而形成的學(xué)科(諸如計算化學(xué)、生物計算或計算生物、計算物理等學(xué)科統(tǒng))稱為計算學(xué)科(ComputationalDiscipline)。從計算機的角度來說，計算學(xué)科(ComputingDiscipline)是對描述和變換信息的算法過程進行系統(tǒng)的研究，它包括算法過程的理論、分析、設(shè)計、效率分析、實現(xiàn)和應(yīng)用等。計算學(xué)科來源于對數(shù)理邏輯、算法理論、計算模型和自動計算機器的研究，形成于20世紀40年代。

4、計算學(xué)科

計算學(xué)科的基本問題是“什么能被(有效地)自動執(zhí)行”,討論可行性的有關(guān)內(nèi)容，包括:什么是(實際)可計算的，什么是(實際)不可計算的，如保證計算的自動性、有效性和正確性。計算學(xué)科是在數(shù)學(xué)和電子科學(xué)基礎(chǔ)上發(fā)展起來的一門新興學(xué)科，它既是一門深入理論研究的學(xué)科，又是一門實踐性很強的學(xué)科。計算學(xué)科包括：計算機科學(xué)與技術(shù)(Computerscienceandtechnology)和計算機科學(xué)與工程(ComputerScienceandEngineering)5、計算機科學(xué)與計算機學(xué)科的關(guān)系計算機學(xué)科(ComputerDiscipline),即計算機科學(xué)與技術(shù)，是研究計算機的設(shè)計與制造，利用計算機進行信息獲取、表示、存儲、處理、控制等的理論、原則、方法和技術(shù)的學(xué)科。它包括科學(xué)和技術(shù)兩個方面。計算機科學(xué)側(cè)重于研究現(xiàn)象和揭示規(guī)律；計算機技術(shù)側(cè)重于研制計算機及使用計算機進行信息技術(shù)處理的方法和技術(shù)手段。計算機科學(xué)分為理論計算機科學(xué)與應(yīng)用計算機科學(xué)兩部分。理論計算機科學(xué)包括計算理論、信息與編碼理論、算法與數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計語言理論、形式化方法、并行與分布計算系統(tǒng)、數(shù)據(jù)庫與信息檢索等；應(yīng)用計算機科學(xué)包括人工智能、計算機系統(tǒng)結(jié)構(gòu)、計算機圖形學(xué)、計算機視覺、計算機安全與密碼學(xué)、信息科學(xué)與軟件工程等。計算機人才的專業(yè)基本能力包括計算思維能力、算法分析與設(shè)計能力、程序設(shè)計與實現(xiàn)能力、系統(tǒng)分析與應(yīng)用開發(fā)能力。但是，學(xué)科形態(tài)的不同，相應(yīng)類型的人才需要強調(diào)的能力是有區(qū)別的。比如，研究型人才強調(diào)的是理論形態(tài)的內(nèi)容，培養(yǎng)的重點在于強化計算思維分析能力、算法分析與設(shè)計能力、系統(tǒng)分析設(shè)計能力；工程應(yīng)用型人才強調(diào)的是涉及形態(tài)的內(nèi)容，培養(yǎng)的重點在于強化計算思維應(yīng)用能力、系統(tǒng)分析與開發(fā)應(yīng)用能力、程序設(shè)計與實現(xiàn)能力。6、計算學(xué)科的三個形態(tài)計算機科學(xué)與技術(shù)學(xué)科中的三個學(xué)科形態(tài)（理論、抽象和設(shè)計）描述了該學(xué)科的研究與實踐的三種形態(tài)，對應(yīng)于計算機科學(xué)與技術(shù)學(xué)科中問題求解的三個過程，也是學(xué)科方法論最根本的內(nèi)容。理論理論源于數(shù)學(xué)，其主要要素為定義、公理、定理證明和結(jié)果。即用定義和公理來表達被研究對象的特征，用定理來假設(shè)對象之間的基本性質(zhì)和對象之間可能存在的關(guān)系，通過證明來確定這些關(guān)系是否成立，最后得出相應(yīng)的結(jié)果(論)。

抽象

即抽出事物的本質(zhì)特征，從現(xiàn)象中把握本質(zhì)的認知過程和思維方法。抽象的結(jié)果是概念、符號。抽象建模是自然科學(xué)之根本。其主要要素為確定可能的實現(xiàn)環(huán)境并形成假設(shè)，構(gòu)造模型并給出預(yù)測結(jié)果，設(shè)計實驗并采集數(shù)據(jù)，進行試驗結(jié)果分析。設(shè)計

設(shè)計源于工程科學(xué)，即廣泛采用工程科學(xué)的研究方法來開發(fā)或求解某個問題的系統(tǒng)和裝備。在計算學(xué)科中，理論的主要要素為需求分析、規(guī)格說明、設(shè)計和實現(xiàn)方法、測試和分析。計算理論是研究使用計算機解決計算問題的數(shù)學(xué)理論。它有3個核心領(lǐng)域:自動機理論、可計算性理論和計算的復(fù)雜性理論。自動機理論是數(shù)理語言學(xué)中研究抽象自動機的理論。抽象自動機是一種能夠識別語言的抽象的裝置.7、計算理論請注意：它不是真正物理的機器，而是表示計算機運算方式的抽象的邏輯關(guān)系系統(tǒng)，這樣的抽象自動機可以用來檢驗輸入的符號串是不是語言中合格的句子，如果是合格的句子，自動機就接收它，如果不是，就不接收它。圖示如下：可計算性理論的中心問題是建立計算的數(shù)學(xué)模型,進而研究哪些是可計算的,哪些是不可計算的。它通過建立計算的數(shù)學(xué)模型(如抽象計算機),精確區(qū)分哪些是可計算的，哪些是不可計算的。計算的過程就是執(zhí)行算法的過程。可計算性理論的重要課題之一是將算法精確化。算法精確化的途徑很多,其中之一是通過定義抽象計算機,把算法看作抽象計算機的程序。通常把那些存在算法計算其值的函數(shù)叫做可計算函數(shù)。因此,可計算函數(shù)的精確定義為：能夠在抽象計算機上編出程序,并計算其值的函數(shù)?？捎嬎阈岳碚撌撬惴ㄔO(shè)計與分析的基礎(chǔ),也是計算機科學(xué)的理論基礎(chǔ)?？捎嬎阈允呛瘮?shù)的一個特性。設(shè)函數(shù)f的定義域是D,值域是R,如果存在一種算法,對D中任意給定的值X都能計算出f(X)的值,則稱函數(shù)f是可計算的。例如:若M和N是兩個正整數(shù),并且M>=N時,求M和N的最大公因數(shù)的歐幾里得算法可表示為：步驟一：【求余數(shù)】以N除M得余數(shù)R。步驟二：【余數(shù)為0嗎】若余數(shù)R=0,計算結(jié)束,N即為答案；否則轉(zhuǎn)到步驟步驟3。步驟三：【互換】把M的值變?yōu)镹,N的值變?yōu)镽,重復(fù)上述步驟。依照這3條規(guī)則指示的步驟,可計算出任何兩個正整數(shù)的最大公因數(shù),可以把計算過程看成執(zhí)行這些步驟的序列。計算過程是有窮的,計算的每一步都是能夠機械實現(xiàn)的。為了精確刻畫算法的特征,人們建立了各種各樣的數(shù)學(xué)模型。計算機學(xué)科的三個過程(抽象、理論和自動化設(shè)計及實現(xiàn))中，最根本的問題在是：如何描述問題?哪些部分能夠被自動化?如何進行自動化描述?建立物理符號系統(tǒng)并對其實施等價變換是計算機學(xué)科進行問題描述和求解的重要手段。"可行性"所要求的"形式化"及其"離散特征"使得數(shù)學(xué)成為重要的工具,而計算模型無論方法還是工具等方面,都表現(xiàn)出它在計算機上科學(xué)中的重要作用。計算的復(fù)雜性理論研究的是算法的時間復(fù)雜性和空間復(fù)雜性。在復(fù)雜性理論中,目標是把可計算的問題分成簡單的和困難的。1.4計算機與計算思維的關(guān)系1、計算機促進計算思維的研究與發(fā)展2、計算思維研究推動計算機的發(fā)展

計算機對信息的處理快速快、記憶力強的特點，使得原本只能理論上實現(xiàn)的過程，變成實際可行的實現(xiàn)過程。在對計算思維的廣泛、深入研究過程中，逐步揭示出一些屬于計算思維的特點，計算思維與理論思維、驗證思維的差異越來越明晰。計算思維的內(nèi)容得到不斷的豐富與發(fā)展。從思維的角度來說，計算科學(xué)主要研究計算思維的概念、方法和內(nèi)容，并發(fā)展成為解決問題的一種思維方式，極大地推動了計算思維的發(fā)展。1.5計算學(xué)科的典型案例【案例1】到底誰真話？張三說:李四在說謊;李四說:王五在說謊;王五說:張三和李四都在說謊。已知三人中只有一人說真話。根據(jù)以上的陳述，現(xiàn)在要問到底誰說真話？這是一個典型的邏輯推理命題?？瓷先ズ孟窀嬎阏床簧线?。實際上利用窮舉法求解，即把邏輯推理的敘述性命題數(shù)學(xué)化，再用計算機程序的自動化，把每一種可能情況中，滿足條件的情況輸出，就可求得命題的解。首先可以考慮每個人說話的真假，用一個表達式來表示。設(shè)Z、L、W分別代表張三、李四和王五，各自取值為0(或False)時表示說的是假話，取值為1(或True)時表示說的是真話；再用C代表說真話計數(shù)器，每當有說真話時，C就加1。如果Z、L、W三人中只有一人說真話(即Z+L+W=1)并且C的值為1，說明滿足命題給定的前提條件。此時可得出結(jié)論，即輸出Z、L、W各自的值。其中值為1(True)的就是說真話的人。如第一句話張三說:李四在說謊;中的“李四在說謊;”用數(shù)學(xué)式子表示為L==0(或L==False),同時也表達了如果張三說的是真話，則L==0(或L==False)表達式成立。同理第二句話李四說:王五在說謊;中的“王五在說謊;”

用數(shù)學(xué)式子表示為W==0(或W==False)；同時也表達了如果李四說的是真話，則W==0(或W==False)表達式成立。第三句話王五說:張三和李四都在說謊?！皬埲屠钏亩荚谡f謊”用數(shù)學(xué)式子表示為Z==0AndL==0(或Z==FalseAndL==False)；同時也表達了如果王五說的是真話，則Z==0AndL==0(或Z==FalseAndL==False)表達式成立。第四句話已知三人中只有一人說真話。即Z、L、W中只有一個變量的值是1(