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

Click to edit Master text styles Second level Third level Fourth level Fifth level 25/08/2014 GVC, ThS.Võ Minh Đức ‹#› Click to edit Master title style 25/08/2014 GVC, ThS.Võ Minh Đứ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 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 3 TOÁN RỜI RẠC Định nghĩa 1: Hệ thức truy hồi đối với dãy số {an} là công thức biểu diễn an 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. V. Hệ thức truy hồi 25/08/2014 GVC, ThS.Võ Minh Đức 4 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 mình tại một 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? TOÁN RỜI RẠC V. Hệ thức truy hồi 25/08/2014 GVC, ThS.Võ Minh Đức 5 GIẢI Gọi Pn 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 {Pn} thoả mãn hệ thức truy hồi sau: Pn = Pn-1 + 0,11Pn-1 = (1,11)Pn-1 với điều kiện đầu P0 = 10.000 đô la. Từ đó suy ra Pn = (1,11)n.10.000. Thay n = 30 cho ta P30 = 228922,97 đô la. TOÁN RỜI RẠC V. Hệ thức truy hồi 25/08/2014 GVC, ThS.Võ Minh Đức 6 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à 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? TOÁN RỜI RẠC V. Hệ thức truy hồi 25/08/2014 GVC, ThS.Võ Minh Đức 7 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. Ta có: Số các xâu np độ dài n và không có hai số 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ế kết thúc bằng số 0 (cn). Vậy an = bn + cn (1) TOÁN RỜI RẠC V. Hệ thức truy hồi 25/08/2014 GVC, ThS.Võ Minh Đức 8 GIẢI 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 có tất cả là bao nhiêu xâu? * cn là số các xâu np 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. Hỏi có tất cả là bao nhiêu xâu như thế ? có tất cả là an-1xâu. Vậy bn = ? có tất cả là an-2 xâu. Vậy cn = ? TOÁN RỜI RẠC V. Hệ thức truy hồi 25/08/2014 GVC, ThS.Võ Minh Đức 9 GIẢI Vậy: an = an-1 + an-2 với n  3. n = 1 ta có 2 xâu: 0, 1. Vậy: a1 = 2 n = 2, ta có 3 xâu: ???. Vậy a2 = 3 Khi đó a5 = a4 + a3 = a3 + a2 + a3 = 2(a2 + a1) + a2 = 13. TOÁN RỜI RẠC V. Hệ thức truy hồi 25/08/2014 GVC, ThS.Võ Minh Đức 10 2. Giải các hệ thức truy hồi. Định nghĩa 2: Một hệ thức truy hồi tuyến tính thuần nhất bậc k là hệ thức truy hồi có dạng: an = c1an-1 + c2an-2 + ... + ckan-k trong đó c1, c2, ..., ck là các số thực và ck  0. TOÁN RỜI RẠC V. Hệ thức truy hồi 25/08/2014 GVC, ThS.Võ Minh Đức 11 2. Giải các hệ thức truy hồi. Là tuyến tính vì vế phải của nó là tổng các tích của các số hạng trước nhân với một hệ số Là thuần nhất vì các số hạng đều là ai và hệ số đều là hằng số. Có bậc k vì an được biểu diễn qua k số hạng đứng trước nó. Hệ thức truy hồi 25/08/2014 GVC, ThS.Võ Minh Đức 12 Pn = (1,11)Pn-1 là tuyến tính bậc nhất an = an-1+ an-2 là tuyến tính thuần nhất bậc 2. an = an-5 là tuyến tính thuần nhất bậc 5. Cho ví dụ một hệ thức không phải là hệ thức truy hồi? a0 = 3; a1 = 10 an = an-1 + (an-4)2 2. Giải các hệ thức truy hồi. Hệ thức truy hồi 25/08/2014 GVC, ThS.Võ Minh Đức 13 an = rn, (r là hằng số) là nghiệm của hệ thức truy hồi an = c1an-1 + c2an-2 + ... + ckan-k  rn = c1rn-1 + c2rn-2 + ... + ckrn-k Hay rk  c1rk-1  c2rk-2 … ck-1r – ck = 0. 2. Giải các hệ thức truy hồi. 25/08/2014 GVC, ThS.Võ Minh Đức 14 Phương trình: rk - c1rk-1 - c2rk-2 - ... Ck-1r - ck = 0 được gọi là phương trình đặc trưng của hệ thức truy hồi an = c1an-1 + c2an-2 + ... + ckan-k, nghiệm của nó gọi là nghiệm đặc trưng của hệ thức truy hồi. 2. Giải các hệ thức truy hồi. 25/08/2014 GVC, ThS.Võ Minh Đức 15 Cho c1, c2, ..., ck là các số thực. Giả sử rằng phương trình đặc trưng: rk - c1rk-1 - c2rk-2 - ... ck-1r - ck = 0 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ồi an = c1an-1 + c2an-2 + ... + ckan-k khi và chỉ khi an = 1r1n + 2r2n + ... + krkn, với n = 1, 2, ... trong đó 1, 2, ..., k là các hằng số. 2. Giải các hệ thức truy hồi. Mệnh đề 25/08/2014 GVC, ThS.Võ Minh Đức 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: an = an-1 + an-2 (với đk đầu a0 = 0, a1 = 1). k = 2, c1 = 1, c2 = 1 Phương trình đặc trưng là: r2 – r – 1 = 0 Có các nghiệm là : Do đó các số Fibonacci được cho bởi công thức: 2. Giải các hệ thức truy hồi. 25/08/2014 GVC, ThS.Võ Minh Đức 17 Ví dụ Tìm công thức hiển của các số Fibonacci. Với các điều kiện đầu: a0 = 0 và a1 = 1. Từ (1). Ta có: α1+ α2 = 0 = a0 Từ 2 phương trình trên, ta được: 2. Giải các hệ thức truy hồi. 25/08/2014 GVC, ThS.Võ Minh Đức 18 Ví dụ Tìm công thức hiển của các số Fibonacci. Do đó các số Fibonacci được cho bởi công thức hiển sau: 2. Giải các hệ thức truy hồi. 25/08/2014 GVC, ThS.Võ Minh Đức 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 20 Chơi trò chơi đoán số: Em hãy nghĩ trong đầu một số lớn hơn 100 và nhỏ hơn 200 (gọi SV). Số em nghĩ là 150 (nhỏ hơn hoặc lớn hơn) … Đây chính là bài toán chia để trị VI. QUAN HỆ CHIA ĐỂ TRỊ 25/08/2014 GVC, ThS.Võ Minh Đức 21 Chia: Chia bài toán cần giải thành nhiều bài toán con độc lập. Trị: Giải các bài toán con Tổng hợp: Xây dựng lời giải bài toán từ lời giải hoặc kết quả của các bài toán con. Vấn đề đặt ra là giải các bài toán con như thế nào? Đó chính là Vấn đề trung tâm của bài toán Khái niệm VI. Quan hệ chia để trị 25/08/2014 GVC, ThS.Võ Minh Đức 22 Procedure Chia_tri(n); Begin If n thuật toán BÀI TOÁN nhân hai số nguyên. -> thuật toán (về nhà đọc sách tr.84) Các thuật toán này gọi là các thuật toán chia để trị. VÍ DỤ VI. Quan hệ chia để trị 25/08/2014 GVC, ThS.Võ Minh Đức 24 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 số nguyên dương n0 và hằng số C sao cho: F(n) n0 Thì ta nói hàm f(n) cùng bậc với g(n) và viết là: F(n) = O(g(n)) (đọc là “f(n) là Ô lớn của g(n)”) VI. Quan hệ chia để trị Khái niệm Ô lớn 25/08/2014 GVC, ThS.Võ Minh Đức 25 Giả sử f là một hàm tăng thỏa mãn hệ thức truy hồi f(n)= af(n/b)+c, với mọi 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 dương. Khi đó: Định lý VI. Quan hệ chia để trị 25/08/2014 GVC, ThS.Võ Minh Đức 26 Giả sử f là một hàm tăng thỏa mãn hệ thức truy hồi f(n)= 5f(n/2)+3, hãy tìm f(2k), trong đó k là số nguyên dương và đánh giá f(n). Bài toán VI. Quan hệ chia để trị