Giáo trình Toán rời rạc - Trần Thanh Tuân

pdf

168 trang huongle 3280

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 - Trần Thanh Tuân", để 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_tran_thanh_tuan.pdf

Nội dung text: Giáo trình Toán rời rạc - Trần Thanh Tuân

Đ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