Giáo trình Toán rời rạc

pdf

168 trang ngocly 1900

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Toán rời rạc", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_trinh_toan_roi_rac.pdf

Nội dung text: Giáo trình Toán rời rạc

ĐH Huế Giáo trình Toán rời rạc Edited and Published by Tran Thanh Tuan
LI NÓI ĐU Đưc s đng viên m nh m c a các đng nghi p trong các Khoa Toán-Cơ-Tin hc, Công ngh Thông tin và V t lý (Tr ưng Đi h c Khoa h c-Đi h c Hu ), các Khoa Toán và Tin h c (Tr ưng Đi h c S ư ph m-Đi h c Hu ) và đc bi t do nhu c u h c t p ca các sinh viên trong Đi h c Hu các Khoa nói trên và các h c viên cao h c ngành Ph ươ ng pháp gi ng d y Toán, chúng tôi m nh d n vi t giáo trình Toán r i r c trong khi trên th tr ưng sách có khá nhi u tài li u liên quan đn Toán r i r c. Điu mà chúng tôi mong mu n là các ki n th c c a h c ph n này ph i đưc đưa vào đy đ, cô đng, chính xác, c p nh t, bám sát theo yêu c u đào t o sinh viên các ngành Công ngh Thông tin, Toán-Tin, V t lý-Tin và m t s ngành k thu t khác c a các tr ưng đi h c và cao đng. Vi s n l c h t mình c a b n thân, chúng tôi thi t ngh ĩ đây s là tài li u tham kh o t t cho các giáo viên gi ng d y h c ph n toán r i r c, các h c viên cao h c ngành Ph ươ ng pháp gi ng d y Toán, các thí sinh thi vào cao h c ngành công ngh thông tin, các sinh viên thu c các ngành đưc đ c p trên và các h c sinh thu c kh i chuyên Toán, chuyên Tin. Ni dung c a tài li u này đưc b trí trong 4 ph n, không k l i nói đu, m c l c, tài li u tham kh o và ph n ph l c: Ph n 1 đưc dành cho Ch ươ ng I đ c p đn Thu t toán ; Ph n 2 đưc dành cho Ch ươ ng II nói đn bài toán đm; Ph n 3, đây là ph n chi m nhi u trang nh t trong giáo trình, bàn v Lý thuy t đ th và các ng d ng g m 5 ch ươ ng: Đ th , Đ th Euler và đ th Hamilton, M t s bài toán ti ưu trên đ th , Cây, Đ th ph ng và tô màu đ th ; Ph n 4 đưc dành cho Ch ươ ng 8, ch ươ ng cu i cùng, đ c p đn Đi s Boole . Trong m i ch ươ ng, các ch ng minh c a các đnh lý, m nh đ đưc trình bày chi ti t, ngo i tr m t s đnh lý có ph n ch ng minh quá ph c t p thì đưc chúng tôi b qua. Trong các ph n c a m i ch ươ ng có nhi u ví d c th minh ho cho nh ng khái ni m cũng nh ư nh ng k t qu c a chúng. Cu i c a m i ch ươ ng là nh ng bài t p đưc ch n lc t d đn khó, bám theo n i dung c a ch ươ ng đó. Chúng tôi xin chân thành cám ơn các đng nghi p đã đng viên và góp ý cho công vi c vi t giáo trình Toán r i r c này và l i cám ơn đc bi t xin dành cho Khoa Công ngh Thông tin v s giúp đ quý báu và t o điu ki n thu n l i cho vi c xu t b n giáo trình này. Tác gi mong nh n đưc s ch giáo c a các đng nghi p và đc gi v nh ng thi u sót khó tránh kh i c a cu n sách. Mùa Thu năm 2003 1
MC L C Li nói đu 1 Mc l c 2 Ch ươ ng I: Thu t toán 4 1.1. Khái ni m thu t toán 4 1.2. Thu t toán tìm ki m 5 1.3. Đ ph c t p c a thu t toán 7 1.4. S nguyên và thu t toán 12 1.5. Thu t toán đ quy 17 Bài t p Ch ươ ng I 19 Ch ươ ng II: Bài toán đm 22 2.1. C ơ s c a phép đm 22 2.2. Nguyên lý Dirichlet 25 2.3. Ch nh h p và t h p suy r ng 28 2.4. Sinh các hoán v và t h p 30 2.5. H th c truy h i 32 2.6. Quan h chia đ tr 34 Bài t p Ch ươ ng II 35 Ch ươ ng III: Đ th 37 3.1. Đnh ngh ĩa và thí d 37 3.2. B c c a đnh 39 3.3. Nh ng đơn đ th đc bi t 41 3.4. Bi u di n đ th b ng ma tr n và s đng c u đ th 44 3.5. Các đ th m i t đ th c ũ 46 3.6. Tính liên thông 47 Bài t p Ch ươ ng III 51 Ch ươ ng IV: Đ th Euler và Đ th Hamilton 54 4.1. Đưng đi Euler và đ th Euler 54 4.2. Đưng đi Hamilton và đ th Hamilton 58 Bài t p Ch ươ ng IV 64 Ch ươ ng V: M t s bài toán ti ưu trên đ th 67 5.1. Đ th có tr ng s và bài toán đưng đi ng n nh t 67 5.2. Bài toán lu ng c c đi 72 5.3. Bài toán du l ch 79 Bài t p Ch ươ ng V 84 2
Ch ươ ng VI: Cây 87 6.1. Đnh ngh ĩa và các tính ch t c ơ b n 87 6.2. Cây khung và bài toán tìm cây khung nh nh t 88 6.3. Cây có g c 93 6.4. Duy t cây nh phân 94 Bài t p Ch ươ ng VI 101 Ch ươ ng VII: Đ th ph ng và tô màu đ th 104 7.1. Đ th ph ng 104 7.2. Đ th không ph ng 106 7.3. Tô màu đ th 107 Bài t p Ch ươ ng VII 112 Ch ươ ng VIII: Đi s Boole 114 8.1. Khái ni m đi s Boole 114 8.2. Hàm Boole 117 8.3. M ch lôgic 120 8.4. C c ti u hoá các m ch lôgic 125 Bài t p Ch ươ ng VIII 132 Tài li u tham kh o 134 Ph n ph l c 135 Ph l c 1 135 Ph l c 2 158 3
CH ƯƠ NG I: THU T TOÁN 1.1. KHÁI NI M THU T TOÁN. 1.1.1. M đ u: Có nhi u l p bài toán t ng quát xu t hi n trong toán h c r i r c. Ch ng h n, cho mt dãy các s nguyên, tìm s l n nh t; cho m t t p h p, li t kê các t p con c a nó; cho tp h p các s nguyên, x p chúng theo th t tăng d n; cho m t m ng, tìm đưng đi ng n nh t gi a hai đ nh c a nó. Khi đ ưc giao cho m t bài toán nh ư v y thì vi c đ u tiên ph i làm là xây d ng m t mô hình d ch bài toán đó thành ng c nh toán h c. Các cu trúc r i r c đ ưc dùng trong các mô hình này là t p h p, dãy, hàm, hoán v , quan h , cùng v i các c u trúc khác nh ư đ th , cây, m ng - nh ng khái ni m s đ ưc nghiên c u các ch ươ ng sau. Lp đ ưc m t mô hình toán h c thích h p ch là m t ph n c a quá trình gi i. Đ hoàn t t quá trình gi i, còn c n ph i có m t ph ươ ng pháp dùng mô hình đ gi i bài toán tng quát. Nói m t cách lý t ưng, cái đ ưc đòi h i là m t th t c, đó là dãy các b ưc dn t i đáp s mong mu n. M t dãy các b ưc nh ư v y, đ ưc g i là m t thu t toán. Khi thi t k và cài đ t m t ph n m m tin h c cho m t v n đ nào đó, ta c n ph i đưa ra ph ươ ng pháp gi i quy t mà th c ch t đó là thu t toán gi i quy t v n đ này. Rõ ràng r ng, n u không tìm đưc m t ph ươ ng pháp gi i quy t thì không th l p trình đưc. Chính vì th , thut toán là khái ni m n n t ng c a h u h t các l ĩnh v c c a tin hc. 1.1.2. Đ nh ngh ĩa: Thu t toán là m t b ng li t kê các ch d n (hay quy t c) c n th c hi n theo t ng b ưc xác đ nh nh m gi i m t bài toán đ ã cho. Thu t ng “Algorithm” (thu t toán) là xu t phát t tên nhà toán h c R p Al- Khowarizmi. Ban đ u, t algorism đ ưc dùng đ ch các quy t c th c hi n các phép tính s h c trên các s th p phân. Sau đ ó, algorism chuy n thành algorithm vào th k 19. Vi s quan tâm ngày càng t ă ng đ i v i các máy tính, khái ni m thu t toán đ ã đưc cho mt ý ngh ĩa chung h ơn, bao hàm c các th t c xác đ nh đ gi i các bài toán, ch không ph i ch là th t c đ th c hi n các phép tính s h c. Có nhi u cách trình bày thu t toán: dùng ngôn ng t nhiên, ngôn ng l ưu đ (s ơ đ kh i), ngôn ng l p trình. Tuy nhiên, m t khi dùng ngôn ng l p trình thì ch nh ng lnh đ ưc phép trong ngôn ng đ ó m i có th dùng đ ưc và đ i u này th ưng làm cho s mô t các thu t toán tr nên r i r m và khó hi u. H ơn n a, vì nhi u ngôn ng l p trình đu đ ưc dùng r ng rãi, nên ch n m t ngôn ng đ c bi t nào đ ó là đ i u ng ưi ta không mu n. Vì v y đ ây các thu t toán ngoài vi c đ ưc trình bày b ng ngôn ng t nhiên cùng v i nh ng ký hi u toán h c quen thu c còn dùng m t d ng gi mã đ mô t thu t 4
toán. Gi mã t o ra b ưc trung gian gi a s mô t m t thu t toán b ng ngôn ng thông th ưng và s th c hi n thu t toán đ ó trong ngôn ng l p trình. Các b ưc c a thu t toán đưc ch rõ b ng cách dùng các l nh gi ng nh ư trong các ngôn ng l p trình. Thí d 1: Mô t thu t toán tìm ph n t l n nh t trong m t dãy h u h n các s nguyên. a) Dùng ngôn ng t nhiên đ mô t các b ưc c n ph i th c hi n: 1. Đ t giá tr c c đ i t m th i b ng s nguyên đ u tiên trong dãy. (C c đ i t m th i s là s nguyên l n nh t đ ã đưc ki m tra m t giai đ o n nào đ ó c a th t c.) 2. So sánh s nguyên ti p sau v i giá tr c c đ i t m th i, n u nó l n h ơn giá tr cc đ i t m th i thì đt c c đ i t m th i b ng s nguyên đ ó. 3. L p l i b ưc tr ưc n u còn các s nguyên trong dãy. 4. Dng khi không còn s nguyên nào n a trong dãy. C c đ i t m th i đ i m này chính là s nguyên l n nh t c a dãy. b) Dùng đo n gi mã: procedure max (a 1, a 2, , a n: integers) max:= a 1 for i:= 2 to n if max <a i then max:= a i {max là ph n t l n nh t} Thu t toán này tr ưc h t gán s h ng đ u tiên a 1 c a dãy cho bi n max. Vòng l p “for” đ ưc dùng đ ki m tra l n l ưt các s h ng c a dãy. N u m t s h ng l n h ơn giá tr hi n th i c a max thì nó đưc gán làm giá tr m i c a max. 1.1.3. Các đ c tr ưng c a thu t toán: Đu vào (Input) : Mt thu t toán có các giá tr đ u vào t m t t p đ ã đưc ch rõ. Đ u ra (Output) : T m i t p các giá tr đ u vào, thu t toán s t o ra các giá tr đ u ra. Các giá tr đ u ra chính là nghi m c a bài toán. Tính d ng: Sau m t s h u h n b ưc thu t toán ph i d ng. Tính xác đ nh: m i b ưc, các b ưc thao tác ph i h t s c rõ ràng, không gây nên s nh p nh ng. Nói rõ h ơn, trong cùng m t đ i u ki n hai b x lý cùng th c hi n m t b ưc ca thu t toán ph i cho nh ng k t qu nh ư nhau. Tính hi u qu : Tr ưc h t thu t toán c n đ úng đ n, ngh ĩa là sau khi đ ưa d li u vào thu t toán ho t đ ng và đ ưa ra k t qu nh ư ý mu n. Tính ph d ng: Thu t toán có th gi i b t k ỳ m t bài toán nào trong l p các bài toán. C th là thu t toán có th có các đ u vào là các b d li u khác nhau trong m t mi n xác đ nh. 1.2. THU T TOÁN TÌM KI M. 1.2.1. Bài toán tìm ki m: Bài toán xác đ nh v trí c a m t ph n t trong m t b ng li t kê s p th t th ưng g p trong nhi u tr ưng h p khác nhau. Ch ng h n ch ương trình 5
ki m tra chính t c a các t , tìm ki m các t này trong m t cu n t đ i n, mà t đ i n ch ng qua c ũng là m t b ng li t kê s p th t c a các t . Các bài toán thu c lo i này đưc g i là các bài toán tìm ki m. Bài toán tìm ki m t ng quát đ ưc mô t nh ư sau: xác đ nh v trí c a ph n t x trong m t b ng li t kê các ph n t phân bi t a 1, a2, , a n ho c xác đ nh r ng nó không có mt trong b ng li t kê đ ó. L i gi i c a bài toán trên là v trí c a s h ng c a b ng li t kê có giá tr b ng x (t c là i s là nghi m n u x=a i và là 0 n u x không có m t trong b ng li t kê). 1.2.2. Thu t toán tìm ki m tuy n tính: Tìm ki m tuy n tính hay tìm ki m tu n t là bt đ u b ng vi c so sánh x v i a 1; khi x=a 1, nghi m là v trí a 1, t c là 1; khi x ≠a1, so sánh x v i a 2. N u x=a 2, nghi m là v trí c a a 2, t c là 2. Khi x ≠a2, so sánh x v i a 3. Ti p tc quá trình này b ng cách tu n t so sánh x v i m i s h ng c a b ng li t kê cho t i khi tìm đưc s h ng b ng x, khi đ ó nghi m là v trí c a s h ng đ ó. N u toàn b ng li t kê đ ã đưc ki m tra mà không xác đ nh đ ưc v trí c a x, thì nghi m là 0. Gi mã đi vi thu t toán tìm ki m tuy n tính đ ưc cho d ưi đ ây: procedure tìm ki m tuy n tính (x: integer, a 1,a 2, ,an: integers phân bi t) i := 1 while (i ≤ n and x ≠ a i) i := i + 1 if i ≤ n then location := i else location := 0 {location là ch s d ưi c a s h ng b ng x ho c là 0 n u không tìm đưc x} 1.2.3. Thu t toán tìm ki m nh phân: Thu t toán này có th đ ưc dùng khi b ng li t kê có các s h ng đ ưc s p theo th t t ă ng d n. Ch ng h n, n u các s h ng là các s thì chúng đưc s p t s nh nh t đ n s l n nh t ho c n u chúng là các t hay xâu ký t thì chúng đưc s p theo th t t đ i n. Thu t toán th hai này g i là thu t toán tìm ki m nh phân. Nó đ ưc ti n hành b ng cách so sánh ph n t c n xác đ nh v trí v i s hng gi a b ng li t kê. Sau đ ó b ng này đ ưc tách làm hai b ng kê con nh h ơn có kích th ưc nh ư nhau, ho c m t trong hai b ng con ít h ơn b ng con kia m t s h ng. S tìm ki m ti p t c b ng cách h n ch tìm ki m m t b ng kê con thích h p d a trên vi c so sánh ph n t c n xác đ nh v trí v i s h ng gi a b ng kê. Ta s th y r ng thu t toán tìm ki m nh phân hi u qu h ơn nhi u so v i thu t toán tìm ki m tuy n tính. Thí d 2. Đ tìm s 19 trong b ng li t kê 1,2,3,5,6,7,8,10,12,13,15,16,18,19,20,22 ta tách b ng li t kê g m 16 s h ng này thành hai b ng li t kê nh h ơn, m i b ng có 8 s hng, c th là: 1,2,3,5,6,7,8,10 và 12,13,15,16,18,19,20,22. Sau đ ó ta so sánh 19 v i s hng cu i cùng c a b ng con th nh t. Vì 10<19, vi c tìm ki m 19 ch gi i h n trong bng li t kê con th 2 t s h ng th 9 đ n 16 trong b ng li t kê ban đ u. Ti p theo, ta 6
li tách b ng li t kê con g m 8 s h ng này làm hai b ng con, m i b ng có 4 s h ng, c th là 12,13,15,16 và 18,19,20,22. Vì 16 a m, vi c tìm ki m x gi i h n n a th hai c a dãy, g m a m+1 ,a m+2 , ,a n. N u x không l n h ơn a m, thì s tìm ki m gi i h n trong n a đ u c a dãy g m a 1,a 2, ,a m. Bây gi s tìm ki m ch gi i h n trong b ng li t kê có không h ơn [n/2] ph n t . Dùng chính th t c này, so sánh x v i s h ng gi a c a b ng li t kê đ ưc hn ch . Sau đ ó l i h n ch vi c tìm ki m n a th nh t ho c n a th hai c a b ng li t kê. L p l i quá trình này cho t i khi nh n đ ưc m t b ng li t kê ch có m t s h ng. Sau đ ó, ch còn xác đ nh s h ng này có ph i là x hay không. Gi mã cho thu t toán tìm ki m nh phân đưc cho d ưi đ ây: procedure tìm ki m nh phân (x: integer, a 1,a 2, ,an: integers t ă ng d n) i := 1 {i là đ i m mút trái c a kho ng tìm ki m} j := n {j là đ i m mút ph i c a kho ng tìm ki m} while i a m then i:=m+1 else j := m end if x = ai then location := i else location := 0 {location là ch s d ưi c a s h ng b ng x ho c 0 n u không tìm th y x} 1.3. Đ PH C T P C A THU T TOÁN. 1.3.1. Khái ni m v đ ph c t p c a m t thu t toán: Th ưc đ o hi u qu c a m t thu t toán là th i gian mà máy tính s d ng đ gi i bài toán theo thu t toán đ ang xét, khi các giá tr đ u vào có m t kích th ưc xác đ nh. 7
Mt th ưc đ o th hai là dung l ưng b nh đ òi h i đ th c hi n thu t toán khi các giá tr đ u vào có kích th ưc xác đ nh. Các v n đ nh ư th liên quan đ n đ ph c t p tính toán c a m t thu t toán. S phân tích th i gian c n thi t đ gi i m t bài toán có kích th ưc đ c bi t nào đ ó liên quan đ n đ ph c t p th i gian c a thu t toán. S phân tích b nh c n thi t c a máy tính liên quan đ n đ ph c t p không gian ca thu t toán. V c xem xét đ ph c t p th i gian và không gian c a m t thu t toán là m t v n đ r t thi t yu khi các thu t toán đ ưc th c hi n. Bi t m t thu t toán s đ ưa ra đ áp s trong m t micro giây, trong m t phút ho c trong m t t n ă m, hi n nhiên là h t s c quan tr ng. Tươ ng t nh ư v y, dung l ưng b nh đ òi h i ph i là kh d ng đ gi i m t bài toán,vì vy đ ph c t p không gian c ũng c n ph i tính đ n.Vì vi c xem xét đ ph c t p không gian g n li n v i các c u trúc d li u đ c bi t đ ưc dùng đ th c hi n thu t toán nên đ ây ta s t p trung xem xét đ ph c t p th i gian. Đ ph c t p th i gian c a m t thu t toán có th đ ưc bi u di n qua s các phép toán đ ưc dùng b i thu t toán đ ó khi các giá tr đ u vào có m t kích th ưc xác đ nh. S dĩ đ ph c t p th i gian đ ưc mô t thông qua s các phép toán đ òi h i thay vì th i gian th c c a máy tính là b i vì các máy tính khác nhau th c hi n các phép tính s ơ c p trong nh ng kho ng th i gian khác nhau. H ơn n a, phân tích t t c các phép toán thành các phép tính bit s ơ c p mà máy tính s d ng là đ i u r t ph c t p. Thí d 3: Xét thu t toán tìm s l n nh t trong dãy n s a 1, a 2, , a n. Có th coi kích th ưc c a d li u nh p là s l ưng ph n t c a dãy s , t c là n. N u coi m i l n so sánh hai s c a thu t toán đ òi h i m t đ ơn v th i gian (giây ch ng h n) thì th i gian th c hi n thu t toán trong tr ưng h p x u nh t là n-1 giây. V i dãy 64 s , th i gian th c hi n thu t toán nhi u l m là 63 giây. Thí d 4: Thu t toán v trò ch ơi “Tháp Hà N i” Trò ch ơi “Tháp Hà N i” nh ư sau: Có ba c c A, B, C và 64 cái đ ĩa (có l đ đ t vào c c), các đ ĩa có đ ưng kính đ ôi m t khác nhau. Nguyên t c đ t đ ĩa vào c c là: m i đĩa ch đ ưc ch ng lên đ ĩa l n h ơn nó. Ban đ u, c 64 đ ĩa đưc đ t ch ng lên nhau c t A; hai c t B, C tr ng. V n đ là ph i chuy n c 64 đ ĩa đ ó sang c t B hay C, m i l n ch đưc di chuy n m t đ ĩa. Xét trò ch ơi v i n đ ĩa ban đ u c c A (c c B và C tr ng). G i S n là s l n chuy n đ ĩa đ ch ơi xong trò ch ơi v i n đ ĩa. Nu n=1 thì rõ ràng là S 1=1. Nu n>1 thì tr ưc h t ta chuy n n-1 đ ĩa bên trên sang c c B (gi yên đ ĩa th n dưi cùng c a c c A). S l n chuy n n-1 đ ĩa là S n-1. Sau đ ó ta chuy n đ ĩa th n t c c A sang c c C. Cu i cùng, ta chuy n n-1 đ ĩa t c c B sang c c C (s l n chuy n là S n-1). Nh ư v y, s l n chuy n n đ ĩa t A sang C là: 2 n-1 n-2 n Sn=S n-1+1+S n=2S n-1+1=2(2S n-2+1)+1=2 Sn-2+2+1= =2 S1+2 + +2+1=2 −1. 8
Thu t toán v trò ch ơi “Tháp Hà N i” đ òi h i 2 64 −1 l n chuy n đ ĩa (x p x 18,4 t t l n). N u m i l n chuy n đ ĩa m t 1 giây thì th i gian th c hi n thu t toán x p x 585 t n ă m! Hai thí d trên cho th y r ng: m t thu t toán ph i k t thúc sau m t s h u h n bưc, nh ưng n u s h u h n này quá l n thì thu t toán không th th c hi n đ ưc trong th c t . Ta nói: thu t toán trong Thí d 3 có đ ph c t p là n-1 và là m t thu t toán h u hi u (hay thu t toán nhanh); thu t toán trong Thí d 4 có đ ph c t p là 2 n−1 và đ ó là mt thu t toán không h u hi u (hay thu t toán ch m). 1.3.2. So sánh đ ph c t p c a các thu t toán: Mt bài toán th ưng có nhi u cách gi i, có nhi u thu t toán đ gi i, các thu t toán đ ó có đ ph c t p khác nhau. n n-1 Xét bài toán: Tính giá tr c a đ a th c P(x)=a nx +a n-1x + +a 1x+a 0 t i x 0. Thu t toán 1: Procedure tính giá tr c a đ a th c (a 0, a 1, , a n, x 0: các s th c) sum:=a 0 for i:=1 to n i sum:=sum+a ix0 {sum là giá tr c a đ a th c P(x) t i x 0} Chú ý r ng đ a th c P(x) có th vi t d ưi d ng: P(x)=( ((a nx+a n-1)x+a n-2)x )x+a 0. Ta có th tính P(x) theo thu t toán sau: Thu t toán 2: Procedure tính giá tr c a đ a th c (a 0, a 1, , a n, x 0: các s th c) P:=a n for i:=1 to n P:=P.x 0+a n-i {P là giá tr c a đ a th c P(x) t i x 0} Ta hãy xét đ ph c t p c a hai thu t toán trên. Đi v i thu t toán 1: b ưc 2, ph i th c hi n 1 phép nhân và 1 phép c ng v i i=1; 2 phép nhân và 1 phép c ng v i i=2, , n phép nhân và 1 phép c ng v i i=n. V y s phép tính (nhân và c ng) mà thu t toán 1 đ òi h i là: n(n + )1 n(n + )3 (1+1)+(2+1)+ +(n+1)= +n= . 2 2 Đi v i thu t toán 2, b ưc 2 ph i th c hi n n l n, m i l n đ òi h i 2 phép tính (nhân r i c ng), do đ ó s phép tính (nhân và c ng) mà thu t toán 2 đ òi h i là 2n. 9
Nu coi th i gian th c hi n m i phép tính nhân và c ng là nh ư nhau và là m t đơn v th i gian thì v i m i n cho tr ưc, th i gian th c hi n thu t toán 1 là n(n+3)/2, còn th i gian th c hi n thu t toán 2 là 2n. Rõ ràng là th i gian th c hi n thu t toán 2 ít h ơn so v i th i gian th c hi n thu t toán 1. Hàm f 1(n)=2n là hàm b c nh t, t ă ng ch m h ơn nhi u so v i hàm b c hai f2(n)=n(n+3)/2. Ta nói r ng thu t toán 2 (có đ ph c t p là 2n) là thu t toán h u hi u h ơn (hay nhanh h ơn) so v i thu t toán 1 (có đ ph c t p là n(n+3)/2). Đ so sánh đ ph c t p c a các thu t toán, đ i u ti n l i là coi đ ph c t p c a mi thu t toán nh ư là c p c a hàm bi u hi n th i gian th c hi n thu t toán y. Các hàm xét sau đ ây đ u là hàm c a bi n s t nhiên n>0. Đnh ngh ĩa 1: Ta nói hàm f(n) có c p th p h ơn hay b ng hàm g(n) n u t n t i h ng s C>0 và m t s t nhiên n 0 sao cho |f(n)| ≤ C|g(n)| v i m i n ≥n0. Ta vi t f(n)=O(g(n)) và còn nói f(n) tho mãn quan h big-O đ i v i g(n). Theo đ nh ngh ĩa này, hàm g(n) là m t hàm đ ơn gi n nh t có th đ ưc, đ i di n cho “s bi n thiên” c a f(n). Khái ni m big-O đ ã đưc dùng trong toán h c đ ã g n mt th k nay. Trong tin hc, nó đ ưc s d ng r ng rãi đ phân tích các thu t toán. Nhà toán h c ng ưi Đ c Paul Bachmann là ng ưi đ u tiên đ ưa ra khái ni m big-O vào n ă m 1892. n(n + )3 Thí d 5: Hàm f(n)= là hàm b c hai và hàm b c hai đ ơn gi n nh t là n 2. Ta có: 2 n(n + )3 2 n(n + )3 2 f(n)= =O(n ) vì ≤ n v i m i n ≥3 (C=1, n 0=3). 2 2 k k-1 k Mt cách t ng quát, n u f(n)=a kn +a k-1n + +a 1n+a 0 thì f(n)=O(n ). Th t v y, vi n>1, k k-1 k k-1 k |f(n)|| ≤ |a k|n +|a k-1|n + +|a 1|n+|a 0| = n (|ak|+|a k-1|/n+ +|a 1|/n +a 0/n ) k ≤ n (|a k|+|a k-1|+ +|a 1|+a 0). Đ i u này ch ng t |f(n)| ≤ Cn k v i m i n>1. Cho g(n)=3n+5nlog 2n, ta có g(n)=O(nlog 2n). Th t v y, 3n+5nlog 2n = n(3+5log 2n) ≤ n(log 2n+5log 2n) = 6nlog 2n v i m i n ≥8 (C=6, n 0=8). Mnh đ : Cho f 1(n)=O(g 1(n)) và f 2(n) là O(g 2(n)). Khi đ ó (f 1 + f 2)(n) = O(max(|g 1(n)|,|g 2(n)|), (f 1f2)(n) = O(g 1(n)g 2(n)). Ch ng minh. Theo gi thi t, t n t i C 1, C 2, n 1, n 2 sao cho |f 1(n)| ≤ C 1|g 1(n)| và |f 2(n)| ≤ C 2|g 2(n)| v i m i n > n 1 và m i n > n 2. Do đ ó |(f 1 + f 2)(n)| = |f 1(n) + f 2(n)| ≤ |f 1(n)| + |f 2(n)| ≤ C 1|g 1(n)| + C 2|g 2(n)| ≤ (C 1+C 2)g(n) vi m i n > n 0=max(n 1,n 2), đ âyC=C 1+C 2 và g(n)=max(|g 1(n)| , |g 2(n)|). |(f 1f2)(n)| = |f 1(n)||f 2(n)| ≤ C 1|g 1(n)|C 2|g 2(n)| ≤ C 1C2|(g 1g2)(n)| v i mi n > n 0=max(n 1,n 2). 10
Đnh ngh ĩa 2: Nu m t thu t toán có đ ph c t p là f(n) v i f(n)=O(g(n)) thì ta c ũng nói thu t toán có đ ph c t p O(g(n)). Nu có hai thu t toán gi i cùng m t bài toán, thu t toán 1 có đ ph c t p O(g 1(n)), thu t toán 2 có đ ph c tp O(g 2(n)), mà g 1(n) có c p th p h ơn g 2(n), thì ta nói rng thu t toán 1 h u hi u h ơn (hay nhanh h ơn) thu t toán 2. 1.3.3. Đánh giá đ ph c t p c a m t thu t toán: 1) Thu t toán tìm ki m tuy n tính: S các phép so sánh đ ưc dùng trong thu t toán này c ũng s đ ưc xem nh ư th ưc đ o đ ph c t p th i gian c a nó. m i m t b ưc c a vòng l p trong thu t toán, có hai phép so sánh đ ưc th c hi n: m t đ xem đ ã t i cu i b ng ch ưa và m t đ so sánh ph n t x v i m t s h ng c a b ng. Cu i cùng còn m t phép so sánh na làm ngoài vòng lp. Do đ ó, n u x=a i, thì đã có 2i+1 phép so sánh đưc s d ng. S phép so sánh nhi u nh t, 2n+2, đ òi h i ph i đ ưc s d ng khi ph n t x không có m t trong b ng. T đ ó, thu t toán tìm ki m tuy n tính có đ ph c t p là O(n). 2) Thu t toán tìm ki m nh phân: k Đ đ ơn gi n, ta gi s r ng có n=2 ph n t trong b ng li t kê a 1,a 2, ,a n, v i k là s nguyên không âm (n u n không ph i là l ũy th a c a 2, ta có th xem b ng là m t ph n c a b ng g m 2 k+1 ph n t , trong đ ó k là s nguyên nh nh t sao cho n < 2 k+1 ). m i giai đ o n c a thu t toán v trí c a s h ng đ u tiên i và s h ng cu i cùng j ca b ng con h n ch tìm ki m giai đ o n đ ó đ ưc so sánh đ xem b ng con này còn nhi u h ơn m t ph n t hay không. N u i < j, m t phép so sánh s đ ưc làm đ xác đ nh x có l n h ơn s h ng gi a c a b ng con h n ch hay không. Nh ư v y m i giai đ o n, có s d ng hai phép so sánh. Khi trong b ng ch còn m t ph n t , m t phép so sánh s cho chúng ta bi t r ng không còn m t ph n t nào thêm n a và m t phép so sánh n a cho bi t s h ng đ ó có ph i là x hay không. Tóm l i c n ph i có nhi u nh t 2k+2=2log 2n+ 2 phép so sánh đ th c hi n phép tìm ki m nh phân (n u n không ph i là k+1 lũy th a c a 2, b ng g c s đ ưc m r ng t i b ng có 2 ph n t , v i k=[log 2n] và s tìm ki m đ òi h i ph i th c hi n nhi u nh t 2[log 2n]+2 phép so sánh). Do đ ó thu t toán tìm ki m nh phân có đ ph c t p là O(log 2n). T s phân tích trên suy ra r ng thu t toán tìm ki m nh phân, ngay c trong tr ưng h p x u nh t, c ũng hi u qu h ơn thu t toán tìm ki m tuy n tính. 3) Chú ý: M t đ i u quan tr ng c n ph i bi t là máy tính ph i c n bao lâu đ gi i xong mt bài toán. Thí d , n u m t thu t toán đ òi h i 10 gi , thì có th còn đ áng chi phí th i gian máy tính đ òi h i đ gi i bài toán đ ó. Nh ưng n u m t thu t toán đ òi h i 10 t n ă m đ gi i m t bài toán, thì th c hi n thu t toán đ ó s là m t đ i u phi lý. M t trong nh ng hi n tưng lý thú nh t c a công ngh hi n đ i là s t ă ng ghê g m c a t c đ và l ưng b nh trong máy tính. M t nhân t quan trng khác làm gi m th i gian c n thi t đ gi i m t 11
bài toán là s x lý song song - đ ây là k thu t th c hi n đ ng th i các dãy phép tính. Do s t ă ng t c đ tính toán và dung l ưng b nh c a máy tính, c ũng nh ư nh vi c dùng các thu t toán l i d ng đ ưc ưu th c a k thu t x lý song song, các bài toán vài n ă m tr ưc đ ây đ ưc xem là không th gi i đ ưc, thì bây gi có th gi i bình th ưng. 1. Các thu t ng th ưng dùng cho đ ph c t p c a m t thu t toán: Đ ph c t p Thu t ng O(1) Đ ph c t p h ng s O(logn) Đ ph c t p lôgarit O( n) Đ ph c t p tuy n tính O( nlogn ) Đ ph c t p nlogn O(n b) Đ ph c t p đ a th c O(b n) (b>1) Đ ph c t p hàm m ũ O(n!) Đ ph c t p giai th a 2. Th i gian máy tính đ ưc dùng b i m t thu t toán: Kích th ưc Các phép tính bit đ ưc s d ng ca bài toán n logn N nlogn n2 2n n! 10 3.10 -9 s 10 -8 s 3.10 -8 s 10 -7 s 10 -6 s 3.10 -3 s 10 2 7.10 -9 s 10 -7 s 7.10 -7 s 10 -5 s 4.10 13 n ă m * 10 3 1,0.10 -8 s 10 -6 s 1.10 -5 s 10 -3 s * * 10 4 1,3.10 -8 s 10 -5 s 1.10 -4 s 10 -1 s * * 10 5 1,7.10 -8 s 10 -4 s 2.10 -3 s 10 s * * 10 6 2.10 -8 s 10 -3 s 2.10 -2 s 17 phút * * 1.4. S NGUYÊN VÀ THU T TOÁN. 1.4.1. Thu t toán Euclide: Ph ươ ng pháp tính ưc chung l n nh t c a hai s b ng cách dùng phân tích các s nguyên đ ó ra th a s nguyên t là không hi u qu . Lý do là ch th i gian ph i tiêu t n cho s phân tích đ ó. D ưi đ ây là ph ươ ng pháp hi u qu h ơn đ tìm ưc s chung l n nh t, g i là thu t toán Euclide . Thu t toán này đ ã bi t t th i c đ i. Nó mang tên nhà toán h c c Hy l p Euclide, ng ưi đ ã mô t thu t toán này trong cu n sách “ Nh ng y u t” n i ti ng c a ông. Thu t toán Euclide d a vào 2 m nh đ sau đ ây. Mnh đ 1 (Thu t toán chia): Cho a và b là hai s nguyên và b ≠0. Khi đ ó t n t i duy nh t hai s nguyên q và r sao cho a = bq+r, 0 ≤ r < |b|. Trong đ ng th c trên, b đ ưc g i là s chia, a đ ưc g i là s b chia, q đ ưc g i là th ươ ng s và r đ ưc g i là s d ư. 12
Khi b là nguyên d ươ ng, ta ký hi u s d ư r trong phép chia a cho b là a mod b. Mnh đ 2: Cho a = bq + r, trong đ ó a, b, q, r là các s nguyên. Khi đ ó UCLN(a,b) = UCLN(b,r). ( đ ây UCLN(a,b) đ ch ưc chung l n nh t c a a và b.) Gi s a và b là hai s nguyên d ươ ng v i a ≥ b. Đ t r 0 = a và r 1 = b. B ng cách áp dng liên ti p thu t toán chia, ta tìm đưc: r0 = r 1q1 + r 2 0 ≤ r 2 r 1 > r 2 > ≥ 0 không th ch a quá a s h ng đ ưc. H ơn n a, t M nh đ 2 trên ta suy ra: UCLN(a,b) = UCLN(r 0,r 1) = UCLN(r 1,r 2) = = UCLN(r n-2, r n-1) = UCLN(r n-1,r n) = r n. Do đ ó, ưc chung l n nh t là s d ư khác không cu i cùng trong dãy các phép chia. Thí d 6: Dùng thu t toán Euclide tìm UCLN(414, 662). 662 = 441.1 + 248 414 = 248.1 + 166 248 = 166.1+ 82 166 = 82.2 + 2 82 = 2.41. Do đ ó, UCLN(414, 662) = 2. Thu t toán Euclide đ ưc vi t d ưi d ng gi mã nh ư sau: procedure ƯCLN (a,b: positive integers) x := a y := b while y ≠ 0 begin r := x mod y x := y y := r end {UCLN (a,b) là x} Trong thu t toán trên, các giá tr ban đ u c a x và y t ươ ng ng là a và b. m i giai đ o n c a th t c, x đ ưc thay b ng y và y đ ưc thay b ng x mod y. Quá trình này đưc lp l i ch ng nào y ≠ 0. Thu t toán s ng ng khi y = 0 và giá tr c a x đ i m này, đ ó là s d ư khác không cu i cùng trong th t c, c ũng chính là ưc chung l n nh t c a a và b. 13
1.4.2. Bi u di n các s nguyên: Mnh đ 3: Cho b là m t s nguyên d ươ ng l n h ơn 1. Khi đ ó n u n là m t s nguyên dươ ng, nó có th đ ưc bi u di n m t cách duy nh t d ưi d ng: k k-1 n = a kb + a k-1b + + a 1b + a 0. đ ây k là m t s t nhiên, a 0, a 1, , a k là các s t nhiên nh h ơn b và a k ≠ 0. Bi u di n c a n đ ưc cho trong M nh đ 3 đ ưc g i là khai tri n c a n theo c ơ s b, ký hi u là (a kak-1 a 1a0)b. Bây gi ta s mô t thu t toán xây d ng khai tri n c ơ s b ca s nguyên n b t k ỳ. Tr ưc h t ta chia n cho b đ đ ưc th ươ ng và s d ư, t c là n = bq 0 + a 0, 0 ≤ a 0 < b. S d ư a 0 chính là ch s đ ng bên ph i cùng trong khai tri n c ơ s b c a n. Ti p theo chia q 0 cho b, ta đ ưc: q0 = bq 1 + a 1, 0 ≤ a 1 < b. S d ư a 1 chính là ch s th hai tính t bên ph i trong khai tri n c ơ s b c a n. Ti p t c quá trình này, b ng cách liên ti p chia các th ươ ng cho b ta s đ ưc các ch s ti p theo trong khai tri n c ơ s b c a n là các s d ư t ươ ng ng. Quá trình này s k t thúc khi ta nh n đ ưc m t th ươ ng b ng 0. Thí d 7: Tìm khai tri n c ơ s 8 c a (12345) 10 . 12345 = 8.1543 + 1 1543 = 8.192 + 7 192 = 8.24 + 0 24 = 8.3 + 0 3 = 8.0 + 3. Do đ ó, (12345) 10 = (30071) 8. Đ o n gi mã sau bi u di n thu t toán tìm khai tri n c ơ s b c a s nguyên n. procedure khai tri n theo c ơ s b (n: positive integer) q := n k := 0 while q ≠ 0 begin ak := q mod b q q := [ ] b k := k + 1 end 1.4.3. Thu t toán cho các phép tính s nguyên: Các thu t toán th c hi n các phép tính v i nh ng s nguyên khi dùng các khai tri n nh phân c a chúng là c c k ỳ quan tr ng trong s h c c a máy tính. Ta s mô t 14
đ ây các thu t toán c ng và nhân hai s nguyên trong bi u di n nh phân. Ta c ũng s phân tích đ ph c t p tính toán c a các thu t toán này thông qua s các phép toán bit th c s đ ưc dùng. Gi s khai tri n nh phân c a hai s nguyên d ươ ng a và b là: a = (a n-1an-2 a 1 a0)2 và b = (b n-1 b n-2 b 1 b 0)2 sao cho a và b đ u có n bit ( đ t các bit 0 đ u m i khai tri n đ ó, n u c n). 1) Phép c ng: Xét bài toán c ng hai s nguyên vi t d ng nh phân. Th t c th c hi n phép c ng có th d a trên ph ươ ng pháp thông th ưng là c ng c p ch s nh phân v i nhau (có nh ) đ tính t ng c a hai s nguyên. Đ c ng a và b, tr ưc h t c ng hai bit ph i cùng c a chúng, t c là: a0 + b 0 = c 0.2 + s 0. đ ây s 0 là bit ph i cùng trong khai tri n nh phân c a a+b, c 0 là s nh , nó có th b ng 0 ho c 1. Sau đ ó ta c ng hai bit ti p theo và s nh a1 + b 1 + c 0 = c 1.2 + s 1. đ ây s 1 là bit ti p theo (tính t bên ph i) trong khai tri n nh phân c a a+b và c 1 là s nh . Ti p t c quá trình này b ng cách c ng các bit t ươ ng ng trong hai khai tri n nh phân và s nh đ xác đ nh bit ti p sau tính t bên ph i trong khai tri n nh phân c a tng a+b. giai đ o n cu i cùng, c ng a n-1, b n-1 và c n-2 đ nh n đ ưc c n-1.2+s n-1. Bit đ ng đu c a t ng là s n=c n-1. K t qu , th t c này t o ra đ ưc khai tri n nh phân c a t ng, c th là a+b = (s n s n-1 s n-2 s 1 s 0)2. Thí d 8: Tìm t ng c a a = (11011) 2 và b = (10110) 2. a0 + b 0 = 1 + 0 = 0.2 + 1 (c 0 = 0, s 0 = 1), a 1 + b 1 + c 0 = 1 + 1 + 0 = 1.2 + 0 (c 1 = 1, s1 = 0), a 2 + b 2 +c 1 = 0 + 1 + 1 = 1.2 + 0 (c 2 = 1, s 2 = 0), a 3 + b 3 + c 2 = 1 + 0 + 1 = 1.2 + 0 (c 3 = 1, s 3 = 0), a 4 + b 4 +c 3 = 1 + 1 + 1 = 1.2 + 1 (s 5 = c 4 =1, s 4 = 1). Do đ ó, a + b = (110001) 2. Thu t toán c ng có th đ ưc mô t b ng cách dùng đ o n gi mã nh ư sau. procedure cng (a,b: positive integers) c := 0 for j := 0 to n-1 begin + + a j bj c d :=    2  sj := a j + b j + c − 2d c := d end sn := c {khai tri n nh phân c a t ng là (s n s n-1 s 1 s0) 2 } 15
Tng hai s nguyên đ ưc tính b ng cách c ng liên ti p các c p bit và khi c n ph i c ng c s nh n a. C ng m t c p bit và s nh đ òi ba ho c ít h ơn phép c ng các bit. Nh ư v y, t ng s các phép c ng bit đ ưc s d ng nh h ơn ba l n s bit trong khai tri n nh phân. Do đ ó, đ ph c t p c a thu t toán này là O(n). 2) Phép nhân: Xét bài toán nhân hai s nguyên vi t d ng nh phân. Thu t toán thông th ưng ti n hành nh ư sau. Dùng lu t phân ph i, ta có: n−1 n−1 j j ab = a ∑b j 2 = ∑ a(b j 2 ). j=0 j=0 Ta có th tính ab b ng cách dùng ph ươ ng trình trên. Tr ưc h t, ta th y r ng ab j=a n u bj=1 và ab j=0 n u b j=0. M i l n ta nhân m t s h ng v i 2 là ta d ch khai tri n nh phân ca nó m t ch v phía trái b ng cách thêm m t s không vào cu i khai tri n nh phân j ca nó. Do đ ó, ta có th nh n đ ưc (ab j)2 b ng cách d ch khai tri n nh phân c a ab j đ i j ch v phía trái, t c là thêm j s không vào cu i khai tri n nh phân c a nó. Cu i cùng, j ta s nh n đ ưc tích ab b ng cách c ng n s nguyên ab j.2 v i j=0, 1, , n-1. Thí d 9: Tìm tích c a a = (110) 2 và b = (101) 2. 0 0 1 1 2 Ta có ab 0.2 = (110) 2.1.2 = (110) 2, ab 1.2 = (110) 2.0.2 = (0000) 2, ab 2.2 = 2 (110) 2.1.2 = (11000) 2. Đ tìm tích, hãy c ng (110) 2, (0000) 2 và (11000) 2. T đ ó ta có ab= (11110) 2. Th t c trên đ ưc mô t b ng đ o n gi mã sau: procedure nhân (a,b: positive integers) for j := 0 to n-1 begin if b j = 1 then cj := a đ ưc d ch đ i j ch else c j := 0 end {c 0, c 1, , c n-1 là các tích riêng ph n} p := 0 for j := 0 to n-1 p := p + c j {p là giá tr c a tích ab} Thu t toán trên tính tích c a hai s nguyên a và b b ng cách c ng các tích riêng ph n c 0, c 1, c 2, , c n-1. Khi b j=1, ta tính tích riêng ph n c j b ng cách d ch khai tri n nh phân c a a đ i j bit. Khi b j=0 thì không c n có d ch chuy n nào vì c j=0. Do đ ó, đ tìm t t j c n s nguyên ab j.2 v i j=0, 1, , n-1, đ òi h i t i đ a là n(n − )1 0 + 1 + 2 + + n −1 = 2 phép d ch ch . Vì v y, s các d ch chuy n ch đ òi h i là O(n 2). 16
Đ c ng các s nguyên ab j t j=0 đ n n −1, đ òi h i ph i c ng m t s nguyên n bit, mt s nguyên n+1 bit, và m t s nguyên 2n bit. Ta đ ã bi t r ng m i phép c ng đ ó đòi h i O(n) phép c ng bit. Do đ ó, đ ph c t p c a thu t toán này là O(n 2). 1.5. THU T TOÁN Đ QUY. 1.5.1. Khái ni m đ quy: Đ ôi khi chúng ta có th quy vi c gi i bài toán v i t p các d li u đ u vào xác đnh v vi c gi i cùng bài toán đ ó nh ưng v i các giá tr đ u vào nh h ơn. Ch ng h n, bài toán tìm UCLN c a hai s a, b v i a > b có th rút g n v bài toán tìm ƯCLN c a hai s nh h ơn, a mod b và b. Khi vi c rút g n nh ư v y th c hi n đ ưc thì l i gi i bài toán ban đu có th tìm đưc b ng m t dãy các phép rút g n cho t i nh ng tr ưng h p mà ta có th d dàng nh n đ ưc l i gi i c a bài toán. Ta s th y r ng các thu t toán rút g n liên ti p bài toán ban đ u t i bài toán có d li u đ u vào nh h ơn, đ ưc áp d ng trong m t lp r t r ng các bài toán. Đnh ngh ĩa: Mt thu t toán đ ưc g i là đ quy n u nó gi i bài toán b ng cách rút g n liên ti p bài toán ban đ u t i bài toán c ũng nh ư v y nh ưng có d li u đ u vào nh h ơn. Thí d 10: Tìm thu t toán đ quy tính giá tr a n v i a là s th c khác không và n là s nguyên không âm. Ta xây d ng thu t toán đ quy nh đ nh ngh ĩa đ quy c a a n, đ ó là a n+1 =a.a n v i n>0 và khi n=0 thì a 0=1. V y đ tính a n ta quy v các tr ưng h p có s m ũ n nh h ơn, cho t i khi n=0. procedure power (a: s th c khác không; n: s nguyên không âm) if n = 0 then power(a,n) := 1 else power(a,n) := a * power(a,n-1) Thí d 11: Tìm thu t toán đ quy tính UCLN c a hai s nguyên a,b không âm và a > b. procedure UCLN (a,b: các s nguyên không âm, a > b) if b = 0 then UCLN (a,b) := a else UCLN (a,b) := UCLN (a mod b, b) Thí d 12: Hãy bi u di n thu t toán tìm ki m tuy n tính nh ư m t th t c đ quy. Đ tìm x trong dãy tìm ki m a 1,a 2, ,a n trong b ưc th i c a thu t toán ta so sánh x v i a i. N u x b ng a i thì i là v trí c n tìm, ng ưc l i thì vi c tìm ki m đ ưc quy v dãy có s ph n t ít h ơn, c th là dãy a i+1 , ,a n. Thu t toán tìm ki m có d ng th t c đ quy nh ư sau. Cho search (i,j,x) là th t c tìm s x trong dãy a i, a i+1 , , a j. D li u đ u vào là b ba (1,n,x). Th t c s d ng khi s h ng đ u tiên c a dãy còn l i là x ho c là khi dãy còn li ch có m t ph n t khác x. N u x không là s h ng đ u tiên và còn có các s h ng khác thì l i áp d ng th t c này, nh ưng dãy tìm ki m ít h ơn m t ph n t nh n đ ưc b ng cách xóa đ i ph n t đ u tiên c a dãy tìm ki m b ưc v a qua. 17
procedure search (i,j,x) if ai = x then loacation := i else if i = j then loacation := 0 else search (i+1,j,x) Thí d 13: Hãy xây d ng phiên b n đ quy c a thu t toán tìm ki m nh phân. Gi s ta mu n đ nh v x trong dãy a 1, a 2, , a n b ng tìm ki m nh phân. Tr ưc tiên ta so sánh x v i s h ng gi a a [(n+1)/2] . N u chúng b ng nhau thì thu t toán k t thúc, nu không ta chuy n sang tìm ki m trong dãy ng n h ơn, n a đ u c a dãy n u x nh h ơn giá tr gi a c a c a dãy xu t phát, n a sau nu ng ưc l i. Nh ư v y ta rút g n vi c gi i bài toán tìm ki m v vi c gi i c ũng bài toán đ ó nh ưng trong dãy tìm ki m có đ dài l n lưt gi m đ i m t n a. procedure binary search (x,i,j) m := [(i+j)/2] if x = a m then loacation := m else if (x a m and j > m) then binary search (x,m+1,j) else loacation := 0 1.5.2. Đ quy và l p: Thí d 14. Th t c đ quy sau đ ây cho ta giá tr c a n! v i n là s nguyên d ươ ng. procedure factorial (n: positive integer) if n = 1 then factorial(n) := 1 else factorial(n) := n * factorial(n-1) Có cách khác tính hàm giai th a c a m t s nguyên t đ nh ngh ĩa đ quy c a nó. Thay cho vi c l n l ưt rút g n vi c tính toán cho các giá tr nh h ơn, ta có th xu t phát t giá tr c a hàm t i 1và l n l ưt áp d ng đ nh ngh ĩa đ quy đ tìm giá tr c a hàm t i các s nguyên l n d n. Đ ó là th t c l p. procedure iterative factorial (n: positive integer) x := 1 for i := 1 to n x := i * x {x là n!} Thông th ưng đ tính m t dãy các giá tr đ ưc đ nh ngh ĩa b ng đ quy, n u dùng ph ươ ng pháp l p thì s các phép tính s ít h ơn là dùng thu t toán đ quy (tr khi dùng các máy đ quy chuyên d ng). Ta s xem xét bài toán tính s h ng th n c a dãy Fibonacci. procedure fibonacci (n: nguyên không âm) 18
if n = 0 the fibonacci (n) := 0 else if n = 1 then fibonacci (n) := 1 else fibonacci (n) := fibonacci (n - 1) + fibonacci (n - 2) Theo thu t toán này, đ tìm f n ta bi u di n f n = f n-1 + f n-2. Sau đ ó thay th c hai s này b ng t ng c a hai s Fibonacci b c th p h ơn, c ti p t c nh ư v y cho t i khi f 0 và f 1 xu t hi n thì đưc thay b ng các giá tr c a chúng theo đ nh ngh ĩa. Do đ ó đ tính f n c n fn+1 -1 phép c ng. Bây gi ta s tính các phép toán c n dùng đ tính f n khi s d ng ph ươ ng pháp lp. Th t c này khi t o x là f 0 = 0 và y là f 1 = 1. Khi vòng l p đ ưc duy t qua t ng c a x và y đ ưc gán cho bi n ph z. Sau đ ó x đ ưc gán giá tr c a y và y đ ưc gán giá tr ca z. V y sau khi đ i qua vòng l p l n 1, ta có x = f 1 và y = f 0 + f 1 = f 2. Khi qua vòng l p ln n-1 thì x = f n-1. Nh ư v y ch có n – 1 phép c ng đ ưc dùng đ tìm f n khi n > 1. procedure Iterative fibonacci (n: nguyên không âm) if n = 0 then y := 0 else begin x := 0 ; y := 1 for i := 1 to n - 1 begin z := x + y x := y ; y := z end end {y là s Fibonacci th n} Ta đ ã ch ra r ng s các phép toán dùng trong thu t toán đ quy nhi u h ơn khi dùng ph ươ ng pháp l p. Tuy nhiên đ ôi khi ng ưi ta v n thích dùng th t c đ quy h ơn ngay c khi nó t ra kém hi u qu so v i th t c l p. Đ c bi t, có nh ng bài toán ch có th gi i b ng th t c đ quy mà không th gi i b ng th t c l p. BÀI T P CH ƯƠ NG I: 1. Tìm m t s nguyên n nh nh t sao cho f(x) là O(x n) đ i v i các hàm f(x) sau: a) f(x) = 2x 3 + x 2log x. b) f(x) = 2x 3 + (log x) 4. x4 + x2 +1 c) f(x) = x3 +1 19
x5 + 5log x d) f(x) = . x4 +1 2. Ch ng minh r ng a) x2 + 4x + 7 là O(x 3), nh ưng x 3 không là O(x 2 +4x + 17). b) xlog x là O(x 2), nh ưng x 2 không là O(xlog x). 3. Cho m t đ ánh giá big-O đ i v i các hàm cho d ưi đ ây. Đ i v i hàm g(x) trong đ ánh giá f(x) là O(g(x)), hãy ch n hàm đ ơn gi n có b c th p nh t. a) nlog(n 2 + 1) + n 2logn. b) (nlogn + 1) 2 + (logn + 1)(n 2 + 1). n 2 c) n2 + nn . 4. Cho H n là s đ i u hoà th n: 1 1 1 Hn = 1 + + + + 2 3 n Ch ng minh r ng H n là O(logn). 5. L p m t thu t toán tính t ng t t c các s nguyên trong m t b ng. 6. L p thu t toán tính x n v i x là m t s th c và n là m t s nguyên. 7. Mô t thu t toán chèn m t s nguyên x vào v trí thích h p trong dãy các s nguyên a1, a 2, , a n x p theo th t t ă ng d n. 8. Tìm thu t toán xác đ nh v trí g p đ u tiên c a ph n t l n nh t trong b ng li t kê các s nguyên, trong đ ó các s này không nh t thi t ph i khác nhau. 9. Tìm thu t toán xác đ nh v trí g p cu i cùng c a ph n t nh nh t trong b ng li t kê các s nguyên, trong đ ó các s này không nh t thi t ph i khác nhau. 10. Mô t thu t toán đ m s các s 1 trong m t xâu bit b ng cách ki m tra m i bit c a xâu đ xác đ nh nó có là bit 1 hay không. 11. Thu t toán tìm ki m tam phân . Xác đ nh v trí c a m t ph n t trong m t b ng li t kê các s nguyên theo th t t ă ng d n b ng cách tách liên ti p b ng li t kê đ ó thành ba bng li t kê con có kích th ưc b ng nhau (ho c g n b ng nhau nh t có th đ ưc) và gi i hn vi c tìm ki m trong m t b ng li t kê con thích h p. Hãy ch rõ các b ưc c a thu t toán đ ó. 12. L p thu t toán tìm trong m t dãy các s nguyên s h ng đ u tiên b ng m t s h ng nào đ ó đ ng tr ưc nó trong dãy. 20
13. L p thu t toán tìm trong m t dãy các s nguyên t t c các s h ng l n h ơn t ng t t c các s h ng đ ng tr ưc nó trong dãy. 14. Cho đ ánh giá big-O đ i v i s các phép so sánh đ ưc dùng b i thu t toán trong Bài tp 10. 15. Đ ánh giá đ ph c t p c a thu t toán tìm ki m tam phân đ ưc cho trong Bài t p 11. 16. Đ ánh giá đ ph c t p c a thu t toán trong Bài t p 12. 17. Mô t thu t toán tính hi u c a hai khai tri n nh phân. 18. L p m t thu t toán đ xác đ nh a > b, a = b hay a < b đ i v i hai s nguyên a và b dng khai tri n nh phân. 19. Đ ánh giá đ ph c t p c a thu t toán tìm khai tri n theo c ơ s b c a s nguyên n qua s các phép chia đ ưc dùng. 20. Hãy cho thu t toán đ quy tìm t ng n s nguyên d ươ ng l đ u tiên. 21. Hãy cho thu t toán đ quy tìm s c c đ i c a t p h u h n các s nguyên. 22. Mô t thu t toán đ quy tìm x n mod m v i n, x, m là các s nguyên d ươ ng. n 23. Hãy ngh ĩ ra thu t toán đ quy tính a2 trong đ ó a là m t s th c và n là m t s nguyên d ươ ng. 24. Hãy ngh ĩ ra thu t toán đ quy tìm s h ng th n c a dãy đưc xác đ nh nh ư sau: a0=1, a 1 = 2 và a n = a n-1 an-2 v i n = 2, 3, 4, 25. Thu t toán đ quy hay thu t toán l p tìm s h ng th n c a dãy trong Bài t p 24 là có hi u qu h ơn? 21
CH ƯƠ NG II BÀI TOÁN Đ M Lý thuy t t h p là m t ph n quan tr ng c a toán h c r i r c chuyên nghiên c u s phân b các ph n t vào các t p h p. Thông th ưng các ph n t này là h u h n và vi c phân b chúng ph i tho mãn nh ng đi u ki n nh t đ nh nào đó, tùy theo yêu c u ca bài toán c n nghiên c u. M i cách phân b nh ư v y g i là m t c u hình t h p. Ch đ này đã đưc nghiên c u t th k 17, khi nh ng câu h i v t h p đ ưc nêu ra trong nh ng công trình nghiên c u các trò ch ơi may r i. Li t kê, đ m các đ i t ưng có nh ng tính ch t nào đó là m t ph n quan tr ng c a lý thuy t t h p. Chúng ta c n ph i đ m các đi t ưng đ gi i nhi u bài toán khác nhau. H ơn n a các k thu t đ m đ ưc dùng r t nhi u khi tính xác su t c a các bi n c . 2.1. C Ơ S C A PHÉP Đ M. 2.1.1. Nh ng nguyên lý đm c ơ b n: 1) Quy t c c ng: Gi s có k công vi c T 1, T 2, , T k. Các vi c này có th làm t ươ ng ng b ng n 1, n 2, , n k cách và gi s không có hai vi c nào có th làm đ ng th i. Khi đó s cách làm m t trong k vi c đó là n 1+n 2+ + n k. Thí d 1: 1) Mt sinh viên có th ch n bài th c hành máy tính t m t trong ba danh sách t ươ ng ng có 23, 15 và 19 bài. Vì v y, theo quy t c c ng có 23 + 15 + 19 = 57 cách ch n bài th c hành. 2) Giá tr c a bi n m b ng bao nhiêu sau khi đo n ch ươ ng trình sau đưc th c hi n? m := 0 for i 1 := 1 to n 1 m := m+1 for i2 :=1 to n 2 m := m+1 for i k := 1 to n k m := m+1 Giá tr kh i t o c a m b ng 0. Kh i l nh này g m k vòng l p khác nhau. Sau m i bưc l p c a t ng vòng l p giá tr c a k đ ưc t ă ng lên m t đ ơn v . G i T i là vi c thi hành vòng l p th i. Có th làm T i b ng n i cách vì vòng l p th i có n i b ưc l p. Do các vòng l p không th th c hi n đ ng th i nên theo quy t c c ng, giá tr cu i cùng c a m bng s cách th c hi n m t trong s các nhi m v T i, t c là m = n 1+n 2+ + n k. Quy t c c ng có th phát bi u d ưi d ng c a ngôn ng t p h p nh ư sau: N u A 1, A2, , A k là các t p h p đ ôi m t r i nhau, khi đ ó s ph n t c a h p các t p h p này bng t ng s các ph n t c a các tp thành ph n. Gi s T i là vi c ch n m t ph n t t 22
tp A i v i i=1,2, , k. Có |A i| cách làm T i và không có hai vi c nào có th đ ưc làm cùng m t lúc. S cách ch n m t ph n t c a h p các t p h p này, m t m t b ng s ph n t c a nó, m t khác theo quy t c c ng nó b ng |A 1|+|A 2|+ +|A k|. Do đ ó ta có: |A 1 ∪ A 2 ∪ ∪ A k| = |A 1| + |A 2| + + |A k|. 2) Quy t c nhân: Gi s m t nhi m v nào đ ó đ ưc tách ra thành k vi c T 1, T 2, , T k. Nu vi c T i có th làm b ng n i cách sau khi các vi c T 1, T 2, T i-1 đ ã đưc làm, khi đ ó có n 1.n 2 n k cách thi hành nhi m v đ ã cho. Thí d 2: 1) Ng ưi ta có th ghi nhãn cho nh ng chi c gh trong m t gi ng đ ưng b ng mt ch cái và m t s nguyên d ươ ng không v ưt quá 100. B ng cách nh ư v y, nhi u nh t có bao nhiêu chi c gh có th đ ưc ghi nhãn khác nhau? Th t c ghi nhãn cho m t chi c gh g m hai vi c, gán m t trong 26 ch cái và sau đ ó gán m t trong 100 s nguyên d ươ ng. Quy t c nhân ch ra r ng có 26.100=2600 cách khác nhau đ gán nhãn cho m t chi c gh . Nh ư v y nhi u nh t ta có th gán nhãn cho 2600 chi c gh . 2) Có bao nhiêu xâu nh phân có đ dài n. Mi m t trong n bit c a xâu nh phân có th ch n b ng hai cách vì m i bit ho c bng 0 ho c b ng 1. B i v y theo quy t c nhân có t ng c ng 2 n xâu nh phân khác nhau có đ dài b ng n. 3) Có th t o đ ưc bao nhiêu ánh x t t p A có m ph n t vào t p B có n ph n t ? Theo đ nh ngh ĩa, m t ánh x xác đ nh trên A có giá tr trên B là m t phép t ươ ng ng m i ph n t c a A v i m t ph n t nào đ ó c a B. Rõ ràng sau khi đã ch n đ ưc nh ca i - 1 ph n t đ u, đ ch n nh c a ph n t th i c a A ta có n cách. Vì v y theo quy tc nhân, ta có n.n n=n m ánh x xác đ nh trên A nh n giá tr trên B. 4) Có bao nhiêu đ ơn ánh xác đ nh trên t p A có m ph n t và nh n giá tr trên t p B có n ph n t ? Nu m > n thì v i m i ánh x , ít nh t có hai ph n t c a A có cùng m t nh, đ i u đ ó có ngh ĩa là không có đ ơn ánh t A đ n B. Bây gi gi s m ≤ n và g i các ph n t ca A là a 1,a 2, ,a m. Rõ ràng có n cách ch n nh cho ph n t a 1. Vì ánh x là đ ơn ánh nên nh c a ph n t a 2 ph i khác nh c a a 1 nên ch có n - 1 cách ch n nh cho ph n t a2. Nói chung, đ ch n nh c a a k ta có n - k + 1 cách. Theo quy t c nhân, ta có n! n(n − 1)(n − 2) (n − m + 1) = (n− m )! đơn ánh t t p A đ n t p B. 5) Giá tr c a bi n k b ng bao nhiêu sau khi ch ươ ng trình sau đưc th c hi n? m := 0 for i 1 := 1 to n 1 for i 2 := 1 to n 2 23
for i k := 1 to n k k := k+1 Giá tr kh i t o c a k b ng 0. Ta có k vòng l p đ ưc l ng nhau. G i T i là vi c thi hành vòng l p th i. Khi đ ó s l n đ i qua vòng l p b ng s cách làm các vi c T 1, T 2, , Tk. S cách th c hi n vi c T j là n j (j=1, 2, , k), vì vòng l p th j đ ưc duy t v i m i giá tr nguyên i j n m gi a 1 và n j. Theo quy t c nhân vòng l p l ng nhau này đ ưc duy t qua n 1.n 2 n k l n. Vì v y giá tr cu i cùng c a k là n 1.n 2 n k. Nguyên lý nhân th ưng đ ưc phát bi u b ng ngôn ng t p h p nh ư sau. N u A 1, A2, , A k là các t p h u h n, khi đ ó s ph n t c a tích Descartes c a các t p này bng tích c a s các ph n t c a m i t p thành ph n. Ta bi t r ng vi c ch n m t ph n t c a tích Descartes A 1 x A 2 x x A k đ ưc ti n hành b ng cách ch n l n l ưt m t ph n t c a A1, m t ph n t c a A 2, , m t ph n t c a A k. Theo quy t c nhân ta có: |A 1 x A 2 x x A k| = |A 1|.|A 2| |A k|. 2.1.2. Nguyên lý bù tr : Khi hai công vi c có th đ ưc làm đ ng th i, ta không th dùng quy t c c ng đ tính s cách th c hi n nhi m v g m c hai vi c. Đ tính đ úng s cách th c hi n nhi m v này ta c ng s cách làm mi m t trong hai vi c r i tr đ i s cách làm đ ng th i c hai vi c. Ta có th phát bi u nguyên lý đm này b ng ngôn ng t p h p. Cho A 1, A 2 là hai t p h u h n, khi đ ó |A 1 ∪ A 2| = |A 1| + |A 2| − |A 1 ∩ A 2|. T đ ó v i ba t p h p h u h n A 1, A 2, A 3, ta có: |A 1 ∪ A 2 ∪ A 3| = |A 1| + |A 2| + |A 3| − |A 1 ∩ A 2| − |A 2 ∩ A 3| − |A 3 ∩ A 1| + |A 1 ∩ A 2 ∩ A 3|, và b ng quy n p, v i k t p h u h n A 1, A 2, , A k ta có: k-1 | A 1 ∪ A 2 ∪ ∪ A k| = N 1 − N 2 + N 3 − + ( −1) Nk, trong đ ó N m (1 ≤ m ≤ k) là t ng ph n t c a t t c các giao m t p l y t k t p đ ã cho, ngh ĩa là N = | A ∩ A ∩ ∩ A | m ∑ i1 i2 im ≤ < < < ≤ 1 i1 i2 im k Bây gi ta đ ng nh t t p A m (1 ≤ m ≤ k) v i tính ch t A m cho trên t p v ũ tr h u hn U nào đ ó và đ m xem có bao nhiêu ph n t c a U sao cho không th a mãn b t k ỳ mt tính ch t A m nào. Gi N là s c n đ m, N là s ph n t c a U. Ta có: k N = N − | A 1 ∪ A 2 ∪ ∪ A k| = N − N 1 + N 2 − + ( −1) Nk, trong đ ó N m là t ng các ph n t c a U th a mãn m tính ch t l y t k tính ch t đ ã cho. Công th c này đ ưc g i là nguyên lý bù tr . Nó cho phép tính N qua các N m trong tr ưng h p các s này d tính toán h ơn. 24
Thí d 3: Có n lá th ư và n phong bì ghi s n đ a ch . B ng u nhiên các lá th ư vào các phong bì. H i xác su t đ x y ra không m t lá th ư nào đ úng đ a ch . Mi phong bì có n cách b th ư vào, nên có t t c n! cách b th ư. V n đ còn l i là đ m s cách b th ư sao cho không lá th ư nào đ úng đ a ch . G i U là t p h p các cách b th ư và A m là tính ch t lá th ư th m b đ úng đ a ch . Khi đ ó theo công th c v nguyên lý bù tr ta có: n N = n! − N 1 + N 2 − + ( −1) Nn, trong đ ó N m (1 ≤ m ≤ n) là s t t c các cách b th ư sao cho có m lá th ư đ úng đ a ch . Nh n xét r ng, N m là t ng theo m i cách l y m lá th ư t n lá, v i m i cách l y m lá th ư, có (n-m)! cách b đ m lá th ư này đ úng đ a ch , ta nh n đ ưc: n! 1 1 1 N = C m (n - m)! = và N = n!(1 − + − + ( −1) n ), m n k! 1! 2! n! n! trong đ ó C m = là t h p ch p m c a t p n ph n t (s cách ch n m đ i n m (! n − m)! 1 1 tưng trong n đ i t ưng đ ưc cho). T đ ó xác su t c n tìm là: 1 − + − + ( −1) n 1! 2! 1 1 . M t đ i u lý thú là xác su t này d n đ n e -1 (ngh ĩa là còn > ) khi n khá l n. n! 3 S N trong bài toán này đ ưc g i là s m t th t và đ ưc ký hi u là D n. D ưi đ ây là m t vài giá tr c a Dn, cho ta th y D n t ă ng nhanh nh ư th nào so v i n: n 2 3 4 5 6 7 8 9 10 11 Dn 1 2 9 44 265 1854 14833 133496 1334961 14684570 2.2. NGUYÊN LÝ DIRICHLET. 2.2.1. M đ u: Gi s có m t đ àn chim b câu bay vào chu ng. N u s chim nhi u h ơn s ng ă n chu ng thì ít nh t trong m t ng ă n có nhi u h ơn m t con chim. Nguyên lý này d ĩ nhiên là có th áp d ng cho các đ i t ưng không ph i là chim b câu và chu ng chim. Mnh đ (Nguyên lý): N u có k+1 (ho c nhi u h ơn) đ v t đ ưc đ t vào trong k h p thì t n t i m t h p có ít nh t hai đ v t. Ch ng minh: Gi s không có h p nào trong k h p ch a nhi u h ơn m t đ v t. Khi đ ó tng s v t đ ưc ch a trong các h p nhi u nh t là b ng k. Đ i u này trái gi thi t là có ít nh t k + 1 v t. Nguyên lý này th ưng đ ưc g i là nguyên lý Dirichlet, mang tên nhà toán h c ng ưi Đ c th k 19. Ông th ưng xuyên s d ng nguyên lý này trong công vi c c a mình. Thí d 4: 1) Trong b t k ỳ m t nhóm 367 ng ưi th nào c ũng có ít nh t hai ng ưi có ngày sinh nh t gi ng nhau b i vì ch có t t c 366 ngày sinh nh t khác nhau. 25
2) Trong k ỳ thi h c sinh gi i, đ i m bài thi đ ưc đ ánh giá b i m t s nguyên trong kho ng t 0 đ n 100. H i r ng ít nh t có bao nhiêu h c sinh d thi đ cho ch c ch n tìm đưc hai h c sinh có k t qu thi nh ư nhau? Theo nguyên lý Dirichlet, s h c sinh c n tìm là 102, vì ta có 101 k t qu đ i m thi khác nhau. 3) Trong s nh ng ng ưi có m t trên trái đ t, ph i tìm đưc hai ng ưi có hàm r ă ng gi ng nhau. N u xem m i hàm r ă ng g m 32 cái nh ư là m t xâu nh phân có chi u dài 32, trong đ ó r ă ng còn ng v i bit 1 và r ă ng m t ng v i bit 0, thì có t t c 2 32 = 4.294.967.296 hàm r ă ng khác nhau. Trong khi đ ó s ng ưi trên hành tinh này là v ưt quá 5 t , nên theo nguyên lý Dirichlet ta có đ i u c n tìm. 2.2.2. Nguyên lý Dirichlet t ng quát: Mnh đ : N u có N đ v t đ ưc đ t vào trong k h p thì s t n t i m t h p ch a ít nh t ]N/k [ đ v t. ( đ ây, ]x[ là giá tr c a hàm tr n t i s th c x, đ ó là s nguyên nh nh t có giá tr l n hơn ho c b ng x. Khái ni m này đ i ng u v i [x] – giá tr c a hàm sàn hay hàm ph n nguyên t i x – là s nguyên l n nh t có giá tr nh h ơn ho c b ng x.) Ch ng minh: Gi s m i h p đ u ch a ít h ơn ]N/k [ v t. Khi đ ó t ng s đ v t là N N ≤ k ( ] [ − 1) < k = N. k k Đ i u này mâu thu n v i gi thit là có N đ v t c n x p. Thí d 5: 1) Trong 100 ng ưi, có ít nh t 9 ng ưi sinh cùng m t tháng. Xp nh ng ng ưi sinh cùng tháng vào m t nhóm. Có 12 tháng t t c . V y theo nguyên lý Dirichlet, t n t i m t nhóm có ít nh t ]100/12 [= 9 ng ưi. 2) Có n ă m lo i h c b ng khác nhau. H i r ng ph i có ít nh t bao nhiêu sinh viên đ ch c ch n r ng có ít ra là 6 ng ưi cùng nh n h c b ng nh ư nhau. Gi N là s sinh viên, khi đ ó ]N/5 [ = 6 khi và ch khi 5 < N/5 ≤ 6 hay 25 < N ≤ 30. V y s N c n tìm là 26. 3) S mã vùng c n thi t nh nh t ph i là bao nhiêu đ đ m b o 25 tri u máy đ i n tho i trong n ưc có s đ i n tho i khác nhau, m i s có 9 ch s (gi s s đ i n tho i có d ng 0XX - 8XXXXX v i X nh n các giá tr t 0 đ n 9). Có 10 7 = 10.000.000 s đ i n tho i khác nhau có d ng 0XX - 8XXXXX. Vì v y theo nguyên lý Dirichlet t ng quát, trong s 25 tri u máy đ i n tho i ít nh t có ]25.000.000/10.000.000 [ = 3 có cùng m t s . Đ đ m b o m i máy có m t s c n có ít nh t 3 mã vùng. 2.2.3. M t s ng d ng c a nguyên lý Dirichlet. Trong nhi u ng d ng thú v c a nguyên lý Dirichlet, khái ni m đ v t và h p cn ph i đ ưc l a ch n m t cách khôn khéo. Trong ph n nay có vài thí d nh ư v y. 26
Thí d 6: 1) Trong m t phòng h p có n ng ưi, bao gi c ũng tìm đưc 2 ng ưi có s ng ưi quen trong s nh ng ng ưi d h p là nh ư nhau. S ng ưi quen c a m i ng ưi trong phòng h p nh n các giá tr t 0 đ n n − 1. Rõ ràng trong phòng không th đ ng th i có ng ưi có s ng ưi quen là 0 (t c là không quen ai) và có ng ưi có s ng ưi quen là n − 1 (t c là quen t t c ). Vì v y theo s l ưng ng ưi quen, ta ch có th phân n ng ưi ra thành n −1 nhóm. V y theo nguyên lý Dirichlet t n tai m t nhóm có ít nh t 2 ng ưi, t c là luôn tìm đưc ít nh t 2 ng ưi có s ng ưi quen là nh ư nhau. 2) Trong m t tháng g m 30 ngày, m t đ i bóng chuy n thi đ u m i ngày ít nh t 1 tr n nh ưng ch ơi không quá 45 tr n. Ch ng minh r ng tìm đưc m t giai đ o n g m m t s ngày liên t c nào đ ó trong tháng sao cho trong giai đ o n đ ó đ i ch ơi đ úng 14 tr n. Gi a j là s tr n mà đ i đ ã ch ơi t ngày đ u tháng đ n h t ngày j. Khi đ ó 1 ≤ a 1 < a 2 < < a 30 < 45 15 ≤ a 1+14 < a 2+14 < < a 30 +14 < 59. Sáu m ươ i s nguyên a 1, a 2, , a 30 , a 1+ 14, a 2 + 14, , a 30 +14 n m gi a 1 và 59. Do đ ó theo nguyên lý Dirichlet có ít nh t 2 trong 60 s này b ng nhau. Vì v y t n t i i và j sao cho ai = aj + 14 (j < i). Đ i u này có ngh ĩa là t ngày j + 1 đ n h t ngày i đ i đ ã ch ơi đ úng 14 tr n. 3) Ch ng t r ng trong n + 1 s nguyên d ươ ng không v ưt quá 2n, t n t i ít nh t m t s chia h t cho s khác. k j Ta vi t m i s nguyên a 1, a 2, , a n+1 d ưi d ng a j = 2 qj trong đ ó kj là s nguyên không âm còn q j là s d ươ ng l nh h ơn 2n. Vì ch có n s nguyên d ươ ng l nh h ơn 2n ki nên theo nguyên lý Dirichlet t n t i i và j sao cho q i = q j = q. Khi đ ó a i= 2 q và aj = k j 2 q. Vì v y, n u k i ≤ k j thì a j chia h t cho a i còn trong tr ưng h p ng ưc l i ta có a i chia h t cho a j. Thí d cu i cùng trình bày cách áp d ng nguyên lý Dirichlet vào lý thuy t t h p mà v n quen g i là lý thuy t Ramsey , tên c a nhà toán h c ng ưi Anh. Nói chung, lý thuy t Ramsey gi i quy t nh ng bài toán phân chia các t p con c a m t t p các ph n t . Thí d 7. Gi s trong m t nhóm 6 ng ưi m i c p hai ho c là b n ho c là thù. Ch ng t rng trong nhóm có ba ng ưi là b n l n nhau ho c có ba ng ưi là k thù l n nhau. Gi A là m t trong 6 ng ưi. Trong s 5 ng ưi c a nhóm ho c là có ít nh t ba ng ưi là b n c a A ho c có ít nh t ba ng ưi là k thù c a A, đ i u này suy ra t nguyên lý Dirichlet t ng quát, vì ]5/2 [ = 3. Trong tr ưng h p đ u ta g i B, C, D là b n c a A. nu trong ba ng ưi này có hai ng ưi là b n thì h cùng v i A l p thành m t b ba ng ưi bn l n nhau, ng ưc l i, t c là n u trong ba ng ưi B, C, D không có ai là b n ai c thì ch ng t h là b ba ng ưi thù l n nhau. T ươ ng t có th ch ng minh trong tr ưng h p có ít nh t ba ng ưi là k thù c a A. 27
2.3. CH NH H P VÀ T H P SUY R NG. 2.3.1. Ch nh h p có l p. Mt cách s p x p có th t k ph n t có th l p l i c a m t t p n ph n t đ ưc gi là m t ch nh h p l p ch p k t t p n ph n t . N u A là t p g m n ph n t đ ó thì m i ch nh h p nh ư th là m t ph n t c a t p A k. Ngoài ra, m i ch nh h p l p ch p k t t p n ph n t là m t hàm t t p k ph n t vào t p n ph n t . Vì v y s ch nh h p l p ch p k t t p n ph n t là n k. 2.3.2. T h p l p. Mt t h p l p ch p k c a m t t p h p là m t cách ch n không có th t k ph n t có th l p l i c a t p đ ã cho. Nh ư v y m t t h p l p ki u này là m t dãy không k th t g m k thành ph n l y t t p n ph n t . Do đ ó có th là k > n. k Mnh đ 1: S t h p l p ch p k t t p n ph n t b ng Cn+k−1 . Ch ng minh. M i t h p l p ch p k t t p n ph n t có th bi u di n b ng m t dãy n −1 thanh đ ng và k ngôi sao. Ta dùng n − 1 thanh đ ng đ phân cách các ng ă n. Ng ă n th i ch a thêm m t ngôi sao m i l n khi ph n t th i c a t p xu t hi n trong t h p. Ch ng hn, t h p l p ch p 6 c a 4 ph n t đ ưc bi u th b i: * * | * | | * * * mô t t h p ch a đ úng 2 ph n t th nh t, 1 ph n t th hai, không có ph n t th 3 và 3 ph n t th t ư c a t p h p. Mi dãy n − 1 thanh và k ngôi sao ng v i m t xâu nh phân đ dài n + k − 1 v i k s 1. Do đ ó s các dãy n − 1 thanh đ ng và k ngôi sao chính là s t h p ch p k t t p n + k − 1 ph n t . Đ ó là đ i u c n ch ng minh. Thi d 8: 1) Có bao nhiêu cách ch n 5 t gi y b c t m t két đ ng ti n g m nh ng t 1000 đ , 2000 đ , 5000 đ , 10.000 đ , 20.000 đ , 50.000 đ , 100.000 đ . Gi s th t mà các t ti n đ ưc ch n là không quan tr ng, các t ti n cùng lo i là không phân bi t và m i lo i có ít nh t 5 t . Vì ta không k t i th t ch n t ti n và vì ta ch n đ úng 5 l n, m i l n l y m t t 1 trong 7 lo i ti n nên m i cách ch n 5 t gi y b c này chính là m t t h p l p ch p 5 t 5 7 ph n t . Do đ ó s c n tìm là C7+5−1 = 462. 2) Ph ươ ng trình x 1 + x 2 + x 3 = 15 có bao nhiêu nghi m nguyên không âm? Chúng ta nh n th y m i nghi m c a ph ươ ng trình ng v i m t cách ch n 15 ph n t t m t t p có 3 lo i, sao cho có x 1 ph n t lo i 1, x 2 ph n t lo i 2 và x 3 ph n t lo i 3 đ ưc ch n. Vì v y s nghi m b ng s t h p l p ch p 15 t t p có 3 ph n t và 15 bng C3+15 −1= 136. 2.3.3. Hoán v c a t p h p có các ph n t gi ng nhau. Trong bài toán đ m, m t s ph n t có th gi ng nhau. Khi đ ó c n ph i c n th n, tránh đ m chúng h ơn m t l n. Ta xét thí d sau. 28
Thí d 9: Có th nh n đ ưc bao nhiêu xâu khác nhau b ng cách s p x p l i các ch cái ca t SUCCESS? Vì m t s ch cái c a t SUCCESS là nh ư nhau nên câu tr l i không ph i là s hoán v c a 7 ch cái đ ưc. T này ch a 3 ch S, 2 ch C, 1 ch U và 1 ch E. Đ xác đnh s xâu khác nhau có th t o ra đ ưc ta nh n th y có C(7,3) cách ch n 3 ch cho 3 ch S, còn l i 4 ch tr ng. Có C(4,2) cách ch n 2 ch cho 2 ch C, còn l i 2 ch tr ng. Có th đ t ch U b ng C(2,1) cách và C(1,1) cách đ t ch E vào xâu. Theo nguyên lý nhân, s các xâu khác nhau có th t o đ ưc là: 7!!!! 4 2 1 7! C 3 .C 2 .C1 .C1= = = 420. 7 4 2 1 3!. 4!. 2!. 2!.1!.1!.1!. 0! 3!. 2!.1!.1! Mnh đ 2: S hoán v c a n ph n t trong đ ó có n 1 ph n t nh ư nhau thu c lo i 1, n 2 ph n t nh ư nhau thu c lo i 2, , và n k ph n t nh ư nhau thu c lo i k, b ng n! . n1!. n2! nk ! n1 Ch ng minh. Đ xác đ nh s hoán v tr ưc tiên chúng ta nh n th y có Cn cách gi n 1 n2 ch cho n 1 ph n t lo i 1, còn l i n - n 1 ch tr ng. Sau đ ó có C − cách đ t n 2 ph n t n n1 lo i 2 vào hoán v , còn l i n - n 1 - n 2 ch tr ng. Ti p t c đ t các ph n t lo i 3, lo i 4, , nk lo i k - 1vào ch tr ng trong hoán v . Cu i cùng có C − − − cách đ t n k ph n t lo i n n1 nk −1 k vào hoán v . Theo quy t c nhân t t c các hoán v có th là: n n n! C n1 .C 2 C k = . n n−n n−n − −n − 1 1 k 1 n1!. n2! nk ! 2.3.4. S phân b các đ v t vào trong h p. Thí d 10: Có bao nhiêu cách chia nh ng x p bài 5 quân cho m i m t trong 4 ng ưi ch ơi t m t c bài chu n 52 quân? 5 Ng ưi đ u tiên có th nh n đ ưc 5 quân bài b ng C52 cách. Ng ưi th hai có th 5 đưc chia 5 quân bài b ng C47 cách, vì ch còn 47 quân bài. Ng ưi th ba có th nh n 5 đưc 5 quân bài b ng C42 cách. Cu i cùng, ng ưi th t ư nh n đ ưc 5 quân bài b ng 5 C37 cách. Vì v y, theo nguyên lý nhân t ng c ng có 52! C 5 .C 5 .C 5 .C 5 = 52 47 42 37 5!. 5!. 5!. 5!. 32! cách chia cho 4 ng ưi m i ng ưi m t x p 5 quân bài. Thí d trên là m t bài toán đ i n hình v vi c phân b các đ v t khác nhau vào các h p khác nhau. Các đ v t là 52 quân bài, còn 4 h p là 4 ng ưi ch ơi và s còn l i đ trên bàn. S cách s p x p các đ v t vào trong h p đ ưc cho b i m nh đ sau Mnh đ 3: S cách phân chia n đ v t khác nhau vào trong k h p khác nhau sao cho có n i v t đ ưc đ t vào trong h p th i, v i i = 1, 2, , k b ng 29
n! . − − − n1!. n2! nk !.( n n1 nk )! 2.4. SINH CÁC HOÁN V VÀ T H P. 2.4.1. Sinh các hoán v : Có nhi u thu t toán đ ã đưc phát tri n đ sinh ra n! hoán v c a t p {1,2, ,n}. Ta s mô t m t trong các ph ươ ng pháp đ ó, ph ươ ng pháp li t kê các hoán v c a t p {1,2, ,n} theo th t t đ i n. Khi đ ó, hoán v a 1a2 a n đ ưc g i là đ i tr ưc hoán v b1b2 b n n u t n t i k (1 ≤ k ≤ n), a 1 = b 1, a 2 = b 2, , a k-1 = b k-1 và a k a j+2 > > a n, t c là tìm c p s nguyên li n k đ u tiên tính t bên ph i sang bên trái c a hoán v mà s đ u nh h ơn s sau. Sau đ ó, đ nh n đ ưc hoán v li n sau ta đ t vào v trí th j s nguyên nh nh t trong các s l n h ơn a j c a t p a j+1 , a j+2 , , a n, r i li t kê theo th t t ă ng d n c a các s còn l i c a a j, a j+1 , a j+2 , , a n vào các v trí j+1, , n. D th y không có hoán v nào đ i sau hoán v xu t phát và đ i tr ưc hoán v v a t o ra. Thí d 11: Tìm hoán v li n sau theo th t t đ i n c a hoán v 4736521. Cp s nguyên đ u tiên tính t ph i qua trái có s tr ưc nh h ơn s sau là a 3 = 3 và a 4 = 6. S nh nh t trong các s bên ph i c a s 3 mà l i l n h ơn 3 là s 5. Đ t s 5 vào v trí th 3. Sau đ ó đ t các s 3, 6, 1, 2 theo th t t ă ng d n vào b n v trí còn l i. Hoán v li n sau hoán v đ ã cho là 4751236. procedure Hoán v li n sau (a 1, a 2, , an) (hoán v c a {1,2, ,n} khác (n, n −1, , 2, 1)) j := n − 1 while aj > a j+1 j := j − 1 {j là ch s l n nh t mà a j a k k := k - 1 {a k là s nguyên nh nh t trong các s l n h ơn a j và bên ph i a j} đi ch (a j, a k) r := n s := j + 1 while r > s đi ch (a r, a s) r := r - 1 ; s := s + 1 { Đ i u này s x p phn đ uôi c a hoán v sau v trí th j theo th t t ă ng d n.} 30
2.4.2. Sinh các t h p: Làm th nào đ t o ra t t c các t h p các ph n t c a m t t p h u h n? Vì t hp chính là m t t p con, nên ta có th dùng phép t ươ ng ng 1-1 gi a các t p con c a {a 1,a 2, ,a n} và xâu nh phân đ dài n. Ta th y m t xâu nh phân đ dài n c ũng là khai tri n nh phân c a m t s nguyên nm gi a 0 và 2 n − 1. Khi đ ó 2 n xâu nh phân có th li t kê theo th t t ă ng d n c a s nguyên trong bi u di n nh phân c a chúng. Chúng ta s b t đ u t xâu nh phân nh nh t 00 00 (n s 0). M i b ưc đ tìm xâu li n sau ta tìm v trí đ u tiên tính t ph i qua trái mà đ ó là s 0, sau đ ó thay t t c s 1 bên ph i s này b ng 0 và đ t s 1 vào chính v trí này. procedure Xâu nh phân li n sau (b n-1bn-2 b 1b0): xâu nh phân khác (11 11) i := 0 while bi = 1 begin bi := 0 i := i + 1 end bi := 1 Ti p theo chúng ta s trình bày thu t toán t o các t h p ch p k t n ph n t {1,2, ,n}. M i t h p ch p k có th bi u di n b ng m t xâu t ă ng. Khi đ ó có th li t kê các t h p theo th t t đ i n. Có th xây d ng t h p li n sau t h p a 1a2 a k b ng cách sau. Tr ưc h t, tìm ph n t đ u tiên a i trong dãy đã cho k t ph i qua trái sao cho a i ≠ n − k + i. Sau đ ó thay a i b ng a i + 1 và a j b ng a i + j − i + 1 v i j = i + 1, i + 2, , k. Thí d 12: Tìm t h p ch p 4 t t p {1, 2, 3, 4, 5, 6} đ i li n sau t h p {1, 2, 5, 6}. Ta th y t ph i qua trái a 2 = 2 là s h ng đ u tiên c a t h p đ ã cho th a mãn đ i u ki n a i ≠ 6 − 4 + i. Đ nh n đ ưc t h p ti p sau ta t ă ng a i lên m t đ ơn v , t c a 2 = 3, sau đ ó đ t a 3 = 3 + 1 = 4 và a 4 = 3 + 2 = 5. V y t h p li n sau t h p đ ã cho là {1,3,4,5}. Th t c này đ ưc cho d ưi d ng thu t toán nh ư sau. procedure T h p li n sau ({a 1, a 2, , a k}: t p con thc s c a t p {1, 2, , n} không bng {n − k + 1, , n} v i a 1 < a 2 < < a k) i := k while a i = n − k + i i := i − 1 ai := a i + 1 for j := i + 1 to k aj := a i + j − i 31
2.5. H TH C TRUY H I. 2.5.1. Khái ni m m đ u và mô hình hóa b ng h th c truy h i: Đ ôi khi ta r t khó đ nh ngh ĩa m t đ i t ưng m t cách t ưng minh. Nh ưng có th d dàng đ nh ngh ĩa đ i t ưng này qua chính nó. K thu t này đ ưc g i là đ quy. Đ nh ngh ĩa đ quy c a m t dãy s đ nh rõ giá tr c a m t hay nhi u h ơn các s h ng đ u tiên và quy t c xác đ nh các s h ng ti p theo t các s h ng đ i tr ưc. Đ nh ngh ĩa đ quy có th dùng đ gi i các bài toán đ m. Khi đ ó quy t c tìm các s h ng t các s h ng đ i tr ưc đ ưc g i là các h th c truy h i. Đnh ngh ĩa 1: H th c truy h i (hay công th c truy h i) đ i v i dãy s {a n} là công th c bi u di n a n qua m t hay nhi u s h ng đ i tr ưc c a dãy. Dãy s đ ưc g i là l i gi i hay nghi m c a h th c truy h i n u các s h ng c a nó th a mãn h th c truy h i này. Thí d 13 (Lãi kép) : 1) Gi s m t ng ưi g i 10.000 đ ô la vào tài kho n c a mình t i mt ngân hàng v i lãi su t kép 11% m i n ă m. Sau 30 n ă m anh ta có bao nhiêu ti n trong tài kho n c a mình? Gi P n là t ng s ti n có trong tài kho n sau n n ă m. Vì s ti n có trong tài kho n sau n n ă m b ng s có sau n − 1 n ă m c ng lãi su t c a n ă m th n, nên ta th y dãy {P n} tho mãn h th c truy h i sau: Pn = P n-1 + 0,11P n-1 = (1,11)P n-1 n vi đ i u ki n đ u P 0 = 10.000 đ ô la. T đ ó suy ra P n = (1,11) .10.000. Thay n = 30 cho ta P 30 = 228922,97 đ ô la. 2) Tìm h th c truy h i và cho đ i u ki n đ u đ tính s các xâu nh phân đ dài n và không có hai s 0 liên ti p. Có bao nhiêu xâu nh phân nh ư th có đ dài b ng 5? Gi a n là s các xâu nh phân đ dài n và không có hai s 0 liên ti p. Đ nh n đưc h th c truy h i cho {a n}, ta th y r ng theo quy t c c ng, s các xâu nh phân đ dài n và không có hai s 0 liên ti p b ng s các xâu nh phân nh ư th k t thúc b ng s 1 cng v i s các xâu nh ư th k t thúc b ng s 0. Gi s n ≥ 3. Các xâu nh phân đ dài n, không có hai s 0 liên ti p k t thúc b ng s 1 chính là xâu nh phân nh ư th , đ dài n − 1 và thêm s 1 vào cu i c a chúng. V y chúng có t t c là a n-1. Các xâu nh phân đ dài n, không có hai s 0 liên ti p và k t thúc b ng s 0, c n ph i có bit th n − 1 b ng 1, n u không thì chúng có hai s 0 hai bit cu i cùng. Trong tr ưng h p này chúng có t t c là a n-2. Cu i cùng ta có đ ưc: an = a n-1 + a n-2 v i n ≥ 3. Đ i u ki n đ u là a 1 = 2 và a 2 = 3. Khi đ ó a 5 = a 4 + a 3 = a 3 + a 2 + a 3 = 2(a 2 + a 1) + a 2 = 13. 2.5.2. Gi i các h th c truy h i. Đnh ngh ĩa 2: Mt h th c truy h i tuy n tính thu n nh t b c k v i h s h ng s là h th c truy h i có d ng: 32
an = c 1an-1 + c 2an-2 + + c kan-k , trong đ ó c 1, c 2, , c k là các s th c và c k ≠ 0. Theo nguyên lý c a quy n p toán h c thì dãy s th a mãn h th c truy h i nêu trong đ nh ngh ĩa đ ưc xác đ nh duy nh t b ng h th c truy h i này và k đ i u ki n đ u: a0 = C 0, a 1 = C 1, , a k-1 = C k-1. Ph ươ ng pháp c ơ b n đ gi i h th c truy h i tuy n tính thu n nh t là tìm nghi m n n dưi d ng a n = r , trong đ ó r là h ng s . Chú ý r ng a n = r là nghi m c a h th c truy hi a n = c 1an-1 + c 2an-2 + + c kan-k n u và ch n u n n-1 n-2 n-k k k-1 k-2 r = c 1r + c 2r + + c kr hay r − c 1r − c 2r − − c k-1r – c k = 0. Ph ươ ng trình này đưc g i là ph ươ ng trình đc tr ưng c a h th c truy h i, nghi m c a nó g i là nghi m đ c tr ưng c a h th c truy h i. Mnh đ : Cho c 1, c 2, , c k là các s th c. Gi s r ng ph ươ ng trình đc tr ưng k k-1 k-2 r − c 1r − c 2r − − c k-1r – c k = 0 có k nghi m phân bi t r 1, r 2, , r k. Khi đ ó dãy {a n} là nghi m c a h th c truy h i a n = n n n c1an-1 + c 2an-2 + + c kan-k n u và ch n u a n = α1r1 + α2r2 + + αkrk , v i n = 1, 2, trong đ ó α1, α2, , αk là các h ng s . Thí d 14: 1) Tìm công th c hi n c a các s Fibonacci. Dãy các s Fibonacci th a mãn h th c f n = f n-1 + f n-2 và các đ i u ki n đ u f 0 = 0 1+ 5 1− 5 và f = 1. Các nghi m đ c tr ưng là r = và r = . Do đ ó các s Fibonacci 1 1 2 2 2 1+ 5 1− 5 đưc cho b i công th c f = α ( )n + α ( )n. Các đ i u ki n ban đ u f = 0 = n 1 2 2 2 0 1+ 5 1− 5 1 α + α và f = 1 = α ( ) + α ( ). T hai ph ươ ng trình này cho ta α = , 1 2 1 1 2 2 2 1 5 1 α = - . Do đ ó các s Fibonacci đ ưc cho b i công th c hi n sau: 2 5 1 1+ 5 1 1− 5 f = ( )n - ( )n. n 5 2 5 2 2) Hãy tìm nghi m c a h th c truy h i a n = 6a n-1 - 11a n-2 + 6a n-3 v i đ i u ki n ban đ u a 0 = 2, a 1 = 5 và a 2 = 15. Đ a th c đ c tr ưng c a h th c truy h i này là r 3 - 6r 2 + 11r - 6. Các nghi m đ c tr ưng là r = 1, r = 2, r = 3. Do v y nghi m c a h th c truy h i có d ng n n n an = α11 + α22 + α33 . Các đ i u ki n ban đ u a0 = 2 = α1 + α2 + α3 a1 = 5 = α1 + α22 + α33 a2 = 15 = α1 + α24 + α39. Gi i h các ph ươ ng trình này ta nh n đ ưc α1= 1, α2 = −1, α3 = 2. Vì th , nghi m duy nh t c a h th c truy h i này và các đ i u ki n ban đ u đ ã cho là dãy {a n} v i 33
n n an = 1 − 2 + 2.3 . 2.6. QUAN H CHIA Đ TR . 2.6.1. M đ u: Nhi u thu t toán đ quy chia bài toán v i các thông tin vào đ ã cho thành m t hay nhi u bài toán nh h ơn. S phân chia này đ ưc áp d ng liên ti p cho t i khi có th tìm đưc l i gi i c a bài toán nh m t cách d dàng. Ch ng h n, ta ti n hành vi c tìm ki m nh phân b ng cách rút g n vi c tìm ki m m t ph n t trong m t danh sách t i vi c tìm ph n t đ ó trong m t danh sách có đ dài gi m đ i m t n a. Ta rút g n liên ti p nh ư v y cho t i khi còn l i m t ph n t . M t ví d khác là th t c nhân các s nguyên. Th t c này rút g n bài toán nhân hai s nguyên t i ba phép nhân hai s nguyên v i s bit gi m đ i m t n a. Phép rút g n này đ ưc dùng liên ti p cho t i khi nh n đ ưc các s nguyên có m t bit. Các th t c này g i là các thu t toán chia đ tr . 2.6.2. H th c chia đ tr : Gi s r ng m t thu t toán phân chia m t bài toán c n thành a bài toán nh , n trong đ ó m i bài toán nh có c ( đ đ ơn gi n gi s r ng n chia h t cho b; trong th c b n n t các bài toán nh th ưng có c [ ] ho c ] [). Gi s r ng t ng các phép toán thêm b b vào khi th c hi n phân chia bài toán c n thành các bài toán có c nh h ơn là g(n). Khi đ ó, n u f(n) là s các phép toán c n thi t đ gi i bài toán đ ã cho thì f th a mãn h th c truy h i sau: n f(n) = af( ) + g(n) b H th c này có tên là h th c truy h i chia đ tr . Thí d 15: 1) Thu t toán tìm ki m nh phân đ ưa bài toán tìm ki m c n v bài toán tìm ki m ph n t này trong dãy tìm ki m c n/2, khi n ch n. Khi th c hi n vi c rút g n c n hai phép so sánh. Vì th , n u f(n) là s phép so sánh c n ph i làm khi tìm ki m m t ph n t trong danh sách tìm ki m c n ta có f(n) = f(n/2) + 2, n u n là s ch n. 2) Có các thu t toán hi u qu h ơn thu t toán thông th ưng đ nhân hai s nguyên. đ ây ta s có m t trong các thu t toán nh ư v y. Đ ó là thu t toán phân nhanh, có dùng k thu t chia đ tr . Tr ưc tiên ta phân chia m i m t trong hai s nguyên 2n bit thành hai kh i m i kh i n bit. Sau đ ó phép nhân hai s nguyên 2n bit ban đ u đ ưc thu v ba phép nhân các s nguyên n bit c ng v i các phép d ch chuy n và các phép c ng. Gi s a và b là các s nguyên có các bi u di n nh phân đ dài 2n là a = (a 2n-1 a2n-2 a 1 a 0)2 và b = (b 2n-1 b 2n-2 b 1 b 0)2. n n Gi s a = 2 A1 + A 0 , b = 2 B1 + B 0 , trong đ ó A1 = (a 2n-1 a 2n-2 a n+1 a n)2 , A 0 = (a n-1 a 1 a 0)2 B 1 = (b 2n -1 b 2n -2 b n+1 b n)2 , B 0 = (b n-1 b 1 b 0)2. Thu t toán nhân nhanh các s nguyên d a trên đ ng th c: 34
2n n n n ab = (2 + 2 )A 1B1 + 2 (A 1 - A 0)(B 0 - B 1) + (2 + 1)A 0B0. Đng th c này ch ra r ng phép nhân hai s nguyên 2n bit có th th c hi n b ng cách dùng ba phép nhân các s nguyên n bit và các phép c ng, tr và phép d ch chuy n. Đ i u đ ó có ngh ĩa là n u f(n) là t ng các phép toán nh phân c n thi t đ nhân hai s nguyên n bit thì f(2n) = 3f(n) + Cn. Ba phép nhân các s nguyên n bit c n 3f(n) phép toán nh phân. M i m t trong các phép cng, tr hay d ch chuy n dùng m t h ng s nhân v i n l n các phép toán nh phân và Cn là t ng các phép toán nh phân đ ưc dùng khi làm các phép toán này. n Mnh đ 1: Gi s f là m t hàm t ă ng tho mãn h th c truy h i f(n) = af( ) + c v i b mi n chia h t cho b, a ≥ 1, b là s nguyên l n h ơn 1, còn c là s th c d ươ ng. Khi đ ó O(nlog b a ,) a > 1 f(n) =  . O(log n ,) a = 1 n Mnh đ 2: Gi s f là hàm t ă ng tho mãn h th c truy h i f(n) = af( ) + cn d v i m i b n = b k, trong đ ó k là s nguyên d ươ ng, a ≥ 1, b là s nguyên l n h ơn 1, còn c và d là các s th c d ươ ng. Khi đ ó O(nlog b a ,) a > bd  f(n) = O(nd log n ,) a = bd .  d < d O(n ) ,a b Thí d 16: Hãy ưc l ưng s phép toán nh phân c n dùng khi nhân hai s nguyên n bit bng thu t toán nhân nhanh. Thí d 15.2 đ ã ch ra r ng f(n) = 3f(n/2) + Cn, khi n ch n. Vì th , t M nh đ 2 ta log 2 3 suy ra f(n) = O( n ). Chú ý là log 23 ≈ 1,6. Vì thu t toán nhân thông th ưng dùng O(n 2) phép toán nh phân, thu t toán nhân nhanh s th c s t t h ơn thu t toán nhân thông th ưng khi các s nguyên là đ l n. BÀI T P CH ƯƠ NG II: 1. Trong t ng s 2504 sinh viên c a m t khoa công ngh thông tin, có 1876 theo h c môn ngôn ng l p trình Pascal, 999 h c môn ngôn ng Fortran và 345 h c ngôn ng C. Ngoài ra còn bi t 876 sinh viên h c c Pascal và Fortran, 232 h c c Fortran và C, 290 hc c Pascal và C. N u 189 sinh viên h c c 3 môn Pascal, Fortran và C thì trong tr ưng h p đ ó có bao nhiêu sinh viên không h c môn nào trong 3 môn ngôn ng l p trình k trên. 35
2. Mt cu c h p g m 12 ng ưi tham d đ bàn v 3 v n đ . Có 8 ng ưi phát bi u v vn đ I, 5 ng ưi phát bi u v v n đ II và 7 ng ưi phát bi u v v n đ III. Ngoài ra, có đ úng 1 ng ưi không phát bi u v n đ nào. H i nhi u l m là có bao nhiêu ng ưi phát bi u c 3 v n đ . 3. Ch ra r ng có ít nh t 4 ng ưi trong s 25 tri u ng ưi có cùng tên h vi t t t b ng 3 ch cái sinh cùng ngày trong n ă m (không nh t thi t trong cùng m t n ă m). 4. M t tay đ ô v t tham gia thi đ u giành ch c vô đ ch trong 75 gi . M i gi anh ta có ít nh t m t tr n đ u, nh ưng toàn b anh ta có không quá 125 tr n. Ch ng t r ng có nh ng gi liên ti p anh ta đ ã đu đ úng 24 tr n. 5. Cho n là s nguyên d ươ ng b t k ỳ. Ch ng minh r ng luôn l y ra đ ưc t n s đ ã cho mt s s h ng thích h p sao cho t ng c a chúng chia h t cho n. 6. Trong m t cu c l y ý ki n v 7 v n đ , ng ưi đ ưc h i ghi vào m t phi u tr l i s n bng cách đ nguyên ho c ph đ nh các câu tr l i t ươ ng ng v i 7 v n đ đ ã nêu. Ch ng minh r ng v i 1153 ng ưi đ ưc h i luôn tìm đưc 10 ng ưi tr l i gi ng ht nhau. 7. Có 17 nhà bác h c vi t th ư cho nhau trao đ i 3 v n đ . Ch ng minh r ng luôn tìm đưc 3 ng ưi cùng trao đ i m t v n đ . 8. Trong k ỳ thi k t thúc h c ph n toán h c r i r c có 10 câu h i. Có bao nhiêu cách gán đ i m cho các câu h i n u t ng s đ i m b ng 100 và m i câu ít nh t đ ưc 5 đ i m. 9. Ph ươ ng trình x 1 + x 2 + x 3 + x 4 + x 5 = 21 có bao nhiêu nghi m nguyên không âm? 10. Có bao nhiêu xâu khác nhau có th l p đ ưc t các ch cái trong t MISSISSIPI , yêu c u ph i dùng t t c các ch ? 11. Mt giáo s ư c t b s ưu t p g m 40 s báo toán h c vào 4 chi c ng ă n t , m i ng ă n đng 10 s . Có bao nhiêu cách có th c t các t báo vào các ng ă n n u: 1) Mi ng ă n đ ưc đ ánh s sao cho có th phân bi t đ ưc; 2) Các ng ă n là gi ng h t nhau? 12. Tìm h th c truy h i cho s m t th t D n. 13. Tìm h th c truy h i cho s các xâu nh phân ch a xâu 01. 14. Tìm h th c truy h i cho s cách đ i lên n b c thang n u m t ng ưi có th b ưc m t, hai ho c ba b c m t l n. 15. 1) Tìm h th c truy h i mà R n tho mãn, trong đ ó R n là s mi n c a m t ph ng b phân chia b i n đ ưng th ng n u không có hai đ ưng nào song song và không có 3 đưng nào cùng đ i qua m t đ i m. b) Tính R n b ng ph ươ ng pháp l p. 16. Tìm nghi m c a h th c truy h i a n = 2a n-1 + 5a n-2 - 6a n-3 v i a 0 = 7, a 1 = -4, a 2 = 8. 36
CH ƯƠ NG III Đ TH Lý thuy t đ th là m t ngành khoa h c đ ưc phát tri n t lâu nh ưng l i có nhi u ng d ng hi n đ i. Nh ng ý t ưng c ơ b n c a nó đ ưc đ ưa ra t th k 18 b i nhà toán hc Th y S ĩ tên là Leonhard Euler. Ông đã dùng đ th đ gi i quy t bài toán 7 chi c cu Konigsberg n i ti ng. Đ th c ũng đ ưc dùng đ gi i các bài toán trong nhi u l ĩnh v c khác nhau. Thí d, dùng đ th đ xác đ nh xem có th c hi n m t m ch đi n trên m t b ng đi n ph ng đưc không. Chúng ta c ũng có th phân bi t hai h p ch t hóa h c có cùng công th c phân t nh ưng có c u trúc khác nhau nh đ th . Chúng ta c ũng có th xác đ nh xem hai máy tính có đ ưc n i v i nhau b ng m t đ ưng truy n thông hay không n u dùng mô hình đ th m ng máy tính. Đ th v i các tr ng s đ ưc gán cho các c nh c a nó có th dùng đ gi i các bài toán nh ư bài toán tìm đưng đi ng n nh t gi a hai thành ph trong mt m ng giao thông. Chúng ta c ũng có th dùng đ th đ l p l ch thi và phân chia kênh cho các đài truy n hình. 3.1. Đ NH NGH ĨA VÀ THÍ D . Đ th là m t c u trúc r i r c g m các đ nh và các c nh (vô h ưng ho c có hưng) n i các đ nh đó. Ng ưi ta phân lo i đ th tùy theo đ c tính và s các c nh n i các c p đ nh c a đ th . Nhi u bài toán thu c nh ng l ĩnh v c r t khác nhau có th gi i đưc b ng mô hình đ th . Ch ng h n ng ưi ta có th dùng đ th đ bi u di n s c nh tranh các loài trong m t môi tr ưng sinh thái, dùng đ th đ bi u di n ai có nh h ưng lên ai trong m t t ch c nào đó, và c ũng có th dùng đ th đ bi u di n các k t c c c a cu c thi đ u th thao. Chúng ta c ũng có th dùng đ th đ gi i các bài toán nh ư bài toán tính s các t h p khác nhau c a các chuy n bay gi a hai thành ph trong m t m ng hàng không, hay đ gi i bài toán đi tham quan t t c các đ ưng ph c a m t thành ph sao cho m i đ ưng ph đi qua đúng m t l n, ho c bài toán tìm s các màu c n thi t đ tô các vùng khác nhau c a m t b n đ . Trong đ i s ng, chúng ta th ưng g p nh ng s ơ đ , nh ư s ơ đ t ch c b máy, s ơ đ giao thông, s ơ đ h ưng d n th t đ c các ch ươ ng trong m t cu n sách, , g m nh ng đi m bi u th các đ i t ưng đ ưc xem xét (ng ưi, t ch c, đ a danh, ch ươ ng m c sách, ) và n i m t s đi m v i nhau b ng nh ng đo n th ng (ho c cong) hay nh ng mũi tên, t ưng tr ưng cho m t quan h nào đó gi a các đ i t ưng. Đó là nh ng thí d v đ th . 3.1.1. Đ nh ngh ĩa: Mt đ ơn đ th G = (V, E) g m m t t p khác r ng V mà các ph n t c a nó g i là các đ nh và m t t p E mà các ph n t c a nó g i là các c nh, đó là các cp không có th t c a các đ nh phân bi t. 37
3.1.2. Đ nh ngh ĩa: Mt đa đ th G = (V, E) g m m t t p khác r ng V mà các ph n t ca nó g i là các đ nh và m t h E mà các ph n t c a nó g i là các c nh, đó là các c p không có th t c a các đ nh phân bi t. Hai c nh đ ưc g i là c nh b i hay song song nu chúng cùng t ươ ng ng v i m t c p đ nh. Rõ ràng m i đ ơn đ th là đa đ th , nh ưng không ph i đa đ th nào c ũng là đ ơn đ th . 3.1.3. Đ nh ngh ĩa: M t gi đ th G = (V, E) g m m t t p khác r ng V mà các ph n t ca nó g i là các đ nh và m t h E mà các ph n t c a nó g i là các c nh, đó là các c p không có th t c a các đ nh (không nh t thi t là phân bi t). Vi v ∈V, n u (v,v) ∈E thì ta nói có m t khuyên t i đ nh v. Tóm l i, gi đ th là lo i đ th vô h ưng t ng quát nh t vì nó có th ch a các khuyên và các cnh b i. Đa đ th là lo i đ th vô h ưng có th ch a c nh b i nh ưng không th có các khuyên, còn đơn đ th là lo i đ th vô h ưng không ch a c nh b i ho c các khuyên. Thí d 1: v 1 v2 v3 v4 v1 v2 v3 v5 v6 v7 v4 v5 v6 Đơn đ th Gi đ th 3.1.4. Đ nh ngh ĩa: M t đ th có h ưng G = (V, E) g m m t t p khác r ng V mà các ph n t c a nó g i là các đ nh và m t t p E mà các ph n t c a nó g i là các cung, đó là các c p có th t c a các ph n t thu c V. 3.1.5. Đ nh ngh ĩa: M t đa đ th có h ưng G = (V, E) g m m t t p khác r ng V mà các ph n t c a nó g i là các đ nh và m t h E mà các ph n t c a nó g i là các cung, đó là các c p có th t c a các ph n t thu c V. Đ th vô h ưng nh n đ ưc t đ th có h ưng G b ng cách xoá b các chi u m ũi tên trên các cung đ ưc g i là đ th vô h ưng n n c a G. Thí d 2: v v v 1 2 v3 v5 v1 v2 3 V 5 v6 v7 v4 v5 v6 Đ th có h ưng Đa đ th có h ưng 38
Thí d 3: 1) Đ th “l n t ” trong sinh thái h c. Đ th đ ưc dùng trong nhi u mô hình có tính đn s t ươ ng tác c a các loài v t. Ch ng h n s c nh tranh c a các loài trong m t h sinh thái có th mô hình hóa b ng đ th “l n t ”. M i loài đ ưc bi u di n bng m t đ nh. M t c nh vô h ưng n i hai đ nh n u hai loài đ ưc bi u di n b ng các đnh này là c nh tranh v i nhau. 2) Đ th nh h ưng . Khi nghiên c u tính cách c a m t nhóm ngu i, ta th y m t s ng ưi có th có nh h ưng lên suy ngh ĩ c a nh ng ng ưi khác. Đ th có h ưng đ ưc gi là đ th nh h ưng có th dùng đ mô hình bài toán này. M i ng ưi c a nhóm đ ưc bi u di n b ng m t đ nh. Khi m t ng ưi đ ưc bi u di n b ng đ nh a có nh h ưng lên ng ưi đưc bi u di n b ng đ nh b thì có m t cung n i t đ nh a đ n đ nh b. 3) Thi đ u vòng tròn. M t cu c thi đ u th thao trong đó m i đ i đ u v i m i đ i khác đúng m t l n g i là đ u vòng tròn. Cu c thi đ u nh ư th có th đ ưc mô hình b ng m t đ th có h ưng trong đó m i đ i là m t đ nh. M t cung đi t đ nh a đ n đ nh b n u đ i a th ng đ i b. 4) Các ch ươ ng trình máy tính có th thi hành nhanh h ơn b ng cách thi hành đ ng th i mt s câu l nh nào đó. Đi u quan tr ng là không đ ưc th c hi n m t câu l nh đòi h i kt qu c a câu l nh khác ch ưa đ ưc th c hi n. S ph thu c c a các câu l nh vào các câu l nh tr ưc có th bi u di n b ng m t đ th có h ưng. M i câu l nh đ ưc bi u di n bng m t đ nh và có m t cung t m t đ nh t i m t đ nh khác n u câu l nh đ ưc bi u di n b ng đ nh th hai không th th c hi n đ ưc tr ưc khi câu l nh đ ưc bi u di n b ng đnh th nh t đ ưc th c hi n. Đ th này đ ưc g i là đ th có ưu tiên tr ưc sau . 3.2. B C C A Đ NH. 3.2.1. Đ nh ngh ĩa: Hai đ nh u và v trong đ th (vô h ưng) G=(V,E) đ ưc g i là li n k n u (u,v) ∈E. N u e = (u,v) thì e g i là c nh liên thu c v i các đ nh u và v. C nh e cũng đ ưc g i là c nh n i các đ nh u và v. Các đ nh u và v g i là các đi m đ u mút c a cnh e. 3.2.2. Đ nh ngh ĩa: B c c a đ nh v trong đ th G=(V,E), ký hi u deg(v), là s các c nh liên thu c v i nó, riêng khuyên t i m t đ nh đ ưc tính hai l n cho b c c a nó. Đnh v g i là đ nh treo n u deg(v)=1 và g i là đ nh cô l p n u deg(v)=0. Thí d 4: v1 v2 v3 v4 v v5 6 v7 Ta có deg(v 1)=7, deg(v 2)=5, deg(v 3)=3, deg(v4)=0, deg(v 5)=4, deg(v 6)=1, deg(v 7)=2. Đnh v 4 là đ nh cô l p và đ nh v 6 là đ nh treo. 39
3.2.3. M nh đ : Cho đ th G = (V, E). Khi đ ó 2|E| = ∑deg( v) . v∈V Ch ng minh: Rõ ràng m i c nh e = (u,v) đ ưc tính m t l n trong deg(u) và m t l n trong deg(v). T đ ó suy ra t ng t t c các b c c a các đ nh b ng hai l n s c nh. 3.2.4. H qu : S đ nh b c l c a m t đ th là m t s ch n. Ch ng minh: G i V 1 và V 2 t ươ ng ng là t p các đ nh b c ch n và t p các đ nh b c l ca đ th G = (V, E). Khi đ ó 2|E| = ∑deg( v) + ∑deg( v) ∈ ∈ v V1 v V2 V trái là m t s ch n và t ng th nh t c ũng là m t s ch n nên t ng th hai là m t s ch n. Vì deg(v) là l v i m i v ∈ V 2 nên |V 2| là m t s ch n. 3.2.5. M nh đ : Trong m t đ ơn đ th , luôn t n t i hai đ nh có cùng b c. Ch ng minh: Xét đ ơn đ th G=(V,E) có |V|=n. Khi đ ó phát bi u trên đ ưc đ ưa v bài toán: trong m t phòng h p có n ng ưi, bao gi c ũng tìm đưc 2 ng ưi có s ng ưi quen trong s nh ng ng ưi d h p là nh ư nhau (xem Thí d 6 c a 2.2.3). 3.2.6. Đ nh ngh ĩa: Đ nh u đ ưc g i là n i t i v hay v đ ưc g i là đ ưc n i t u trong đ th có h ưng G n u (u,v) là m t cung c a G. Đ nh u g i là đ nh đ u và đ nh v g i là đnh cu i c a cung này. 3.2.7. Đ nh ngh ĩa: B c vào (t. ư. b c ra) c a đ nh v trong đ th có h ưng G, ký hi u deg t(v) (t. ư. deg o(v)), là s các cung có đ nh cu i là v. Thí d 5: v2 v3 v1 v4 v5 v6 deg t(v 1) = 2, deg o(v 1) = 3, deg t(v 2) = 5, deg o(v 2) = 1, deg t(v 3) = 2, deg o(v 3) = 4, deg t(v 4) = 1, deg 0(v 4) = 3, deg t(v 5) = 1, deg o(v 5) = 0, deg t(v 6) = 0, deg o(v 6) = 0. Đnh có b c vào và b c ra cùng b ng 0 g i là đ nh cô l p. Đnh có b c vào b ng 1 và b c ra b ng 0 g i là đ nh treo, cung có đ nh cu i là đ nh treo g i là cung treo. 3.2.8. M nh đ : Cho G =(V, E) là m t đ th có h ưng. Khi đ ó 40
∑deg t (v) = ∑deg o (v) = |E|. v∈V v ∈ V Ch ng minh: K t qu có ngay là vì m i cung đ ưc tính m t l n cho đ nh đ u và m t ln cho đ nh cu i. 3.3. NH NG Đ ƠN Đ TH Đ C BI T. 3.3.1. Đ th đ y đ : Đ th đ y đ n đ nh, ký hi u là K n, là đ ơn đ th mà hai đ nh n(n − )1 phân bi t b t k ỳ c a nó luôn li n k . Nh ư v y, K n có c nh và m i đ nh c a K n 2 có b c là n −1. v1 v2 v v Thí d 6: 1 1 v v1 v2 v4 v3 v5 v2 1 v3 v2 K 1 K 2 V4 v3 K3 K 4 K 5 3.3.2. Đ th vòng: Đ ơn đ th n đ nh v 1, v 2, , v n (n ≥3) và n c nh (v 1,v 2), (v 2,v 3), , (v n-1,v n), (v n,v 1) đ ưc g i là đ th vòng, ký hi u là C n. Nh ư v y, m i đ nh c a C n có b c là 2. v1 v1 Thí d 7: v v v v v 1 1 2 v v 6 2 5 2 v5 v3 v3 v2 v4 v3 v4 v3 v4 C 3 C 4 C 5 C 6 3.3.3. Đ th bánh xe: T đ th vòng C n, thêm vào đ nh v n+1 và các c nh (v n+1 ,v 1), (v n+1 ,v 2), , (v n+1 ,v n), ta nh n đ ưc đ ơn đ th g i là đ th bánh xe, ký hi u là W n. Nh ư vy, đ th W n có n+1 đ nh, 2n c nh, m t đ nh b c n và n đ nh b c 3. v1 v1 Thí d 8: v1 v1 v2 v6 v2 v5 v2 v v7 v 6 v 5 4 v5 v3 v3 v2 v4 v3 v4 v3 v4 W 3 W 4 W 5 W 6 3.3.4. Đ th l p ph ươ ng: Đ ơn đ th 2 n đ nh, t ươ ng ng v i 2 n xâu nh phân đ dài n và hai đ nh k nhau khi và ch khi 2 xâu nh phân t ươ ng ng v i hai đ nh này ch khác nhau đ úng m t bit đ ưc g i là đ th l p ph ươ ng, ký hi u là Q n. Nh ư v y, m i đ nh c a n-1 Qn có b c là n và s c nh c a Q n là n.2 (t công th c 2|E| = ∑deg( v) ). v∈V 41
110 Thí d 9: 10 11 111 0 1 100 101 00 01 Q 1 Q 2 010 011 000 001 Q 3 3.3.5. Đ th phân đôi (đ th hai phe): Đ ơn đ th G=(V,E) sao cho V=V 1∪V2, V1∩V2=∅, V 1≠∅, V 2≠∅ và m i c nh c a G đ ưc n i m t đ nh trong V 1 và m t đ nh trong V 2 đ ưc g i là đ th phân đ ôi. Nu đ th phân đ ôi G=(V 1∪V2,E) sao cho v i m i v 1∈V1, v 2∈V2, (v 1,v 2)∈E thì G đ ưc g i là đ th phân đ ôi đ y đ . N u |V 1|=m, |V 2|=n thì đ th phân đ ôi đ y đ G ký hi u là K m,n . Nh ư v y K m,n có m.n c nh, các đ nh c a V 1 có b c n và các đ nh c a V 2 có b c m. Thí d 10: v1 v2 v1 v2 v3 v 3 v 4 v5 v6 v4 v5 v6 K 2,4 K 3,3 3.3.6. M t vài ng d ng c a các đ th đ c bi t: 1) Các m ng c c b (LAN): M t s m ng c c b dùng c u trúc hình sao, trong đ ó t t c các thi t b đ ưc n i v i thi t b đ i u khi n trung tâm. M ng c c b ki u này có th bi u di n b ng m t đ th phân đ ôi đ y đ K 1,n . Các thông báo g i t thi t b này t i thi t b khác đ u ph i qua thi t b đ i u khi n trung tâm. Mng c c b c ũng có th có c u trúc vòng tròn, trong đ ó m i thi t b n i v i đ úng hai thi t b khác. M ng c c b ki u này có th bi u di n b ng m t đ th vòng C n. Thông báo g i t thi t b này t i thi t b khác đ ưc truy n đ i theo vòng tròn cho t i khi đn n ơi nh n. v2 v3 v4 v1 v2 v2 v3 v8 v3 v9 v4 v5 v1 v6 v1 v7 v4 v8 v5 v7 v8 v9 v6 v5 v7 v6 C u trúc hình sao C u trúc vòng tròn C u trúc h n h p 42
Cu i cùng, m t s m ng c c b dùng c u trúc h n h p c a hai c u trúc trên. Các thông báo đ ưc truy n vòng quanh theo vòng tròn ho c có th qua thi t b trung tâm. S dư th a này có th làm cho m ng đ áng tin c y h ơn. M ng c c b ki u này có th bi u di n b ng m t đ th bánh xe W n. 2) X lý song song: Các thu t toán đ gi i các bài toán đ ưc thi t k đ th c hi n m t phép toán t i m i th i đ i m là thu t toán n i ti p. Tuy nhiên, nhi u bài toán v i s lưng tính toán r t l n nh ư bài toán mô ph ng th i ti t, t o hình trong y h c hay phân tích m t mã không th gi i đ ưc trong m t kho ng th i gian h p lý n u dùng thu t toán ni ti p ngay c khi dùng các siêu máy tính. Ngoài ra, do nh ng gi i h n v m t v t lý đi v i t c đ th c hi n các phép toán c ơ s , nên th ưng g p các bài toán không th gi i trong kho ng th i gian h p lý b ng các thao tác n i ti p. Vì v y, ng ưi ta ph i ngh ĩ đ n ki u x lý song song. Khi x lý song song, ng ưi ta dùng các máy tính có nhi u b x lý riêng bi t, mi b x lý có b nh riêng, nh đ ó có th kh c ph c đ ưc nh ng h n ch c a các máy ni ti p. Các thu t toán song song phân chia bài toán chính thành m t s bài toán con sao cho có th gi i đ ng th i đ ưc. Do v y, b ng các thu t toán song song và nh vi c s d ng các máy tính có b đ a x lý, ng ưi ta hy v ng có th gi i nhanh các bài toán ph c t p. Trong thu t toán song song có m t dãy các ch th theo dõi vi c th c hi n thu t toán, g i các bài toán con t i các b x lý khác nhau, chuy n các thông tin vào, thông tin ra t i các b x lý thích h p. Khi dùng cách x lý song song, m i b x lý có th c n các thông tin ra c a các b x lý khác. Do đ ó chúng c n ph i đ ưc k t n i v i nhau. Ng ưi ta có th dùng lo i đ th thích h p đ bi u di n m ng k t n i các b x lý trong m t máy tính có nhi u b x lý. Ki u m ng k t n i dùng đ th c hi n m t thu t toán song song c th ph thu c vào nh ng yêu c u v i vi c trao đ i d li u gi a các b x lý, ph thu c vào t c đ mong mu n và t t nhiên vào ph n c ng hi n có. Mng k t n i các b x lý đ ơn gi n nh t và c ũng đ t nh t là có các liên k t hai chi u gi a m i c p b x lý. Các m ng này có th mô hình b ng đ th đ y đ K n, trong đ ó n là s b x lý. Tuy nhiên, các m ng liên k t ki u này có s k t n i quá nhi u mà trong th c t s k t n i c n ph i có gi i h n. Các b x lý có th k t n i đ ơn gi n là s p x p chúng theo m t m ng m t chi u. Ưu đ i m c a m ng m t chi u là m i b x lý có nhi u nh t 2 đ ưng n i tr c ti p v i các b x lý khác. Nh ưc đ i m là nhi u khi c n có r t nhi u các k t n i trung gian đ các b x lý trao đ i thông tin v i nhau. P1 P2 P3 P4 P5 P6 Mng ki u l ưi (ho c m ng hai chi u) r t hay đ ưc dùng cho các m ng liên k t. Trong m t m ng nh ư th , s các b x lý là m t s chính ph ươ ng, n=m 2. Các b x lý 43
đưc gán nhãn P(i,j), 0 ≤ i, j ≤ m −1. Các k t n i hai chi u s n i b x lý P(i,j) v i b n b x lý bên c nh, t c là v i P(i,j ±1) và P(i ±1,j) ch ng nào các b x lý còn trong lưi. P(0,0) P(0,1) P(0,2) P(0,3) P(1,0) P(1,1) P(1,2) P(1,3) P(2,0) P(2,1) P(2,2) P(2,3) P(3,0) P(3,1) P(3,2) P(3,3) Mng k t n i quan tr ng nh t là m ng ki u siêu kh i. V i các m ng lo i này s m các b x lý là lu th a c a 2, n=2 . Các b x lý đ ưc gán nhãn là P 0, P 1, , P n-1. M i b x lý có liên k t hai chi u v i m b x lý khác. B x lý P i n i v i b x lý có ch s bi u di n b ng dãy nh phân khác v i dãy nh phân bi u di n i t i đ úng m t bit. M ng ki u siêu kh i cân b ng s các k t n i tr c ti p c a m i b x lý và s các k t n i gián ti p sao cho các b x lý có th truy n thông đ ưc. Nhi u máy tính đ ã ch t o theo mng ki u siêu kh i và nhi u thu t toán đ ã đưc thi t k đ s d ng m ng ki u siêu m kh i. Đ th l p ph ươ ng Q m bi u di n m ng ki u siêu kh i có 2 b x lý. P0 P1 P2 P3 P4 P5 P6 P7 3.4. BI U DI N Đ TH B NG MA TR N VÀ S Đ NG C U Đ TH : 3.4.1. Đ nh ngh ĩa: Cho đ th G=(V,E) (vô h ưng ho c có h ưng), v i V={v 1,v 2, , v n}. Ma tr n li n k c a G ng v i th t các đ nh v 1,v 2, , v n là ma tr n ∈ A= (aij )1≤i, j≤n M (n, Z) , trong đ ó a ij là s c nh ho c cung n i t v i t i v j. Nh ư v y, ma tr n li n k c a m t đ th vô h ưng là ma tr n đ i x ng, ngh ĩa là aij = a ji , trong khi ma tr n li n k c a m t đ th có h ưng không có tính đ i x ng. Thí d 11: Ma tr n li n k v i th t các đ nh v 1, v 2, v 3, v 4 là: v1 v2 0 3 0 2   3 0 1 1    0 1 1 2    v4 v3 2 1 2 0  44