The discipline of algorithms 有關演算法的一門學科

Presentation on theme: "The discipline of algorithms 有關演算法的一門學科"— Presentation transcript:

1 The discipline of algorithms 有關演算法的一門學科
Algorithmics 演算法(學) The discipline of algorithms 有關演算法的一門學科

2 演算法名稱的由來

3 阿布‧迦法‧穆罕默德‧賓‧穆薩‧阿爾‧可瓦里茲米
“Algorithm”(演算法)一詞源自一位波斯人  阿布‧迦法‧穆罕默德‧賓‧穆薩‧阿爾‧可瓦里茲米(Abu Ja’far Mohammed ibn Musa al Khowarizmi) (780 – 850 A. D.)的拉丁文譯名。

4 阿爾‧可瓦里茲米 (al-Khwarizmi)
演算法(algorithm)名稱來自於”al-Khwarizmi”，這是一個約在西元780年出生於伊拉克( Iraq )巴格達( Baghdad )城的波斯(阿拉伯)數學家阿爾‧可瓦里茲米(Abu Jafar Muhammad ibn Musa al-Khwarizmi)名字的最後一部份，此數學家將印度所發明的十進位數字記號傳入阿拉伯地區(稍後傳入歐洲並成為現今我們使用的數字記號)，並且著有一本名為”ilm al jabr w’al-muqabala”的書籍，此書有系統地討論一元二次方程的解法，啟發了代數學的發展。此書在12世紀被翻譯為拉丁文，名為Algebra et Almucabala， (Algebra源自阿拉伯書名中之al jabr)，而成為代數學(Algebra)一字的由來。

5 什麼是演算法?

6 什麼是演算法? (1) Any special method of solving a certain kind of problem -- Webster’s 解決某一類特定問題的任何方法 – 韋伯字典。 A precise method useable by a computer for the solution of a problem. -- Viewed by Computer Engineers 藉由使用電腦執行精確解法以尋求某問題的解答 – 程 式設計師的觀點。

7 什麼是演算法? (2) In mathematics and computing, an algorithm is a procedure (a finite set of well-defined instructions) for accomplishing some task which, given an initial state, will terminate in a defined end-state. – WiKipedia 在數學以及電腦科學的觀點中，演算法是一種完成一 些任務的程序(由一些具有明確定義的指令所組成)， 而這些任務會給定一個起始狀態，並在達到預先定義 好的最終狀態時終止程序 – 維基百科。

8 什麼是演算法? (3) 演算法是由解決某特定問題的一些步驟組成，必須滿足以下條件: 0或多個輸入 1個以上的輸出
有限性 (finiteness): 步驟數有限而且步驟執行會終止 明確性 (definiteness): 每個步驟必須明確且不含糊(unambiguous) 例如: 計算 5/0不是明確的 (definite) 有效性 (effectiveness): 每個步驟必須是有效可行的(feasible) 例如: 計算√2到有限小數點後位數是有效的，但是計算到無窮位數不是有效的(effective) Definiteness: each instruction is clear and unambiguous. To compute “add 6 or 7 to x” is not definite. Finiteness: (the number of steps should be finite and the execution of the steps should terminate) if we trace out the instructions of an algorithm, then for all cases, the algorithm terminates after a finite number of steps. Finiteness implies termination (OS is thus not an algorithm) Effectiveness: All operations should be feasible. Each step must be such that it can, at least in principle, be done by a person using pencil and paper in a finite amount of time.

9 演算法的例子

10 食譜 (recipe) 是演算法 非正式地，我們常用食譜來舉例作為演算法概念的陳述。
梅焗肉排 材料：（４人份） 一字排12兩 鹹話梅6-8粒 紅椒2隻 中國芹菜2條 洋蔥1小個 紅谷米少許 冰糖適量 生抽適量 　 做法： 1. 話梅連一隻切角紅椒和紅谷米以六碗水煎至一碗水，隔渣保留汁及話梅備用。中國芹菜切段；洋蔥及另一隻紅椒切角，備用。 2. 一字排洗淨，切件，加適量生粉拌勻，放滾油內炸至金黃香脆，瀝乾油備用。 3. 取話梅及汁，加入生抽、冰糖煮滾，再加中國芹菜、紅椒角、洋蔥略煮約1分鐘，放一字排燜焗約2分鐘至入味，埋少許生粉水即可。 (取材自蘋果日報)

11 流程圖 (flowchart) 是演算法

12 程式 (program)是演算法 import javax.swing.*;
public class EuclidGCDApplet extends JApplet{ public void init( ){ int 整數m,整數n,最大公因數; String 輸入字串1,輸入字串2,顯示字串; 輸入字串1=JOptionPane.showInputDialog("請輸入正整數m？"); 輸入字串2=JOptionPane.showInputDialog("請輸入正整數n？"); 整數m=Integer.parseInt(輸入字串1); 整數n=Integer.parseInt(輸入字串2); 最大公因數=EuclidGCD(整數m, 整數n); 顯示字串="整數"+整數m+"與整數"+整數n+"的最大公因數為"+最大公因數; JOptionPane.showMessageDialog(null,顯示字串); } //方法:init() 定義區塊結束

13 如何表示演算法?

14 演算法的表示 一般我們使用自然語言(中文或英文等語言)、虛擬碼(pseudo code)或流程圖(flow chart)來表示演算法。
例如，以下的例子使用自然語言(中文與英文)與虛擬碼描述一個古老的演算法  歐幾里德(Euclid)GCD演算法。 歐幾里德(Euclid)GCD演算法大約在西元前300年由希臘數學家歐幾里德提出，可用於求出二個整數的最大公因數(GCD, Greatest Common Divisor)，又稱為輾轉相除法。

15 歐幾里德GCD演算法 (輾轉相除法)範例

16 歐幾里德GCD演算法 (Euclid GCD Algorithm) 以自然語言表示
Euclid GCD演算法: 問題：已知二個正整數m及n，找出此二數的最大公因數(也就是能同時整除m及n的最大正整數) 解法： E1.[找出餘數] 求出m除以n的餘數，並記錄於r。 E2.[餘數為0嗎？] 如果r=0則停止，輸出n為GCD。 E3.[互換二數] 設定m=n,n=r，並跳至步驟E1。

17 虛擬碼 (Pseudo Code) 虛擬碼以一種混雜著自然語言與高階程式語言結構的方式來描述演算法，試圖達到簡潔易讀、容易分析，而且也容易轉換為高階程式語言的目的。 以下介紹Goodrich及Tamassia在「Data Structures and Algorithms in JAVA」一書中所提出的虛擬碼格式:

18 虛擬碼 (Pseudo Code) 宣告：以 Algorithm 方法名稱(參數1,參數2,…):來宣告一個演算法並指明其參數。例如，Algorithm Euclid-GCD(m, n): 表示我們要定義一個具有兩個參數m及n而名稱為Euclid-GCD的演算法，。 設定動作：以 ← 表示，用以將一個算式之值存入某一個變數中。例如，m←3+8 表示要將3+8的值存入變數m中。 相等比較：以 = 表示，可以比較二個算式是否等值。例如，m=3+8 表示要比較3+8的值是否與變數m的值相等。

19 虛擬碼 (Pseudo Code) 決策結構：以 if條件then條件為真的動作 else 條件為偽的動作 來表示，並以縮排來表示所有包含在條件為真的動作及條件為偽的動作中的所有指令。例如， if m=3+8 then b←3+8 else c←3+8 表示當變數m的值與3+8相等時，會執行將3+8的值存入變數b的動作，否則即執行將3+8的值存入變數c的動作。

20 虛擬碼 (Pseudo Code) while迴圈：以 while條件do迴圈指令 來表示，並以縮排來表示所有包含在迴圈中的所有指令。當條件成立時，會持續執行所有包含在迴圈中的指令。例如， while m=3+8 do b←3+8 c←3+8 表示當變數m的值與3+8相等時，會持續執行將3+8的值存入變數b與將3+8的值存入變數c的動作。

21 虛擬碼 (Pseudo Code) repeat迴圈：以 repeat迴圈指令 until條件 來表示，並以縮排來表示所有包含在迴圈中的所有指令。此虛擬碼會持續執行所有包含在迴圈值中的指令，直到條件成立為止。例如， repeat b←3+8 c←3+8 until m=3+8 表示會持續執行將3+8的值存入變數b與將3+8的值存入變數c的動作，直到變數m的值與3+8相等為止。

22 虛擬碼 (Pseudo Code) for迴圈：以 for迴圈範圍及變動 do 迴圈指令 來表示，並以縮排來表示所有包含在迴圈中的所有指令。例如， for i←3 to 8 do b←3+8 c←3+8 表示在變數i的值由3到8(即i為3、4、5、6、7、8)的情況下，會持續執行將3+8的值存入變數b與將3+8的值存入變數c的動作。

23 虛擬碼 (Pseudo Code) 陣列元素索引：以 A[i] 代表陣列A中註標(index)為i的元素，一個有n個元素的陣列，其元素註標為0,1,…,n-1。例如，A[5] 表示陣列A中註標為5的元素。 方法呼叫：以 物件.方法(參數…) 來代表。注意，當物件是明確的時候，物件可以省略不寫。例如，Math.random() 表示要呼叫Math物件無參數的random()方法。 方法返回:以 return 方法返回值 來代表。例如，return 3+8 表示要傳回3+8之值。

24 歐幾里德GCD演算法 以虛擬碼表示 Algorithm Euclid_GCD(m, n): Input: two integers m and n Output: GCD of m and n r←m%n while r0 do m←n n←r r←m%n return n

25 如何實作演算法?

26 演算法的實作(implementation)
一般我們使用高階程式語言(high level programming language)、電子電路(如積體電路IC等)甚至於機械設備(如打孔卡與齒輪等)來實現或實作(implement)演算法。 以下的例子使用Java程式語言來實作歐幾里德GCD演算法。除了Java之外，我們也可以使用其他程式語言(如C、C++、C#、JavaScrip、Lisp、Python等)來實作演算法。

27 以Java程式語言實作 歐幾里德GCD演算法
使用虛擬碼表示演算法可以方便演算法的分析，增加演算法的易讀性，並且可以方便的以程式語言實作演算法，以便可以直接在電腦上執行演算法。下例將以虛擬碼表示的歐幾里德GCD演算法以Java語言方法(method)實作： int Euclid_GCD(int m, int n) { int r=m%n; while (r!=0) { m=n; n=r; r=m%n; } return n;

28 以Java程式語言實作 歐幾里德GCD演算法
範例程式(檔名：EuclidGCDApplet.java) //檔名:EuclidGCDApplet.java //說明:此程式可輸入二個整數，並以歐幾里得GCD演算法求其最大公因數(GCD) import javax.swing.*; public class EuclidGCDApplet extends JApplet{ public void init( ){ int 整數m,整數n,最大公因數; String 輸入字串1,輸入字串2,顯示字串; 輸入字串1=JOptionPane.showInputDialog("請輸入正整數m？");

29 以Java程式語言實作 歐幾里德GCD演算法
輸入字串2=JOptionPane.showInputDialog("請輸入正整數n？"); 整數m=Integer.parseInt(輸入字串1); 整數n=Integer.parseInt(輸入字串2); 最大公因數=EuclidGCD(整數m, 整數n); 顯示字串="整數"+整數m+"與整數"+整數n+"的最大公因數為"+最大公因數; JOptionPane.showMessageDialog(null,顯示字串); } //方法:init() 定義區塊結束

30 以Java程式語言實作 歐幾里德GCD演算法
static int EuclidGCD(int m, int n) { int r=m%n; while (r!=0) { m=n; n=r; r=m%n; } return n; } //方法:EuclidGCD() 定義區塊結束 } //類別:EuclidGCDApplet 定義區塊結束

31 以Java程式語言實作 歐幾里德GCD演算法
網頁檔案(檔名：EuclidGCDApplet.html) <html> <h1>EuclidGCDApplet執行中<h1> <applet code="EuclidGCDApplet.class" width=350 height=100> </applet> </html> 執行結果(以瀏覽器載入檔案：EuclidGCDApplet.html)

32 以Java程式語言實作 歐幾里德GCD演算法 執行結果

33 演算法的正確性與效能

34 演算法的正確性與效能 設計一個演算法，首先要考慮的就是正確性(correctness)，也就是演算法是否能產生正確的結果，在達到正確性的要求之後，我們就要特別考慮演算法的效能(efficiency)了，也就是要考慮演算法是否能夠有效率的的執行。一般而言，若是數個演算法均能夠產生相同且正確的結果，則我們大都以效能來衡量其優劣。

35 一個用以測試質數的演算法 Algorithm Prime1(n): Input:一個大於2的正整數n Output:true或false(表示n是質數或不是質數) for i←2 to n-1 do if (n%i)=0 then return false return true 我們可以看出，輸入大於2的任意正整數n，若n是質數，則演算法Prime1需要執行整數除法求餘數(n%i)動作與整數比較((n%i)=0)動作n-2次之後，才可以知道n是質數。另外，若n不是質值，則演算法Prime1只要執行整數除法求餘數與整數比較動作1次，就可以知道n不是質數了。

36 測試質數的一個定理 [定理] 對於任意的大於2的整數n而言，若所有小於或等於 的整數(1除外)都無法整除n，則 n是一個質數。

37 提示 每個整數n的因數都是成對出現的，例如，16的因數為1與16(1*16=16)、2與8(2*8=16)、4與4(4*4=16)。成對出現的因數中，一個會小於等於n的平方根，而另一個則是大於等於n的平方根，因此，我們只要檢查小於等於n的平方根的所有不等於1的整數中是否有n的因數就可以知道n是不是質數了。

38 另一個用以測試質數的演算法 我們根據上列的定理設計出另一個演算法Prime2： Algorithm Prime2(n): Input:一個大於2的正整數n Output:true或false(表示n是質數或不是質數) for i←2 to √n do if (n%i)=0 then return false return true

39 Prime1Applet 範例程式(檔名：Prime1Applet.java) //檔名:Prime1Applet.java
//說明:此程式可輸入一個大於2的整數，並判斷此整數是否為質數(prime number) import javax.swing.*; public class Prime1Applet extends JApplet { public void init(){ int 整數n; String 輸入字串,顯示字串; 輸入字串=JOptionPane.showInputDialog("請輸入大於2的整數n？");

40 Prime1Applet 整數n=Integer.parseInt(輸入字串); boolean 是質數;
long 演算法執行前時間=System.currentTimeMillis(); 是質數=Prime1(整數n); long 演算法執行後時間=System.currentTimeMillis(); long 演算法執行時間=演算法執行後時間-演算法執行前時間; if(是質數) 顯示字串=整數n+"是質數"; else 顯示字串=整數n+"不是質數"; 顯示字串+=("\n演算法執行時間為"+演算法執行時間+"毫秒(milli-seconds)");

41 Prime1Applet JOptionPane.showMessageDialog(null,顯示字串);
} //方法:init() 定義區塊結束 boolean Prime1(int n) { for (int i=2;i<=n-1;++i) if (n%i==0) return false; return true; } } //類別:Prime1Applet 定義區塊結束

42 Prime1Applet 網頁檔案(檔名：Prime1Applet.html)
<h1>Prime1Applet執行中<h1> <applet code="Prime1Applet.class" width=350 height=100> </applet> </html> 執行結果(以瀏覽器載入檔案：Prime1Applet.html)

43 範例程式: 質數檢查演算法Prime1於瀏覽器中執行情形。

44 Prime2Applet 範例程式(檔名：Prime2Applet.java) //檔名:Prime2Applet.java
//說明:此程式可輸入一個大於2的整數，並判斷此整數是否為質數(prime number) import javax.swing.*; public class Prime2Applet extends JApplet { public void init(){ int 整數n; String 輸入字串,顯示字串; 輸入字串=JOptionPane.showInputDialog("請輸入大於2的整數n？"); 整數n=Integer.parseInt(輸入字串);

45 Prime2Applet boolean 是質數; long 演算法執行前時間=System.currentTimeMillis();
是質數=Prime2(整數n); long 演算法執行後時間=System.currentTimeMillis(); long 演算法執行時間=演算法執行後時間-演算法執行前時間; if(是質數) 顯示字串=整數n+"是質數"; else 顯示字串=整數n+"不是質數"; 顯示字串+=("\n演算法執行時間為"+演算法執行時間+"毫秒(milli-seconds)");

46 Prime2Applet JOptionPane.showMessageDialog(null,顯示字串);
} //方法:init() 定義區塊結束 boolean Prime2(int n) { for (int i=2;i<=Math.sqrt(n);++i) if (n%i==0) return false; return true; } } //類別:Prime2Applet 定義區塊結束

47 Prime2Applet 網頁檔案(檔名：Prime2Applet.html)
<h1>Prime2Applet執行中<h1> <applet code="Prime2Applet.class" width=350 height=100> </applet> </html> 執行結果(以瀏覽器載入檔案：Prime2Applet.html)

48 範例程式: 質數檢查演算法Prime2於瀏覽器中執行情形。

49 Q&A