Bài giảng Toán rời rạc

Nội dung text: Bài giảng Toán rời rạc

1. TOÁN RỜI RẠC CH1: Hãy cho một ví dụ về định nghĩa đệ quy? 1. Định nghĩa giai thừa của n: n! = n * (n-1)! 2. Lũy thừa nguyên của một số: an = a * an-1 CH2: Có thể ĐN hai khái niệm trên không dùng đệ quy được không? 25/08/2014 GVC, ThS.Võ Minh Đức 1
2. TOÁN RỜI RẠC CH1: Đọc giá trị của dãy số gồm các giai thừa của một số, bắt đầu từ 0: 0, 1, 2, 6, 12, 20, ,n! a1, a2, a3, a4 an 25/08/2014 GVC, ThS.Võ Minh Đức 2
3. TOÁN RỜI RẠC 1. Định nghĩa 1: V. Hệ thức truy hồi đối với dãy số Hệ {an} là công thức biểu diễn an qua thức 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 truy nghiệm của hệ thức truy hồi nếu hồi các số hạng của nó thỏa mãn hệ thức truy hồi này. 25/08/2014 GVC, ThS.Võ Minh Đức 3
4. TOÁN RỜI RẠC CÁC VÍ DỤ Ví dụ 1(Lãi kép): Giả sử một người gửi 10.000 đô la vào tài khoản của V. mình tại một ngân hàng với lãi suất Hệ kép 11% mỗi năm. Sau 30 năm anh thức ta có bao nhiêu tiền trong tài khoản của mình? truy hồi 25/08/2014 GVC, ThS.Võ Minh Đức 4
5. TOÁN RỜI RẠC GIẢI Gọi Pn là tổng số tiền có trong tài khoản V. 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 Hệ lãi suất của năm thứ n, nên ta thấy dãy thức {Pn} thoả mãn hệ thức truy hồi sau: truy Pn = Pn-1 + 0,11Pn-1 = (1,11)Pn-1 với điều kiện đầu P0 = 10.000 đô la. Từ đó hồi n suy ra Pn = (1,11) .10.000. Thay n = 30 cho ta P30 = 228922,97 đô la. 25/08/2014 GVC, ThS.Võ Minh Đức 5
6. TOÁN RỜI RẠC VÍ DỤ 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à V. không có hai số 0 liên tiếp. Hệ Có bao nhiêu xâu nhị phân như thế có độ thức dài bằng 5? truy hồi 25/08/2014 GVC, ThS.Võ Minh Đức 6
7. TOÁN RỜI RẠC GIẢI Gọi an là số các xâu nhị phân (np) độ dài n và không có hai số 0 liên tiếp. V. Ta có: Hệ Số các xâu np độ dài n và không có hai số thức 0 liên tiếp (an) = số các xâu np như thế kết thúc bằng số 1 (bn) + số các xâu np như thế truy kết thúc bằng số 0 (cn). hồi Vậy an = bn + cn (1) 25/08/2014 GVC, ThS.Võ Minh Đức 7
8. GIẢI TOÁN RỜI RẠC Giả sử n 3. * bn chính là số xâu np như thế, độ dài n − 1 và thêm số 1 vào cuối của chúng. Hỏi V. có tất cả là bao nhiêu xâu? Hệ có tất cả là an-1xâu. thức Vậy bn = ? * cn là số các xâu np có bit thứ n − 1 truy bằng 1, nếu không thì chúng có hai số 0 ở hồi hai bit cuối cùng. Hỏi có tất cả là bao nhiêu xâu như thế ? có tất cả là an-2 xâu. Vậy cn = ? 25/08/2014 GVC, ThS.Võ Minh Đức 8
9. TOÁN RỜI RẠC GIẢI Vậy: an = an-1 + an-2 với n 3. V. Hệ • n = 1 ta có 2 xâu: 0, 1. Vậy: a = 2 thức 1 • n = 2, ta có 3 xâu: ???. truy Vậy a2 = 3 hồi Khi đó a5 = a4 + a3 = a3 + a2 + a3 = 2(a2 + a1) + a2 = 13. 25/08/2014 GVC, ThS.Võ Minh Đức 9
10. TOÁN RỜI RẠC 2. Giải các hệ thức truy hồi. Định nghĩa 2: Một hệ thức truy hồi V. tuyến tính thuần nhất bậc k là hệ Hệ thức truy hồi có dạng: thức an = c1an-1 + c2an-2 + + ckan-k truy trong đó c1, c2, , ck là các số thực và c 0. hồi k 25/08/2014 GVC, ThS.Võ Minh Đức 10
11. Hệ thức truy hồi 2. Là tuyến tính vì vế phải của nó là Giải tổng các tích của các số hạng trước các nhân với một hệ số Là thuần nhất vì các số hạng đều là hệ a và hệ số đều là hằng số. thức i Có bậc k vì an được biểu diễn qua k truy số hạng đứng trước nó. hồi. 25/08/2014 GVC, ThS.Võ Minh Đức 11
12. Hệ thức truy hồi Pn = (1,11)Pn-1 là tuyến tính bậc 2. nhất Giải an = an-1+ an-2 là tuyến tính thuần các nhất bậc 2. an = an-5 là tuyến tính thuần nhất hệ bậc 5. thức Cho ví dụ một hệ thức không phải là truy hệ thức truy hồi? a0 = 3; a1 = 10 hồi. 2 an = an-1 + (an-4) 25/08/2014 GVC, ThS.Võ Minh Đức 12
13. a = rn, (r là hằng số) là nghiệm 2. n Giải của hệ thức truy hồi các an = c1an-1 + c2an-2 + + ckan-k n n-1 n-2 n-k hệ  r = c1r + c2r + + ckr thức k k-1 k-2 Hay r − c1r − c2r − − ck-1r – ck = 0. truy hồi. 25/08/2014 GVC, ThS.Võ Minh Đức 13
14. 2. Phương trình: k k-1 k-2 Giải r - c1r - c2r - Ck-1r - ck = 0 các được gọi là phương trình đặc trưng hệ của hệ thức truy hồi an = c1an-1 + c2an-2 + thức + ckan-k, nghiệm của nó gọi là nghiệm truy đặc trưng của hệ thức truy hồi. hồi. 25/08/2014 GVC, ThS.Võ Minh Đức 14
15. Mệnh đề Cho c1, c2, , ck là các số thực. Giả sử rằng 2. phương trình đặc trưng: k k-1 k-2 Giải r - c1r - c2r - ck-1r - ck = 0 các có k nghiệm phân biệt r1, r2, , rk. Khi đó dãy {an} là nghiệm của hệ thức truy hệ hồi an = c1an-1 + c2an-2 + + ckan-k thức khi và chỉ khi n n n truy an = 1r1 + 2r2 + + krk , với n = 1, 2, hồi. trong đó 1, 2, , k là các hằng số. 25/08/2014 GVC, ThS.Võ Minh Đức 15
16. Ví dụ Tìm công thức hiển của các số Fibonacci. Dãy số Fibonacci thỏa mãn hệ thức: 2. a = a + a (với đk đầu a = 0, a = 1). Giải n n-1 n-2 0 1 k = 2, c = 1, c = 1 các 1 2 Phương trình đặc trưng là: r2 – r – 1 = 0 hệ 1+ 5 1− 5 Có các nghiệm rlà=: và r = thức 1 2 2 2 truy Do đó các số Fibonacci được cho bởi công hồi. thức: 1+ 5 1− 5 a = ( )n + ( )n n 1 2 2 2 25/08/2014 GVC, ThS.Võ Minh Đức 16
17. Ví dụ Tìm công thức hiển của các số Fibonacci. 2. 1+ 5 n 1− 5 n an = 1( ) + 2 ( ) (1) Giải 2 2 Với các điều kiện đầu: a = 0 và a = 1. các 0 1 Từ (1). Ta có: α + α = 0 = a hệ 1 2 0 1+ 5 1− 5 a =1 = ( ) + ( ) thức 1 1 2 2 2 truy Từ 2 phương trình trên, ta được: hồi. 5 − 5 = , = 1 5 2 5 25/08/2014 GVC, ThS.Võ Minh Đức 17
18. Ví dụ Tìm công thức hiển của các số Fibonacci. 2. Do đó các số Fibonacci được cho bởi công Giải thức hiển sau: các 5 1+ 5 n 5 1− 5 n an = ( ) − ( ) hệ 5 2 5 2 thức truy hồi. 25/08/2014 GVC, ThS.Võ Minh Đức 18
19. Hãy tìm nghiệm của hệ thức truy hồi an = 6an- 1 - 11an-2 + 6an-3 với điều kiện ban đầu a0 = 2, a1 = 5 và a2 = 15. 2. Giải các hệ thức truy hồi. 25/08/2014 GVC, ThS.Võ Minh Đức 19
20. VI. QUAN HỆ CHIA ĐỂ TRỊ Chơi trò chơi đoán số: 1. Em hãy nghĩ trong đầu một số lớn hơn 100 và nhỏ hơn 200 (gọi SV). 2. Số em nghĩ là 150 (nhỏ hơn hoặc lớn hơn) Đây chính là bài toán chia để trị 25/08/2014 GVC, ThS.Võ Minh Đức 20
21. Khái niệm ❑ Chia: Chia bài toán cần giải thành nhiều bài toán con độc lập. VI. ❑ Trị: Giải các bài toán con Quan ❑ Tổng hợp: Xây dựng lời giải bài toán từ lời hệ giải hoặc kết quả của các bài toán con. chia Vấn đề đặt ra là giải các bài toán con như thế để nào? trị Đó chính là Vấn đề trung tâm của bài toán 25/08/2014 GVC, ThS.Võ Minh Đức 21
22. Procedure Chia_tri(n); Begin If n< n0 then giai truc tiep bai toan Else VI. Begin Quan Chia bài toán thành a bài toán con có kích hệ thước n/b For (mỗi bài toán trong a bài toán con) do chia chia_tri(n/b); để Tổng hợp lời giải từ a bài toán con để có lời giải bài toán. trị End; End; 25/08/2014 GVC, ThS.Võ Minh Đức 22
23. VÍ DỤ BÀI TOÁN tìm kiếm nhị phân. -> thuật toán VI. BÀI TOÁN nhân hai số nguyên. -> thuật Quan toán (về nhà đọc sách tr.84) hệ Các thuật toán này gọi là các thuật toán chia chia để trị. để trị 25/08/2014 GVC, ThS.Võ Minh Đức 23
24. Khái niệm Ô lớn Giả sử f(n) và g(n) là hai hàm số xác định trên tập các số nguyên dương. Nếu tồn tại VI. số nguyên dương n0 và hằng số C sao cho: Quan F(n) n0 hệ Thì ta nói hàm f(n) cùng bậc với g(n) và viết chia là: F(n) = O(g(n)) (đọc là “f(n) là Ô lớn của để g(n)”) trị 25/08/2014 GVC, ThS.Võ Minh Đức 24
25. Định lý Giả sử f là một hàm tăng thỏa mãn hệ VI. thức truy hồi f(n)= af(n/b)+c, với mọi Quan n chia hết cho b với a, b là các số nguyên và a>=1, b>1, c là số thực hệ dương. Khi đó: loga chia O(n b ) nêu a 1 f (n) = n để O(logb ) nêu a=1 trị 25/08/2014 GVC, ThS.Võ Minh Đức 25
26. Bài toán Giả sử f là một hàm tăng thỏa mãn hệ VI. thức truy hồi f(n)= 5f(n/2)+3, hãy Quan tìm f(2k), trong đó k là số nguyên dương và đánh giá f(n). hệ a 5 chia f (n) = O(nlogb ) = O(nlog2 ) để trị 25/08/2014 GVC, ThS.Võ Minh Đức 26