Bài giảng Toán rời rạc trình bày về hệ thức truy hồi và quan hệ chia để trị trong Toán rời rạc. Tài liệu giúp các bạn củng cố thêm kiến thức về Toán rời rạc là nền tảng cho việc học nhiều môn khoa học tự nhiên sau này. | 25/08/2014 GVC, 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? Chưong IV: Bài toán tìm luồng cực đại trên mạng GV: Võ Minh Đức 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. 25/08/2014 GVC, 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 Chưong IV: Bài toán tìm luồng cực đại trên mạng GV: Võ Minh Đức 2 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. 25/08/2014 GVC, 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 Chưong IV: Bài toán tìm luồng cực đại trên mạng GV: Võ Minh Đức 3 Khái niệm mở đầu và mô hình hóa bằng hệ thức truy hồi: | 25/08/2014 GVC, 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? Chưong IV: Bài toán tìm luồng cực đại trên mạng GV: Võ Minh Đức 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. 25/08/2014 GVC, 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 Chưong
