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

Slides:



Advertisements
Similar presentations
3.2 Java的类 Java 类库的概念 语言规则——程序的书写规范 Java语言 类库——已有的有特定功能的Java程序模块
Advertisements

第一單元 建立java 程式.
Introduction to C Programming
計算機程式語言實習課.
第一章 資料結構導論 1-1 資料結構簡介 1-2 認識程式設計 1-3 演算法效能分析 1-4 物件導向程式設計與Java.
Java程序设计教程 第一讲 Java概述.
08 CSS 基本語法 8-1 CSS 的演進 8-2 CSS 樣式規則與選擇器 8-3 連結HTML 文件與CSS 樣式表
Hello小程序的运行和编译 Java AppletJava小程序的构成 1、关键字
算法设计与分析 Algorithm Design and Analysis
1 認識演算法 從食譜到高階程式語言.
從食譜到高階程式語言 國立中央大學 資工系 江振瑞
The discipline of algorithms
File Access 井民全製作.
TQC+ JAVA全國教師研習會 PLWeb 程式設計練習平台 簡介.
Hadoop 單機設定與啟動 step 1. 設定登入免密碼 step 2. 安裝java step 3. 下載安裝Hadoop
Chapter 5 迴圈.
程式設計概論 1.1 程式設計概論 程式語言的演進 物件導向程式 程式開發流程 1.2 C++開發工具
從食譜到高階程式語言 中央大學 資工系 江振瑞 教授
計算方法設計與分析 Design and Analysis of Algorithms 唐傳義
資料結構設計與C++程式應用 Fundamentals of Data Structures and Their Applications Using C++ 第3章 佇列 資料結構設計與C++程式應用.
Java程式概觀.
C語言簡介 日期 : 2018/12/2.
程式撰寫流程.
類別(class) 類別class與物件object.
SQL Stored Procedure SQL 預存程序.
安裝JDK 安裝Eclipse Eclipse 中文化
Introduction.
CHAP13 演算法概論 高中資訊科技概論 松崗圖書公司.
程式設計專題.
Java 程式設計 講師:FrankLin.
邏輯關係運算 == 等於 & 且 (logical and) ~= 不等於 | 或 (logical or) < 小於
JAVA 程式設計與資料結構 第四章 陣列、字串與數學物件.
第一章 直角坐標系 1-1 數系的發展.
程式設計實習課(四) ----C 函數運用----
第一單元 建立java 程式.
Chapter 5 Recursion.
分支宣告與程式設計 黃聰明 國立臺灣師範大學數學系
選擇性結構 if-else… switch-case 重複性結構 while… do-while… for…
義守大學電機工程學系 陳慶瀚 第4章 VHDL Sequential語法 義守大學電機工程學系 陳慶瀚
JAVA 程式設計 資訊管理系 - 網路組.
Introduction to C Programming
小學四年級數學科 8.最大公因數.
第一次Labview就上手 參考書籍: LabVIEW for Everyone (Jeffrey Travis/Jim Kring)
CH05. 選擇敘述.
挑戰C++程式語言 ──第8章 進一步談字元與字串
實作輔導 本周5/5(六)安排實作輔導 二時段: 周六 11:00~12:30 周六13:30~15:30.
第二章 Java语法基础.
挑戰C++程式語言 ──第7章 輸入與輸出.
流程控制:Switch-Case 94學年度第一學期‧資訊教育 東海大學物理系.
10394: Twin Primes ★★★☆☆ 題組:Problem Set Archive with Online Judge
第二章 Java基本语法 讲师:复凡.
※歡迎挑戰,兩人(隊)中先完成連線即算過關!
選擇性結構 if-else… switch-case 重複性結構 while… do-while… for…
反覆迴圈、陣列、副程式 靜宜大學資管系 楊子青
反覆迴圈、陣列、副程式 靜宜大學資管系 楊子青
if (j…) printf ("… prime\n"); else printf ("… not prime\n");
1757: Secret Chamber at Mount Rushmore
13194: DPA Number II ★★☆☆☆ 題組:Problem Set Archive with Online Judge
因數與倍數.
查表法&電腦IO Port二進制轉七段顯示器
Programming & Language Telling the computer what to do
10791: Minimum Sum LCM ★★★☆☆ 題組:Problem Set Archive with Online Judge
ABAP Basic Concept (2) 運算子 控制式與迴圈 Subroutines Event Block
String類別 在C語言中提供兩種支援字串的方式 可以使用傳統以null結尾的字元陣列 使用string類別
10303: How Many Trees? ★★☆☆☆ 題組:Contest Archive with Online Judge
11621 : Small Factors ★★☆☆☆ 題組:Problem Set Archive with Online Judge
微 處 理 機 專 題 – 8051 C語言程式設計 主題:階乘計算
方法(Method) 函數.
ABAP Basic Concept (2) 運算子 控制式與迴圈 Subroutines Event Block
InputStreamReader Console Scanner
Presentation transcript:

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

演算法名稱的由來

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

阿爾‧可瓦里茲米 (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)一字的由來。

什麼是演算法?

什麼是演算法? (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 藉由使用電腦執行精確解法以尋求某問題的解答 – 程 式設計師的觀點。

什麼是演算法? (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 在數學以及電腦科學的觀點中,演算法是一種完成一 些任務的程序(由一些具有明確定義的指令所組成), 而這些任務會給定一個起始狀態,並在達到預先定義 好的最終狀態時終止程序 – 維基百科。

什麼是演算法? (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.

演算法的例子

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

流程圖 (flowchart) 是演算法

程式 (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() 定義區塊結束

如何表示演算法?

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

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

歐幾里德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。

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

虛擬碼 (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的值相等。

虛擬碼 (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的動作。

虛擬碼 (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的動作。

虛擬碼 (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相等為止。

虛擬碼 (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的動作。

虛擬碼 (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之值。

歐幾里德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

如何實作演算法?

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

以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;

以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?");

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

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

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

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

演算法的正確性與效能

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

一個用以測試質數的演算法 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不是質數了。

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

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

另一個用以測試質數的演算法 我們根據上列的定理設計出另一個演算法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

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?");

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

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

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

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

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

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

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

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

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

Q&A