演算法整数及矩阵课件

1、Discrete Mathematics Chapter 3 The Fundamentals : Algorithms, the Integers, and Matrices大葉大學 資訊工程系 黃鈴玲Ch3-23.1 Algorithms (演算法)Def 1. An algorithm is a finite sequence of precise instructions for performing a computation or for solving a problem.Example 1. Describe an algorithm for finding the maxim

2、um value in a finite sequence of integers.(假設給定的整數序列是a1,a2,an，求最大值)Ch3-3Solution : ( English language)Set the temporary maximum equal to the first integer in the sequence.Compare the next integer in the sequence to the temporary maximum, and if it is larger than the temporary maximum, set the tempor

3、ary maximum equal to this integer.Repeat the previous step if there are more integers in the sequence.Stop when there are no integers left in the sequence. The temporary maximum at this point is the largest integer in the sequence.Ch3-4procedure 表示開始一個副程式:= 用來表示指定 max := a1表示指定max變數的值等於a1大括號用來存放註解，此

4、處標示輸出變數是maxAlgorithm 1. Finding the Maximum Elementprocedure max(a1, a2, , an : integers)max := a1for i := 2 to n if max ai then max := ai max is the largest elementSolution (pseudo-code虛擬碼)演算法名稱輸入變數名稱輸入變數型別Ch3-5 There are several properties that algorithms generally share : InputOutputDefiniteness

5、: The steps of an algorithm must be defined precisely.Correctness : produce correct output valuesFiniteness : produce the desired output after a finite number of step.EffectivenessGenerality : The procedure should be applicable for all problems of the desired form, not just for a particular set of i

6、nput values.Exercise 3.13. 設計一個演算法，找出某個整數集合中所有數目的總和。Ch3-6參考找最大值的演算法做修改：procedure max(a1, a2, , an : integers)max := a1for i := 2 to n if max ai then max := ai max is the largest elementprocedure sum (a1, a2, , an : integers)sum := for i := to sum is the largest elementCh3-7Problem : Locate an elemen

7、t x in a list of distinct elements a1,a2,an, or determine that it is not in the list. 做法 : linear search(線性搜尋), binary search(二元搜尋)Algorithm 2. The linear search algorithm procedure linear_search( x : integer, a1,a2,an: distinct integers)i := 1While ( i n and xai ) i := i + 1if i n then location :=

8、i else location := 0 location = j if x = aj; location = 0 if x is not found. Searching (搜尋) AlgorithmsExercise 3.113(a). 列出線性搜尋用來從序列 1, 3, 4, 5, 6, 8, 9, 11中尋找 9 的步驟。Ch3-8參考：procedure linear_search( x : integer, a1,a2,an: distinct integers)i := 1While ( i n and xai ) i := i + 1if i n then location :

9、= i else location := 0 location = j if x = aj; location = 0 if x is not found.Ch3-9兩種search方式的概念 : Linear Search : 從 a1 開始，逐一比對 x 是否等於 ai，若找到則 location = i , 若到 an 比完後還找不到，則 location = 0。Binary Search : (必須具備 a1 a2 am 表示 x 應在右半，否則在左半。 (2) 重覆上一步驟至 list 只剩一個元素 ai， 若 x = ai 則 location = i，否則 location =

10、 0。Ch3-10Example 3. Search 19 from a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14 a15 a16 1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22 12 13 15 16 18 19 20 22 18 19 20 22 18 19 191. 切兩半, m=8 因 x=19 a8=10，取右半，i=9 2. 再切二半, m=12 因 x=19 a12=16，取右半, i=133. 再切二半, m=14 因 x=19 a14=19，取左半, j=144. 再切二半, m=13 因 x=

11、19 a13=18，取右半, i=145 此時 i = j =14, 數列只剩一個元素 a14 = 19 因 x= 19 = a14，故 location =14Note : ai, ai+1, , aj 數列的切法 : 令 m = 則 am 即切開紅線左邊那點。x正在搜尋 x 的數列為 ai, ai+1, , aj 一開始 i=1, j=16 Ch3-11Algorithm 3. The Binary Search Algorithmprocedure binary_search( x : integer, a1,a2,an : increasing integers)i :=1 i is

12、left endpoint of search interval j := n j is right endpoint of search interval while i am then i := m+1 else j := m endif x = ai then location := i else location := 0 location = i if x = ai , location = 0 if xai , i Exercise 3.113(b). 列出二元搜尋用來從序列 1, 3, 4, 5, 6, 8, 9, 11中尋找 9 的步驟。Ch3-12參考：procedure b

13、inary_search( x : integer, a1,a2,an : increasing integers)i :=1 i is left endpoint of search interval j := n j is right endpoint of search interval while i am then i := m+1 else j := m endif x = ai then location := i else location := 0 location = i if x = ai ; location = 0 if xai, i 13(補充). 列出二元搜尋用來

14、從序列 2, 4, 6, 8, 10, 12, 14 中尋找 3 的步驟。Ch3-13參考：procedure binary_search( x : integer, a1,a2,an : increasing integers)i :=1 i is left endpoint of search interval j := n j is right endpoint of search interval while i am then i := m+1 else j := m endif x = ai then location := i else location := 0 locatio

15、n = i if x = ai ; location = 0 if xai, i Ch3-14Problem : Suppose that we have a list of elements, a sorting is putting these elements into a list in which the elements are in increasing order.eg. 7, 2, 1, 4, 5, 9 = 1, 2, 4, 5, 7, 9 d, t, c, a, f = a, c, d, f, t 解法有很多，此處僅介紹 : bubble sort (氣泡排序法)，及 in

16、sertion sort (插入排序法)。Bubble Sort 概念 : 設原 list 為 a1,an。從a1,a2開始，向後兩兩比較，若ai ai+1 則交換，當檢查完 an 時，an 必定是最大數。再從 a1,a2 開始向後比較，若ai ai+1 則交換，此時只需檢查到 an-1 即可。依此類推。 Sorting Algorithms(跳過)Ch3-15Example 4. Use the bubble sort to put 3, 2, 4, 1, 5 into increasing order.Sol : 32415First pass (i=1) :234152341523145

17、Second pass (i=2) :Third pass (i=3) :Fourth pass (i=4) :12345231452314521345213452314521345123451234512345(跳過)Ch3-16 Algorithm 4 The Bubble Sort procedure bubble_sort (a1,an )for i := 1 to n-1 for j := 1 to n-i if aj aj+1 then interchange aj and aj+1 a1,a2,an is in increasing order (跳過)Ch3-17Inserti

18、on Sort 的概念 : 從 j = 2 開始，將 aj 插入已排序好的 a1,aj-1間的位置，使得 a1,aj 都由小 大排好。j 逐次遞增，重複上一步驟至做完。(跳過)Ch3-18Example 5. Use insertion sort to sort 3, 2, 4, 1, 5Sol :(j=2時，a1=3可看成已經排序好的數列，此時要插入a2) : 3 2, 4 3 4的位置不變 2, 3, 4, 1, 5 (j=4時，a1,a2 ,a3已經排序好，此時要插入a4) : 1 1, 5 2, 5 3, 5 4 5不變 1, 2, 3, 4, 5a1 a2 a3 a4 a5(跳過)C

19、h3-19Algorithm 5 The Insertion Sort procedure insertion_sort ( a1,an : real numbers with n 2 )for j := 2 to n begin i := 1 while aj ai i := i + 1 m := aj for k := 0 to j i 1aj-k := aj-k-1 ai := mend a1,a2,an are sorted ( Exercise : 13, 23, 35, 39 )找出 aj 應插入的位置最後ai-1 aj k . ( read as “f (x) is big-oh

20、 of g(x)” )我們說函數 f (x) 是 O(g(x) 代表在 x 夠大時，| f (x)| |g(x)| 的某個常數倍數Ch3-22Example 1. Show that f (x) = x2+2x+1 is O(x2)Sol : Since x2+2x+1 x2+2x2+x2 = 4x2 whenever x 1 , it follows that f (x) is O(x2)(take C = 4 and k =1 ) 另法： If x 2, we see that x2+2x+1 x2+x2+x2 = 3x2 ( take C = 3 and k = 2 )通常都是把最高次項

21、搬進來Ch3-23Figure 2. The function f (x) is O(g(x) Example 1(補充). Show that f (x)= x2 +2x +2 is O(x3)Sol : Since x2+2x+2 x3+x3+x3 = 3x3 whenever x 1, we see that f (x) is O(x3) ( take C = 3 and k = 1 ) kCg(x)f (x)g(x)f (x) kNote. The function g is chosen to be as small as possible. 大O符號裡放的函數 要越小越好Ch3-2

22、4Example 5. How can big-O notation be used to estimate the sum of the first n positive integers? ( i.e., )Sol : 1 + 2 + 3 + + n n + n + + n = n2 is O(n2), taking C =1 and k =1.Theorem 1. Let f (x) = anxn+an-1xn-1+a1x+a0 where a0, a1, , an are real numbers. Then f (x) is O(xn).(跳過)Ch3-25Example 6. Gi

23、ve big-O estimates for f (n) = n!Sol : n! = 12 3 n n n n = nn n! is O(nn) , taking C =1 and k =1.Theorem 2,3 Suppose that f1(x) is O(g1(x) and f2(x) is O(g2(x), then (f1+f2)(x) is O(max(|g1(x)|, |g2(x)|), (f1 f2)(x) is O(g1(x) g2(x).Example 7. (see Figure 3) 常見function的成長速度由小至大排列： 1 log n n n log n

24、n2 2n n!(跳過)Ch3-26Exercise 7,11,19Exercise 19(c) : f (n) = (n!+2n)(n3+log(n2+1) (n!+n!)(n3+n3) = 4n3n! f (n) is O(n3n!) 取 C = 4, k = 3(跳過)Ch3-273.3 Complexity of AlgorithmsQ : 如何分析演算法的執行效能？ Ans : (1) time (2) memoryDef : Time complexity: an analysis of the time required to solve a problem of a parti

25、cular size. (評量方式 : 計算運算次數，如 “做比較”的次數，“加法” 或 “乘法”次數等) Space complexity: 分析解問題時所需的電腦記憶體容量 (通常是資料結構探討的範圍)(複雜度)Ch3-28Example 1. 描述 Algorithm 1 (Find Max) 的時間複雜度.Algorithm 1. ( Find Max )procedure max(a1,an : integers)max := a1for i := 2 to n if max n.當 i 變成 n+1 時因比 n 大，故結束 for 迴圈。 共有 n 次比較共有 n-1 次比較故整個

26、演算法共做 2n-1 次比較其時間複雜度 為 O(n).Ch3-29Example 2. Describe the time complexity of the linear search algorithm.Algorithm 2 ( Linear Search )procedure ls ( x : integer , a1,an : distinct integers )i := 1While ( i n and x ai ) i := i +1if i n then location := i else location := 0 location = i if x = ai; loc

27、ation = 0 if x ai iSol : ( 計算比較次數) (Case 1) 當 x = 某個 ai 時 此行只執行 i 次，故此行共2i次比較 加上if，共計 2i +1次比較. (Case 2) 當 x 任何 ai 時 此行執行 n 次後 第 n + 1 次時 i = n + 1 n 即跳出 共計 2n+2 次比較 由(1)、(2)取 worst-case (最糟的情形) 故演算法的 time complexity為 O(n)Exercise 3.37. 對多項式 an xn + an-1xn-1 + + a1x +a0， 求出 x = c 時的值，傳統演算法做法如下：Ch3-3

28、0procedure polynomial (c, a0, a1,an : real numbers)power := 1 變數power用來表示乘冪y := a0 變數y用來表示目前已算出的多項式值for i := 1 to nbegin power := power * c y := y + ai * powerend y = anc n + an-1c n-1 + + a1c +a0執行上述演算法的每一步驟，計算 3x2 + x +1 在 x =2 時的值為求出n階多項式在x = c時的值，所需乘法與加法次數為何？Exercise 3.38. 對多項式 an xn + an-1xn-1

29、+ + a1x +a0， 求出 x = c 時的值，更有效率的Horner演算法做法如下：Ch3-31procedure Horner (c, a0, a1,an : real numbers)y := an for i := 1 to n y := y * c + an-i y = anc n + an-1c n-1 + + a1c +a0執行上述演算法的每一步驟，計算 3x2 + x +1 在 x =2 時的值為求出n階多項式在x = c時的值，所需乘法與加法次數為何？Ch3-32Example 4. Describe the average-case performance of the

30、 linear search algorithm, assuming that x is in the list.Sol : ( 計算 “平均比較次數” )已知當 x = ai 時，共需 2i + 1 次比較.( by Example 2 )x = a1,a2, , 或 an 的機率都是 1/n.平均比較次數 (即期望值)= ( x = a1 的比較次數 ) ( x = a1 的機率 )+ ( x = a2 的比較次數 ) ( x = a2 的機率 )+ + ( x = an 的比較次數 ) ( x = an 的機率 )= 3 1/n + 5 1/n + + ( 2n+1) 1/n= ( 3+

31、5+(2n+1) / n= / n = n + 2average-case的time complexity為O(n)Alg. 2 ( Linear Search )procedure ls ( x,a1,an)i := 1While ( i n and x ai ) i := i +1if i n then location := i else location := 0(跳過)Exercise : 13Ch3-33Example 3. Describe the time complexity of the binary search algorithm.Sol : 設 n = 2k 以簡化計

32、算(若 n 2k，其比較次數必小於等 於 n = 2k 的情況)因while迴圈每次執行後整個 list 會切成兩半故最多只能切 k 次就會因 i = j 而跳出迴圈共比較 2k+2 次time complexity 為 O(k) = O(log n)Alg. 3 ( Binary Search )procedure bs ( x : integer, a1,an : increasing integers )i := 1 left endpoint j := n right endpoint while i am then i := m+1 /* ( k次 ) else j := mendi

33、f x = ai then location := i /* ( 1次 )else location := 0Ch3-34Example 5. What is the worst-case complexity of the bubble sort in terms of the number of comparisons made ?procedure bubble_sort ( a1,an )for i := 1 to n -1 for j := 1 to n i if aj aj+1 then interchange aj and ai+1 a1,an is in increasing

34、order Sol : 共 n-1 個 pass 第 i 個 pass 需 n i 次比較 共計 (n-1)+(n-2)+1 = 次比較 O(n2)Note 1. 不管何種 case 都需做 次比較。Note 2. For 迴圈所需比較次數通常會省略，因此Example 5,6 不再考慮。(跳過)Ch3-35Example 6. What is the worst-case complexity of the insertion sort in terms of the number of comparisons made ?procedure insertion_sort ( a1,an )

35、for j := 2 to n begin i := 1 while aj ai i := i +1 m := aj for k := 0 to j - i -1 aj-k := aj-k-1 ai := mend a1,an are sorted Sol : 做最多次比較的情況如下： 在考慮 aj 時 a1 a2 aj-1 aj 此時共做 j 次比較 故共計 2+3+n = -1 次比較 O(n2)(即 worst case 是 a1 a2 1Exponential complexityO(n!)Factorial complexityCh3-373.4 The integers and d

36、ivision探討一些 Number Theory 的基本觀念Def 1. a,b : integers, a0. a divides b (denote a | b) if cZ, b=ac. a : a factor (因數) of b, b : a multiple (倍數) of a (a b if a does not divide b) Theorem 1. a,b,c Z, (i) If a | b and a | c then a | (b+c). (ii) If a | b then a | bc for any integer c. (iii) If a | b and b

37、 | c then a | c.Corollary 1. If a,b,c Z and a | b , a | c. then a | (mb+nc) whenever m,n Z.(除法)Ch3-38Def 2. In the equality a = dq + r with 0 r d, d is called the divisor (除數), a is called the dividend (被除數), q is called the quotient (商數), and r is called the remainder (餘數). q = a div d, r = a mod d

38、Example 3. 101 div 11= ? (商數) 101 mod 11 =? (餘數)Sol: 101 = 11 9 + 2 故 101 div 11 = 9, 101 mod 11 = 2 Example 4. -11 div 3= ? (商數) -11 mod 3 =? (餘數)Sol: -11 = 3 (-4) + 1 故 -11 div 3 = -4, -11 mod 3 = 1 Exercise 3.410. (b) 777 div 21 = 777 mod 21 = (c) -123 div 19 = -123 mod 19Ch3-39Ch3-40Def 3. If a,

39、bZ, mZ+, then a is congruent (同餘) to b modulo m if m | (a-b). (表示為 a b (mod m), 即整數a、b 對模m同餘). 模算術Thm 3. Let mZ+, a,bZ. a b (mod m) iff a mod m = b mod m. Example 5. 判斷在模6時，17是否同餘於5? 24是否同餘於14?Sol: 17 mod 6 = 5, 5 mod 6 = 5, 故17同餘於5 24 mod 6 = 0, 14 mod 6 = 2, 故24不同餘於14Ch3-41Thm 5. Let mZ+, a,bZ. If

40、 a b (mod m) and c d (mod m), then a+c b+d (mod m) and ac bd (mod m). Thm 4. Let mZ+, a,bZ. a b (mod m) iff kZ, 使得 a = b + km.Example 6. 7 2 (mod 5), 11 1 (mod 5), 故 18 3 (mod 5), 77 2 (mod 5).Exercise 3.419. 判斷下列何者在模數 17 時，與 5 同餘。 (a) 80 (b) 103 (c) -29 (d) -122Ch3-42補充： 請計算 (1717 9 + 31) mod 5 =?同

41、餘的應用-密碼學凱撒大帝的加密法：將訊息中每個字母向後移動三位，最後三個字母則以最前面三個字母取代，如 B 換成 E，X 換成 A。以數學方式表示：將AZ以025編碼，將編號 p 的字母以 f(p) 取代，其中 f(p) = (p+3) mod 26。Ch3-43Example 9. 根據凱撒大帝的密碼製作方式，下面的訊息會被加密成什麼？ “MEET YOU IN THE PARK”Sol. “PHHW BRX LQ WKH SDUN”改進加密法：將AZ以025編碼，將編號 p 的字母以 f(p) 取代，其中 f(p) = (ap + b) mod 26，所選取的整數 a, b 只要能使 f(

42、p) 成為對射函數即可。Ch3-44Example 10. 若使用 f(p) = (7p + 3) mod 26來加密，則將會用哪一個字母來取代 K?Sol. K 的編碼是 10， (710+3) mod 26 = 21 故用V取代KABCDEFGHIJKLM0123456789101112NOPQRSTUVWXYZ13141516171819202122232425Exercise 3.431. 利用給定的函數 f(p) = (7p + 3) mod 26，將訊息 “PASS THROUGH” 加密，寫出加密的訊息。32. 將下列經凱撒密碼加密之訊息解密： “EOXH MHDQV” Ch3-

43、45ABCDEFGHIJKLM0123456789101112NOPQRSTUVWXYZ13141516171819202122232425Ch3-463.5 Primes and Greatest Common DivisorsDef 1. pZ+-1 is called prime (質數) if a p, 1a x then r = x) x := y y := r end gcd (a, b) = x eg. 求 gcd (6,12)x = 6 y = 12while y0 r = 6 mod 12 =6 x = 12 y = 6while y0 r = 12 mod 6 = 0 x

44、= 6 y = 0 while y = 0 , end. gcd (6,12) = 6Exercise : 23,25歐基里得演算法Exercise 3.623(c). 利用歐基里得演算法求出 gcd(1001, 1331) Ch3-5325. 利用歐基里得演算法求 gcd(21, 34)時，共需用到多少次除法？ Ch3-543.7 Applications of Number Theory介紹中國餘數定理Example 5. 孫子算經 :某物不知其數，三三數之餘二，五五數之餘三，七七數之餘二，問物幾何 ?i.e. x 2 (mod 3) x 3 (mod 5) x = ? x 2 (mod 7) Theorem 4. (The Chinese Remainder Theorem)Let m1,m2,mn be pairwise relatively prime positive