第1章

計(jì)算與信息基礎(chǔ)常熟理工學(xué)院·計(jì)算機(jī)科學(xué)與工程學(xué)院目錄1計(jì)算機(jī)計(jì)算機(jī)系統(tǒng)的構(gòu)成23計(jì)算機(jī)軟件計(jì)算思維41

計(jì)算機(jī)計(jì)算機(jī)

01圖靈機(jī)02計(jì)算與自動(dòng)計(jì)算03電子自動(dòng)計(jì)算：元器件圖靈機(jī)

1936年，英國(guó)數(shù)學(xué)家阿蘭?麥席森?圖靈(1912―1954年)提出了一種抽象的計(jì)算模型，即圖靈機(jī)(Turingmachine)。圖靈機(jī)，又稱圖靈計(jì)算機(jī)，即將人們使用紙筆進(jìn)行數(shù)學(xué)運(yùn)算的過(guò)程進(jìn)行抽象，由一個(gè)虛擬的機(jī)器替代人類進(jìn)行數(shù)學(xué)運(yùn)算。圖靈的基本思想是用機(jī)器來(lái)模擬人們用紙筆進(jìn)行數(shù)學(xué)運(yùn)算的過(guò)程，他把這樣的過(guò)程看作下列兩種簡(jiǎn)單的動(dòng)作：（1）在紙上寫(xiě)上或擦除某個(gè)符號(hào)；（2）把注意力從紙的一個(gè)位置移動(dòng)到另一個(gè)位置。圖靈機(jī)

1.圖靈機(jī)的思想圖靈機(jī)主要有以下幾個(gè)部分：輸入符號(hào)集合，一條無(wú)限長(zhǎng)的紙帶。紙帶被劃分為一個(gè)接一個(gè)的小格子，每個(gè)格子上包含一個(gè)來(lái)自有限字母表的符號(hào)，字母表中有一個(gè)特殊的符號(hào)表示空白。紙帶上的格子從左到右依此被編號(hào)為0，1，2，...，紙帶的右端可以無(wú)限伸展。2.一個(gè)讀寫(xiě)頭，該讀寫(xiě)頭位于處理盒內(nèi)部，可以在紙帶上左右移動(dòng)，它能讀出當(dāng)前所指的格子上的符號(hào)，并能改變當(dāng)前格子上的符號(hào)。3.一套控制規(guī)則。它根據(jù)當(dāng)前機(jī)器所處的狀態(tài)以及當(dāng)前讀寫(xiě)頭所指的格子上的符號(hào)來(lái)確定讀寫(xiě)頭下一步的動(dòng)作，并改變狀態(tài)寄存器的值，令機(jī)器進(jìn)入一個(gè)新的狀態(tài)。4.一個(gè)狀態(tài)寄存器。它用來(lái)保存圖靈機(jī)當(dāng)前所處的狀態(tài)。圖靈機(jī)的所有可能狀態(tài)的數(shù)目是有限的，并且有一個(gè)特殊的狀態(tài)，稱為停機(jī)狀態(tài)。圖靈機(jī)

2.圖靈機(jī)的意義（1）它證明了通用計(jì)算理論，肯定了計(jì)算機(jī)實(shí)現(xiàn)的可能性，同時(shí)它給出了計(jì)算機(jī)應(yīng)有的主要架構(gòu)；（2）圖靈機(jī)模型引入了讀寫(xiě)、算法與程序語(yǔ)言的概念，極大的突破了過(guò)去的計(jì)算機(jī)器的設(shè)計(jì)理念；（3）圖靈機(jī)模型是計(jì)算學(xué)科最核心的理論，因?yàn)橛?jì)算機(jī)的極限計(jì)算能力就是通用圖靈機(jī)的計(jì)算能力，很多問(wèn)題可以轉(zhuǎn)化到圖靈機(jī)這個(gè)簡(jiǎn)單的模型來(lái)考慮。圖靈機(jī)模型向人們展示這樣一個(gè)過(guò)程：程序和其輸入可以先保存到存儲(chǔ)帶上，圖靈機(jī)就按程序一步一步運(yùn)行直到給出結(jié)果，結(jié)果也保存在存儲(chǔ)帶上。更重要的是，從圖靈機(jī)模型可以隱約看到現(xiàn)代計(jì)算機(jī)主要組成，尤其是馮?諾依曼計(jì)算機(jī)的主要組成。計(jì)算與自動(dòng)計(jì)算（0，1）比特：創(chuàng)造了信息世界，數(shù)字媒介—軟件，自媒體，構(gòu)造了虛擬世界。計(jì)算的力量源泉：

將不可計(jì)算的轉(zhuǎn)為可計(jì)算、可量化，解決了從定性到定量的問(wèn)題。

原來(lái)：?jiǎn)栴}→人→答案

現(xiàn)在：?jiǎn)栴}→AI（決策，人臉識(shí)別，內(nèi)容生成等）→人→答案計(jì)算與自動(dòng)計(jì)算人與計(jì)算機(jī)的差別例如：求ax2+bx+c=0的根人-求解機(jī)器-求解利用上述公式計(jì)算得到x值(1)從-n到n，產(chǎn)生x的每一個(gè)整數(shù)值；(2)將其依次代入到方程中計(jì)算;(3)如果其值使方程式成立，則即為其解；否則不是

計(jì)算與自動(dòng)計(jì)算枚舉-計(jì)算-驗(yàn)證暴力/蠻干思維人-計(jì)算一條規(guī)則可能很復(fù)雜,但計(jì)算量卻可能很小人需要知道具體的計(jì)算規(guī)則特定規(guī)則，只能求:a1x2+a2x=c機(jī)器-計(jì)算每條規(guī)則可能很簡(jiǎn)單,但計(jì)算量卻很大機(jī)器也可以采用人所使用的計(jì)算規(guī)則一般性的規(guī)則，可以求任意:a1x1b1+a2x2b2+…+anxnbn=c計(jì)算與自動(dòng)計(jì)算什么是計(jì)算？是從表示-自動(dòng)存儲(chǔ)-自動(dòng)執(zhí)行的角度，設(shè)計(jì)簡(jiǎn)單的規(guī)則讓計(jì)算機(jī)重復(fù)計(jì)算。

計(jì)算思維之可計(jì)算機(jī)性就是一個(gè)問(wèn)題當(dāng)且僅當(dāng)能夠?qū)懗梢粋€(gè)計(jì)算機(jī)程序時(shí)，才被認(rèn)為是可計(jì)算的。凡是可計(jì)算的都是圖靈機(jī)可計(jì)算的。（丘奇-圖靈）命題。計(jì)算與自動(dòng)計(jì)算自動(dòng)計(jì)算自動(dòng)計(jì)算要解決的幾個(gè)問(wèn)題:表示-存儲(chǔ)-執(zhí)行“數(shù)據(jù)”的表示“計(jì)算規(guī)則”的表示：程序（算法+數(shù)據(jù)結(jié)構(gòu)）數(shù)據(jù)與計(jì)算規(guī)則的“自動(dòng)存儲(chǔ)”計(jì)算規(guī)則的“自動(dòng)執(zhí)行”電子自動(dòng)計(jì)算：元器件

解決0和1的存儲(chǔ)與控制電子管人類第一只電子管(真空二極管),1895存儲(chǔ)0和1的元器件電子管計(jì)算機(jī)ENIAC,1946年,17468只電子管電子自動(dòng)計(jì)算：元器件

晶體管與集成電路人類第一只晶體管(點(diǎn)接觸晶體管),1947封裝后的集成電路芯片超大規(guī)模集成電路(VLSI)集成電路:可自動(dòng)實(shí)現(xiàn)一定變換的元件電子自動(dòng)計(jì)算：元器件

自動(dòng)計(jì)算中的元器件的發(fā)展從表示-自動(dòng)存儲(chǔ)-自動(dòng)執(zhí)行的角度電子管:可自動(dòng)控制0和1變化的元件晶體管集成電路:可自動(dòng)實(shí)現(xiàn)一定變換的元件超大規(guī)模集成電路(VLSI)體積越來(lái)越??；可靠性越來(lái)越高；電路規(guī)模越來(lái)越大；速度越來(lái)越快；功能越來(lái)越強(qiáng)大；電子自動(dòng)計(jì)算：元器件

計(jì)算機(jī)系統(tǒng)要解決的幾個(gè)問(wèn)題“控制與計(jì)算”微處理器“輸入”如何將外部信息輸入到計(jì)算機(jī)中?“輸出”如何將計(jì)算機(jī)中信息輸出到外界(顯示或打印)?“永久存儲(chǔ)與臨時(shí)存儲(chǔ)”如何將計(jì)算機(jī)中的信息永久保存或臨時(shí)保存?提問(wèn)：元器件和自動(dòng)計(jì)算有什么關(guān)系呢？(與門(mén)，非門(mén)，半加法器，加法器）2計(jì)算機(jī)系統(tǒng)的構(gòu)成計(jì)算機(jī)系統(tǒng)的構(gòu)成

01馮.諾依曼計(jì)算機(jī):思想與構(gòu)成

02電子自動(dòng)計(jì)算-計(jì)算機(jī)系統(tǒng)馮.諾依曼計(jì)算機(jī):思想與構(gòu)成

1944~1945年間，馮.諾依曼提出“存儲(chǔ)程序”的計(jì)算機(jī)設(shè)計(jì)思想，并進(jìn)行了實(shí)踐，現(xiàn)代計(jì)算機(jī)普遍來(lái)講屬于馮.諾伊曼機(jī)體系。馮.諾伊曼機(jī)的基本思想：運(yùn)算和存儲(chǔ)分離存儲(chǔ)程序：指令和數(shù)據(jù)以同等地位事先存于存儲(chǔ)器,可按地址尋訪,連續(xù)自動(dòng)執(zhí)行。五大部件構(gòu)成：運(yùn)算器、控制器、存儲(chǔ)器、輸入設(shè)備和輸出設(shè)備指令和數(shù)據(jù)用二進(jìn)制表示，指令由操作碼和地址碼組成以運(yùn)算器為中心，控制器負(fù)責(zé)解釋指令，運(yùn)算器負(fù)責(zé)執(zhí)行指令

馮.諾依曼計(jì)算機(jī):思想與構(gòu)成

（1）馮.諾依曼計(jì)算機(jī)的結(jié)構(gòu)是怎樣的?部件有哪些?部件的關(guān)系怎樣?以運(yùn)算器為中心的馮.諾依曼計(jì)算機(jī)構(gòu)成圖

馮.諾依曼計(jì)算機(jī):思想與構(gòu)成

（2）存儲(chǔ)器為中心與運(yùn)算器為中心相比的優(yōu)點(diǎn)在哪里?以存儲(chǔ)器為中心的現(xiàn)代計(jì)算機(jī)構(gòu)成圖同樣是五個(gè)部件，以不同的結(jié)構(gòu)來(lái)連接，便體現(xiàn)了不同的性能這就是“系統(tǒng)”：強(qiáng)調(diào)“結(jié)構(gòu)”，強(qiáng)調(diào)部件連接后的整體性、協(xié)同性

馮.諾依曼計(jì)算機(jī):思想與構(gòu)成

（3）馮.諾依曼計(jì)算機(jī)的工作原理是怎樣的?工作原理運(yùn)算器存儲(chǔ)器(9)(5)控制器(10)(7)(3)(8)(2)(4)(6)控制臺(tái)(1)(1)啟動(dòng)控制器工作(2)發(fā)送第1條指令地址(3)取出指令并分析指令(4)執(zhí)行指令：發(fā)送操作數(shù)x所在地址(5)執(zhí)行指令：取出操作數(shù)x(6)發(fā)送下一條指令地址(7)取出指令并分析指令(8)執(zhí)行指令：發(fā)送操作數(shù)a所在地址(9)執(zhí)行指令：取出操作數(shù)a(10)執(zhí)行指令：通知運(yùn)算器計(jì)算a乘x(11)繼續(xù)后續(xù)指令的取指、執(zhí)行…

馮.諾依曼計(jì)算機(jī):思想與構(gòu)成

（4）什么是CPU?現(xiàn)代計(jì)算機(jī)的幾大部件是什么?

計(jì)算機(jī)的基本部件CPU：中央處理單元(CentralProcessUnit)，將運(yùn)算器和控制器集成在一塊芯片上，形成微處理器。CPU、主存儲(chǔ)器、I/O設(shè)備及總線成為現(xiàn)代計(jì)算機(jī)的四大核心部件。現(xiàn)代計(jì)算機(jī)里面，一個(gè)微處理器(芯片)可能包含多個(gè)CPU，即多核.8086/8088

電子自動(dòng)計(jì)算-計(jì)算機(jī)系統(tǒng)

(1)控制與計(jì)算-微處理器-計(jì)算機(jī)系統(tǒng)的核心？微處理器的發(fā)展字長(zhǎng)：8位

16位

32位

64位主頻：幾MHz

幾百M(fèi)Hz

幾GHz晶體管數(shù)量：幾萬(wàn)

幾百萬(wàn)

幾億顆功能/規(guī)模：微處理器

微處理器+協(xié)處理器(浮點(diǎn)運(yùn)算)

微處理器+圖形處理單元GPU

微處理器+3D處理器+多媒體處理器

多核微處理器8086/80881974Intel80286Intel80386Intel80486PentiumPentiumIIPentiumIII雙核CORE八核-十核COREi系列19821985198919931997199920052010

存儲(chǔ)設(shè)備存儲(chǔ)設(shè)備類別發(fā)展水平固態(tài)硬盤(pán)USBRemovablediskFlashRAM磁帶/磁芯/磁鼓存儲(chǔ)磁盤(pán)存儲(chǔ)(硬盤(pán)與軟盤(pán))光盤(pán)存儲(chǔ)(CD-ROM,CDR/W,DVD)汞延遲線納米存儲(chǔ)/量子存儲(chǔ)半導(dǎo)體存儲(chǔ)(ROM/RAM)體積越來(lái)越小容量越來(lái)越大訪問(wèn)速度越來(lái)越快可靠性越來(lái)越高功耗越來(lái)越低持久性越來(lái)越好DRAM半導(dǎo)體存儲(chǔ)器芯片F(xiàn)lashRAM存儲(chǔ)器U-Disk固態(tài)硬盤(pán)(2)怎樣解決大規(guī)?？焖俅鎯?chǔ)問(wèn)題？

電子自動(dòng)計(jì)算-計(jì)算機(jī)系統(tǒng)

輸入設(shè)備類別發(fā)展水平穿孔紙帶(0/1輸入)鍵盤(pán)輸入(符號(hào)輸入)鼠標(biāo)輸入(點(diǎn)輸入)輸入設(shè)備

電子自動(dòng)計(jì)算-計(jì)算機(jī)系統(tǒng)

(3)怎樣解決輸入問(wèn)題？

輸出設(shè)備(顯示器)類別發(fā)展水平CRT：陰極射線管(模擬顯示器：黑白與彩色)CRT:字符發(fā)生器(向量式模擬顯示器:輸出字符)CRT:數(shù)字光柵掃描顯示器(基于內(nèi)存的顯示:輸出圖形)3D顯示器：3維圖形數(shù)字顯示器：高清圖形(液晶、等離子技術(shù))GPU芯片多顯示卡并聯(lián)分辨率越來(lái)越高顏色越來(lái)越逼真顯示速度越來(lái)越快(屏幕刷新速度和圖形處理速度)越來(lái)越薄，越清晰可視角度越來(lái)越接近平角輸出設(shè)備---顯示及顯示控制

電子自動(dòng)計(jì)算-計(jì)算機(jī)系統(tǒng)

(4)怎樣解決輸出問(wèn)題？3計(jì)算機(jī)軟件

計(jì)算機(jī)軟件

多樣化的“計(jì)算機(jī)器”，各種設(shè)備的“大腦”系統(tǒng)

計(jì)算機(jī)軟件

計(jì)算機(jī)軟件

軟件正在占領(lǐng)全世界4計(jì)算思維

計(jì)算思維

什么是計(jì)算思維？計(jì)算思維是人類應(yīng)具備的第三種思維實(shí)驗(yàn)思維:實(shí)驗(yàn)觀察發(fā)現(xiàn)、推斷與總結(jié).觀察與歸納理論思維:假設(shè)/預(yù)設(shè)定義/性質(zhì)/定理證明.推理和演繹計(jì)算思維:設(shè)計(jì),構(gòu)造與計(jì)算.設(shè)計(jì)與構(gòu)造計(jì)算思維關(guān)注的是人類思維中有關(guān)可行性、可構(gòu)造性和可評(píng)價(jià)性的部分當(dāng)前環(huán)境下，理論與實(shí)驗(yàn)手段在面臨大規(guī)模數(shù)據(jù)的情況下，不可避免地要用計(jì)算手段來(lái)輔助進(jìn)行。

計(jì)算思維

《ComputationalThinking》fromCMU，周以真（JeannetteM.Wing），CommunicationsofACM,Vol.49,No.3,March2006,Pages33-35Computationalthinkingisawayofsolvingproblems,designingsystems,andunderstandinghumanbehaviorthatdrawsonconceptsfundamentaltocomputerscience.Computationalthinkingwillbeafundamentalskillusedbyeveryoneintheworldbythemiddleofthe21stCentury.–Justlikereading,writing,andarithmetic.–Imagineeverypersonknowinghowtothinklikeacomputerscientist!–Computationalthinkingisnotjustforotherscientists,it’sforeveryone.–Thinkinglikeacomputerscientistmeansmorethanbeingabletoprogramacomputer計(jì)算思維的本質(zhì)就是