Ch1計算與計算思維

計算與計算思維1計算機:硬件(1)2計算機:硬件(2)中央處理器(CPU):執(zhí)行指令.每條指令只能完成簡單的操作!例如:加法，

比較，

將數(shù)據(jù)從一個內(nèi)存單元移到另一單元，etc.存儲器:存儲信息(程序和數(shù)據(jù)).主存:CPU能直接訪問，速度快但易失.次級存儲器:速度慢但持久.輸入/輸出設(shè)備:人機交互33444計算機:軟件計算機是信息處理機器，信息處理過程由預(yù)定的程序控制單條指令是做不了什么事情的，需要大量指令組成一個逐步執(zhí)行的指令序列－程序各種程序統(tǒng)稱為計算機軟件沒有軟件的計算機毫無用處4計算計算:利用計算機執(zhí)行程序來解決問題不是狹義的數(shù)學計算!程序使得簡單指令完成復(fù)雜任務(wù)問:只會加法的小學生能完成乘法運算任務(wù)嗎?答:能!關(guān)鍵是編寫合適的程序

在紙上寫下0，記住結(jié)果；給所記結(jié)果加上第1個n，記住結(jié)果；給所記結(jié)果加上第2個n，記住結(jié)果；

……給所記結(jié)果加上第m個n，記住結(jié)果;報告結(jié)果(即m×n)55通用計算機計算機執(zhí)行一個程序即可實現(xiàn)一個功能;換著執(zhí)行不同的程序即可實現(xiàn)不同的功能.通用計算機:可以加載不同的程序來執(zhí)行.與一些電器的比較:電視機功能單一，洗衣機則功能較多(可加載多種洗滌程序)，現(xiàn)在的手機則功能更多，基本上就是計算機.6計算機科學并非研究計算機!計算機之于計算機科學家正如望遠鏡之于天文學家.(E.W.Dijkstra)CS研究計算的基礎(chǔ)，實現(xiàn)與應(yīng)用.例如，CS的一個基本問題:什么是可計算的?本課程的學習目標:像計算機科學家一樣思考.77程序設(shè)計計算的關(guān)鍵是程序設(shè)計(編程).給定一個問題，利用計算機支持的簡單操作，設(shè)計出一個操作步驟的序列，計算機執(zhí)行這個序列從而解決問題.學習程序設(shè)計的好處:做計算機的主人提高問題求解能力本身是很有樂趣的智力活動88程序設(shè)計語言問:用什么語言告訴計算機做什么?答:用精確無歧義的程序設(shè)計語言.精確的語法和語義Isawthemanintheparkwiththetelescope.有不同層次的程序設(shè)計語言計算機的"母語":機器語言例如:0000010000000001.是Intel8086能理解的一條指令.將機器語言用助憶符表示:匯編語言上例即:ADDAL，1.需要匯編器處理后機器才懂.適合人用的語言:高級語言如:x=y+1.需要編譯器或解釋器翻譯后機器才懂.99程序設(shè)計語言程序設(shè)計語言不一樣導(dǎo)致語法不一樣，但解題思路、思維方式是一樣的10importmath#Makesthemathlibraryavailable.defmain():print"Thisprogramfindstherealsolutionstoaquadratic"printa,b,c=input("Pleaseenterthecoefficients(a,b,c):")delt=b*b-4*a*cifdelt>=0:discRoot=math.sqrt(delt)root1=(-b+discRoot)/(2*a)root2=(-b-discRoot)/(2*a)printprint"Thesolutionsare:",root1,root2else:printprint"delt<0,noroot."printmain()intmain(){floata,b,c,x1,x2,dlt;cout<<“input3parameters:”;cout<<“inputa:”;cin>>a;cout<<“inputb:”;cin>>b;cout<<“inputc:”;cin>>c;dlt=b*b–4*a*c;if(dlt>=0){x1=(-b+sqrt(dlt))/2/a;

x2=(-b-sqrt(dlt))/2/a;cout<<x1<<x2;}elsecout<<“noroot”;return0;}編譯vs解釋思考:為什么高級語言程序具有可移植性，即同一個程序可以在不同廠商的計算機上執(zhí)行?11算法與編碼實現(xiàn)程序設(shè)計先用非形式化的語言將問題求解步驟表達出來——算法;偽代碼再用形式化的編程語言將上述算法實現(xiàn)——程序.代碼12算法例:歐幾里德算法歐幾里德算法:求最大公約數(shù).輸入:自然數(shù)a、b輸出:a、b的最大公約數(shù)步驟:第1步:令r為a除以b所得余數(shù)第2步:若r=0，則算法結(jié)束，b即為答案;否則置a←b，b←r，轉(zhuǎn)到第1步.13對算法的要求算法的每個步驟必須是明確的，可行的.不明確:"在菜中放點鹽"不可行:"用青菜豆腐做出龍肝鳳髓的美味"每個步驟不必是最底層的瑣細步驟，可以是組合的高級步驟.如:"焯水"算法的步驟必須在有限時間內(nèi)完成.我們說的計算，即是指"算法計算":用明確可行的基本步驟組成的序列來解決問題.14151515計算思維計算思維(computationalthinking)是計算機科學家利用計算機(計算過程)解決問題時的思想和方法.計算機科學(CS)是關(guān)于“計算”的科學.如何像計算機科學家一樣思考?15161616真的有計算思維嗎?人們在解決不同問題時有不同的思考方式數(shù)學思維:解數(shù)學問題工程思維:工程設(shè)計形象思維:文學創(chuàng)作......計算思維:建立在計算機的能力與局限之上.由于計算機的廣泛應(yīng)用，計算思維未來會成為人們的基本能力.與閱讀，書寫，算術(shù)能力一樣!計算思維例:問題表示問題的表示(建模)抽象:將現(xiàn)實中的各種數(shù)量關(guān)系，空間關(guān)系，處理過程抽象為計算機的數(shù)據(jù)結(jié)構(gòu)和控制結(jié)構(gòu)例如:溫度數(shù)據(jù)抽象為數(shù)值還是文字?不同抽象層次問題表示得合適與否直接影響問題的解法的發(fā)現(xiàn)和效率17計算思維例:算法設(shè)計化難為易:分解，約簡，嵌入，轉(zhuǎn)換，模擬...分治法，遞歸法，貪心法，動態(tài)規(guī)劃...遞歸地思考并行處理1818計算思維例:編程實現(xiàn)類型系統(tǒng)與類型檢查結(jié)構(gòu)化與模塊化的思考編程范型:過程式，面向?qū)ο?，函?shù)式，...程序美學，系統(tǒng)設(shè)計的簡潔與優(yōu)雅1919計算思維例:計算理論算法復(fù)雜度分析問題的解法是有效率差別的有些問題是難解的尋求近似解問題的可計算性有些問題是不可計算的2020計算思維例:其他預(yù)取和緩存對最壞情況的預(yù)防，保護，恢復(fù)啟發(fā)式推理時空等不可兼得要素的權(quán)衡……21計算思維的特點是概念化思考，而非編程是基本思考能力，而非機械的套用是人的思考，而非計算機與數(shù)學思維和工程思維相結(jié)合是思想，而非人造物人人皆有，處處皆是2222生活中的計算思維算法:小學算術(shù)中的長除法查找方法:查黃頁是順序翻找還是借助索引排序:整理撲克牌排隊:先來先處理預(yù)取與緩存:書包存放當天上課用的書并行處理:燒菜……23計算+X計算數(shù)學，計算幾何，自動定理證明計算物理學計算化學計算生物學，生物信息學計算經(jīng)濟學計算機藝術(shù):電影特效，計算機作曲繪畫書法……24計算+X:十二五863計劃征集重大應(yīng)用軟件課題聚變與裂變能源數(shù)值模擬真實飛機外型全流場和優(yōu)化設(shè)計數(shù)值模擬航天飛行器全飛行流域數(shù)值模擬新藥研發(fā)與蛋白質(zhì)折疊數(shù)值模擬真實感動漫渲染與創(chuàng)作大型工程設(shè)備結(jié)構(gòu)力學分析復(fù)雜電磁環(huán)境數(shù)值模擬新型材料設(shè)計與性能評估2525本課程的定位學習利用計算機解決問題的思想方法，應(yīng)用于其他專業(yè)領(lǐng)域不是程序設(shè)計語言課程!編程是計算思維的實踐壞消息:學習編程語言需要掌握非常繁瑣的細節(jié)好消息:Python語言非常簡單，易學易用不是算法和數(shù)據(jù)結(jié)構(gòu)課程!會學習一些基本的知識26本課程的定位(續(xù))27計算機科學程序設(shè)計語言算法設(shè)計與分析數(shù)據(jù)結(jié)構(gòu)理，化，生...經(jīng)，管，金融...工程數(shù)學藝術(shù)計算思維可計算性理論27Python語言荷蘭人GuidovanRossum于1980年代發(fā)明.通用/跨平臺/開源/自由(免費)簡單易學，高度的可讀性支持多種編程范型編譯+解釋:源代碼先編譯成字節(jié)碼，再解釋執(zhí)行流行編程語言前10名之一./index.php/content/paperinfo/tpci/index.html

2828Python安裝與運行版本:教材和上課都采用Python2.7與最新的Python3.x有不兼容的地方.安裝后，啟動Python解釋器命令行GUI2929第一個程序:HelloWorld交互方式>>>print"Hello，World!"Hello，World!本課程的教學中常用交互方式演示新語句實際上很少用交互方式執(zhí)行程序多次執(zhí)行同一程序需要多次輸入程序多行語句無法一次性執(zhí)行3030第一個程序:HelloWorld程序文件將語句保存在純文本文件hello.py中四種執(zhí)行方式在IDLE中用RunModule菜單執(zhí)行雙擊hello.py文件圖標>>>importhello

C:\Python27>pythonhello.py31print"Hello，World!"31程序?qū)嵗?convert.py#AprogramtoconvertCelsiustempstoFahrenheit#by:SusanComputewelldefmain():celsius=input("WhatistheCelsiustemperature?")fahrenheit=(9.0/5.0)*celsius+32print"Thetemperatureis"，fahrenheit，"degreesFahrenheit."main()32程序構(gòu)件:數(shù)據(jù)數(shù)據(jù)是被處理的信息有不同類型的數(shù)據(jù)字符串數(shù)據(jù)>>>print"Hello，World!"數(shù)值數(shù)據(jù)>>>print3.14153333程序構(gòu)件:變量和數(shù)學類似:用一個名字表示可變的數(shù)據(jù)數(shù)學中多用單字母，程序中多用單詞/詞組標識符:Python命名以字母或下劃線開頭，后跟0個或多個字母，數(shù)字，下劃線.區(qū)分大小寫字母.合法:xxYzx_123_

___w3非法:3qx-123

firstname良好的命名風格:有意義，風格一致3434程序構(gòu)件:變量35保留字程序構(gòu)件:表達式表達式:能計算出一個值.字面值:3.14，“hello”變量數(shù)據(jù)+運算符(如)>>>2+3*4-5運算符不同類型的數(shù)據(jù)有不同運算運算符有優(yōu)先級良好編程風格:用空格，括號增加表達式的可讀性.3636程序構(gòu)件:語句輸出語句我們用語句模板來給出正確用法print<表達式>print<表達式1>，<表達式2>，...賦值語句>>>x=3.14>>>printx*103737程序構(gòu)件:函數(shù)多條語句構(gòu)成一個整體，并命名>>>defgreet():prin