計(jì)算機(jī)導(dǎo)論-計(jì)算機(jī)學(xué)科的基本概念

計(jì)算機(jī)學(xué)科的基本概念計(jì):數(shù)數(shù)或者進(jìn)行計(jì)數(shù)算:算籌等工具計(jì)算:最原始的含義利用計(jì)算工具進(jìn)行計(jì)數(shù)進(jìn)一步，計(jì)算首先指數(shù)的加減乘除、平方、開方等初等運(yùn)算，其次為函數(shù)的微分、積分等高等運(yùn)算，以及方程的求解、代數(shù)的化簡(jiǎn)、定理的證明等。1計(jì)算與計(jì)算科學(xué)計(jì)算的本質(zhì)是什么呢？1930年代，哥德爾、丘奇、圖靈等數(shù)學(xué)家的工作，人們才弄清楚什么是計(jì)算的本質(zhì)，什么是可計(jì)算的、什么是不可計(jì)算的等根本性問題。抽象地說，所謂計(jì)算，就是從一個(gè)符號(hào)串f變換成另一個(gè)符號(hào)串g。如，從符號(hào)串12+3變換成15就是一個(gè)加法計(jì)算。如果符號(hào)串f是X2，而符號(hào)串g是2x,從f到g的計(jì)算就是微分。定理證明也如此。令f表示一組公理和推導(dǎo)規(guī)則，令g是一個(gè)定理,那么從f到g的一系列變換就是定理g的證明。文字翻譯也是計(jì)算，如f代表一個(gè)英文句子，而g為含意相同的中文句子，那么從f到g就是把英文翻譯成中文。計(jì)算的本質(zhì)這些變換間有什么共同點(diǎn)？為什么把它們都叫做計(jì)算？因?yàn)樗鼈兌际菑募褐?hào)(串)開始，一步一步地改變符號(hào)(串)，經(jīng)過有限步驟，最后得到一個(gè)滿足預(yù)先規(guī)定的符號(hào)(串)的變換過程。計(jì)算的本質(zhì)計(jì)算的類型從類型上講，主要有兩大類：數(shù)值計(jì)算和符號(hào)推導(dǎo)。數(shù)值計(jì)算包括實(shí)數(shù)和函數(shù)的加減乘除、幕運(yùn)算、開方運(yùn)算、方程的求解等。符號(hào)推導(dǎo)包括代數(shù)與各種函數(shù)的恒等式、不等式的證明，幾何命題的證明等。無論是數(shù)值計(jì)算還是符號(hào)推導(dǎo),它們?cè)诒举|(zhì)上是等價(jià)的、一致的，即二者是密切關(guān)聯(lián)的，可以相互轉(zhuǎn)化，具有共同的計(jì)算本質(zhì)。隨著數(shù)學(xué)的發(fā)展,還可能出現(xiàn)新的計(jì)算類型。什么是可計(jì)算的?可計(jì)算的描述方式：形式系統(tǒng)例：狼羊白菜過河問題描述問題：農(nóng)夫帶著狼、羊、白菜從河的左岸到河的右岸，農(nóng)夫每次只能帶一樣?xùn)|西多河，而且，沒有農(nóng)夫看管，狼會(huì)吃羊，羊會(huì)吃白菜。提示：利用圖論解決問題。[解]：渡河的方法如下：

第一次，獵人把羊帶至右崖；

第二次，獵人單身回左岸，把白菜帶至右岸，此時(shí)右岸有獵人，羊和白菜；

第三次，獵人再把羊帶回左岸，放下羊，把狼帶至右岸，此時(shí)右岸有獵人，狼和白菜；

第四次，獵人單身回到左岸，最后把羊帶至右岸，便可完成渡河的任務(wù)。

這是一個(gè)著名的古題，同樣也是“圖論”應(yīng)用的經(jīng)典例子。

首先，用字母P、L、C和X分別代表獵人、狼、羊和白菜，即P—獵人，L—狼，C—羊，X—白菜。用字母的組合表示左岸的情況。開始時(shí)，狼、羊、白菜和獵人全在左岸，用LCXP表示；若左岸只剩下狼時(shí)，就用L表之，等等。因?yàn)槔呛脱颉⒀蚝桶撞瞬荒茉跓o人監(jiān)視的情況下共處，所以在整個(gè)渡河過程中，左岸始終不允許出現(xiàn)LC、CX、LP和XP所表示的情況。仔細(xì)地列出左岸所允許出現(xiàn)的全部情況，它們是：

LCXP，LCP，CXP，LXP，LX，CP，C，L，X，ψ，其中記號(hào)ψ表示左岸已空無所有。用A表示LCXP，用B表示ψ，那么只要在圖中找到一條由A到B的通道（折線），實(shí)際上就給出了一個(gè)滿足題意的過渡方法。狼羊白菜過河問題解法用1表示在左岸,0表示在右岸.用頂點(diǎn)序號(hào)的二進(jìn)制碼的0位表示農(nóng)夫,1位表示狼,2位表示羊,3位表示菜.那么,總共可能有16個(gè)頂點(diǎn)0-15.頂點(diǎn)0表示全在左岸,頂點(diǎn)15表示全在右岸.有些頂點(diǎn)是不允許存在的,比如頂點(diǎn)3,表示農(nóng)夫和狼在右岸,羊和菜在左岸,羊會(huì)吃掉菜.要把所有這類的頂點(diǎn)去掉.在剩下的頂點(diǎn)中,要找出所有的可能的邊.比如頂點(diǎn)5表示農(nóng)夫和羊在右,狼和菜在左,頂點(diǎn)4表示羊在右,那么就存在頂點(diǎn)5到頂點(diǎn)4的有向邊.至此,圖已構(gòu)造完畢,問題就轉(zhuǎn)換成找到一條從頂點(diǎn)0到頂點(diǎn)15的合理路徑.編程作業(yè)：八皇后問題。是19世紀(jì)著名數(shù)學(xué)家高斯1850年提出：在8X8格的國際象棋上擺放八個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。計(jì)算科學(xué)正是在探索“什么是計(jì)算？什么是可計(jì)算的？什么是不可計(jì)算的？”這些根本性問題的基礎(chǔ)上形成的。悖論舉例某理發(fā)師發(fā)誓“要給所有不自已理發(fā)的人理發(fā)，不給所有自己理發(fā)的人理發(fā)”?，F(xiàn)在的問題是“誰為該理發(fā)師理發(fā)？”。首先，若理發(fā)師給自己理發(fā)，那他就是一個(gè)“自己理發(fā)的人”，依其誓言“他不給自己理發(fā)”；其次，若“他不給自己理發(fā)”，依其誓言，他就必須“給自己理發(fā)”圖靈等提出可計(jì)算函數(shù)的模型對(duì)計(jì)算科學(xué)產(chǎn)生深遠(yuǎn)影響。圖靈機(jī)模型1936年，圖靈向倫敦權(quán)威的數(shù)學(xué)雜志投了一篇論文，題為”論可計(jì)算及其在判定問題中的應(yīng)用“。在這篇開創(chuàng)性的論文中，圖靈給”可計(jì)算性“下了一個(gè)嚴(yán)格的數(shù)學(xué)定義，并提出”圖靈機(jī)（TuringMachine）“的設(shè)想?！眻D靈機(jī)“并不是一種具體的機(jī)器，而是一種思想，可制造一種十分簡(jiǎn)單但運(yùn)算能力極強(qiáng)的計(jì)算裝置，用來計(jì)算所有能想象得到的可計(jì)算函數(shù)。圖靈機(jī)模型圖靈機(jī)模型圖靈的基本思想是用機(jī)器來模擬人們用紙筆進(jìn)行數(shù)學(xué)運(yùn)算的過程，為了模擬人的這種運(yùn)算過程，圖靈構(gòu)造出一臺(tái)假想的機(jī)器，該機(jī)器由以下幾個(gè)部分組成：

有限狀態(tài)控制器工作帶

一條無限長(zhǎng)的工作帶：工作帶上的每個(gè)單元可以存放一個(gè)符號(hào)；所有允許出現(xiàn)的符號(hào)屬于一個(gè)預(yù)先規(guī)定好的字母表。

一個(gè)讀寫頭：讀寫頭可以左移一個(gè)單元、右移一個(gè)單元或者保持不動(dòng)。有限狀態(tài)控制器工作帶一個(gè)控制器：控制器在每個(gè)時(shí)刻處于一定狀態(tài)，當(dāng)讀寫頭從工作帶上讀出一個(gè)符號(hào)后，控制器就根據(jù)這個(gè)符號(hào)和當(dāng)時(shí)的機(jī)器狀態(tài)，指揮讀寫頭進(jìn)行讀寫或者移動(dòng)，并決定是否改變機(jī)器狀態(tài)。有限狀態(tài)控制器工作帶計(jì)算與可計(jì)算所謂計(jì)算就是計(jì)算者（人或機(jī)器）對(duì)一條可以無限延長(zhǎng)的工作帶上的符號(hào)串執(zhí)行指令，一步一步地改變工作帶上的符號(hào)串，經(jīng)過有限步驟，最后得到一個(gè)滿足預(yù)先規(guī)定的符號(hào)串的變換過程。控制器的命令可以用五元組表示：（q1,s1,s2,r,q2）q1:當(dāng)前狀態(tài)；s1:讀寫頭從當(dāng)前讀入的數(shù)據(jù)；s2:讀寫頭即將寫入當(dāng)前方格的數(shù)據(jù)；r:讀寫頭移動(dòng)（右/左/不動(dòng)）q2:新狀態(tài)一旦圖靈機(jī)在運(yùn)行中進(jìn)入了一個(gè)狀態(tài)，而且這個(gè)狀態(tài)就是一個(gè)結(jié)束狀態(tài)，那么，圖靈機(jī)就停機(jī)，計(jì)算任務(wù)完成，此時(shí)帶上的內(nèi)容就是計(jì)算輸出的結(jié)果。例：圖靈機(jī)MM的字母表A={0,1,b},b表示空格。狀態(tài)集Q={q1,q2,q3},其中，q1為開始狀態(tài)，q3為終止?fàn)顟B(tài)。M的程序（控制器的命令）如下：q101Rq1q110Rq1q1bbRq2q2bbLq3q200Hq1q111Hq1其中，L,R,H分別表示讀寫頭向左移動(dòng)一格、向右移動(dòng)一格、保持不動(dòng)三個(gè)基本操作。假如此時(shí)M讀入是11100b0011，讀寫頭對(duì)準(zhǔn)第一個(gè)1，狀態(tài)為q1，請(qǐng)給出輸出結(jié)果。bbb1100b0011bbbq1構(gòu)造該圖靈機(jī)的基本思想：使讀寫頭往返移動(dòng)，每往返移動(dòng)一次，就成對(duì)地對(duì)輸入符號(hào)串ω左端的一個(gè)a和右端的一個(gè)b匹配并做標(biāo)記x。如果恰好把輸入符號(hào)串ω的所有符號(hào)都做了標(biāo)記，說明左端的符號(hào)a和右端的符號(hào)b的個(gè)數(shù)相等；否則，說明左端的符號(hào)a和右端的符號(hào)b的個(gè)數(shù)不相等，或者符號(hào)a和b交替出現(xiàn)。例：構(gòu)造一個(gè)識(shí)別符號(hào)串ω＝anbn（n≥1）的圖靈機(jī)控制器的操作指令（也就是程序）如下：(q0aaRq0) (q0bxLq1)(q1xxLq1) (q1axRq2) (q1BBHqN)(q2xxRq2) (q2bxLq1) (q2BBLq3)(q3xxLq3) (q3aaHqN) (q3BBHqF)控制器的指令序列對(duì)應(yīng)一個(gè)狀態(tài)轉(zhuǎn)移圖，計(jì)算就是在執(zhí)行指令的過程進(jìn)行狀態(tài)的變化，也是變換符號(hào)的過程。(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,BBHqN)(q2,xxRq2)程序假定n＝2，輸入符號(hào)串ω＝aabb，圖靈機(jī)的工作過程如下：控制器BaabbB指令機(jī)器狀態(tài)當(dāng)前讀到的字符當(dāng)前寫入的字符讀寫頭的動(dòng)作R:右移L:左移H:不動(dòng)下一機(jī)器狀態(tài)讀寫頭(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,B

BHqN)(q2,xxRq2)讀寫頭程序控制器BaabbB讀寫頭掃描到符號(hào)a，則繼續(xù)往右走(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,B

BHqN)(q2,xxRq2)讀寫頭程序控制器BaabbB讀寫頭掃描到符號(hào)a，則繼續(xù)往右走(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,B

BHqN)(q2,xxRq2)讀寫頭程序控制器BaabbB讀寫頭掃描到符號(hào)b，將當(dāng)前單元寫入字符x，并使讀寫頭往左走，轉(zhuǎn)移到狀態(tài)q1。

(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,B

BHqN)(q2,xxRq2)讀寫頭程序控制器BaaxbB讀寫頭掃描到符號(hào)b，將當(dāng)前單元寫入字符x，并使讀寫頭往左走，轉(zhuǎn)移到狀態(tài)q1。

(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,B

BHqN)(q2,xxRq2)讀寫頭程序控制器BaaxbB讀寫頭掃描到符號(hào)a，則把a(bǔ)改為標(biāo)記x，并使讀寫頭往右走，轉(zhuǎn)移到狀態(tài)q2

(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,B

BHqN)(q2,xxRq2)讀寫頭程序控制器Bax

xbB讀寫頭掃描到符號(hào)a，則把a(bǔ)改為標(biāo)記x，并使讀寫頭往右走，轉(zhuǎn)移到狀態(tài)q2

(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,B

BHqN)(q2,xxRq2)讀寫頭程序控制器Bax

xbB讀寫頭掃描到標(biāo)記x，則繼續(xù)往右走

(q2,bxLq1)(q2,BBLq3)(q3,xxLq3)(q3,aaH

qN)(q3,BBHq4)讀寫頭程序控制器Bax

xbB若讀寫頭掃描到符號(hào)b，則把b改為標(biāo)記x，并使讀寫頭往左走，轉(zhuǎn)移到狀態(tài)q1

讀寫頭程序控制器Bax

x

xB若讀寫頭掃描到符號(hào)b，則把b改為標(biāo)記x，并使讀寫頭往左走，轉(zhuǎn)移到狀態(tài)q1

(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,B

BHqN)(q2,xxRq2)讀寫頭程序控制器Bax

x

xB讀寫頭掃描到標(biāo)記x，則繼續(xù)往左走

(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,B

BHqN)(q2,xxRq2)讀寫頭程序控制器Bax

x

xB讀寫頭掃描到符號(hào)a，則把a(bǔ)改為標(biāo)記x，并使讀寫頭往右走，轉(zhuǎn)移到狀態(tài)q2；

(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,B

BHqN)(q2,xxRq2)讀寫頭程序控制器Bx

x

x

xB讀寫頭掃描到標(biāo)記x，則繼續(xù)往右走

(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,B

BHqN)(q2,xxRq2)讀寫頭程序控制器Bx

x

x

xB讀寫頭掃描到標(biāo)記x，則繼續(xù)往右走

(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,B

BHqN)(q2,xxRq2)讀寫頭程序控制器Bx

x

x

xB讀寫頭掃描到標(biāo)記x，則繼續(xù)往右走

(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,B

BHqN)(q2,xxRq2)讀寫頭程序控制器Bx

x

x

xB讀寫頭掃描到空白符B，說明符號(hào)b已處理完畢，則把狀態(tài)改為q3，并使讀寫頭往左走

(q2,bxLq1)(q2,BBLq3)(q3,xxLq3)(q3,aaH

qN)(q3,BBHq4)讀寫頭程序控制器Bx

x

x

xB讀寫頭掃描到空白符B，說明符號(hào)b已處理完畢，則把狀態(tài)改為q3，并使讀寫頭往左走

(q2,bxLq1)(q2,BBLq3)(q3,xxLq3)(q3,aaH

qN)(q3,BBHq4)讀寫頭程序控制器Bx

x

x

xB讀寫頭掃描到標(biāo)記x，則繼續(xù)往左走

(q2,bxLq1)(q2,BBLq3)(q3,xxLq3)(q3,aaH

qN)(q3,BBHq4)讀寫頭程序控制器Bx

x

x

xB讀寫頭掃描到標(biāo)記x，則繼續(xù)往左走

(q2,bxLq1)(q2,BBLq3)(q3,xxLq3)(q3,aaH

qN)(q3,BBHq4)讀寫頭程序控制器Bx

x

x

xB讀寫頭掃描到標(biāo)記x，則繼續(xù)往左走

(q2,bxLq1)(q2,BBLq3)(q3,xxLq3)(q3,aaH

qN)(q3,BBHq4)讀寫頭程序控制器Bx

x

x

xB讀寫頭掃描到空白符B，說明符號(hào)a和b已成對(duì)標(biāo)記，轉(zhuǎn)移到狀態(tài)q4，達(dá)到接受狀態(tài)。

(q2,bxLq1)(q2,BBLq3)(q3,xxLq3)(q3,aaH

qN)(q3,BBHq4)從圖靈模型我們看到了什么？圖靈模型在一定程度上反映了人類最基本的、最原始的計(jì)算能力，它的基本動(dòng)作非常簡(jiǎn)單、機(jī)械、確定。因此，可以用真正的機(jī)器來實(shí)現(xiàn)圖靈機(jī)。程序并非必須順序執(zhí)行，指令中關(guān)于下一狀態(tài)的指定，實(shí)際上表明指令可以不按程序中所表示的順序執(zhí)行。這意味著，雖然程序只能按線性順序來表示指令序列，但程序的實(shí)際執(zhí)行可以與表示的順序不同。計(jì)算的對(duì)象、中間結(jié)果和最終結(jié)果都在帶上，程序則在控制器中。這意味著什么？為紀(jì)念圖靈對(duì)計(jì)算機(jī)的貢獻(xiàn)，美國計(jì)算機(jī)博物館于1966年設(shè)立了“圖靈獎(jiǎng)”"圖靈機(jī)"在計(jì)算機(jī)歷史上與”馮.諾依曼機(jī)“齊名。馮.諾依曼的助手弗蘭克曾在一封信中寫道：”......計(jì)算機(jī)的基本概念屬于圖靈。按照我的看法，馮.諾依曼的基本作用是使世界認(rèn)識(shí)了由圖靈引入的計(jì)算機(jī)的基本概念...”59馮?諾依曼生平簡(jiǎn)介60馮諾依曼/圖靈StoredProgramconceptMainmemorystoringprogramsanddata

主存儲(chǔ)器：用于存儲(chǔ)數(shù)據(jù)和指令A(yù)LUoperatingonbinarydata

能夠操作二進(jìn)制數(shù)的算術(shù)邏輯單元Controlunitinterpretinginstructionsfrommemoryandexecuting

控制器：解釋內(nèi)存中的指令并執(zhí)行Inputandoutputequipmentoperatedbycontrolunit

由控制器操縱的輸入、輸出設(shè)備6162存儲(chǔ)器運(yùn)算器控制器輸出設(shè)備輸入設(shè)備1.輸入設(shè)備：用于將程序（指令的集合，告訴計(jì)算機(jī)做什么以及怎么做的工作步驟）和數(shù)據(jù)從外界輸入計(jì)算機(jī)（存儲(chǔ)器），供計(jì)算機(jī)處理，主要任務(wù)是數(shù)字化。馮·諾伊曼體系結(jié)構(gòu)存儲(chǔ)器運(yùn)算器控制器輸出設(shè)備輸入設(shè)備2.存儲(chǔ)器：是計(jì)算機(jī)的記憶裝置，用于存放程序和數(shù)據(jù)。存儲(chǔ)器運(yùn)算器控制器輸出設(shè)備輸入設(shè)備3.運(yùn)算器：是計(jì)算機(jī)對(duì)數(shù)據(jù)進(jìn)行加工處理的部件，完成加、減、乘、除等基本算術(shù)運(yùn)算和與、或、非等基本邏輯運(yùn)算。存儲(chǔ)器運(yùn)算器控制器輸出設(shè)備輸入設(shè)備4.控制器：用于控制計(jì)算機(jī)各部件協(xié)調(diào)工作。控制器從存儲(chǔ)器中取出指令（告訴計(jì)算機(jī)做什么以及怎么做）并根據(jù)指令向有關(guān)部件發(fā)出控制命令。存儲(chǔ)器運(yùn)算器控制器輸出設(shè)備輸入設(shè)備5.輸出設(shè)備：用于將計(jì)算機(jī)的處理結(jié)果轉(zhuǎn)換成外界能夠識(shí)別的文字、電壓等信息并輸出。計(jì)算機(jī)：是能夠按照事先存儲(chǔ)的程序，自動(dòng)、高速地對(duì)數(shù)據(jù)進(jìn)行輸入、處理、輸出和存儲(chǔ)的系統(tǒng)。計(jì)算機(jī)=數(shù)據(jù)處理機(jī)數(shù)據(jù)結(jié)果整數(shù)、實(shí)數(shù)、文字、聲音、圖形、圖像等，甚至包括電壓、表情等整數(shù)、實(shí)數(shù)、文字、聲音、圖形、圖像等，甚至包括各種控制動(dòng)作輸入：接收由輸入設(shè)備（如鍵盤、鼠標(biāo)等）提供的數(shù)據(jù)。處理：對(duì)數(shù)值、邏輯字符等各種類型的數(shù)據(jù)進(jìn)行操作，按指定的方式進(jìn)行轉(zhuǎn)換和加工。輸出：將處理所產(chǎn)生的結(jié)果等送到相關(guān)輸出設(shè)備（如顯示器、打印機(jī)、繪圖儀等）。存儲(chǔ)：可以存儲(chǔ)程序和數(shù)據(jù)。馮·諾依曼體系結(jié)構(gòu)的主要特征：存儲(chǔ)程序。

存儲(chǔ)程序：事先編制好程序并將程序（指令的集合）和數(shù)據(jù)存入計(jì)算機(jī)的存儲(chǔ)器中，計(jì)算機(jī)在運(yùn)行時(shí)就能自動(dòng)、連續(xù)地從存儲(chǔ)器中逐條取出指令并執(zhí)行，因此，計(jì)算機(jī)的工作過程就是運(yùn)行程序的過程，也就是執(zhí)行指令的過程。

指令：指示計(jì)算機(jī)執(zhí)行特定操作（告訴計(jì)算機(jī)做什么以及如何做）的命令，一條指令是計(jì)算機(jī)硬件可以執(zhí)行的一步操作。（1）取指令（讀?。嚎刂破鲝拇鎯?chǔ)器中取出一條指令；（2）分析指令（譯碼）：控制器分析所取指令的操作碼，確定執(zhí)行什么操作；（3）執(zhí)行指令（執(zhí)行）：控制器根據(jù)所取指令的含義，發(fā)出相應(yīng)的操作命令，控制運(yùn)算器進(jìn)行指定的運(yùn)算?！白x取-譯碼-執(zhí)行”指令執(zhí)行周期，稱為機(jī)器周期。72小結(jié)：馮?諾依曼結(jié)構(gòu)的主要思想

計(jì)算機(jī)系統(tǒng)由計(jì)算機(jī)硬件和計(jì)算機(jī)軟件構(gòu)成；

計(jì)算機(jī)硬件：構(gòu)成計(jì)算機(jī)系統(tǒng)的所有物理器件（集成電路、電路板以及其他電子元件等）、部件和設(shè)備（控制器、運(yùn)算器、存儲(chǔ)器、輸入/輸出設(shè)備等）的集合；

計(jì)算機(jī)軟件：用程序設(shè)計(jì)語言編寫的程序，以及運(yùn)行程序所需的文檔、數(shù)據(jù)的集合。計(jì)算機(jī)誕生之日起，人們探索的重點(diǎn)不僅在于建造運(yùn)算速度更快、處理能力更強(qiáng)的計(jì)算機(jī)，而且在于開發(fā)能讓人們更有效地使用這種計(jì)算設(shè)備的各種軟件。重點(diǎn)：讓計(jì)算機(jī)能夠良好地運(yùn)轉(zhuǎn)起來重點(diǎn)：解決真實(shí)世界的問題物理層反映了在計(jì)算機(jī)上表示信息的方式，換言之，如何表示數(shù)值、字符、文字、聲音、圖形和圖像等信息，如何使門和電路控制電流實(shí)現(xiàn)數(shù)據(jù)的存儲(chǔ)和運(yùn)算。二進(jìn)制數(shù)字世界：信息（數(shù)據(jù)、指令）的編碼電子元件：門、邏輯電路、集成電路

硬件機(jī)器層反映了構(gòu)成計(jì)算機(jī)硬件的主要部件、部件的主要性能以及這些部件之間的連接方式。

二進(jìn)制數(shù)字世界：信息（數(shù)據(jù)、指令）的編碼電子元件：門、邏輯電路、集成電路

計(jì)算機(jī)部件：存儲(chǔ)器、CPU、輸入/輸出設(shè)備

硬件系統(tǒng)軟件用于擴(kuò)展計(jì)算機(jī)的硬件功能，維護(hù)整個(gè)計(jì)算機(jī)系統(tǒng)，為應(yīng)用開發(fā)人員提供平臺(tái)支持。

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

硬件軟件工具軟件、語言翻譯程序

操作系統(tǒng)：計(jì)算機(jī)的管家

系統(tǒng)軟件層閱讀：奠定計(jì)算機(jī)理論基礎(chǔ)的重要人物和思想布爾及邏輯代數(shù)香農(nóng)及計(jì)算機(jī)開關(guān)電路圖靈及圖靈機(jī)、圖靈測(cè)試阿塔納索夫及ABC計(jì)算機(jī)維納及計(jì)算機(jī)設(shè)計(jì)五原則馮.諾依曼及馮.諾依曼結(jié)構(gòu)思考題：2什么是計(jì)算機(jī)學(xué)科計(jì)算機(jī)學(xué)科的定義計(jì)算機(jī)學(xué)科是研究計(jì)算機(jī)的設(shè)計(jì)、制造和利用計(jì)算機(jī)進(jìn)行信息獲取、表示、存儲(chǔ)、處理、控制等的理論、原則、方法和技術(shù)的學(xué)科，包括科學(xué)和技術(shù)兩方面。計(jì)算機(jī)科學(xué)側(cè)重于研究現(xiàn)象、揭示規(guī)律。計(jì)算機(jī)技術(shù)側(cè)重于研制計(jì)算機(jī)和研究使用計(jì)算機(jī)進(jìn)行信息處理的方法和手段?？茖W(xué)與技術(shù)相輔相成，相互作用。計(jì)算機(jī)學(xué)科還具有較強(qiáng)的工程性理論教學(xué)與實(shí)踐教學(xué)并重?；A(chǔ)理論知識(shí)扎實(shí)/動(dòng)手能力強(qiáng)。計(jì)算機(jī)學(xué)科是科學(xué)性/工程性/技術(shù)性的統(tǒng)一側(cè)重點(diǎn)不同的學(xué)科分支計(jì)算機(jī)科學(xué)/計(jì)算機(jī)工程/軟件工程/信息技術(shù)。計(jì)算機(jī)學(xué)科和數(shù)學(xué)密切相關(guān)

3計(jì)算機(jī)學(xué)科的經(jīng)典問題程序設(shè)計(jì)方法學(xué)圖論進(jìn)程同步計(jì)算復(fù)雜性NP問題組合爆炸人工智能/201304/19690.html哥尼斯堡七橋問題18世紀(jì)的東普魯士有一座名叫哥尼斯堡的城堡，城中有一個(gè)島。普雷格爾河的兩條支流環(huán)繞其旁，并將整個(gè)城市分成北區(qū)、東區(qū)、南區(qū)和島區(qū)4個(gè)區(qū)域。全城共有7座橋，這7座橋?qū)?個(gè)城區(qū)連起來，如右圖所示。人們常通過這7座橋到各城區(qū)游玩，于是產(chǎn)生了一個(gè)有趣的數(shù)學(xué)難題：尋找不重復(fù)地走遍這7座橋回到原出發(fā)點(diǎn)的路徑。該問題就是著名的哥尼斯堡七橋問題。1736年大數(shù)學(xué)家列昂納德·歐拉發(fā)表了關(guān)于哥尼斯堡七橋問題的論文——《與位置幾何有關(guān)的一個(gè)問題的解》。他在文中指出，從一點(diǎn)出發(fā)不重復(fù)地走遍7座橋最后又回到原出發(fā)點(diǎn)是不可能的。為了解決哥尼斯堡七橋問題，歐拉用4個(gè)字母A、B、C、D代表4個(gè)城區(qū)并用7條線表示7座橋，如右圖所示。圖中，只有4個(gè)點(diǎn)和7條線。它抽象出問題最本質(zhì)的東西，忽視問題非本質(zhì)的東西如橋的長(zhǎng)度等。從而將哥尼斯堡七橋問題抽象為一個(gè)數(shù)學(xué)問題，即經(jīng)過圖中各邊一次且僅一次的回路問題。歐拉在論文中論證了這樣的回路是不存在的，后來人們把存在這種回路的圖稱為歐拉圖。歐拉在將問題進(jìn)行了一般化處理，即對(duì)給定的任意一個(gè)河道圖與任意多座橋，判定是否能每座橋恰好走過一次，并用數(shù)學(xué)方法給出了3條判定的規(guī)則：1）如果通奇數(shù)座橋的地方不止兩個(gè)，滿足要求的路線是找不到的。2）如果只有兩個(gè)地方通奇數(shù)座橋，可以從這兩個(gè)地方之一出發(fā)，找到所要求的路線。3）如果沒有一個(gè)地方是通奇數(shù)座橋的，則無論從哪里出發(fā)所要求的路線都能實(shí)現(xiàn)。可計(jì)算問題與不可計(jì)算問題Turing論題：一個(gè)問題是可計(jì)算的當(dāng)且僅當(dāng)它在圖靈機(jī)上經(jīng)過有限步驟最后得到正確的結(jié)果。Turing論題把人類面臨的所有問題劃分成兩類，一類是可計(jì)算的，另一類是不可計(jì)算的。Turing論題中“有限步驟”是一個(gè)相當(dāng)寬松的條件，即使需要計(jì)算幾個(gè)世紀(jì)的問題，在理論上也都是可計(jì)算的。因此Turing論題界定出的可計(jì)算問題幾乎包括了人類遇到的所有問題。4計(jì)算機(jī)學(xué)科的根本問題不可計(jì)算問題的典型例子

停機(jī)問題。給定一個(gè)計(jì)算機(jī)程序和一個(gè)特定的輸入，判斷該程序是否可以停機(jī)。如果停機(jī)問題是可計(jì)算的，那么編譯系統(tǒng)就能夠在運(yùn)行程序之前檢查出程序中是否有死循環(huán)，事實(shí)上，當(dāng)一個(gè)程序處于死循環(huán)時(shí)，系統(tǒng)無法確切地知道它只是一個(gè)很慢的程序，還是一個(gè)進(jìn)入死循環(huán)的程序。判斷一個(gè)程序中是否包含計(jì)算機(jī)病毒。實(shí)際的病毒檢測(cè)程序做得很好，通常能夠確定一個(gè)程序中是否包含特定的計(jì)算機(jī)病毒，至少能夠檢測(cè)現(xiàn)在已經(jīng)知道的那些病毒，但是心懷惡意的人總能開發(fā)出病毒檢測(cè)程序還不能夠識(shí)別出來的新病毒，換言之，不存在一個(gè)病毒檢測(cè)程序，能夠檢測(cè)出所有未來的新病毒。易解問題與難解問題

認(rèn)識(shí)計(jì)算機(jī)學(xué)科——易解問題理論上可計(jì)算的問題不一定是實(shí)際可計(jì)算的。

Cook論題：一個(gè)問題是實(shí)際可計(jì)算的當(dāng)且僅當(dāng)它在圖靈機(jī)上經(jīng)過多項(xiàng)式步驟得到正確的結(jié)果。

易解問題：可以在多項(xiàng)式時(shí)間內(nèi)求解的問題，這類問題在可以接受的時(shí)間內(nèi)實(shí)現(xiàn)問題求解。

難解問題：需要指數(shù)時(shí)間求解的問題，這類問題的計(jì)算時(shí)間隨著問題規(guī)模（輸入量的大?。┑脑鲩L(zhǎng)而快速增長(zhǎng)，即使中等規(guī)模的輸入，其計(jì)算時(shí)間也是以世紀(jì)來衡量的。難解問題的典型例子漢諾塔問題：在世界剛被創(chuàng)建的時(shí)候有一座寶塔（塔A），其上有64個(gè)金碟。所有碟子按從大到小的次序從塔底堆放至塔頂。緊挨著這座塔有另外兩個(gè)寶塔（塔B和塔C）。從世界創(chuàng)始之日起，婆羅門的牧師們就一直在試圖把塔A上的碟子移動(dòng)到塔C上去，其間借助于塔B的幫助。每次只能移動(dòng)一個(gè)碟子，任何時(shí)候都不能把一個(gè)碟子放在比它小的碟子上面。當(dāng)牧師們完成任務(wù)時(shí)，世界末日也就到了。ABC難解問題的典型例子ABC難解問題的典型例子難解問題的典型例子1212221222)0(21)1)2(2(21)1(2)(121121-=++++=+++++==++-=+-=--nnnnhnhnhnh………h(huán)(64)=264-1=18,446,744,073,709,551,615如果每秒移動(dòng)一次，則僧侶們一刻不停地來回移動(dòng)，則需要花費(fèi)5849億年的時(shí)間；假定計(jì)算機(jī)以每秒1000萬個(gè)碟子的速度進(jìn)行移動(dòng)，則需要花費(fèi)58,490年的時(shí)間。證比求易認(rèn)識(shí)計(jì)算機(jī)學(xué)科——NP問題通常來說，求解一個(gè)問題往往比較困難，但驗(yàn)證一個(gè)問題相對(duì)來說就比較容易，也就是證比求易。從是否可以被驗(yàn)證的角度，計(jì)算復(fù)雜性理論將難解問題劃分為NP問題和非NP問題。

NP問題：可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證的問題。

NP完全問題：NP問題中有大量問題都具有這樣的特性：可以多項(xiàng)式時(shí)間內(nèi)得到驗(yàn)證，但是不知道是否可以在多項(xiàng)式時(shí)間內(nèi)得到求解，同時(shí)，我們不能證明這些問題中的任何一個(gè)無法在多項(xiàng)式時(shí)間內(nèi)得到求解，這類問題稱為NP完全問題。

NP完全問題的典型例子TSP問題（又稱貨郎擔(dān)問題、郵遞員問題、售貨員問題）是數(shù)學(xué)家克克曼于19世紀(jì)初提出的一個(gè)數(shù)學(xué)問題，是指旅行家要旅行n個(gè)城市然后回到出發(fā)城市，要求各個(gè)城市經(jīng)歷且僅經(jīng)歷一次，并要求所走的路程最短。8abdc23571否18a→d→c→b→a6否23a→d→b→c→a5是11a→c→d→b→a4否23a→c→b→d→a3是11a→b→d→c→a2否18a→b→c→d→a1是否最短路徑長(zhǎng)度路徑序號(hào)NP完全問題的典型例子對(duì)于具有n個(gè)頂點(diǎn)的TSP問題，可能的解有(n-1)!/2個(gè)。10城市的TSP問題有大約180,000個(gè)可能解。20城市的TSP問題有大約60,000,000,000,000,000個(gè)可能解。50城市的TSP問題有大約1062個(gè)可能解。考慮TSP問題的驗(yàn)證形式：給定一個(gè)正整數(shù)k，是否存在一條路徑長(zhǎng)度小于k的簡(jiǎn)單回路。假設(shè)有一個(gè)可以同時(shí)測(cè)試所有可能答案的超級(jí)并行計(jì)算機(jī)，首先生成TSP問題的所有可能的回路，然后并行驗(yàn)證所有可能的答案，即把各個(gè)邊的代價(jià)加起來，驗(yàn)證路徑長(zhǎng)度是否小于k。顯然，這可以在多項(xiàng)式時(shí)間內(nèi)得到驗(yàn)證。NP完全問題的典型例子科學(xué)問題的提出和解決是任何一個(gè)學(xué)科持續(xù)發(fā)展的動(dòng)力，一個(gè)學(xué)科如果沒有科學(xué)問題需要解決，這個(gè)學(xué)科的生命也就該結(jié)束了。在計(jì)算機(jī)學(xué)科各個(gè)分支學(xué)科方向的發(fā)展進(jìn)程中，存在一些在表現(xiàn)形式上雖然不同，但在科學(xué)哲學(xué)的解釋下本質(zhì)上是相同或相近的問題，即學(xué)科研究與發(fā)展普遍關(guān)心的基本問題。什么是科學(xué)問題5.認(rèn)識(shí)計(jì)算機(jī)學(xué)科——科學(xué)問題為了實(shí)現(xiàn)自動(dòng)計(jì)算，人們首先想到要發(fā)明和制造自動(dòng)計(jì)算機(jī)器，不僅要在理論上提供計(jì)算的平臺(tái)——觀察和描述計(jì)算的起點(diǎn)，而且要實(shí)際制造出能夠真正運(yùn)行的自動(dòng)計(jì)算機(jī)器。進(jìn)一步地，從廣義計(jì)算的概念出發(fā)，計(jì)算的平臺(tái)在使用上還必須方便，例如，計(jì)算模型、計(jì)算機(jī)體系結(jié)構(gòu)、實(shí)際的計(jì)算機(jī)系統(tǒng)、系統(tǒng)軟件和工具軟件、高級(jí)程序設(shè)計(jì)語言、軟件開發(fā)工具與環(huán)境等都是圍繞這一基本問題展開的，其核心是計(jì)算的能行性。計(jì)算的平臺(tái)與環(huán)境問題哲學(xué)家共餐問題與計(jì)算機(jī)資源管理哲學(xué)家的生活進(jìn)程可表示為：（1）思考問題；（2）俄了停止思考，左手拿起一只筷子（如果左側(cè)哲學(xué)家已持有它，則等待）；（3）右手拿起一只筷子（如果右側(cè)哲學(xué)家已持有它，則等待）；（4）進(jìn)餐；（5）放下左手筷子；（6）放下右手筷子；（7）重新回到狀態(tài)（1）思考問題；程序并發(fā)執(zhí)行時(shí)進(jìn)程同步的兩個(gè)關(guān)鍵問題——死鎖和饑餓：（1）按哲學(xué)家的生活進(jìn)程，當(dāng)所有的哲學(xué)家都同時(shí)拿起左手筷子時(shí)，則所有哲學(xué)家都將拿不到右手筷子，并處于等待狀態(tài)，那么，哲學(xué)家都將無法進(jìn)餐，最終餓死。（2）將哲學(xué)家的生活進(jìn)程修改為當(dāng)拿不到右手筷子時(shí)，就放下左手筷子。但是，可能在一個(gè)瞬間，所有的哲學(xué)家都同時(shí)拿起左手筷子，則自然拿不到右手筷子，于是都同時(shí)放下左手筷子，等一會(huì)，又同時(shí)拿起左手筷子，如此重復(fù)下去，則所有的哲學(xué)家都將無法進(jìn)餐。很久以前，有一個(gè)年輕的國王向鄰國一位聰明美麗的公主求婚，公主出了這樣一道題：求出48770428433377171的一個(gè)因子，若國王能在一天之內(nèi)求出答案，便接受國王的求婚。證比求易與并行計(jì)算嫁給我好嗎？那你回答一個(gè)問題吧。國王回去后立即開始逐個(gè)數(shù)地進(jìn)行試除，總共試了三萬多個(gè)數(shù)，還是沒有結(jié)果。國王向公主求情，公主將答案相告：223092827是它的一個(gè)因子，國王很快就驗(yàn)證了這個(gè)數(shù)的確能除盡48770428433377171。告訴你吧，223092827是它的一個(gè)因子再給我一次機(jī)會(huì)吧！國王立即回國，并向時(shí)任宰相的大數(shù)學(xué)家求教，宰相在仔細(xì)地思考后認(rèn)為這個(gè)數(shù)為17位，如果這個(gè)數(shù)存在因子，則最小的一個(gè)因子不會(huì)超過9位。于是，他給國王出了一個(gè)主意：按自然數(shù)的順序給全國的老百姓每人編一個(gè)號(hào)發(fā)下去，等公主給出數(shù)后，立即將它通報(bào)全國，讓每個(gè)老百姓用自己的編號(hào)去除這個(gè)數(shù)，除盡了立即上報(bào)，賞金萬兩。最后國王用這個(gè)辦法求婚成功。國王使用的是串行算法，宰相提出的是一種并行算法。一個(gè)問題在判定為可計(jì)算問題后，為求解這個(gè)問題，必須給出實(shí)際解決該問題的操作序列，同時(shí)還必須確保操作序列的資源（時(shí)間和空間）消耗是合理的。圍繞這一問題，計(jì)算機(jī)學(xué)科發(fā)展了大量與之相關(guān)的研究?jī)?nèi)容與分支學(xué)科方向。例如，集成電路技術(shù)、數(shù)字系統(tǒng)邏輯設(shè)計(jì)、自動(dòng)布線技術(shù)、RISC技術(shù)、數(shù)值計(jì)算方法、算法設(shè)計(jì)技術(shù)、計(jì)算復(fù)雜性理論、密碼學(xué)、演化計(jì)算、人工智能等都是圍繞這一基本問題展開的，其核心是計(jì)算的效率。計(jì)算過程的能行操作與效率問題背包問題：給定n種物品和一個(gè)容量為C的背包，物品i的重量是wi，其價(jià)值為vi，如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值