演算法整數(shù)及矩陣課件

1、Discrete Mathematics Chapter 3 The Fundamentals : Algorithms, the Integers, and Matrices大葉大學(xué) 資訊工程系 黃鈴玲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.(假設(shè)給定的整數(shù)序列是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 表示開始一個(gè)副程式:= 用來表示指定 max := a1表示指定max變數(shù)的值等於a1大括號(hào)用來存放註解，此

4、處標(biāo)示輸出變數(shù)是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虛擬碼)演算法名稱輸入變數(shù)名稱輸入變數(shù)型別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. 設(shè)計(jì)一個(gè)演算法，找出某個(gè)整數(shù)集合中所有數(shù)目的總和。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 開始，逐一比對(duì) x 是否等於 ai，若找到則 location = i , 若到 an 比完後還找不到，則 location = 0。Binary Search : (必須具備 a1 a2 am 表示 x 應(yīng)在右半，否則在左半。 (2) 重覆上一步驟至 list 只剩一個(gè)元素 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 此時(shí) i = j =14, 數(shù)列只剩一個(gè)元素 a14 = 19 因 x= 19 = a14，故 location =14Note : ai, ai+1, , aj 數(shù)列的切法 : 令 m = 則 am 即切開紅線左邊那點(diǎn)。x正在搜尋 x 的數(shù)列為 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(補(bǔ)充). 列出二元搜尋用來

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 概念 : 設(shè)原 list 為 a1,an。從a1,a2開始，向後兩兩比較，若ai ai+1 則交換，當(dāng)檢查完 an 時(shí)，an 必定是最大數(shù)。再從 a1,a2 開始向後比較，若ai ai+1 則交換，此時(shí)只需檢查到 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時(shí)，a1=3可看成已經(jīng)排序好的數(shù)列，此時(shí)要插入a2) : 3 2, 4 3 4的位置不變 2, 3, 4, 1, 5 (j=4時(shí)，a1,a2 ,a3已經(jīng)排序好，此時(shí)要插入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 應(yīng)插入的位置最後ai-1 aj k . ( read as “f (x) is big-oh

20、 of g(x)” )我們說函數(shù) f (x) 是 O(g(x) 代表在 x 夠大時(shí)，| f (x)| |g(x)| 的某個(gè)常數(shù)倍數(shù)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 )通常都是把最高次項(xiàng)

21、搬進(jìn)來Ch3-23Figure 2. The function f (x) is O(g(x) Example 1(補(bǔ)充). 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符號(hào)裡放的函數(shù) 要越小越好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的成長(zhǎng)速度由小至大排列： 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 : 如何分析演算法的執(zhí)行效能？ Ans : (1) time (2) memoryDef : Time complexity: an analysis of the time required to solve a problem of a parti

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

26、演算法共做 2n-1 次比較其時(shí)間複雜度 為 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 : ( 計(jì)算比較次數(shù)) (Case 1) 當(dāng) x = 某個(gè) ai 時(shí) 此行只執(zhí)行 i 次，故此行共2i次比較 加上if，共計(jì) 2i +1次比較. (Case 2) 當(dāng) x 任何 ai 時(shí) 此行執(zhí)行 n 次後 第 n + 1 次時(shí) i = n + 1 n 即跳出 共計(jì) 2n+2 次比較 由(1)、(2)取 worst-case (最糟的情形) 故演算法的 time complexity為 O(n)Exercise 3.37. 對(duì)多項(xiàng)式 an xn + an-1xn-1 + + a1x +a0， 求出 x = c 時(shí)的值，傳統(tǒng)演算法做法如下：Ch3-3

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

29、+ + a1x +a0， 求出 x = c 時(shí)的值，更有效率的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執(zhí)行上述演算法的每一步驟，計(jì)算 3x2 + x +1 在 x =2 時(shí)的值為求出n階多項(xiàng)式在x = c時(shí)的值，所需乘法與加法次數(shù)為何？Ch3-32Example 4. Describe the average-case performance of the

30、 linear search algorithm, assuming that x is in the list.Sol : ( 計(jì)算 “平均比較次數(shù)” )已知當(dāng) x = ai 時(shí)，共需 2i + 1 次比較.( by Example 2 )x = a1,a2, , 或 an 的機(jī)率都是 1/n.平均比較次數(shù) (即期望值)= ( x = a1 的比較次數(shù) ) ( x = a1 的機(jī)率 )+ ( x = a2 的比較次數(shù) ) ( x = a2 的機(jī)率 )+ + ( x = an 的比較次數(shù) ) ( x = an 的機(jī)率 )= 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 : 設(shè) n = 2k 以簡(jiǎn)化計(jì)

32、算(若 n 2k，其比較次數(shù)必小於等 於 n = 2k 的情況)因while迴圈每次執(zhí)行後整個(gè) list 會(huì)切成兩半故最多只能切 k 次就會(huì)因 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 個(gè) pass 第 i 個(gè) pass 需 n i 次比較 共計(jì) (n-1)+(n-2)+1 = 次比較 O(n2)Note 1. 不管何種 case 都需做 次比較。Note 2. For 迴圈所需比較次數(shù)通常會(huì)省略，因此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 時(shí) a1 a2 aj-1 aj 此時(shí)共做 j 次比較 故共計(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 (因數(shù)) of b, b : a multiple (倍數(shù)) 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 (除數(shù)), a is called the dividend (被除數(shù)), q is called the quotient (商數(shù)), and r is called the remainder (餘數(shù)). q = a div d, r = a mod d

38、Example 3. 101 div 11= ? (商數(shù)) 101 mod 11 =? (餘數(shù))Sol: 101 = 11 9 + 2 故 101 div 11 = 9, 101 mod 11 = 2 Example 4. -11 div 3= ? (商數(shù)) -11 mod 3 =? (餘數(shù))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), 即整數(shù)a、b 對(duì)模m同餘). 模算術(shù)Thm 3. Let mZ+, a,bZ. a b (mod m) iff a mod m = b mod m. Example 5. 判斷在模6時(shí)，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. 判斷下列何者在模數(shù) 17 時(shí)，與 5 同餘。 (a) 80 (b) 103 (c) -29 (d) -122Ch3-42補(bǔ)充： 請(qǐng)計(jì)算 (1717 9 + 31) mod 5 =?同

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

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

43、45ABCDEFGHIJKLM0123456789101112NOPQRSTUVWXYZ13141516171819202122232425Ch3-463.5 Primes and Greatest Common DivisorsDef 1. pZ+-1 is called prime (質(zhì)數(shù)) 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)時(shí)，共需用到多少次除法？ Ch3-543.7 Applications of Number Theory介紹中國(guó)餘數(shù)定理Example 5. 孫子算經(jīng) :某物不知其數(shù)，三三數(shù)之餘二，五五數(shù)之餘三，七七數(shù)之餘二，問物幾何 ?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