簡(jiǎn)介:西南林業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院,大學(xué)計(jì)算機(jī)基礎(chǔ)與計(jì)算思維,第四章算法與程序設(shè)計(jì)基礎(chǔ)本章作者趙家剛、林宏,本章主要內(nèi)容,41可計(jì)算問題42圖靈機(jī)43解決問題的一般方法44用框圖表示解決問題的算法45常用語言簡(jiǎn)介46PYTHON程序設(shè)計(jì)初步附錄PYTHON常用知識(shí),41可計(jì)算問題,,算法的概念算法ALGORITHM是求解特定問題的步驟。算法的五個(gè)重要特性1有窮性一個(gè)算法必須在執(zhí)行有窮步之后結(jié)束,且每一步都可在有窮時(shí)間內(nèi)完成。2確定性算法中每個(gè)步驟必須有確切的含義,讀者理解不會(huì)產(chǎn)生二義性。3可行性一個(gè)算法是能行的,即算法中描述的操作都是可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)的。4輸入一個(gè)算法有0個(gè)或多個(gè)輸入。5輸出一個(gè)算法有一個(gè)或多個(gè)輸出。,41可計(jì)算問題,,算法的設(shè)計(jì)要求1正確性算法應(yīng)當(dāng)滿足具體問題的需求。對(duì)正確的輸入應(yīng)有正確的輸出。2可讀性算法應(yīng)當(dāng)盡可能設(shè)計(jì)得易讀易懂,以便以進(jìn)行閱讀和修改。3鍵壯性當(dāng)輸入數(shù)據(jù)非法時(shí),算法也能適當(dāng)?shù)刈鞒龇磻?yīng)或處理,而不會(huì)意外停止或輸出錯(cuò)誤結(jié)果。4高效率設(shè)計(jì)算法時(shí)應(yīng)考慮使算法的執(zhí)行時(shí)間盡可能短。5低存儲(chǔ)量設(shè)計(jì)算法時(shí)應(yīng)考慮使算法占用的存儲(chǔ)空間盡可能少。,41可計(jì)算問題,,計(jì)算的可行性是算法設(shè)計(jì)與分析的基礎(chǔ),也是計(jì)算機(jī)科學(xué)的理論基礎(chǔ)。為了回答什么是計(jì)算,什么是可計(jì)算性等問題,許多科學(xué)家提出了計(jì)算模型。K哥德爾SC克林尼提出了遞歸函數(shù)。AM圖靈和E波斯特各自獨(dú)立地提出了抽象計(jì)算機(jī)的概念(后人把圖靈提出的抽象計(jì)算機(jī)稱為圖靈機(jī))。胡海星和宋方敏提出了算盤機(jī)。理論上已經(jīng)證明,遞歸函數(shù)、圖靈機(jī)、算盤機(jī)具有相同的計(jì)算能力。,可計(jì)算問題能夠在上述任何一種數(shù)學(xué)模型上編出算法有限步驟進(jìn)行計(jì)算的問題稱為可計(jì)算問題,否則就是不可計(jì)算問題。丘奇圖靈論題能夠在抽象計(jì)算機(jī)上編出算法有限步驟進(jìn)行計(jì)算的問題稱為可計(jì)算問題,否則就是不可計(jì)算問題。該論題是一個(gè)經(jīng)驗(yàn)結(jié)論,未經(jīng)證明。已得到計(jì)算科學(xué)界的公認(rèn)。,41可計(jì)算問題,英國數(shù)學(xué)家圖靈于1936年發(fā)表論可計(jì)算數(shù)及其在判定問題中的應(yīng)用一文,文中提出了一種十分簡(jiǎn)單而運(yùn)算能力極強(qiáng)的理想計(jì)算裝置圖靈機(jī)的概念,推進(jìn)了計(jì)算機(jī)理論的發(fā)展。圖靈機(jī)的基本思想就是用機(jī)器來模擬人們用紙和筆進(jìn)行數(shù)學(xué)運(yùn)算的過程,他把這樣的過程看作是兩種簡(jiǎn)單的動(dòng)作,即在紙上寫上或擦除某個(gè)符號(hào);把注意力從紙的一個(gè)位置移動(dòng)到另一個(gè)位置。,42圖靈機(jī),圖靈機(jī)在理論上能夠模擬現(xiàn)代數(shù)字計(jì)算機(jī)的一切運(yùn)算,可視為現(xiàn)代數(shù)字計(jì)算機(jī)的數(shù)學(xué)模型,是一種抽象的計(jì)算模型。實(shí)際上,一切“可計(jì)算”函數(shù)都等價(jià)于圖靈機(jī)可計(jì)算函數(shù),而圖靈機(jī)可計(jì)算函數(shù)類又等價(jià)于一般遞歸函數(shù)類。圖靈機(jī)能表示算法、程序和符號(hào)行的變換,因而可作為電子計(jì)算器的數(shù)學(xué)模型。,圖靈TURING,圖靈機(jī)TURINGMACHINE的藝術(shù)表示,421圖靈機(jī)的圖形表示,圖靈機(jī)由以下幾個(gè)部分組成(1)一條無限長(zhǎng)的紙帶TAPE。(2)一個(gè)讀寫頭HEAD。(3)一套控制規(guī)則TABLE。(4)一個(gè)狀態(tài)寄存器。圖靈認(rèn)為這樣的一臺(tái)機(jī)器就能模擬人類所能進(jìn)行的任何計(jì)算過程。,圖靈機(jī)模型,讀寫頭沿著固定的紙帶移動(dòng)。要進(jìn)行的指令(Q1)存儲(chǔ)在讀寫頭內(nèi)。圖中“空白”的紙帶全部填入0。有陰影的方格,包括讀寫頭掃描到的空白,標(biāo)記了1,1,B的那些方格,和讀寫頭符號(hào),構(gòu)成了整個(gè)系統(tǒng)的狀態(tài)。,一臺(tái)圖靈機(jī)是一個(gè)七元組Q,?,?,?,Q0,QACCEPT,QREJECT,其中Q,?,?都是有限集合,且滿足(1)Q是狀態(tài)集合;(2)?是輸入字母表,其中不包含特殊的空白符?;(3)?是帶字母表,其中???且???;(4)?Q??Q???{L,R}是轉(zhuǎn)移函數(shù),其中L,R表示讀寫頭是向左移還是向右移;(5)Q0?Q是起始狀態(tài);(6)QACCEPT?Q是接受狀態(tài);(7)QREJECT?Q是拒絕狀態(tài),且QACCEPT?QREJECT。,422圖靈機(jī)的形式化定義,圖靈機(jī)的計(jì)算規(guī)則,根據(jù)圖靈機(jī)的形式化定義,圖靈機(jī)的計(jì)算規(guī)則如下AA,XBB,Y,D中AA是當(dāng)前狀態(tài),X是當(dāng)前格子的值,BB是程序下一步的狀態(tài),Y是當(dāng)前格的修改值,D是讀寫頭移動(dòng)的方向L為左移,R為右移,空則表示不移動(dòng)。具體規(guī)則由算法設(shè)計(jì)者根據(jù)計(jì)算需要而定義。如0,01,0,R請(qǐng)同學(xué)們猜一下該規(guī)則的意思。,加法圖靈機(jī),根據(jù)圖靈機(jī)的計(jì)算規(guī)則,人們?cè)O(shè)計(jì)了不同的圖靈機(jī)來完成不同的計(jì)算。如加法圖靈機(jī)、乘法圖靈機(jī)、除法圖靈機(jī)等。加法圖靈機(jī)的規(guī)則如下簡(jiǎn)化版0,01,0,R0,10,01,A10,1,1,11,1,R遇到未定義的規(guī)則時(shí)停機(jī),紙帶上的內(nèi)容就是計(jì)算結(jié)果。,例用加法圖靈機(jī)計(jì)算32,以1的個(gè)數(shù)表示數(shù)值,在紙帶上的數(shù)據(jù)是111A110,表示32。加法圖靈機(jī)的規(guī)則如下10,10,020,01,0,R31,A10,141,11,1,R5遇到無定義規(guī)則時(shí)停機(jī),1011A110,,0111A110,,1011A110,100111110,,0011A110,,,狀態(tài)10,讀到的值為1的規(guī)則無定義,從而停機(jī)。計(jì)算結(jié)果為5,1011A110,,,圖靈機(jī)就其計(jì)算能力而言,它能模擬任何現(xiàn)代的計(jì)算機(jī)。丘奇圖靈論題也已經(jīng)得到計(jì)算機(jī)科學(xué)界的公認(rèn)。圖靈機(jī)形式簡(jiǎn)潔且功能強(qiáng)大,但是圖靈機(jī)形式化表示一個(gè)算法非常復(fù)雜。比如乘法需要近23條規(guī)則。由于計(jì)算機(jī)已經(jīng)發(fā)明出來,為了充分利用計(jì)算機(jī)的計(jì)算功能,因此通常用框圖(流程圖)、自然語言來表示算法。,43解決問題的一般方法,,用計(jì)算機(jī)可以解決兩類問題1數(shù)值計(jì)算問題,抽象出數(shù)學(xué)模型,,設(shè)計(jì)算法,編程,測(cè)試,修改,,,,2非數(shù)值計(jì)算問題通常要用到一些復(fù)雜的數(shù)據(jù)結(jié)構(gòu),43解決問題的一般方法,用計(jì)算機(jī)解決問題的一般方法1描繪出解決問題的步驟自然語言、框圖等2用程序設(shè)計(jì)語言實(shí)現(xiàn)上述步驟,44用框圖表示解決問題的算法,框圖又稱流程圖,是表達(dá)程序設(shè)計(jì)思想和程序設(shè)計(jì)步驟的一種直觀工具。,,開始,結(jié)束,,流程線,44用框圖表示解決問題的算法,功能框,例子1X1Y3X例子2X05YMATHSINX,輸入框,用于向程序輸入數(shù)據(jù)例子XINPUTX,用于向程序輸出數(shù)據(jù)例子PRINTS,輸出框,44用框圖表示解決問題的算法,單分支判斷框用于解決單分支問題,例子IFX0NN1,FALSE,44用框圖表示解決問題的算法,,,雙分支判斷框用于解決雙分支問題,例子IFX0Y12XELSEYX2,44用框圖表示解決問題的算法,循環(huán)框用于解決需要反復(fù)進(jìn)行的問題,,,例子N100I1S0WHILEI,,0YXELSEYX,PYTHON的常用知識(shí),10WHILE循環(huán)語句如T1I1N10WHILEINTTIII1PRINTT,T,PYTHON的常用知識(shí),11列表的使用A1,2,8,5,9A24XA0A2PRINTX請(qǐng)同學(xué)們猜一下輸出結(jié)果12FOR循環(huán)語句如A1,2,8,5,9S0FORXINASSXPRINTS,S,
下載積分: 4 賞幣
上傳時(shí)間:2024-01-06
頁數(shù): 43
大小: 1.32(MB)
子文件數(shù):