Nội dung bài giảng: 1. Đệ quy và hệ thức truy hồi 2. Phân tích độ phức tạp giải thuật 3. Phân tích giải thuật lặp 4. Phân tích giải thuật đệ quy 5. Chiến lược thiết kế giải thuật 6. Thiết kế giải thuật kiểu “trực tiếp” (bruce-force) | Môn học: Phân tích và Thiết kế Giải thuật BÀI GIẢNG ĐIỆN TỬ TS. Phạm văn Chung Khoa CNTT, Nghiệp Biên soạn theo bài giảng: . Dương Tuấn Anh ĐH. Bách Khoa Tp HCM Tài liệu tham khảo [1] Cormen, T. H., Leiserson, C. E, and Rivest, R. L., Introduction to Algorithms, The MIT Press, 1997. [2] Levitin, A., Introduction to the Design and Analysis of Algorithms, Addison Wesley, 2003 [3] Sedgewick, R., Algorithms in C++, Addison-Wesley, 1998 [4] Giáo trình PTTKGT ĐH. Cần thơ Đề cương Môn học Các khái niệm căn bản Chiến lược chia-để-trị Chiến lược giảm-để-trị Chiến lược biến thể-để-trị Qui hoạch động và giải thuật tham lam Giải thuật quay lui Vấn đề NP-đầy đủ Giải thuật xấp xỉ Chương 1 CÁC KHÁI NIỆM CĂN BẢN Môn học: Phân tích và thiết kế giải thuật Nội dung Đệ quy và hệ thức truy hồi Phân tích độ phức tạp giải thuật Phân tích giải thuật lặp Phân tích giải thuật đệ quy Chiến lược thiết kế giải thuật Thiết kế giải thuật kiểu “trực tiếp” (bruce-force) 1. Đệ . | Môn học: Phân tích và Thiết kế Giải thuật BÀI GIẢNG ĐIỆN TỬ TS. Phạm văn Chung Khoa CNTT, Nghiệp Biên soạn theo bài giảng: . Dương Tuấn Anh ĐH. Bách Khoa Tp HCM Tài liệu tham khảo [1] Cormen, T. H., Leiserson, C. E, and Rivest, R. L., Introduction to Algorithms, The MIT Press, 1997. [2] Levitin, A., Introduction to the Design and Analysis of Algorithms, Addison Wesley, 2003 [3] Sedgewick, R., Algorithms in C++, Addison-Wesley, 1998 [4] Giáo trình PTTKGT ĐH. Cần thơ Đề cương Môn học Các khái niệm căn bản Chiến lược chia-để-trị Chiến lược giảm-để-trị Chiến lược biến thể-để-trị Qui hoạch động và giải thuật tham lam Giải thuật quay lui Vấn đề NP-đầy đủ Giải thuật xấp xỉ Chương 1 CÁC KHÁI NIỆM CĂN BẢN Môn học: Phân tích và thiết kế giải thuật Nội dung Đệ quy và hệ thức truy hồi Phân tích độ phức tạp giải thuật Phân tích giải thuật lặp Phân tích giải thuật đệ quy Chiến lược thiết kế giải thuật Thiết kế giải thuật kiểu “trực tiếp” (bruce-force) 1. Đệ quy Hệ thức truy hồi Thí dụ 1: Hàm tính giai thừa N! = N.(N-1)! với N 1 0! = 1 Những định nghĩa hàm đệ quy mà chứa những đối số nguyên được gọi là những hệ thức truy hồi (recurrence relation). function factorial (N: integer): integer; begin if N = 0 then factorial: = 1 else factorial: = N*factorial (N-1); end; Hệ thức truy hồi Thí dụ 2: Số Fibonacci Hệ thức truy hồi: FN = FN-1 + FN-2 for N 2 F0 = F1 = 1 1, 1, 2, 3, 5, 8, 13, 21, function fibonacci (N: integer): integer; begin if N Số Fibonacci – Cây đệ quy computed Có nhiều tính toán dư thừa khi tính số Fibonacci bằng hàm đệ quy. Một cách khác: Ta có thể dùng một mảng để chứa những trị số đi trước trong khi tính hàm fibonacci. Ta có một giải thuật không đệ quy. Giải thuật không đệ quy thường làm việc hữu hiệu và dễ kiểm soát hơn 1 giải thuật đệ quy. Nhờ vào sử dụng stack, ta có thể chuyển đổi một giải thuật đệ quy thành một giải thuật lặp
