計算學科中的核心概念.ppt

第4章 計算學科中的核心概念,4.1 算法,算法的歷史簡介,公元825年，阿拉伯數(shù)學家阿科瓦里茨米（AlKhowarizmi）寫了著名的波斯教科書（Persian Textbook），書中概括了進行四則算術(shù)運算的法則。 “算法”（Algorithm）一詞就來源于這位數(shù)學家的名字。 后來，韋氏新世界詞典將其定義為“解某種問題的任何專門的方法”。 而據(jù)考古學家發(fā)現(xiàn)，古巴比倫人在求解代數(shù)方程時，就已經(jīng)采用了“算法”的思想。,丟番圖方程的可解性問題,古希臘數(shù)學家丟番圖（Diophantus）：代數(shù)學之父 在算術(shù)（Arithmetica）一書中提出了有關(guān)兩個或多個變量整數(shù)系數(shù)方程的有理數(shù)解問題。 對于具有整數(shù)系數(shù)的不定方程，如果只考慮其整數(shù)解，這類方程就叫做丟番圖方程。 “丟番圖方程可解性問題”的實質(zhì)為：能否寫出一個可以判定任意丟番圖方程是否可解的算法？,一個未知數(shù)的線性丟番圖方程的解,ax=b，只要a能整除b，就可判定其有整數(shù)解，該整數(shù)解即b/a。,兩個未知數(shù)的線性丟番圖方程 的解,ax+by=c，先求出a和b的最大公因子d，若d能整除c，則該方程有解（整數(shù)解）。 問：方程13x+26y=52有無整數(shù)解？ 答：13和26的最大公因子是13，13又可整除52，故該方程有整數(shù)解（如x=2，y=1即方程的解）。 例4.2 問：方程2x+4y=15有無整數(shù)解？ 答：2和4的最大公因子是2，2不能整除15，故該方程無整數(shù)解。,兩個未知數(shù)的線性丟番圖方程 的解：歐幾里德算法,給定兩個正整數(shù)m和n，求它們的最大公因子，即能同時整除m和n的最大正整數(shù)。 步驟如下： （1）以n除m，并令所得余數(shù)為r（r必小于n）； （2）若r=0，算法結(jié)束，輸出結(jié)果n；否則，繼續(xù)步驟（3）； （3）將n置換為m，r置換為n，并返回步驟（1）繼續(xù)進行。,例4.3 設(shè)m=56，n=32，求m、n的最大公因子,算法如下: （1）32除56余數(shù)為24； （2）24除32余數(shù)為8； （3）8除24余數(shù)為0，算法結(jié)束，輸出結(jié)果8。 答：m、n的最大公因子為8。 歐幾里德算法既表述了一個數(shù)的求解過程， 又表述了一個判定過程，該過程可以判定“m和n是互質(zhì)的”（即除1以外，m和n沒有公因子）這個命題的真假。,算法,算法的定義和特征,1算法的非形式化定義,一個算法，就是一個有窮規(guī)則的集合，其中之規(guī)則規(guī)定了一個解決某一特定類型問題的運算序列。,2算法的重要特性,有窮性：一個算法在執(zhí)行有窮步之后必須結(jié)束。 確定性：算法的每一個步驟必須要確切地定義。即算法中所有有待執(zhí)行的動作必須嚴格而不含混地進行規(guī)定，不能有歧義性。 輸入：算法有零個或多個的輸入，即在算法開始之前，對算法最初給出的量。 輸出：算法有一個或多個的輸出，即與輸入有某個特定關(guān)系的量，簡單地說就是算法的最終結(jié)果。 能行性：算法中有待執(zhí)行的運算和操作必須是相當基本的，,3算法的形式化定義,算法是一個四元組，即（Q，I，F(xiàn)）。 其中： （1）Q是一個包含子集I和的集合，它表示計算的狀態(tài)； （2）I表示計算的輸入集合； （3）表示計算的輸出集合； （4）F表示計算的規(guī)則，它是一個由Q到它自身的函數(shù)，且具有自反性，即對于任何一個元素qQ，有F(q)=q。,算法,算法實例,例4.4 求1+2+3+100,設(shè)變量X表示加數(shù)，Y表示被加數(shù)，用自然語言將算法描述如下： （1）將1賦值給X； （2）將2賦值給Y； （3）將X與Y相加，結(jié)果存放在X中； （4）將Y加1，結(jié)果存放在Y中； （5）若Y小于或等于100，轉(zhuǎn)到步驟（3）繼續(xù)執(zhí)行；否則，算法結(jié)束，結(jié)果為X。,例4.5 求解調(diào)和級數(shù),設(shè)變量X表示累加和，變量I表示循環(huán)的次數(shù)，自然語言描述算法如下： （1）將0賦值給X； （2）將1賦值給I； （3）將X與1/I相加，然后把結(jié)果存入X； （4）將I加1； （5）若I大于等于N，算法結(jié)束，結(jié)果為X；否則轉(zhuǎn)到步驟（3）繼續(xù)執(zhí)行。,例4.6 求解斐波那契數(shù),0，1，1，2，3，5，8，13，21，34， （1） 來源于1202年意大利數(shù)學家斐波那契（L.P.Fibonacci）在其珠算之書（Liber Abaci）中提出的一個“兔子問題”： 假設(shè)一對剛出生的兔子一個月后就能長大，再過一個月就能生下一對兔子，并且此后每個月都能生一對兔子，且新生的兔子在第二個月后也是每個月生一對兔子。 問：一對兔子一年內(nèi)可繁殖成多少對兔子？,在序列（1）中，每個數(shù)都是它的前兩個數(shù)之和，F(xiàn)n表示這個序列的第n個數(shù)，該序列可以形式化的定義為： F0=0，F(xiàn)1=1，F(xiàn)n+2=Fn+1+Fn，n0 斐波那契數(shù)列還是一個關(guān)于加法算法的典型實例。,設(shè)變量X表示前一個數(shù)的值，即定義中的Fn，變量Y表示當前數(shù)的值，即定義中的Fn+1，變量Z表示后一個數(shù)的值，即定義中的Fn+2。那么求解問題的自然語言描述如下：,（1）如果=0，那么將0賦值給Y，并輸出Y，轉(zhuǎn)步驟（11）繼續(xù)執(zhí)行； （2）將0賦給X，將1賦值給Y； （3）輸出X、Y； （4）將1賦值給I； （5）如果I大于-1，則轉(zhuǎn)到步驟（11），否則繼續(xù)執(zhí)行； （6）將X和Y的和賦值給Z； （7）將Y賦值給X； （8）將Z賦值給Y； （9）將Y輸出； （10）將I加1，轉(zhuǎn)步驟（5）繼續(xù)執(zhí)行； （11）算法結(jié)束。,算法,算法的表示方法,原語,一個算法的表達需要使用一些語言形式 自然語言“Visiting grandchildren can be nerve-racking”,可能即意味著孫子孫女導致了很多問題，也表示去看他們可能會有問題 圖形語言：很少人能夠根據(jù)折紙圖給出的步驟成功地疊出一只鳥來，但一個專門學習過折紙的學生可以輕松完成 當用來描述算法的語言并沒有被準確定義或者沒有給予足夠信息的時候，交流就會產(chǎn)生問題,原語,通過建立一個可以描述算法的意義明確的基本塊（原語）集合，計算機科學即就可以解決上述的勾通問題 原語描述算法需要建立一個統(tǒng)一的細節(jié)描述級別，原語連同一組表達了原語如何表達復(fù)雜的想法的規(guī)定組成了一種程序設(shè)計語言 組成 語法：原語的符號表示 語義：表達了原語的意義,1自然語言,缺點 由于自然語言的歧義性，容易導致算法執(zhí)行的不確定性； 自然語言的語句一般太長，從而導致了用自然語言描述的算法太長； 由于自然語言表示的串行性，因此，當一個算法中循環(huán)和分支較多時就很難清晰地表示出來； 自然語言表示的算法不便翻譯成計算機程序設(shè)計語言理解的語言。,2流程圖,它采用美國國家標準化協(xié)會ANSI（American National Standard Institute）規(guī)定的一組圖形符號來表示算法。 流程圖可以很方便地表示順序、選擇和循環(huán)結(jié)構(gòu)，而任何程序的邏輯結(jié)構(gòu)都可以用順序、選擇和循環(huán)結(jié)構(gòu)來表示， 流程圖可以表示任何程序的邏輯結(jié)構(gòu)。 用流程圖表示的算法不依賴于任何具體的計算機和計算機程序設(shè)計語言，,（1）求解例4.4的算法流程圖,（2）求解例4.5的算法流程圖,（3）求解例4.6的算法流程圖,3偽代碼（1）求解例4.4的偽代碼算法描述：,BEGIN(算法開始) 1 X 2 Y while（Y=100） X+Y X Y+1 Y Print X END（算法結(jié)束）,（2）求解例4.5的偽代碼算法描述：,BEGIN（算法開始） 0 X 1 I do X+1/I X I+1 I while(I=n) END（算法結(jié)束）,（3）例4.6的偽代碼算法描述：,BEGIN if n = =0 0 Y Print Y else ,0 X 1 Y Print X，Y for(i=1;i=n-1;i+) X+YZ YX ZY Print Y END,4計算機程序設(shè)計語言,計算機程序設(shè)計語言描述的算法（程序）是清晰的、簡明的，最終也能由計算機處理的。 缺點： 算法的基本邏輯流程難于遵循。與自然語言一樣，程序設(shè)計語言也是基于串行的 用特定程序設(shè)計語言編寫的算法限制了與他人的交流，不利于問題的解決； 要花費大量的時間去熟悉和掌握某種特定的程序設(shè)計語言； 要求描述計算步驟的細節(jié)，而忽視算法的本質(zhì)。,例4.4的計算機程序設(shè)計語言（C語言）的算法描述：,main() int X,Y; X=1; Y=2; while(Y=100) X=X+Y; Y=Y+1; ; printf(“%d“,X); ,例4.5的計算機程序設(shè)計語言（C語言）的算法描述,main() int n; float X,I; printf(“Please input n:“); scanf(“%d“,do X=X+1/I; I=I+1; while(I=n); printf(“n%f“,X); ,算法,算法分析,（1）算法的時間復(fù)雜度；,用T(n)表示，n表示問題規(guī)模的大小。 使用一個記號 Order（數(shù)量級）的第一個字母， 允許使用“=”代替“”。如n2+n+1=(n2) 設(shè)f(n)是一個關(guān)于正整數(shù)n的函數(shù)，若存在一個正整數(shù)n0和一個常數(shù)C，當nn0時，T(n)C f(n)均成立，則稱f(n)為T(n)的同數(shù)量級的函數(shù)。 算法時間復(fù)雜度T(n)可表示為： T(n)= (f(n),常見的大表示形式有：,(1)稱為常數(shù)級； (logn)稱為對數(shù)級； (n)稱為線性級； (nc)稱為多項式級； (cn)稱為指數(shù)級； (n!)稱為階乘級。,算法的空間復(fù)雜度,指算法在執(zhí)行過程中所占存儲空間的大小， 用S(n)表示，S為英文單詞Space的第一個字母。與算法的時間復(fù)雜度相同 算法的空間復(fù)雜度S(n)也可表示為：S(n)= (g(n)。,算法,算法的研究,算法,算法：定義一向工作如何完成的步驟的集合 在一臺機器可以完成一個任務(wù)之前，必須找到完成這個任務(wù)的算法并且用與機器兼容的方式來描述 一個與機器兼容的算法的描述程序 算法的研究開始是作為數(shù)學的一個學科 目標：找到描述特定類型問題是如何被解決的指令的集合，如Euclidean算法 一旦一個完成任務(wù)的算法被找到，任務(wù)的實現(xiàn)就不再需要對算法原理的理解，任務(wù)的實現(xiàn)僅僅是遵循算法的只是過程 現(xiàn)有的解決問題需要的智慧被編碼進了算法,算法轉(zhuǎn)化為智慧,通過使用算法來得到并轉(zhuǎn)化智慧，我們才可以構(gòu)建起可以表現(xiàn)智慧行為的機器。 機器表現(xiàn)的智能等級受到通過算法轉(zhuǎn)化的智慧所限制 如果沒有解決問題的算法，意味著問題的解決方案超出了機器的能力范圍 算法的開發(fā)就成了計算機領(lǐng)域的一個主要目標 如何找到算法一個十分接近于尋找通用問題解決方案 描述這個算法轉(zhuǎn)變?yōu)橐粋€清晰的指令的集合（程序設(shè)計語言描述）,計算機技術(shù)別用于復(fù)雜問題（大型軟件系統(tǒng)）,不僅僅包括實現(xiàn)任務(wù)的單個算法的開發(fā) 還要求對組件之間的交互進行設(shè)計 軟件工程：借鑒了工程領(lǐng)域、項目管理領(lǐng)域、人力資源管理以及程序語言設(shè)計領(lǐng)域的經(jīng)驗,執(zhí)行算法的機器的設(shè)計和實現(xiàn),數(shù)據(jù)的存儲 數(shù)據(jù)的操作 體系結(jié)構(gòu)中涵蓋了對現(xiàn)今技術(shù)的討論 我們的目標不是去熟知類似當今體系結(jié)構(gòu)是如何用電路來實現(xiàn)這樣的細節(jié)問題，那將會導致過分陷入電子工程學科 正如昨天的齒輪驅(qū)動的計算機讓位于電子設(shè)備一樣，今天的電子技術(shù)也許很快也被其它的技術(shù)所取代,理想情況下,希望計算機的體系結(jié)構(gòu)是我們的有關(guān)算法過程知識的延續(xù)，并且不應(yīng)該被技術(shù)能力酸限制 使我們的算法知識在當代機器體系結(jié)構(gòu)的發(fā)展背后起推動作用，而不僅僅是從技術(shù)的要求觸發(fā)來解頂機器的設(shè)計 構(gòu)建允許使用多個指令序列來代替算法的機器是可能的 這些指令被同時執(zhí)行或者作為,機器于外部世界的接口的設(shè)計于計算機的設(shè)計緊密相連,算法是如何機器中的？ 機器是如何被告知執(zhí)行的是哪一個算法？,計算理論,對解決越來越復(fù)雜問題的算法的研究 導致了算法過程的最終限制問題 如果沒有算法可以解決這個問題，那么算法是不能被機器所解決的，機器僅僅可以解決在算法上可解的問題 Godel的不完全定理闡述了 在任何傳統(tǒng)算術(shù)領(lǐng)域的數(shù)學理論中，有些是既不能證明有不能被推翻的 任何對算術(shù)系統(tǒng)的徹底研究都超出了算法的能力 對算法的限制的研究欲望似的數(shù)學家們設(shè)計抽象的機器來執(zhí)行算法，并在理論上研究這些假想機器的能力。,數(shù)據(jù)結(jié)構(gòu)：一類定性數(shù)學模型,數(shù)據(jù)結(jié)構(gòu)的基本概念,數(shù)據(jù)結(jié)構(gòu)的基本概念,組成：數(shù)據(jù)結(jié)構(gòu)是一類定性的數(shù)學模型，它由以下3部分組成 邏輯結(jié)構(gòu) 存儲結(jié)構(gòu)（或稱物理結(jié)構(gòu)） 運算 數(shù)據(jù)邏輯結(jié)構(gòu)的形式化定義 DS= 其中： D表示數(shù)據(jù)的集合； R表示數(shù)據(jù)D上關(guān)系的集合。,數(shù)據(jù)的存儲結(jié)構(gòu),數(shù)據(jù)的存儲結(jié)構(gòu)是指在反映數(shù)據(jù)邏輯關(guān)系的原則下，數(shù)據(jù)在存儲器中的存儲方式。 順序存儲結(jié)構(gòu)：借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素的邏輯關(guān)系。 鏈式存儲結(jié)構(gòu)：借助指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系，通常在數(shù)據(jù)元素上增加一個或多個指針類型的屬性來實現(xiàn)這種表示方式。,數(shù)據(jù)結(jié)構(gòu)的基本運算內(nèi)容,建立數(shù)據(jù)結(jié)構(gòu)； 清除數(shù)據(jù)結(jié)構(gòu)； 插入數(shù)據(jù)元素； 刪除數(shù)據(jù)元素； 更新數(shù)據(jù)元素； 查找數(shù)據(jù)元素； 按序重新排列； 判定某個數(shù)據(jù)結(jié)構(gòu)是否為空，或是否已達到最大允許的容量； 統(tǒng)計數(shù)據(jù)元素的個數(shù)。,數(shù)據(jù)結(jié)構(gòu)：一類定性數(shù)學模型,常用的幾種數(shù)據(jù)結(jié)構(gòu),線性表,線性表是n個數(shù)據(jù)元素的有限序列，即（X1，X2，X3，Xi，Xn） 基本操作插入、刪除和存取數(shù)據(jù)元素 幾種特殊的線性表 后進先出（Last In First Out，簡稱LIFO）的線性表。 先進先出（First In First Out，簡稱FIFO）的線性表。 限定所有插入、刪除和存取都在表的兩端進行的線性表。,數(shù)組,線性表的推廣形式之一。 如在一個mn的二維數(shù)組中，每個元素Ai,j都分別屬于兩個線性表，即（Ai,1，Ai,2，Ai,n）和（A1,j，A2,j，Am,j）。,樹（Tree）,由n（n0）個結(jié)點組成的有限集合。若n=0，則稱為空樹，任何一個非空樹均滿足以下兩個條件： 僅有一個稱為根的結(jié)點； 當n0時，其余結(jié)點可分為m（m0）個互不相交的有限集合，其中每個集合又是一棵樹，并稱為根的子樹。,下圖的樹有12個結(jié)點，A是根結(jié)點，該樹又可再分為若干不相交的子樹，如T1=B，E，F(xiàn)，K，T2=C，G，T3=D，H，I，J，L等。圖4.4所示的樹中有12個結(jié)點，A是根結(jié)點，該樹又可再分為若干不相交的子樹，如T1=B，E，F(xiàn)，K，T2=C，G，T3=D，H，I，J，L等。,二叉樹,n（n0）個結(jié)點組成的有限集合，它或者是空集（n0），或者由一個結(jié)點及兩棵互不相交的子樹組成，且這兩個子樹有左、右之分，其次序不能任意顛倒。,圖,由結(jié)點和連接這些結(jié)點的邊所組成的集合。 圖的形式化定義為： G= 其中： V是一個非空結(jié)點的集合； E是連結(jié)結(jié)點的邊的集合。,例 G=,其中V=A，B，C，D， E=(A，B)，(A，C)，(B，D)，(B，C)， (D，C)，(A，D),4.3程序,算法+數(shù)據(jù)結(jié)構(gòu)=程序,概念,從廣義上講可以認為是一種行動方案或工作步驟。 某個會議的日程安排 一條旅游路線的設(shè)計 手工小制作的說明書等 計算機程序：一種處理事務(wù)的時間順序和處理步驟。 組成計算機程序的基本單位是指令 計算機程序就是按照工作步驟事先編排好的、具有特殊功能的指令序列。,軟件,在計算機發(fā)展的初期，硬件設(shè)計和生產(chǎn)是主要問題，那時的軟件就是程序。 現(xiàn)在計算機軟件一般指計算機系統(tǒng)中的程序及其文檔， 也可以指在研究、開發(fā)、維護，以及使用上述含義下的軟件所涉及的理論、方法、技術(shù)所構(gòu)成的分支學科。 軟件一般分為3類 系統(tǒng)軟件 支撐軟件 應(yīng)用軟件,硬件,計算機硬件是構(gòu)成計算機系統(tǒng)的所有物理器件、部件、設(shè)備，以及相應(yīng)的工作原理與設(shè)計、制造、檢測等技術(shù)的總稱。 計算機系統(tǒng)的物理元器件包括：集成電路、印制電路板，以及其他磁性元件、電子元件等。 計算機系統(tǒng)的部件和設(shè)備包括：控制器、運算器、存儲器、輸入輸出設(shè)備、電源等。 硬件工程技術(shù)包括：印制電路板制造、高密度組裝、抗環(huán)境干擾、抗惡劣環(huán)境破壞等技術(shù)，以及在設(shè)計和制造過程中為提高計算機性能所采取的措施等。,4.6 CC1991報告提取的核心概念,核心概念是CC1991報告首次提出的，是具有普遍性、持久性的重要思想、原則和方法。它的基本特征有： 在學科中多處出現(xiàn)； 在各分支領(lǐng)域及抽象、理論和設(shè)計的各個層面上都有很多示例； 在技術(shù)上有高度的獨立性； 一般都在數(shù)學、科學和工程中出現(xiàn)。,1.綁定 2.大問題的復(fù)雜性,綁定指的是通過將一個對象（或事物）與其某種屬性相聯(lián)系，從而使抽象的概念具體化的過程。例如：將一個進程與一個處理機，一個變量與其類型或值分別聯(lián)系起來。這種聯(lián)系的建立，實際上就是建立了某種約束。 大問題的復(fù)雜性是指隨著問題規(guī)模的增長而使問題的復(fù)雜性呈非線性增加的效應(yīng)。這種非線性增加的效應(yīng)是區(qū)分和選擇各種現(xiàn)有方法和技術(shù)的重要因素。,3.概念和形式模型,概念和形式模型 概念和形式模型是對一個想法或問題進行形式化、特征化、可視化思維的方法。抽象數(shù)據(jù)類型、語義數(shù)據(jù)類型以及指定系統(tǒng)的圖形語言，如數(shù)據(jù)流圖和E-R圖等都屬于概念模型。而邏輯、開關(guān)理論和計算理論中的模型大都屬于形式模型。概念模型和形式模型以及形式證明是將計算學科各分支統(tǒng)一起來的重要的核心概念。,4.一致性和完備性,一致性包括用于形式說明的一組公理的一致性、事實和理論的一致性，以及一種語言或接口設(shè)計的內(nèi)部一致性。 完備性包括給出的一組公理，使其能獲得預(yù)期行為的充分性、軟件和硬件系統(tǒng)功能的充分性，以及系統(tǒng)處于出錯和非預(yù)期情況下保持正常行為的能力等。 在計算機系統(tǒng)設(shè)計中，正確性、健壯性和可靠性就是一致性和完備性的具體體現(xiàn)。,5.效率,效率是關(guān)于空間、時間、人力、財力等資源消耗的度量。在計算機軟硬件的設(shè)計中，要充分考慮某種預(yù)期結(jié)果所達到的效率，以及一個給定的實現(xiàn)過程較之替代的實現(xiàn)過程的效率。,6演化,演化 指的是系統(tǒng)的結(jié)構(gòu)、狀態(tài)、