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