The discipline of algorithms

Presentation on theme: "The discipline of algorithms"— Presentation transcript:

1 The discipline of algorithms
Algorithmics The discipline of algorithms

2 Abu Ja’far Mohammed ibn Musa al Khowarizmi
Algorithm comes from the name of a Persian, Abu Ja’far Mohammed ibn Musa al Khowarizmi (c. 825 A. D.).

3 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)一字的由來。

4 What is an algorithm (1/2)
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 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

5 What is an algorithm (2/2)
An algorithm is composed of a set of steps for solving a specific problem. It should satisfy the following properties: Zero or more inputs At least one output Finiteness (the number of steps should be finite and the execution of the steps should terminate) Definiteness (to compute 5/0 is not definite) Effectiveness (to compute √2 as an infinite decimal is not effective) Definiteness: each instruction is clear and unambiguous. To compute “add 6 or 7 to x” is not definite. Finiteness: 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.

6 A recipe is an algorithm
Informally, the concept of an algorithm is often illustrated by the example of a recipe. 梅焗肉排 材料：（４人份） 一字排12兩 鹹話梅6-8粒 紅椒2隻 中國芹菜2條 洋蔥1小個 紅谷米少許 冰糖適量 生抽適量 　 做法： 1. 話梅連一隻切角紅椒和紅谷米以六碗水煎至一碗水，隔渣保留汁及話梅備用。中國芹菜切段；洋蔥及另一隻紅椒切角，備用。 2. 一字排洗淨，切件，加適量生粉拌勻，放滾油內炸至金黃香脆，瀝乾油備用。 3. 取話梅及汁，加入生抽、冰糖煮滾，再加中國芹菜、紅椒角、洋蔥略煮約1分鐘，放一字排燜焗約2分鐘至入味，埋少許生粉水即可。

7 A flowchart is an algorithm

8 A program is an algorithm
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() 定義區塊結束

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

10 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。

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

12 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的值相等。

13 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的動作。

14 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的動作。

15 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相等為止。

16 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的動作。

17 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之值。

18 Pseudo Code for Euclid Alg.
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

19 Java Method for Euclid Alg.
int Euclid_GCD(int m, int n) { int r=m%n; while (r!=0) { m=n; n=r; r=m%n; } return n;

20 Java Applet for Euclid Alg.
範例程式(檔名：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？");

21 Java Applet for Euclid Alg.
輸入字串2=JOptionPane.showInputDialog("請輸入正整數n？"); 整數m=Integer.parseInt(輸入字串1); 整數n=Integer.parseInt(輸入字串2); 最大公因數=EuclidGCD(整數m, 整數n); 顯示字串="整數"+整數m+"與整數"+整數n+"的最大公因數為"+最大公因數; JOptionPane.showMessageDialog(null,顯示字串); } //方法:init() 定義區塊結束

22 Java Applet for Euclid Alg.
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 定義區塊結束

23 Java Applet for Euclid Alg.
網頁檔案(檔名：EuclidGCDApplet.html) <html> <h1>EuclidGCDApplet執行中<h1> <applet code="EuclidGCDApplet.class" width=350 height=100> </applet> </html> 執行結果(以瀏覽器載入檔案：EuclidGCDApplet.html)

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

25 An Alg. for Testing Primes
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不是質數了。

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

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

28 The Other Alg. for Testing Primes
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

29 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？");

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

31 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 定義區塊結束

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

33 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(輸入字串);

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

35 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 定義區塊結束

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

37 Q&A

38 範例程式1-3.質數檢查演算法Prime2於瀏覽器中執行情形。

39 範例程式1-2.質數檢查演算法Prime1於瀏覽器中執行情形。

40 Result