tailieunhanh - Bài giảng Toán rời rạc: Bài 5 - Vũ Thương Huyền

Bài giảng Toán rời rạc: Bài 5 - Vũ Thương Huyền cung cấp cho học viên các kiến thức về kỹ thuật đếm cao cấp; hệ thức truy hồi; mô hình hóa bằng các hệ thức truy hồi; giải các hệ thức truy hồi; nguyên lý bù trừ và dạng khác của nguyên lí bù trừ; hệ thức truy hồi tuyến tính; . Mời các bạn cùng tham khảo chi tiết nội dung bài giảng! | BÀI 5 KỸ THUẬT ĐẾM CAO CẤP Vũ Thương Huyền huyenvt@ 1 NỘI DUNG Hệ thức truy hồi Giải các hệ thức truy hồi Nguyên lý bù trừ Toán rời rạc huyenvt@ 2 HỆ THỨC TRUY HỒI Toán rời rạc huyenvt@ 3 CÁC HỆ THỨC TRUY HỒI Một số bài toán đếm không thể giải được bằng kĩ thuật đếm thông thường Có thể giải bằng cách tìm mối quan hệ gọi là các hệ thức truy hồi Toán rời rạc huyenvt@ 4 CÁC HỆ THỨC TRUY HỒI Định nghĩa 1 Hệ thức truy hồi đối với dãy số an là phương trình biểu diễn an qua một hay nhiều số hạng đứng trước nó cụ thể là a0 a1 . an-1 với mọi số nguyên n n0 trong đó n0 là một số nguyên không âm. Dãy số được gọi là lời giải hay là 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. Toán rời rạc huyenvt@ 5 CÁC HỆ THỨC TRUY HỒI Ví dụ 1 Cho an là dãy số thỏa mãn hệ thức truy hồi an an-1 an-2 với n 2 3 4 . và giả sử a0 3 a1 5. Tìm a2 a3. Ví dụ 2 Hãy xác định xem dãy an trong đó an 3n với mọi n nguyên không âm có phải là lời giải của hệ thức truy hồi an 2an-1 an-2 với n 2 3 4. hay không Cũng câu hỏi như vậy đối với an 2n và an 5 Toán rời rạc huyenvt@ 6 MÔ HÌNH HÓA BẰNG CÁC HỆ THỨC TRUY HỒI Ví dụ 1 Lãi kép. Giả sử một người gửi 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. Hỏi sau 30 năm anh ta có bao nhiêu tiền trong tài khoản của mình Giải - Gọi Pn là tổng số tiền có trong tài khoản sau n năm Pn Pn-1 1 11Pn-1 - Như vậy - P1 1 11P0 - P2 1 11P1 1 11 2 P0 - . - Pn 1 11Pn-1 1 11 n P0 - Thay n 30 vào công thức P30 1 11 30 . 10000 228 923 Toán rời rạc huyenvt@ 7 MÔ HÌNH HÓA BẰNG CÁC HỆ THỨC TRUY HỒI Ví dụ 2 Họ nhà thỏ và các số Fibonacci. Mỗi cặp thỏ mới sinh được thả trên một hòn đảo. Giả sử rằng một cặp thỏ chưa sinh sản được trước khi đầy 2 tháng tuổi. Kể từ khi chúng đầy 2 tháng tuổi mỗi tháng chúng đẻ được một đôi thỏ con. Tìm công thức truy hồi tính số cặp thỏ trên đảo sau n tháng với giả sử các con thỏ là trường thọ. Toán rời rạc .