Giáo trình Toán rời rạc - Vũ Kim Thành

Nội dung text: Giáo trình Toán rời rạc - Vũ Kim Thành

1. Procedure nguyento(m); Input: S nguyên d ươ ng m; Output: True, n u m là s nguyên t ; False, n u m không ph i là s nguyên t ; begin i := 2; while i ≤ m do begin if m mod i = 0 then nguyento := false else nguyento := true; i := i+1; end; end; Cách th hai: repeat câu l nh ho c kh i câu l nh until ñiu ki n; Khi th c hi n, câu l nh (kh i câu l nh) ñưc th c hi n, sau ñó ñiu ki n ñưc ki m tra, n u ñiu ki n sai thì vòng l p ñưc th c hi n, n u ñiu ki n ñúng thì vòng l p d ng và cho k t qu . Thí d : Thu t toán Ơ-clit tìm ưc s chung l n nh t c a hai s nguyên d ươ ng a, b nh ư sau: Gi s a > b và a chia cho b ñưc th ươ ng là q và s d ư là r, trong ñó a, b, q, r là các s nguyên d ươ ng: a = bq + r suy ra: ƯCLN(a, b) = ƯCLN(b, r) và s d ư cu i cùng khác không là ưc s chung l n nh t c a a và b. Th t v y: Gi s d là ưc s chung c a hai s nguyên d ươ ng a và b, khi ñó: r = a – bq chia h t cho d. V y d là ưc chung c a b và r. Ng ưc l i, n u d là ưc s chung c a b và r, khi ñó do bq + r = a c ũng chia h t cho d. Vy d là ưc s chung c a a và b. Ch ng h n, mu n tìm ưc s chung l n nh t c a 111 và 201 ta làm nh ư sau: 201 = 1. 111 + 90 111 = 1. 90 + 21 90 = 4. 21 + 6 21 = 3. 6 + 3 6 = 2. 3 Vy ƯCLN(111, 201) = 3 (3 là s d ư cu i cùng khác 0). Function UCLN(a, b) Input: a, b là 2 s nguyên d ươ ng; Output: UCLN(a, b); begin Tr ưng ð i h c Nông nghi p Hà N i – Giáo trình Giáo trình Toán R i r c . 10
2. x := a; y : = b; repeat begin r := x mod y; (* r là ph n d ư khi chia x cho y *) x : = y; y := r ; if y ≠ 0 then uc := y; end; until y = 0; UCLN := uc; end ; Chú ý: Khi gi i các bài toán ph c t p thì th ưng ph i phân chia bài toán ñó thành các bài toán nh h ơn g i là các bài toán con. Khi ñó ph i xây d ng các th t c ho c hàm ñ gi i các bài toán con ñó, sau ñó t p h p các bài toán con này ñ gi i bài toán ban ñu ñã ñt ra. Thu t ng tin h c g i các ch ươ ng trình gi i bài toán con ñó là các ch ươ ng trình con. Thí d : Tìm s nguyên t nh nh t l n h ơn s nguyên d ươ ng m ñã cho. Procedure So_nguyen_to_lon_hon(m); Input: S nguyên d ươ ng m; Output: n là s nguyên t nh nh t l n h ơn m; begin n := m + 1; while nguyento(n) = false do n := n + 1; end; 4. ð ph c t p c a thu t toán Có hai lý do làm cho m t thu t toán ñúng có th không th c hi n ñưc trên máy tính. ðó là do máy tính không ñ b nh ñ th c hi n ho c th i gian tính toán quá dài. T ươ ng ng v i hai lý do trên ng ưi ta ñưa ra hai khái ni m: - ð ph c t p không gian c a thu t toán, ñ ph c t p này g n li n v i các c u trúc d li u ñưc s d ng. V n ñ này không thu c ph m vi c a môn h c này. - ð ph c t p th i gian c a thu t toán, ñ ph c t p này ñưc th hi n qua s l ưng các câu l nh v các phép gán, các phép tính s h c, phép so sánh, ñưc s d ng trong thu t toán khi các giá tr ñ u vào có kích th ưc ñã cho. 4.1. Khái ni m ñ t ăng c a hàm Tr ưc h t xét thí d : Gi s th i gian tính toán c a m t thu t toán ph thu c vào kích th ưc n c a ñ u vào theo công th c: t(n) = 60n 2 + 9n + 9 Tr ưng ð i h c Nông nghi p Hà N i – Giáo trình Giáo trình Toán R i r c . 11
3. Bng sau cho th y khi n l n, t(n) x p x s h ng 60n 2 : n t(n) = 60n 2 + 9n + 9 60n 2 10 9099 6000 100 600 909 600 000 1 000 60 009 009 60 000 000 10 000 6 000 090 009 6 000 000 000 ðnh ngh ĩa: Cho f(x) và g(x) là hai hàm t t p s nguyên hoc t p s th c vào t p các s th c. Ng ưi ta nói f(x) là O(g(x)) hay f(x) có quan h big-O v i g(x), ký hi u f(x) = O(g(x)), n u t n t i hai h ng s C và k sao cho: | f(x) | ≤ C. | g(x) |, ∀x ≥ k. Thí d 1. t(n) = 60n 2 + 9n + 9 = O(n 2) Th t v y: ∀n ≥ 1, ta có: | 60n 2 + 9n +9| = 60n 2 + 9n +9  9 9  = n2 60 + +   n n2  ≤ n 2 (60 + 9 + 9) = 78n 2. V y C = 78; k = 1. T ươ ng t ta có th ch ng minh: n n-1 n Pn(x) = a 0x + a 1x + + a n = O(x ) , x ∈ R. Thí d 2. f(n) = 1 + 2 + 3 + + n k 1 | f 2(x)| ≤ C2 | g 2(x)) | , ∀x > k 2 Ch n k = max(k 1; k 2) thì c hai b t ñ ng th c ñ u tho mãn. Do ñó: 1) |(f 1 + f 2)(x)| = |f 1(x) + f 2(x)| ≤ |f 1(x)| + |f 2(x)| ≤ ≤ C 1|g 1(x)| + C 2|g 2(x)| ≤ (C 1 + C 2)g(x) ñây g(x) = max{|g 1(x)|, |g 2(x)|}. Tr ưng ð i h c Nông nghi p Hà N i – Giáo trình Giáo trình Toán R i r c . 12
4. 2) |(f 1.f 2)(x)| = |f 1(x)|.|f 2(x)| ≤ C 1C2 |g 1(x)|.|g 2(x)| = C 1C2|g 1(x)g 2(x)| H qu : N u f 1(x) = O(g(x)), f 2(x) = O(g(x)) thì (f 1+f 2)(x) = O(g(x)) Thí d . Cho ñánh giá O c a các hàm: 3 1/ f(n) = 2nlg(n!) + (n + 3)lgn , n ∈ N. 2/ f(x) = (x + 1)lg(x 2 + 1) + 3x 2 , x ∈ R. Gi i: 1) Ta có: lg(n!) = O(nlgn) ⇒ 2nlg(n!) = O(n 2lgn) (n 3 + 3)lgn = O(n 3lgn) V y f(n) = O(n 3lgn) 2) Ta có: lg(x 2 + 1) ≤ lg2x 2 = lg2 + 2lgx ≤ 3lgx , ∀x > 1 ⇒ lg(x 2 + 1) = O(lgx) ⇒ (x + 1)lg(x 2 + 1) = O(xlgx) Mt khác: 3x 2 = O(x 2) và max{xlgx; x 2} = x 2. Vy f(x) = O(x 2). 4.3. ð ph c t p c a thu t toán Nh ư ñã nói ph n ñ u c a m c 4, chúng ta ch ñ c p ñ n ñ ph c t p v th i gian ca thu t toán. ð ph c t p v th i gian c a thu t toán ñưc ñánh giá qua s l ưng các phép toán mà thu t toán s d ng. Vì v y ph i ñ m các phép toán có trong thu t toán. Các phép toán ph i ñ m là: - Các phép so sánh các s nguyên ho c s th c; - Các phép tính s h c: c ng, tr , nhân, chia; - Các phép gán; - Và b t k ỳ m t phép tính s ơ c p nào khác xu t hi n trong quá trình tính toán. Gi s s các phép toán c a thu t toán là f(n), trong ñó n là kích th ưc ñ u vào, khi ñó ng ưi ta th ưng quy ñ ph c t p v th i gian c a thu t toán v các m c: • ð ph c t p O(1), g i là ñ ph c t p h ng s , n u f(n) = O(1). • ð ph c t p O(logan), g i là ñ ph c t p logarit, n u f(n) = O(log an). ( ðiu ki n a > 1) • ð ph c t p O(n), g i là ñ ph c t p tuy n tính, n u f(n) = O(n). • ð ph c t p O(nlog an), g i là ñ ph c t p nlogarit n u f(n) = O(log an). ( ðiu ki n a > 1) • ð ph c t p O(n k), g i là ñ ph c t p ña th c, n u f(n) = O(n k). • ð ph c t p O(a n), g i là ñ ph c t p m ũ, n u f(n) = O(a n). ( ðiu ki n a > 1) • ð ph c t p O(n!), g i là ñ ph c t p giai th a, n u f(n) = O(n!). Thí d 1. Tìm ñ ph c t p c a thu t toán ñ gi i bài toán: Tìm s l n nh t trong dãy n s nguyên a 1, a 2, , a n ñã cho: Procedure max(a 1, a 2, , a n); Input: Dãy s a 1, a 2, , a n; Output: S l n nh t (max) c a dãy s ñã cho; begin max := a 1; for i := 2 to n do Tr ưng ð i h c Nông nghi p Hà N i – Giáo trình Giáo trình Toán R i r c . 13
5. if a i > max then max := a i; end; M i b ưc c a vòng l p for ph i th c hi n nhi u nh t 3 phép toán: phép gán bi n ñiu khi n i, phép so sánh a i v i max và có th là phép gán a i vào max; vòng l p có (n – 1) bưc (i = 2, 3, , n) do ñó nhi u nh t có c th y 3(n - 1) phép toán ph i th c hi n. Ngoài ra thu t toán còn ph i th c hi n phép gán ñ u tiên max := a 1. Vy s phép toán nhi u nh t mà thu t toán ph i th c hi n là: 3(n – 1) + 1 = 3n – 2 = O(n) ð ph c t p v th i gian c a thu t toán là ñ ph c t p tuy n tính. Thí d 2. ð ph c t p c a thu t toán nhân ma tr n. Procedure nhân_matran; Input: 2 ma tr n A = (a ij )m x p và B = (b ij )p x n ; Output: ma tr n tích AB = (c ij )m x n ; Begin for i:=1 to m do for j:=1 to n do begin cij := 0; for k:=1 to p do c ij := c ij + a ik bkj ; end; End. S phép c ng và s phép nhân trong thu t toán trên là: V i m i ph n t c ij ph i th c hi n p phép nhân và p phép c ng. Có t t c m.n ph n t c ij , v y ph i th c hi n 2mnp phép cng và phép nhân. ð xác ñ nh ñ ph c t p c a thu t toán, ta gi s A, B là hai ma tr n vuông c p n, ngh ĩa là m = n = p. nh ư v y ph i c n 2n 3 phép c ng và phép nhân. V y ñ ph c t p c a thu t toán là O(n 3) – ñ ph c t p ña th c. M t ñiu thú v là, khi nhân t 3 ma tr n tr lên thì s phép tính c ng và nhân ph thu c vào th t nhân các ma tr n y. Ch ng h n A, B, C là các ma tr n có kích th ưc tươ ng ng là 30 ×20, 20 ×40, 40 ×10. Khi ñó: Nu th c hi n theo th t ABC =A(BC) thì tích BC là ma tr n kích th ưc 20 ×10 và cn th c hi n 20.40.10 = 8000 phép tính c ng và nhân. Ma tr n A(BC) có kích th ưc 30 ×10 và c n th c hi n 30.20.10 = 6000 phép c ng và nhân. T ñó suy ra c n th c hi n 8000+6000 = 14000 phép tính c ng và nhân ñ hoàn thành tích ABC. Tươ ng t , n u th c hi n theo th t ABC = (AB)C thì c n th c hi n 30.20.40 phép tính c ng và nhân ñ th c hi n tích AB và 30.40.10 phép c ng và nhân ñ th c hiên tích (AB)C. Do ñó s các phép tính c ng và nhân ph i th c hi n ñ hoàn thành tích ABC là 24000+12000 = 36000 phép tính. Rõ ràng hai cách nhân cho k t qu v s l ưng các phép tính ph i th c hi n là khác nhau. Tr ưng ð i h c Nông nghi p Hà N i – Giáo trình Giáo trình Toán R i r c . 14
6. 5. Thu t toán tìm ki m Bài toán tìm ki m ñưc phát bi u nh ư sau: Tìm trong dãy s a 1, a 2, , a n m t ph n t có giá tr b ng s a cho tr ưc và ghi l i v trí c a ph n t tìm ñưc. Bài toán này có nhi u ng d ng trong th c t . Ch ng h n vi c tìm ki m t trong t ñin, vi c ki m tra l i chính t c a m t ñon v ăn b n, Có hai thu t toán c ơ b n ñ gi i bài toán này: Thu t toán tìm ki m tuy n tính và thu t toán tìm ki m nh phân. Chúng ta l n l ưt xét các thu t toán này. 5.1. Thu t toán tìm ki m tuy n tính (còn g i là thu t toán tìm ki m tu n t ). ðem so sánh a l n l ưt v i a i (i = 1, 2, , n) n u g p m t giá tr a i = a thì ghi l i v trí ca a i, n u không g p giá tr a i = a nào (a i ≠ a. ∀i) thì trong dãy không có s nào b ng a. Procedure Tim_tuyen_tinh_phan_tu_bang_a; Input: a và dãy s a 1, a 2, , a n; Output: V trí ph n t c a dãy có giá tr b ng a, ho c là s 0 n u không tìm th y a trong dãy; begin i := 1; while (i ≤ n and a i ≠ a) do i := i + 1; if i ≤ n then vitri := i else vitri := 0; end; Nh ư v y n u a ñưc tìm th y v trí th i c a dãy (a i = a) thì câu l nh i := i + 1 trong vòng l p while ñưc th c hi n i l n (i = 1, 2, , n). N u a không ñưc tìm th y, câu l nh ph i th c hi n n l n. V y s phép toán trung bình mà thu t toán ph i th c hi n là: 1 + 2 + + n n(n + 1) n + 1 = = = O(n) n 2n 2 V y, ñ ph c t p c a thu t toán tìm ki m tuy n tính là ñ ph c t p tuy n tính. 5.2. Thu t toán tìm ki m nh phân. Gi thi t r ng các ph n t c a dãy ñưc x p theo th t t ăng d n. Khi ñó so sánh a 1+ n  vi s gi a dãy, n u a a m thì tìm a trong dãy am+1 , , a n. ði v i m i dãy con (m t n a c a dãy ñã cho) ñưc làm t ươ ng t ñ ch ph i tìm ph n t có giá tr b ng a m t n a dãy con ñó. Quá trình tìm ki m k t thúc khi tìm th y v trí c a ph n t có giá tr b ng a ho c khi dãy con ch còn 1 ph n t . Ch ng h n vi c tìm s 8 trong dãy s 5, 6, 8, 9, 11, 12, 13, 15, 16, 17, 18, 19, 20, 22 ñưc ti n hành nh ư sau: Dãy ñã cho g m 14 s h ng, chia dãy thành 2 dãy con: 5, 6, 8, 9, 11, 12, 13 và 15, 16, 17, 18, 19, 20, 22 Tr ưng ð i h c Nông nghi p Hà N i – Giáo trình Giáo trình Toán R i r c . 15
7. Vì 8 a m then i := m+1 else j := m; end; if a = a i then vitri := i else vitri := 0; end; ð ph c t p c a thu t toán tìm ki m nh phân ñưc ñánh giá như sau: Không gi m k tng quát có th gi s ñ dài c a dãy a 1, a 2, , a n là n = 2 v i k là s nguyên d ươ ng. (N u n không ph i là l ũy th a c a 2, luôn tìm ñưc s k sao cho 2 k – 1 < n < 2 k do ñó có th xem dãy ñã cho là m t ph n c a dãy có 2 k ph n t ). Nh ư v y ph i th c hi n nhi u nh t k ln chia ñôi các dãy s (m i n a dãy c a l n chia ñôi th nh t có 2 k – 1 ph n t , c a l n chia ñôi th hai có 2 k – 2 ph n t , , và c a l n chia ñôi th k là 2 k – k = 2 0 = 1 ph n t ). Nói cách khác là nhi u nh t có k vòng l p while ñưc th c hi n trong thu t toán tìm ki m nh phân. Trong m i vòng l p while ph i th c hi n hai phép so sánh, và vòng l p cu i cùng khi ch còn 1 ph n t ph i th c hi n 1 phép so sánh ñ bi t không còn 1 ph n t nào thêm n a và 1 phép so sánh ñ bi t a có ph i là ph n t ñó hay không. T ñó th y r ng thu t toán ph i th c hi n nhi u nh t 2k + 2 = 2[log 2n] + 2 = O(logn) phép so sánh. V y, ñ ph c t p c a thu t toán tìm kim nh phân là ñ ph c t p logarit. 6. Thu t toán ñ quy 6.1. Công th c truy h i ðôi khi r t khó ñ nh ngh ĩa m t ñ i t ưng nào ñó m t cách t ưng minh, nh ưng có th ñnh ngh ĩa ñ i t ưng ñó qua chính nó v i ñ u vào nh h ơn. Cách ñnh ngh ĩa nh ư v y g i là cách ñnh ngh ĩa b ng truy h i ho c ñ nh ngh ĩa b ng ñ quy và nó cho m t công th c g i là công th c truy h i. Tr ưng ð i h c Nông nghi p Hà N i – Giáo trình Giáo trình Toán R i r c . 16
8. ðnh ngh ĩa: ðnh ngh ĩa b ng truy h i bao g m các quy t c ñ xác ñ nh các ñ i tưng, trong ñó có m t s quy t c dùng ñ xác ñ nh các ñ i t ưng ban ñu g i là các ñiu ki n ban ñ u; còn các quy t c khác dùng ñ xác ñ nh các ñ i t ưng ti p theo g i là công th c truy h i. Thí d 1. Dãy s a n ñưc ñ nh ngh ĩa b ng ñ quy nh ư sau: a0 = 3; a n = a n – 1 + 3. Trong ñó a 0 = 3 là ñiu ki n ban ñ u, còn a n = a n – 1 + 3 là công th c truy h i. Thí d 2. ðnh ngh ĩa b ng ñ quy giai th a c a s t nhiên n là: GT(0) = 1; GT(n) = n.GT(n – 1). Vì GT(n) = n! = n(n-1)(n-2) 1 = n.GT(n-1). Trong ñó GT(0) = 1 là ñiu ki n ban ñ u, còn GT(n) = n.GT(n – 1) là công thc truy h i. Thí d 3. Dãy s F 0, F 1, F 2, , F n ñưc ñ nh ngh ĩa: F0 = 0; F 1 = 1; F n = F n – 1 + F n – 2 . ðó chính là ñnh ngh ĩa b ng ñ quy c a dãy s có tên là dãy Fibonacci. Trong ñó F0 = 0, F 1 = 1 là các ñiu ki n ban ñ u, còn F n = F n – 1 + F n – 2 là công th c ñ quy. D th y m t s s h ng ñ u tiên c a dãy là: 0; 1; 1; 2; 3; 5; 8; 13; 21; 6.2. Thu t toán ñ quy. Nhi u khi vi c gi i bài toán v i ñ u vào xác ñnh có th ñưa v vi c gi i bài toán ñó vi giá tr ñ u vào nh h ơn. Ch ng h n: n! = n . (n-1)! hay UCLN(a, b) = UCLN(a mod b, b) , a > b ðnh ngh ĩa: M t thu t toán g i là ñ quy n u thu t toá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 v i d li u ñ u vào nh hơn. D th y c ơ s c a thu t toán là công th c truy h i. Thí d 1. Tính giai th a c a s t nhiên n b ng ñ quy. Function GT(n); Input: S t nhiên n; Output: Giá tr c a n!; Begin if n = 0 then GT(0) := 1 else GT(n) := n*GT(n – 1); End; Thí d 2. Tính s h ng c a dãy Fibonacci b ng ñ quy. Function Fibonacci(n); Input: V trí th n c a dãy Fibonacci; Output: Giá tr F n c a dãy Fibonaci; Begin Tr ưng ð i h c Nông nghi p Hà N i – Giáo trình Giáo trình Toán R i r c . 17
9. if n = 0 then Fibonacci(0) := 0 else if n = 1 then Fibonacci(1) := 1 else Fibonacci(n) := Fibonacci(n-1) + Fibonacci(n-2); End; Thí d 3. Thu t toán ñ quy tìm UCLN(a, b). Function UCLN(a, b); Input: Hai s nguyên d ươ ng a và b; Output: Ưc s chung l n nh t c a a và b; Begin if b = 0 then UCLN(a, b) := a else if a > b then UCLN(a, b) := UCLN(a mod b, b) else UCLN(a, b) := UCLN(b mod a, a); End; Bây gi chúng ta th tìm ñ ph c t p v th i gian c a m t vài thu t toán vi t b ng ñ quy. Ch ng h n xét thu t toán ñ quy tính s h ng c a dãy Fibonacci, ñ tính 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. Quá trình ti p t c nh ư v y cho ñ n khi F 0 và F 1 xu t hi n thì ñưc thay b ng các giá tr c a chúng trong ñ nh ngh ĩa. Mi b ưc ñ quy cho t i khi F 0 và F 1 xu t hi n, các s Fibonacci ñưc tính hai l n. Ch ng h n gi n ñ cây hình 2 cho ta hình dung cách tính F 5 theo thu t toán ñ quy. T ñó có th th y r ng ñ tính F n c n th c hi n F n + 1 – 1 phép c ng. F 5 F F 4 3 F 3 F 2 F 2 F 1 F 2 F1 F 1 F0 F1 F 0 F 1 F 0 Hình 2. L ưc ñ tính F 5 b ng ñ quy ð ph c t p c a thu t toán ñ quy tìm ưc s chung l n nh t c a hai s nguyên dươ ng a, b (thí d 3): UCLN(a,b) = UCLN(a mod b,b), n u a ≥ b (a mod b là ph n d ư khi chia a cho b) ñưc ñánh giá b ng cách ng d ng dãy Fibonacci. Tr ưc h t b ng quy n p toán h c chúng ta ch ng minh s h ng t ng quát c a dãy Fibonacci th a mãn: Tr ưng ð i h c Nông nghi p Hà N i – Giáo trình Giáo trình Toán R i r c . 18
10. n – 2 1 + 5 F n > α , ∀n ≥ 3, trong ñó α = . (1) 2 Th t v y: Ta có: α α ñúng v i n, xét v i n+1. D th y α là m t nghi m c a ph ươ ng trình x2 – x – 1 = 0 nên suy ra α2 = α + 1. T ñó: αn – 1 = α2αn – 3 = ( α + 1) αn – 3 = αn – 2 + αn – 3 . n – 3 n – 2 Theo gi thi t quy n p, n u n ≥ 4, ta có F n – 1 > α và F n > α . Thay vào ñnh ngh ĩa c a dãy Fibonacci: n – 2 n – 3 n – 1 Fn + 1 = F n + F n – 1 > α + α = α n – 2 V y F n > α , ∀n ≥ 3. Công th c (1) ñưc ch ng minh. Tr l i thu t toán ñ quy tìm ưc s chung l n nh t c a hai s nguyên d ươ ng a, b (a ≥ b). ð ph c t p c a thu t toán ñưc ñánh giá qua s l ưng các phép chia dùng trong thu t toán này. ðt r 0 = a, r 1 = b, ta có: r 0 = r 1q1 + r 2; 0 ≤ r 2 α v i n > 2 và α = nên b > α . 2 n −1 1 T ñó: lgb > (n – 1) lg α > ( vì lg α ≈ 0,208 > ). 5 5 Vy: n – 1 < 5lgb ⇒ n < 5lgb + 1 = O(lgb). Tr ưng ð i h c Nông nghi p Hà N i – Giáo trình Giáo trình Toán R i r c . 19