




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
計算機學(xué)科的基本概念計:數(shù)數(shù)或者進行計數(shù)算:算籌等工具計算:最原始的含義利用計算工具進行計數(shù)進一步,計算首先指數(shù)的加減乘除、平方、開方等初等運算,其次為函數(shù)的微分、積分等高等運算,以及方程的求解、代數(shù)的化簡、定理的證明等。1計算與計算科學(xué)計算的本質(zhì)是什么呢?1930年代,哥德爾、丘奇、圖靈等數(shù)學(xué)家的工作,人們才弄清楚什么是計算的本質(zhì),什么是可計算的、什么是不可計算的等根本性問題。抽象地說,所謂計算,就是從一個符號串f變換成另一個符號串g。如,從符號串12+3變換成15就是一個加法計算。如果符號串f是X2,而符號串g是2x,從f到g的計算就是微分。定理證明也如此。令f表示一組公理和推導(dǎo)規(guī)則,令g是一個定理,那么從f到g的一系列變換就是定理g的證明。文字翻譯也是計算,如f代表一個英文句子,而g為含意相同的中文句子,那么從f到g就是把英文翻譯成中文。計算的本質(zhì)這些變換間有什么共同點?為什么把它們都叫做計算?因為它們都是從己知符號(串)開始,一步一步地改變符號(串),經(jīng)過有限步驟,最后得到一個滿足預(yù)先規(guī)定的符號(串)的變換過程。計算的本質(zhì)計算的類型從類型上講,主要有兩大類:數(shù)值計算和符號推導(dǎo)。數(shù)值計算包括實數(shù)和函數(shù)的加減乘除、幕運算、開方運算、方程的求解等。符號推導(dǎo)包括代數(shù)與各種函數(shù)的恒等式、不等式的證明,幾何命題的證明等。無論是數(shù)值計算還是符號推導(dǎo),它們在本質(zhì)上是等價的、一致的,即二者是密切關(guān)聯(lián)的,可以相互轉(zhuǎn)化,具有共同的計算本質(zhì)。隨著數(shù)學(xué)的發(fā)展,還可能出現(xiàn)新的計算類型。什么是可計算的?可計算的描述方式:形式系統(tǒng)例:狼羊白菜過河問題描述問題:農(nóng)夫帶著狼、羊、白菜從河的左岸到河的右岸,農(nóng)夫每次只能帶一樣?xùn)|西多河,而且,沒有農(nóng)夫看管,狼會吃羊,羊會吃白菜。提示:利用圖論解決問題。[解]:渡河的方法如下:
第一次,獵人把羊帶至右崖;
第二次,獵人單身回左岸,把白菜帶至右岸,此時右岸有獵人,羊和白菜;
第三次,獵人再把羊帶回左岸,放下羊,把狼帶至右岸,此時右岸有獵人,狼和白菜;
第四次,獵人單身回到左岸,最后把羊帶至右岸,便可完成渡河的任務(wù)。
這是一個著名的古題,同樣也是“圖論”應(yīng)用的經(jīng)典例子。
首先,用字母P、L、C和X分別代表獵人、狼、羊和白菜,即P—獵人,L—狼,C—羊,X—白菜。用字母的組合表示左岸的情況。開始時,狼、羊、白菜和獵人全在左岸,用LCXP表示;若左岸只剩下狼時,就用L表之,等等。因為狼和羊、羊和白菜不能在無人監(jiān)視的情況下共處,所以在整個渡河過程中,左岸始終不允許出現(xiàn)LC、CX、LP和XP所表示的情況。仔細地列出左岸所允許出現(xiàn)的全部情況,它們是:
LCXP,LCP,CXP,LXP,LX,CP,C,L,X,ψ,其中記號ψ表示左岸已空無所有。用A表示LCXP,用B表示ψ,那么只要在圖中找到一條由A到B的通道(折線),實際上就給出了一個滿足題意的過渡方法。狼羊白菜過河問題解法用1表示在左岸,0表示在右岸.用頂點序號的二進制碼的0位表示農(nóng)夫,1位表示狼,2位表示羊,3位表示菜.那么,總共可能有16個頂點0-15.頂點0表示全在左岸,頂點15表示全在右岸.有些頂點是不允許存在的,比如頂點3,表示農(nóng)夫和狼在右岸,羊和菜在左岸,羊會吃掉菜.要把所有這類的頂點去掉.在剩下的頂點中,要找出所有的可能的邊.比如頂點5表示農(nóng)夫和羊在右,狼和菜在左,頂點4表示羊在右,那么就存在頂點5到頂點4的有向邊.至此,圖已構(gòu)造完畢,問題就轉(zhuǎn)換成找到一條從頂點0到頂點15的合理路徑.編程作業(yè):八皇后問題。是19世紀著名數(shù)學(xué)家高斯1850年提出:在8X8格的國際象棋上擺放八個皇后,使其不能互相攻擊,即任意兩個皇后都不能處于同一行、同一列或同一斜線上,問有多少種擺法。計算科學(xué)正是在探索“什么是計算?什么是可計算的?什么是不可計算的?”這些根本性問題的基礎(chǔ)上形成的。悖論舉例某理發(fā)師發(fā)誓“要給所有不自已理發(fā)的人理發(fā),不給所有自己理發(fā)的人理發(fā)”?,F(xiàn)在的問題是“誰為該理發(fā)師理發(fā)?”。首先,若理發(fā)師給自己理發(fā),那他就是一個“自己理發(fā)的人”,依其誓言“他不給自己理發(fā)”;其次,若“他不給自己理發(fā)”,依其誓言,他就必須“給自己理發(fā)”圖靈等提出可計算函數(shù)的模型對計算科學(xué)產(chǎn)生深遠影響。圖靈機模型1936年,圖靈向倫敦權(quán)威的數(shù)學(xué)雜志投了一篇論文,題為”論可計算及其在判定問題中的應(yīng)用“。在這篇開創(chuàng)性的論文中,圖靈給”可計算性“下了一個嚴格的數(shù)學(xué)定義,并提出”圖靈機(TuringMachine)“的設(shè)想。”圖靈機“并不是一種具體的機器,而是一種思想,可制造一種十分簡單但運算能力極強的計算裝置,用來計算所有能想象得到的可計算函數(shù)。圖靈機模型圖靈機模型圖靈的基本思想是用機器來模擬人們用紙筆進行數(shù)學(xué)運算的過程,為了模擬人的這種運算過程,圖靈構(gòu)造出一臺假想的機器,該機器由以下幾個部分組成:
有限狀態(tài)控制器工作帶
一條無限長的工作帶:工作帶上的每個單元可以存放一個符號;所有允許出現(xiàn)的符號屬于一個預(yù)先規(guī)定好的字母表。
一個讀寫頭:讀寫頭可以左移一個單元、右移一個單元或者保持不動。有限狀態(tài)控制器工作帶一個控制器:控制器在每個時刻處于一定狀態(tài),當(dāng)讀寫頭從工作帶上讀出一個符號后,控制器就根據(jù)這個符號和當(dāng)時的機器狀態(tài),指揮讀寫頭進行讀寫或者移動,并決定是否改變機器狀態(tài)。有限狀態(tài)控制器工作帶計算與可計算所謂計算就是計算者(人或機器)對一條可以無限延長的工作帶上的符號串執(zhí)行指令,一步一步地改變工作帶上的符號串,經(jīng)過有限步驟,最后得到一個滿足預(yù)先規(guī)定的符號串的變換過程??刂破鞯拿羁梢杂梦逶M表示:(q1,s1,s2,r,q2)q1:當(dāng)前狀態(tài);s1:讀寫頭從當(dāng)前讀入的數(shù)據(jù);s2:讀寫頭即將寫入當(dāng)前方格的數(shù)據(jù);r:讀寫頭移動(右/左/不動)q2:新狀態(tài)一旦圖靈機在運行中進入了一個狀態(tài),而且這個狀態(tài)就是一個結(jié)束狀態(tài),那么,圖靈機就停機,計算任務(wù)完成,此時帶上的內(nèi)容就是計算輸出的結(jié)果。例:圖靈機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分別表示讀寫頭向左移動一格、向右移動一格、保持不動三個基本操作。假如此時M讀入是11100b0011,讀寫頭對準第一個1,狀態(tài)為q1,請給出輸出結(jié)果。bbb1100b0011bbbq1構(gòu)造該圖靈機的基本思想:使讀寫頭往返移動,每往返移動一次,就成對地對輸入符號串ω左端的一個a和右端的一個b匹配并做標記x。如果恰好把輸入符號串ω的所有符號都做了標記,說明左端的符號a和右端的符號b的個數(shù)相等;否則,說明左端的符號a和右端的符號b的個數(shù)不相等,或者符號a和b交替出現(xiàn)。例:構(gòu)造一個識別符號串ω=anbn(n≥1)的圖靈機控制器的操作指令(也就是程序)如下:(q0aaRq0) (q0bxLq1)(q1xxLq1) (q1axRq2) (q1BBHqN)(q2xxRq2) (q2bxLq1) (q2BBLq3)(q3xxLq3) (q3aaHqN) (q3BBHqF)控制器的指令序列對應(yīng)一個狀態(tài)轉(zhuǎn)移圖,計算就是在執(zhí)行指令的過程進行狀態(tài)的變化,也是變換符號的過程。(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,BBHqN)(q2,xxRq2)程序假定n=2,輸入符號串ω=aabb,圖靈機的工作過程如下:控制器BaabbB指令機器狀態(tài)當(dāng)前讀到的字符當(dāng)前寫入的字符讀寫頭的動作R:右移L:左移H:不動下一機器狀態(tài)讀寫頭(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,B
BHqN)(q2,xxRq2)讀寫頭程序控制器BaabbB讀寫頭掃描到符號a,則繼續(xù)往右走(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,B
BHqN)(q2,xxRq2)讀寫頭程序控制器BaabbB讀寫頭掃描到符號a,則繼續(xù)往右走(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,B
BHqN)(q2,xxRq2)讀寫頭程序控制器BaabbB讀寫頭掃描到符號b,將當(dāng)前單元寫入字符x,并使讀寫頭往左走,轉(zhuǎn)移到狀態(tài)q1。
(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,B
BHqN)(q2,xxRq2)讀寫頭程序控制器BaaxbB讀寫頭掃描到符號b,將當(dāng)前單元寫入字符x,并使讀寫頭往左走,轉(zhuǎn)移到狀態(tài)q1。
(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,B
BHqN)(q2,xxRq2)讀寫頭程序控制器BaaxbB讀寫頭掃描到符號a,則把a改為標記x,并使讀寫頭往右走,轉(zhuǎn)移到狀態(tài)q2
(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,B
BHqN)(q2,xxRq2)讀寫頭程序控制器Bax
xbB讀寫頭掃描到符號a,則把a改為標記x,并使讀寫頭往右走,轉(zhuǎn)移到狀態(tài)q2
(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,B
BHqN)(q2,xxRq2)讀寫頭程序控制器Bax
xbB讀寫頭掃描到標記x,則繼續(xù)往右走
(q2,bxLq1)(q2,BBLq3)(q3,xxLq3)(q3,aaH
qN)(q3,BBHq4)讀寫頭程序控制器Bax
xbB若讀寫頭掃描到符號b,則把b改為標記x,并使讀寫頭往左走,轉(zhuǎn)移到狀態(tài)q1
讀寫頭程序控制器Bax
x
xB若讀寫頭掃描到符號b,則把b改為標記x,并使讀寫頭往左走,轉(zhuǎn)移到狀態(tài)q1
(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,B
BHqN)(q2,xxRq2)讀寫頭程序控制器Bax
x
xB讀寫頭掃描到標記x,則繼續(xù)往左走
(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,B
BHqN)(q2,xxRq2)讀寫頭程序控制器Bax
x
xB讀寫頭掃描到符號a,則把a改為標記x,并使讀寫頭往右走,轉(zhuǎn)移到狀態(tài)q2;
(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,B
BHqN)(q2,xxRq2)讀寫頭程序控制器Bx
x
x
xB讀寫頭掃描到標記x,則繼續(xù)往右走
(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,B
BHqN)(q2,xxRq2)讀寫頭程序控制器Bx
x
x
xB讀寫頭掃描到標記x,則繼續(xù)往右走
(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,B
BHqN)(q2,xxRq2)讀寫頭程序控制器Bx
x
x
xB讀寫頭掃描到標記x,則繼續(xù)往右走
(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,B
BHqN)(q2,xxRq2)讀寫頭程序控制器Bx
x
x
xB讀寫頭掃描到空白符B,說明符號b已處理完畢,則把狀態(tài)改為q3,并使讀寫頭往左走
(q2,bxLq1)(q2,BBLq3)(q3,xxLq3)(q3,aaH
qN)(q3,BBHq4)讀寫頭程序控制器Bx
x
x
xB讀寫頭掃描到空白符B,說明符號b已處理完畢,則把狀態(tài)改為q3,并使讀寫頭往左走
(q2,bxLq1)(q2,BBLq3)(q3,xxLq3)(q3,aaH
qN)(q3,BBHq4)讀寫頭程序控制器Bx
x
x
xB讀寫頭掃描到標記x,則繼續(xù)往左走
(q2,bxLq1)(q2,BBLq3)(q3,xxLq3)(q3,aaH
qN)(q3,BBHq4)讀寫頭程序控制器Bx
x
x
xB讀寫頭掃描到標記x,則繼續(xù)往左走
(q2,bxLq1)(q2,BBLq3)(q3,xxLq3)(q3,aaH
qN)(q3,BBHq4)讀寫頭程序控制器Bx
x
x
xB讀寫頭掃描到標記x,則繼續(xù)往左走
(q2,bxLq1)(q2,BBLq3)(q3,xxLq3)(q3,aaH
qN)(q3,BBHq4)讀寫頭程序控制器Bx
x
x
xB讀寫頭掃描到空白符B,說明符號a和b已成對標記,轉(zhuǎn)移到狀態(tài)q4,達到接受狀態(tài)。
(q2,bxLq1)(q2,BBLq3)(q3,xxLq3)(q3,aaH
qN)(q3,BBHq4)從圖靈模型我們看到了什么?圖靈模型在一定程度上反映了人類最基本的、最原始的計算能力,它的基本動作非常簡單、機械、確定。因此,可以用真正的機器來實現(xiàn)圖靈機。程序并非必須順序執(zhí)行,指令中關(guān)于下一狀態(tài)的指定,實際上表明指令可以不按程序中所表示的順序執(zhí)行。這意味著,雖然程序只能按線性順序來表示指令序列,但程序的實際執(zhí)行可以與表示的順序不同。計算的對象、中間結(jié)果和最終結(jié)果都在帶上,程序則在控制器中。這意味著什么?為紀念圖靈對計算機的貢獻,美國計算機博物館于1966年設(shè)立了“圖靈獎”"圖靈機"在計算機歷史上與”馮.諾依曼機“齊名。馮.諾依曼的助手弗蘭克曾在一封信中寫道:”......計算機的基本概念屬于圖靈。按照我的看法,馮.諾依曼的基本作用是使世界認識了由圖靈引入的計算機的基本概念...”59馮?諾依曼生平簡介60馮諾依曼/圖靈StoredProgramconceptMainmemorystoringprogramsanddata
主存儲器:用于存儲數(shù)據(jù)和指令A(yù)LUoperatingonbinarydata
能夠操作二進制數(shù)的算術(shù)邏輯單元Controlunitinterpretinginstructionsfrommemoryandexecuting
控制器:解釋內(nèi)存中的指令并執(zhí)行Inputandoutputequipmentoperatedbycontrolunit
由控制器操縱的輸入、輸出設(shè)備6162存儲器運算器控制器輸出設(shè)備輸入設(shè)備1.輸入設(shè)備:用于將程序(指令的集合,告訴計算機做什么以及怎么做的工作步驟)和數(shù)據(jù)從外界輸入計算機(存儲器),供計算機處理,主要任務(wù)是數(shù)字化。馮·諾伊曼體系結(jié)構(gòu)存儲器運算器控制器輸出設(shè)備輸入設(shè)備2.存儲器:是計算機的記憶裝置,用于存放程序和數(shù)據(jù)。存儲器運算器控制器輸出設(shè)備輸入設(shè)備3.運算器:是計算機對數(shù)據(jù)進行加工處理的部件,完成加、減、乘、除等基本算術(shù)運算和與、或、非等基本邏輯運算。存儲器運算器控制器輸出設(shè)備輸入設(shè)備4.控制器:用于控制計算機各部件協(xié)調(diào)工作??刂破鲝拇鎯ζ髦腥〕鲋噶睿ǜ嬖V計算機做什么以及怎么做)并根據(jù)指令向有關(guān)部件發(fā)出控制命令。存儲器運算器控制器輸出設(shè)備輸入設(shè)備5.輸出設(shè)備:用于將計算機的處理結(jié)果轉(zhuǎn)換成外界能夠識別的文字、電壓等信息并輸出。計算機:是能夠按照事先存儲的程序,自動、高速地對數(shù)據(jù)進行輸入、處理、輸出和存儲的系統(tǒng)。計算機=數(shù)據(jù)處理機數(shù)據(jù)結(jié)果整數(shù)、實數(shù)、文字、聲音、圖形、圖像等,甚至包括電壓、表情等整數(shù)、實數(shù)、文字、聲音、圖形、圖像等,甚至包括各種控制動作輸入:接收由輸入設(shè)備(如鍵盤、鼠標等)提供的數(shù)據(jù)。處理:對數(shù)值、邏輯字符等各種類型的數(shù)據(jù)進行操作,按指定的方式進行轉(zhuǎn)換和加工。輸出:將處理所產(chǎn)生的結(jié)果等送到相關(guān)輸出設(shè)備(如顯示器、打印機、繪圖儀等)。存儲:可以存儲程序和數(shù)據(jù)。馮·諾依曼體系結(jié)構(gòu)的主要特征:存儲程序。
存儲程序:事先編制好程序并將程序(指令的集合)和數(shù)據(jù)存入計算機的存儲器中,計算機在運行時就能自動、連續(xù)地從存儲器中逐條取出指令并執(zhí)行,因此,計算機的工作過程就是運行程序的過程,也就是執(zhí)行指令的過程。
指令:指示計算機執(zhí)行特定操作(告訴計算機做什么以及如何做)的命令,一條指令是計算機硬件可以執(zhí)行的一步操作。(1)取指令(讀取):控制器從存儲器中取出一條指令;(2)分析指令(譯碼):控制器分析所取指令的操作碼,確定執(zhí)行什么操作;(3)執(zhí)行指令(執(zhí)行):控制器根據(jù)所取指令的含義,發(fā)出相應(yīng)的操作命令,控制運算器進行指定的運算?!白x取-譯碼-執(zhí)行”指令執(zhí)行周期,稱為機器周期。72小結(jié):馮?諾依曼結(jié)構(gòu)的主要思想
計算機系統(tǒng)由計算機硬件和計算機軟件構(gòu)成;
計算機硬件:構(gòu)成計算機系統(tǒng)的所有物理器件(集成電路、電路板以及其他電子元件等)、部件和設(shè)備(控制器、運算器、存儲器、輸入/輸出設(shè)備等)的集合;
計算機軟件:用程序設(shè)計語言編寫的程序,以及運行程序所需的文檔、數(shù)據(jù)的集合。計算機誕生之日起,人們探索的重點不僅在于建造運算速度更快、處理能力更強的計算機,而且在于開發(fā)能讓人們更有效地使用這種計算設(shè)備的各種軟件。重點:讓計算機能夠良好地運轉(zhuǎn)起來重點:解決真實世界的問題物理層反映了在計算機上表示信息的方式,換言之,如何表示數(shù)值、字符、文字、聲音、圖形和圖像等信息,如何使門和電路控制電流實現(xiàn)數(shù)據(jù)的存儲和運算。二進制數(shù)字世界:信息(數(shù)據(jù)、指令)的編碼電子元件:門、邏輯電路、集成電路
硬件機器層反映了構(gòu)成計算機硬件的主要部件、部件的主要性能以及這些部件之間的連接方式。
二進制數(shù)字世界:信息(數(shù)據(jù)、指令)的編碼電子元件:門、邏輯電路、集成電路
計算機部件:存儲器、CPU、輸入/輸出設(shè)備
硬件系統(tǒng)軟件用于擴展計算機的硬件功能,維護整個計算機系統(tǒng),為應(yīng)用開發(fā)人員提供平臺支持。
計算機硬件
硬件軟件工具軟件、語言翻譯程序
操作系統(tǒng):計算機的管家
系統(tǒng)軟件層閱讀:奠定計算機理論基礎(chǔ)的重要人物和思想布爾及邏輯代數(shù)香農(nóng)及計算機開關(guān)電路圖靈及圖靈機、圖靈測試阿塔納索夫及ABC計算機維納及計算機設(shè)計五原則馮.諾依曼及馮.諾依曼結(jié)構(gòu)思考題:2什么是計算機學(xué)科計算機學(xué)科的定義計算機學(xué)科是研究計算機的設(shè)計、制造和利用計算機進行信息獲取、表示、存儲、處理、控制等的理論、原則、方法和技術(shù)的學(xué)科,包括科學(xué)和技術(shù)兩方面。計算機科學(xué)側(cè)重于研究現(xiàn)象、揭示規(guī)律。計算機技術(shù)側(cè)重于研制計算機和研究使用計算機進行信息處理的方法和手段??茖W(xué)與技術(shù)相輔相成,相互作用。計算機學(xué)科還具有較強的工程性理論教學(xué)與實踐教學(xué)并重?;A(chǔ)理論知識扎實/動手能力強。計算機學(xué)科是科學(xué)性/工程性/技術(shù)性的統(tǒng)一側(cè)重點不同的學(xué)科分支計算機科學(xué)/計算機工程/軟件工程/信息技術(shù)。計算機學(xué)科和數(shù)學(xué)密切相關(guān)
3計算機學(xué)科的經(jīng)典問題程序設(shè)計方法學(xué)圖論進程同步計算復(fù)雜性NP問題組合爆炸人工智能/201304/19690.html哥尼斯堡七橋問題18世紀的東普魯士有一座名叫哥尼斯堡的城堡,城中有一個島。普雷格爾河的兩條支流環(huán)繞其旁,并將整個城市分成北區(qū)、東區(qū)、南區(qū)和島區(qū)4個區(qū)域。全城共有7座橋,這7座橋?qū)?個城區(qū)連起來,如右圖所示。人們常通過這7座橋到各城區(qū)游玩,于是產(chǎn)生了一個有趣的數(shù)學(xué)難題:尋找不重復(fù)地走遍這7座橋回到原出發(fā)點的路徑。該問題就是著名的哥尼斯堡七橋問題。1736年大數(shù)學(xué)家列昂納德·歐拉發(fā)表了關(guān)于哥尼斯堡七橋問題的論文——《與位置幾何有關(guān)的一個問題的解》。他在文中指出,從一點出發(fā)不重復(fù)地走遍7座橋最后又回到原出發(fā)點是不可能的。為了解決哥尼斯堡七橋問題,歐拉用4個字母A、B、C、D代表4個城區(qū)并用7條線表示7座橋,如右圖所示。圖中,只有4個點和7條線。它抽象出問題最本質(zhì)的東西,忽視問題非本質(zhì)的東西如橋的長度等。從而將哥尼斯堡七橋問題抽象為一個數(shù)學(xué)問題,即經(jīng)過圖中各邊一次且僅一次的回路問題。歐拉在論文中論證了這樣的回路是不存在的,后來人們把存在這種回路的圖稱為歐拉圖。歐拉在將問題進行了一般化處理,即對給定的任意一個河道圖與任意多座橋,判定是否能每座橋恰好走過一次,并用數(shù)學(xué)方法給出了3條判定的規(guī)則:1)如果通奇數(shù)座橋的地方不止兩個,滿足要求的路線是找不到的。2)如果只有兩個地方通奇數(shù)座橋,可以從這兩個地方之一出發(fā),找到所要求的路線。3)如果沒有一個地方是通奇數(shù)座橋的,則無論從哪里出發(fā)所要求的路線都能實現(xiàn)。可計算問題與不可計算問題Turing論題:一個問題是可計算的當(dāng)且僅當(dāng)它在圖靈機上經(jīng)過有限步驟最后得到正確的結(jié)果。Turing論題把人類面臨的所有問題劃分成兩類,一類是可計算的,另一類是不可計算的。Turing論題中“有限步驟”是一個相當(dāng)寬松的條件,即使需要計算幾個世紀的問題,在理論上也都是可計算的。因此Turing論題界定出的可計算問題幾乎包括了人類遇到的所有問題。4計算機學(xué)科的根本問題不可計算問題的典型例子
停機問題。給定一個計算機程序和一個特定的輸入,判斷該程序是否可以停機。如果停機問題是可計算的,那么編譯系統(tǒng)就能夠在運行程序之前檢查出程序中是否有死循環(huán),事實上,當(dāng)一個程序處于死循環(huán)時,系統(tǒng)無法確切地知道它只是一個很慢的程序,還是一個進入死循環(huán)的程序。判斷一個程序中是否包含計算機病毒。實際的病毒檢測程序做得很好,通常能夠確定一個程序中是否包含特定的計算機病毒,至少能夠檢測現(xiàn)在已經(jīng)知道的那些病毒,但是心懷惡意的人總能開發(fā)出病毒檢測程序還不能夠識別出來的新病毒,換言之,不存在一個病毒檢測程序,能夠檢測出所有未來的新病毒。易解問題與難解問題
認識計算機學(xué)科——易解問題理論上可計算的問題不一定是實際可計算的。
Cook論題:一個問題是實際可計算的當(dāng)且僅當(dāng)它在圖靈機上經(jīng)過多項式步驟得到正確的結(jié)果。
易解問題:可以在多項式時間內(nèi)求解的問題,這類問題在可以接受的時間內(nèi)實現(xiàn)問題求解。
難解問題:需要指數(shù)時間求解的問題,這類問題的計算時間隨著問題規(guī)模(輸入量的大?。┑脑鲩L而快速增長,即使中等規(guī)模的輸入,其計算時間也是以世紀來衡量的。難解問題的典型例子漢諾塔問題:在世界剛被創(chuàng)建的時候有一座寶塔(塔A),其上有64個金碟。所有碟子按從大到小的次序從塔底堆放至塔頂。緊挨著這座塔有另外兩個寶塔(塔B和塔C)。從世界創(chuàng)始之日起,婆羅門的牧師們就一直在試圖把塔A上的碟子移動到塔C上去,其間借助于塔B的幫助。每次只能移動一個碟子,任何時候都不能把一個碟子放在比它小的碟子上面。當(dāng)牧師們完成任務(wù)時,世界末日也就到了。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如果每秒移動一次,則僧侶們一刻不停地來回移動,則需要花費5849億年的時間;假定計算機以每秒1000萬個碟子的速度進行移動,則需要花費58,490年的時間。證比求易認識計算機學(xué)科——NP問題通常來說,求解一個問題往往比較困難,但驗證一個問題相對來說就比較容易,也就是證比求易。從是否可以被驗證的角度,計算復(fù)雜性理論將難解問題劃分為NP問題和非NP問題。
NP問題:可以在多項式時間內(nèi)驗證的問題。
NP完全問題:NP問題中有大量問題都具有這樣的特性:可以多項式時間內(nèi)得到驗證,但是不知道是否可以在多項式時間內(nèi)得到求解,同時,我們不能證明這些問題中的任何一個無法在多項式時間內(nèi)得到求解,這類問題稱為NP完全問題。
NP完全問題的典型例子TSP問題(又稱貨郎擔(dān)問題、郵遞員問題、售貨員問題)是數(shù)學(xué)家克克曼于19世紀初提出的一個數(shù)學(xué)問題,是指旅行家要旅行n個城市然后回到出發(fā)城市,要求各個城市經(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是否最短路徑長度路徑序號NP完全問題的典型例子對于具有n個頂點的TSP問題,可能的解有(n-1)!/2個。10城市的TSP問題有大約180,000個可能解。20城市的TSP問題有大約60,000,000,000,000,000個可能解。50城市的TSP問題有大約1062個可能解。考慮TSP問題的驗證形式:給定一個正整數(shù)k,是否存在一條路徑長度小于k的簡單回路。假設(shè)有一個可以同時測試所有可能答案的超級并行計算機,首先生成TSP問題的所有可能的回路,然后并行驗證所有可能的答案,即把各個邊的代價加起來,驗證路徑長度是否小于k。顯然,這可以在多項式時間內(nèi)得到驗證。NP完全問題的典型例子科學(xué)問題的提出和解決是任何一個學(xué)科持續(xù)發(fā)展的動力,一個學(xué)科如果沒有科學(xué)問題需要解決,這個學(xué)科的生命也就該結(jié)束了。在計算機學(xué)科各個分支學(xué)科方向的發(fā)展進程中,存在一些在表現(xiàn)形式上雖然不同,但在科學(xué)哲學(xué)的解釋下本質(zhì)上是相同或相近的問題,即學(xué)科研究與發(fā)展普遍關(guān)心的基本問題。什么是科學(xué)問題5.認識計算機學(xué)科——科學(xué)問題為了實現(xiàn)自動計算,人們首先想到要發(fā)明和制造自動計算機器,不僅要在理論上提供計算的平臺——觀察和描述計算的起點,而且要實際制造出能夠真正運行的自動計算機器。進一步地,從廣義計算的概念出發(fā),計算的平臺在使用上還必須方便,例如,計算模型、計算機體系結(jié)構(gòu)、實際的計算機系統(tǒng)、系統(tǒng)軟件和工具軟件、高級程序設(shè)計語言、軟件開發(fā)工具與環(huán)境等都是圍繞這一基本問題展開的,其核心是計算的能行性。計算的平臺與環(huán)境問題哲學(xué)家共餐問題與計算機資源管理哲學(xué)家的生活進程可表示為:(1)思考問題;(2)俄了停止思考,左手拿起一只筷子(如果左側(cè)哲學(xué)家已持有它,則等待);(3)右手拿起一只筷子(如果右側(cè)哲學(xué)家已持有它,則等待);(4)進餐;(5)放下左手筷子;(6)放下右手筷子;(7)重新回到狀態(tài)(1)思考問題;程序并發(fā)執(zhí)行時進程同步的兩個關(guān)鍵問題——死鎖和饑餓:(1)按哲學(xué)家的生活進程,當(dāng)所有的哲學(xué)家都同時拿起左手筷子時,則所有哲學(xué)家都將拿不到右手筷子,并處于等待狀態(tài),那么,哲學(xué)家都將無法進餐,最終餓死。(2)將哲學(xué)家的生活進程修改為當(dāng)拿不到右手筷子時,就放下左手筷子。但是,可能在一個瞬間,所有的哲學(xué)家都同時拿起左手筷子,則自然拿不到右手筷子,于是都同時放下左手筷子,等一會,又同時拿起左手筷子,如此重復(fù)下去,則所有的哲學(xué)家都將無法進餐。很久以前,有一個年輕的國王向鄰國一位聰明美麗的公主求婚,公主出了這樣一道題:求出48770428433377171的一個因子,若國王能在一天之內(nèi)求出答案,便接受國王的求婚。證比求易與并行計算嫁給我好嗎?那你回答一個問題吧。國王回去后立即開始逐個數(shù)地進行試除,總共試了三萬多個數(shù),還是沒有結(jié)果。國王向公主求情,公主將答案相告:223092827是它的一個因子,國王很快就驗證了這個數(shù)的確能除盡48770428433377171。告訴你吧,223092827是它的一個因子再給我一次機會吧!國王立即回國,并向時任宰相的大數(shù)學(xué)家求教,宰相在仔細地思考后認為這個數(shù)為17位,如果這個數(shù)存在因子,則最小的一個因子不會超過9位。于是,他給國王出了一個主意:按自然數(shù)的順序給全國的老百姓每人編一個號發(fā)下去,等公主給出數(shù)后,立即將它通報全國,讓每個老百姓用自己的編號去除這個數(shù),除盡了立即上報,賞金萬兩。最后國王用這個辦法求婚成功。國王使用的是串行算法,宰相提出的是一種并行算法。一個問題在判定為可計算問題后,為求解這個問題,必須給出實際解決該問題的操作序列,同時還必須確保操作序列的資源(時間和空間)消耗是合理的。圍繞這一問題,計算機學(xué)科發(fā)展了大量與之相關(guān)的研究內(nèi)容與分支學(xué)科方向。例如,集成電路技術(shù)、數(shù)字系統(tǒng)邏輯設(shè)計、自動布線技術(shù)、RISC技術(shù)、數(shù)值計算方法、算法設(shè)計技術(shù)、計算復(fù)雜性理論、密碼學(xué)、演化計算、人工智能等都是圍繞這一基本問題展開的,其核心是計算的效率。計算過程的能行操作與效率問題背包問題:給定n種物品和一個容量為C的背包,物品i的重量是wi,其價值為vi,如何選擇裝入背包的物品,使得裝入背包中物品的總價值
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025屆青海省西寧市高二物理第二學(xué)期期末達標檢測模擬試題含解析
- 醫(yī)療健康中的情緒智力培養(yǎng)方法
- 教育心理學(xué)在跨文化職場溝通中的應(yīng)用研究
- 當(dāng)代學(xué)生激勵的新趨勢融合教育心理學(xué)
- 教育決策優(yōu)化路徑基于大數(shù)據(jù)的實證分析
- 智慧校園建設(shè)中的綠色環(huán)保裝配式建筑研究
- 智慧城市安全體系構(gòu)建與未來展望
- 2025年紅河市重點中學(xué)高二物理第二學(xué)期期末學(xué)業(yè)水平測試試題含解析
- 高一生活適應(yīng)指南
- 中職幼教美術(shù)教學(xué)課件
- 暨南大學(xué)《微觀經(jīng)濟學(xué)》2023-2024學(xué)年第一學(xué)期期末試卷
- 原理及適用范圍 火試金法
- GB/T 44570-2024塑料制品聚碳酸酯板材
- 新疆2020年中考英語真題(含答案)
- 北京市東城區(qū)東直門中學(xué)2024-2025學(xué)年七年級上學(xué)期分班考數(shù)學(xué)試卷
- 內(nèi)蒙古地區(qū)歷年中考語文現(xiàn)代文閱讀之非連續(xù)性文本閱讀14篇(含答案)(2003-2023)
- 國家開放大學(xué)本科《理工英語3》一平臺機考總題庫2025珍藏版
- 防水包工包料合同范本
- 生物基膠粘劑的綠色合成
- 一年級下冊《讀讀童謠和兒歌》試題及答案共10套
- 中國保險行業(yè)協(xié)會官方-2023年度商業(yè)健康保險經(jīng)營數(shù)據(jù)分析報告-2024年3月
評論
0/150
提交評論