演算法整数及矩阵课件

《演算法整数及矩阵课件》由会员分享，可在线阅读，更多相关《演算法整数及矩阵课件（59页珍藏版）》请在装配图网上搜索。

1、Discrete MathematicsChapter3TheFundamentals:Algorithms,theIntegers,andMatrices大葉大學大葉大學 資訊工程系資訊工程系 黃鈴玲黃鈴玲Ch3-23.1 Algorithms(演算法演算法)Def 1.Analgorithmisafinitesequenceofpreciseinstructionsforperformingacomputationorforsolvingaproblem.nExample 1.Describeanalgorithmforfindingthemaximumvalueinafinitesequ

2、enceofintegers.(假設給定的整數序列是a1,a2,an，求最大值)Ch3-3Solution:(Englishlanguage)1.Setthetemporarymaximumequaltothefirstintegerinthesequence.2.Comparethenextintegerinthesequencetothetemporarymaximum,andifitislargerthanthetemporarymaximum,setthetemporarymaximumequaltothisinteger.3.Repeatthepreviousstepiftherea

3、remoreintegersinthesequence.4.Stopwhentherearenointegersleftinthesequence.Thetemporarymaximumatthispointisthelargestintegerinthesequence.Ch3-4procedure 表示開始一個副程式:=用來表示指定 max:=a1表示指定max變數的值等於a1大括號用來存放註解，此處標示輸出變數是maxAlgorithm 1.Finding the Maximum Elementprocedure max(a1,a2,an:integers)max:=a1for i:=2

4、 to n if max ai then max:=ai max is the largest elementSolution(pseudo-code虛擬碼)演算法名稱輸入變數名稱輸入變數型別Ch3-5Thereareseveralpropertiesthatalgorithmsgenerallyshare:nInputnOutputnDefiniteness:Thestepsofanalgorithmmustbedefinedprecisely.nCorrectness:producecorrectoutputvaluesnFiniteness:producethedesiredoutput

5、afterafinitenumberofstep.nEffectivenessnGenerality:Theprocedureshouldbeapplicableforallproblemsofthedesiredform,notjustforaparticularsetofinputvalues.Exercise3.13.設計一個演算法，找出某個整數集合中所有數目的總和。Ch3-6參考找最大值的演算法做修改：參考找最大值的演算法做修改：procedure max(a1,a2,an:integers)max:=a1for i:=2 to n if max ai then max:=ai max

6、 is the largest elementprocedure sum(a1,a2,an:integers)sum:=for i:=to sum is the largest elementCh3-7Problem:Locateanelementxinalistofdistinctelementsa1,a2,an,ordeterminethatitisnotinthelist.做法:linearsearch(線性搜尋),binarysearch(二元搜尋)Algorithm 2.The linear search algorithmprocedure linear_search(x:inte

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

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

9、0Example 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.再切二半再切二

10、半,m=13 因因 x=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 integer

11、s)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 Exercise3.113(b).列出二元搜尋用來從序列1,3,4,5,6,8,9,11中尋找9的步驟。Ch3-12參考：參考：procedure binary_search(x:inte

12、ger,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(補充).列出二元搜尋用來從序列2,4,6,8,10,12,14中尋找3的步驟。Ch3-13參考：參考：procedure

13、 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 location=i if x=ai;location=0 if xai,i Ch3-14nProblem:Supposethatwehavealistofele

14、ments,asortingisputtingtheseelementsintoalistinwhichtheelementsareinincreasingorder.neg.7,2,1,4,5,9=1,2,4,5,7,9d,t,c,a,f=a,c,d,f,tn解法有很多，此處僅介紹:bubblesort(氣泡排序法)，及insertionsort(插入排序法)。nBubbleSort概念:設原list為a1,an。從a1,a2開始，向後兩兩比較，若aiai+1則交換，當檢查完an時，an必定是最大數。再從a1,a2開始向後比較，若aiai+1則交換，此時只需檢查到an-1即可。依此類推。So

15、rtingAlgorithms(跳過)Ch3-15nExample 4.Usethebubblesorttoput3,2,4,1,5intoincreasingorder.nSol:32415First pass(i=1):234152341523145Second 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:

16、=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-17nInsertionSort的概念:從j=2開始，將aj 插入已排序好的a1,aj-1間的位置，使得a1,aj都由小大排好。j 逐次遞增，重複上一步驟至做完。(跳過)Ch3-18nExample 5.Useinsertionsorttosort3,2,4,1,5nSol:(j=2時，a1=3可看成已經排序好的數列，此時要插入a2):3 2,4 3 4的位置不變 2,3,4,1,5 (

17、j=4時，a1,a2,a3已經排序好，此時要插入a4):1 1,5 2,5 3,5 4 5不變 1,2,3,4,5a1 a2 a3 a4 a5(跳過)Ch3-19Algorithm 5 The Insertion Sortprocedure 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

18、應插入的位置最後ai-1 aj k.(readas“f(x)isbig-ohofg(x)”)我們說函數 f(x)是O(g(x)代表在 x 夠大時，|f(x)|g(x)|的某個常數倍數的某個常數倍數Ch3-22Example 1.Showthatf(x)=x2+2x+1isO(x2)Sol:Sincex2+2x+1 x2+2x2+x2=4x2wheneverx 1,itfollowsthatf(x)isO(x2)(takeC=4andk=1)另法：Ifx 2,weseethatx2+2x+1 x2+x2+x2=3x2(takeC=3andk=2)通常都是把最高次項搬進來通常都是把最高次項搬進來C

19、h3-23Figure 2.The function f(x)is O(g(x)Example 1(補充補充).Showthat f(x)=x2+2x+2 is O(x3)Sol:Sincex2+2x+2 x3+x3+x3=3x3wheneverx 1,weseethatf(x)isO(x3)(takeC=3andk=1)kCg(x)f(x)g(x)f(x)kNote.Thefunctiongischosentobeassmallaspossible.大O符號裡放的函數要越小越好Ch3-24Example 5.Howcanbig-Onotationbeusedtoestimatethesumo

20、fthefirstnpositiveintegers?(i.e.,)Sol:1+2+3+n n+n+n=n2isO(n2),takingC=1andk=1.Theorem 1.Letf(x)=anxn+an-1xn-1+a1x+a0wherea0,a1,anarerealnumbers.Thenf(x)isO(xn).(跳過)Ch3-25Example 6.Givebig-Oestimatesforf(n)=n!Sol:n!=12 3 n n n n=nnn!isO(nn),takingC=1andk=1.Theorem 2,3Supposethatf1(x)isO(g1(x)andf2(x)

21、isO(g2(x),then(f1+f2)(x)isO(max(|g1(x)|,|g2(x)|),(f1 f2)(x)isO(g1(x)g2(x).Example 7.(seeFigure3)常見function的成長速度由小至大排列：1 log n n n log n 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)isO(n3n!)取C=4,k=3(跳過)Ch3-273.3 Complexity of AlgorithmsQ:如何分析演算法的執

22、行效能？Ans:(1)time(2)memoryDef:Time complexity:ananalysisofthetimerequiredtosolveaproblemofaparticularsize.(評量方式:計算運算次數，如“做比較”的次數，“加法”或“乘法”次數等)Space complexity:分析解問題時所需的電腦記憶體容量(通常是資料結構探討的範圍)(複雜度)Ch3-28Example 1.描述Algorithm1(FindMax)的時間複雜度.Algorithm 1.(Find Max)procedure max(a1,an:integers)max:=a1for i:

23、=2 to n if max n.當當 i 變成變成 n+1 時時因比因比 n 大，故結束大，故結束 for 迴圈。迴圈。共有共有 n 次比較次比較共有共有 n-1 次比較次比較故整個演算法共做故整個演算法共做 2n-1 次比較次比較其時間複雜度其時間複雜度 為為 O(n).Ch3-29Example 2.Describethetimecomplexityofthelinearsearchalgorithm.Algorithm 2(Linear Search)procedure ls(x:integer,a1,an:distinct integers)i:=1While(i n and x a

24、i)i:=i+1if i n then location:=i else location:=0 location=i if x=ai;location=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(最糟的情形

25、最糟的情形)故演算法的故演算法的 time complexity為為 O(n)Exercise3.37.對多項式an xn+an-1xn-1+a1x+a0，求出 x=c 時的值，傳統演算法做法如下：Ch3-30procedure 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(1)執行上述演算法的每一步驟，計算3x2+x+1 在 x=

26、2 時的值(2)為求出n階多項式在x=c時的值，所需乘法與加法次數為何？Exercise3.38.對多項式an xn+an-1xn-1+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(1)執行上述演算法的每一步驟，計算3x2+x+1 在 x=2 時的值(2)為求出n階多項式在x=c時的值，所需乘法與加法次數為何？Ch3-32Example 4.Describe t

27、he average-case performance of the 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 的機

28、率的機率)=3 1/n+5 1/n+(2n+1)1/n=(3+5+(2n+1)/n=/n=n+2 average-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 以簡化

29、計算以簡化計算(若若 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

30、 i:=m+1 /*(k次)else j:=mendif 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 inc

31、reasing 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-35nExample 6.What is the worst-case complexity of the insertion sort in terms of the number of comp

32、arisons made?procedure insertion_sort(a1,an)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 1ExponentialcomplexityO(

33、n!)FactorialcomplexityCh3-373.4Theintegersanddivision探討一些NumberTheory的基本觀念Def 1.a,b:integers,a0.a divides b(denotea|b)ifcZ Z,b=ac.a:afactor(因數)ofb,b:amultiple(倍數)ofa(abifadoesnotdivideb)Theorem 1.a,b,c Z Z,(i)Ifa|b and a|cthen a|(b+c).(ii)Ifa|b then a|bcforanyintegerc.(iii)Ifa|b and b|cthen a|c.Coro

34、llary 1.Ifa,b,c Z Zanda|b,a|c.thena|(mb+nc)wheneverm,n Z Z.(除法)Ch3-38Def 2.Intheequalitya=dq+r with 0 r d,discalledthedivisor(除數),aiscalledthedividend(被除數),qiscalledthequotient(商數),andr iscalledtheremainder(餘數).q=adivd,r=amoddExample 3.101div11=?(商數)101mod11=?(餘數)Sol:101=119+2故101div11=9,101mod11=2E

35、xample 4.-11div3=?(商數)-11mod3=?(餘數)Sol:-11=3(-4)+1故-11div3=-4,-11mod3=1Exercise3.410.(b)777div21=777mod21=(c)-123div19=-123mod19Ch3-39Ch3-40Def 3.Ifa,bZ Z,mZ Z+,thenaiscongruent(同餘)tobmodulomifm|(a-b).(表示為a b(mod m),即整數a、b對模m同餘).模算術模算術Thm 3.LetmZ Z+,a,bZ Z.a b(mod m)iff a mod m=b mod m.nExample 5.判斷

36、在模6時，17是否同餘於5?24是否同餘於14?nSol:17 mod 6=5,5 mod 6=5,故17同餘於5n24 mod 6=0,14 mod 6=2,故24不同餘於14Ch3-41Thm 5.LetmZ Z+,a,bZ Z.Ifa b(mod m)and c d(mod m),thena+c b+d(mod m)and ac bd(mod m).Thm 4.LetmZ Z+,a,bZ Z.a b(mod m)iffkZ Z,使得a=b+km.nExample 6.7 2(mod 5),11 1(mod 5),n故18 3(mod 5),n77 2(mod 5).Exercise3.4

37、19.判斷下列何者在模數17 時，與5 同餘。(a)80 (b)103 (c)-29 (d)-122Ch3-42補充：請計算(1717 9+31)mod5=?同餘的應用-密碼學n凱撒大帝的加密法：將訊息中每個字母向後移動三位，最後三個字母則以最前面三個字母取代，如B 換成E，X 換成A。n以數學方式表示：將AZ以025編碼，將編號p 的字母以f(p)取代，其中f(p)=(p+3)mod26。Ch3-43Example 9.根據凱撒大帝的密碼製作方式，下面的訊息會被加密成什麼？“MEETYOUINTHEPARK”Sol.“PHHWBRXLQWKHSDUN”n改進加密法：將AZ以025編碼，將編號

38、p 的字母以f(p)取代，其中f(p)=(ap+b)mod26，所選取的整數 a,b 只要能使 f(p)成為對射函數即可。Ch3-44nExample 10.若使用f(p)=(7p+3)mod26來加密，則將會用哪一個字母來取代 K?nSol.K 的編碼是10，n(710+3)mod 26=21n故用V取代KABCDEFGHIJKLM0123456789101112NOPQRSTUVWXYZ13141516171819202122232425Exercise3.431.利用給定的函數f(p)=(7p+3)mod26，將訊息“PASSTHROUGH”加密，寫出加密的訊息。32.將下列經凱撒密碼加

39、密之訊息解密：“EOXHMHDQV”Ch3-45ABCDEFGHIJKLM0123456789101112NOPQRSTUVWXYZ13141516171819202122232425Ch3-463.5PrimesandGreatestCommonDivisorsDef 1.pZ Z+-1iscalledprime(質數)ifap,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=6 y=0 while y=0,e

40、nd.gcd(6,12)=6Exercise:23,25歐基里得演算法歐基里得演算法Exercise3.623(c).利用歐基里得演算法求出gcd(1001,1331)Ch3-5325.利用歐基里得演算法求gcd(21,34)時，共需用到多少次除法？Ch3-543.7ApplicationsofNumberTheory介紹中國餘數定理介紹中國餘數定理Example 5.孫子算經孫子算經:某物不知其數，三三數之餘二，五五數之餘某物不知其數，三三數之餘二，五五數之餘三，七七數之餘二，問物幾何三，七七數之餘二，問物幾何?i.e.x 2(mod 3)x 3(mod 5)x=?x 2(mod 7)The

41、orem 4.(The Chinese Remainder Theorem)Let m1,m2,mn be pairwise relatively prime positive integers.Thesystem x a1(mod m1)x a2(mod m2):x an(mod mn)has a unique solution modulo m=m1m2mn.(即有一解即有一解 x,where 0 x m,且所有其他解且所有其他解 mod m都等於都等於 x)(跳過)Ch3-55ProofofThm4:LetMk=m/mk1knm1,m2,mnarepairwiserelativelypr

42、imegcd(Mk,mk)=1integeryks.t.Mk yk1(mod mk)(byThm.3,此處不証)ak Mk ykak(mod mk),1 k nLet x=a1M1y1+a2M2y2+anMnyn mi|Mj,ij xak Mk ykak(mod mk)1knx即為一解(跳過)Ch3-56Example 6.(承Example5題目敘述，求解)Let m=357=105 M1=m/3=35 M2=m/5=21 M3=m/7=15 352(mod 3)35 2 1(mod 3)211(mod 5)21 1 1(mod 5)151(mod 7)15 1 1(mod 7)x=a1M1

43、y1+a2M2y2+a3M3y3 =2 35 2+3 21 1+2 15 1=233 23(mod 105)最小的解為23，其餘解都等於 23+105t forsometZ+Exercise:19M1y1M2y2M3y3(跳過)Ch3-57Exercise18.Findallsolutionstothesystemofcongruencesx2 (mod 3)x1 (mod 4)x3 (mod 5)Sol:a1=2,a2=1,a3=3,m1=3,m2=4,m3=5 m=345=60 M1=20,M2=15,M3=12 202(mod 3)2021(mod 3)153(mod 4)1531(mo

44、d 4)122(mod 5)1231(mod 5)x=2202+1153+3123 =80+45+108=23353(mod 60)(跳過)Ch3-583.8MatricesAlgorithm 1.Matrix multiplication procedure matrix_multiplication(A:mk matrix,B:kn matrix)for i:=1 to m for j:=1 to n begin cij:=0 for q:=1 to k cij:=cij+aiqbqj end c=cij=AB Exercise:試寫一試寫一algorithm求求At.Exercise3.8設A=,B=，列出Algorithm1執行A B的步驟。Ch3-59procedure matrix_multip(A:mk matrix,B:kn matrix)for i:=1 to m for j:=1 to n begin cij:=0 for q:=1 to k cij:=cij+aiqbqj end c=cij=AB