The role of Algorithms in Computing

Presentation on theme: "The role of Algorithms in Computing"— Presentation transcript:

1 The role of Algorithms in Computing

2 1.1 Algorithms Algorithm: 對一個 computational problem 而言，將輸入轉換為輸出的一連串計算過程，稱為 Algorithm。 例如，給你一堆數字＜31，41，59，26，41，58＞，一個排序的演算法可以把這些數字由小到大輸出成＜26，31，41，41，58，59＞。 排序(Sorting)是一個相當重要且基本的問題 Introduction

3 有什麼問題需要演算法？ 給定 n 個矩陣 ＜A1，A2，…，An＞，要求出他們的乘積 A1A2…An。由於矩陣乘法具有結合律的特性，所以有各種合法的相乘順序。例如當 n=4 時，以下的順序都是合法的：(A1(A2(A3A4)))，(A1((A2A3)A4))，((A1A2)(A3A4))，((A1(A2A3))A4)，或 (((A1A2)A3)A4)。如果這些矩陣都是方形的，那麼相乘的順序不會影響到計算答案的時間；反之，則相乘的順序對於時間的影響就會非常大。要嘗試所有的會花費非常長的時間，在之後會介紹一個有效率的演算法來解決這個問題。 這個問題會在 Dynamic Programming 的章節教到， 算是相當經典的一道題目。 假設 A1 矩陣大小為 2 * 3，A2 矩陣大小為 3 * 1，A3 矩陣大小為 1 * 2 (A1(A2A3))所需要的乘法數目為 = 18 ((A1A2)A3)所需要的乘法數目則只有 = 10，比前者好 Introduction

4 1.2 Algorithms as a technology
效率：不同的演算法在解決相同問題時在效率上可能會有相當的差異。這個差異可能遠比硬體或軟體所造成的影響還要巨大。 例如，在第二章會介紹 insertion sort，要排序 n 個數字所花費的時間約為 c1n2，其中 c1 是一個常數。Merge sort 則要花費約 c2nlg n (c2 為常數)。一般而言 c1 會小於 c2，但是常數的影響會遠比 n 還要小。 優化程式碼能加快的速度有限，但是改進演算法則可能會大大的改善效能。 Introduction

5 1.2 Algorithms as a technology
例如：c1=2，c2=50，電腦 A 每秒鐘可跑 109 個指令，電腦 B 較慢，每秒鐘只能跑 107 個指令。 假設 n=106： 在電腦 A 上跑 insertion sort 的時間為 2 · (106)2 個指令 109 指令/秒 在電腦 B 上跑 merge sort 的時間為 50 · 106 lg 106 個指令 107 指令/秒 = 2000 秒 雖然電腦 B 較慢，但是使用的 merge sort 比電腦 A 上使用的 insertion sort 還要好 因此電腦 B 跑出來的時間遠比電腦 A 還要短。 ≒ 100 秒 Introduction

6 註：當排序的數字個數到達 107 時，使用 insertion sort 需要花約 2
註：當排序的數字個數到達 107 時，使用 insertion sort 需要花約 2.3 天的時間，但 merge sort 只需要 20分鐘。所以當輸入的大小越大時，merge sort 的優勢就越明顯。 這也是設計algorithm的精神， 我們希望當輸入的大小越大時，擁有的優勢越明顯 Introduction

7 Exercises Problem 1: 你構想了一個新的編碼方式，編碼方式是用一個很聰明的方式把一段訊息中的任何地方插入亂數產生的字串。基於專利的關係我們不會在這邊討論字串如何亂數產生以及插入。然而，為了要驗證，我們必須要寫一個程式來檢查是否編碼過後的字串真的包含了原始的字串。 給定兩個字串 s 和 t，你要檢查 s 是否為 t 的 subsequence，換句話說，就是你要檢查是否可以刪去一些 t 的字元，再把剩下的字元合併在一起，而得到 s。 Introduction

8 Exercises 輸入：總共有好幾組測資。每一組測資都包含了由數字或英文字母構成的兩個字串 s 與 t，中間用一個空白隔開。遇到檔案結尾 EOF 代表結束。 輸出：對於每一組測資，輸出是否 s 為 t 的subsequence。 Introduction

9 以下是一個輸出入的實例: Sample Input Sample Output sequence subsequence
person compression VERDI vivaVittorioEmanueleReDiItalia caseDoesMatter CaseDoesMatter Yes No Introduction

10 Exercises Problem 2: 小鮑伯喜歡玩積木。他可以把積木疊成許多不同高度的積木堆。小鮑伯很開心的告訴他姊姊愛麗絲:「你看，我把牆蓋起來了！」。姊姊反駁說：「才沒有呢，真正的牆應該要有一樣的高度，你應該讓每堆積木疊得一樣高才行 」。在經過一番思考後，小鮑伯覺得姊姊是對的，於是他決定要重新堆那些積木。但是小鮑伯太懶惰了，他想要在移動最少積木的情況下完成一樣高的目的，你能幫助他嗎？ Introduction

11 Exercises 輸入：有好幾組測資。每組測資的一開始是一個整數 n，代表小鮑伯疊的積木堆數。接著下一行會包含 n 個整數，分別代表不同積木堆的高度。你可以假設 1n50 以及 1高度100。積木的總數可以被堆數整除，所以我們一定可以堆成高度一樣的積木堆。當 n=0 時代表輸入結束。 輸出：對於每組測資，先印出測資的編號，如同輸出實例所示。接著印”The minimum number of moves is k.”，其中 k 代表的是最少需要移動多少積木才能讓所有的積木堆有相同的高度。在每組測資的輸出之後多印一個空行。 Introduction

12 以下是一個輸出入的實例: Sample Input Sample Output 6 5 2 4 1 7 5 Set #1
Set #1 The minimum number of moves is 5. Introduction

13 Exercises Problem 3: 某個銀行根據可靠線報指出，在最後一批進來銀行的 N 個硬幣之中，有一個是假的，而且重量與其他硬幣不同。(其他真硬幣的重量都相同)。目前銀行只有一個簡單的天秤可以用，只能測出左邊或是右邊的物品誰比較重。 Introduction

14 Exercises 為了要檢查假硬幣，銀行員把所有的硬幣從 1 到 N 編號，每個硬幣都有自己的號碼，跟別的硬幣不重複。之後他們就會開始量重量，量的時候是把相同數量的硬幣放在兩邊的秤盤上。每一次的測量都會把硬幣的編號以及結果紀錄下來。請你寫一個程式來幫助銀行員判斷假硬幣的編號是多少。 輸入：第一行會給一個整數 M，在一個空行之後會接著 M 組測資，每組測資都會用一個空行隔開。接下來的每一組測試資料，一開始會先給兩個整數 N 和 K（中間用空白隔開），N 代表的是硬幣數目(1N100) ，K 代表銀行員量了幾次重量(1K100)。以下的 2K 行是測量的結果。每兩行是一次的測量紀錄，其中的第一行會先給一個整數 Pi (1PiN/2)，代表那次測量放在左邊及右邊的硬幣數，接著會有 Pi 個整數表示放在左秤盤的硬幣編號，然後是 Pi 個整數表示放在右秤盤的硬幣編號。所有的數字都用空白隔開。 Introduction

15 Exercises 其中測試紀錄的第二行會有三種情況：’<’, ’>’, 或是’=’，代表測量的結果：
‘<‘ 表示左邊秤盤的硬幣比右邊秤盤的硬幣還輕 ‘>‘ 表示左邊秤盤的硬幣比右邊秤盤的硬幣還重 ‘=‘ 表示左邊秤盤的硬幣跟右邊秤盤的硬幣一樣重 輸出：對於每組測資，如果不能判斷哪個硬幣是假的，就輸出 0，否則就輸出假硬幣的編號。在每組測資的輸出中間用一個空行隔開。 Introduction

16 以下是一個輸出入的實例: Sample Input Sample Output 1 5 3 2 1 2 3 4 < 1 1 4 =
1 2 5 3 Introduction