Bài giảng Bài 9: Thiết kế thuật toán

Bài giảng Bài 9: Thiết kế thuật toán do Hoàng Thị Điệp biên soạn trình bày về các chiến lược thiết kế thuật toán, thuật toán tiêu biểu, số Fibonacci thứ n đệ quy, Fibonacci(n) quy hoạch động, cấu trúc chung của phương pháp quy hoạch động.
Nội dung trích xuất từ tài liệu:
Bài giảng Bài 9: Thiết kế thuật toánBài 9: Thiết kế thuật toánGiảng viên: Hoàng Thị ĐiệpKhoa Công nghệ Thông tin – ĐH Công NghệCác chiến lược thiết kế thuật toán•Chia-để-trị (Divide-and-conquer)•– Thực hiện từng bước một. Tại mỗibước, chọn phương án được xemlà tốt lúc đó.– Không phải tất cả các thuật toántham ăn đều cho kết quả tối ưutoàn cục– Chia bài toán thành các bài toánkích thước nhỏ có thể giải quyếtđộc lập. Sau đó kết hợp nghiệmcác bài toán kích thước nhỏ thànhnghiệm bài toán gốc– Thuật toán đệ quy•Quy hoạch động (Dynamicprogramming)Tham ăn (Greedy method)•– Giải bài toán lớn dựa vào kết quảbài toán con. Tránh lặp lại việcgiải cùng một bài toán con bằngcách lưu nghiệm các bài toán controng một bảng– Thuật toán lặpINT2203Các chiến lược khác– Quay lui– Thuật toán ngẫu nhiênThuật toán tiêu biểu– Tìm dãy con chung của haidãy số (longest commonsubsequence)• Chia-để-trị– Tìm kiếm nhị phân (binarysearch)– Sắp xếp trộn (merge sort)– Sắp xếp nhanh (quick sort)• Tham ăn– Xây dựng mã Huffman(Huffman encoding)– Tìm cây bao trùm nhỏ nhất(minimum spanning tree)• Quy hoạch động– Tìm dãy con tăng dài nhất(longest increasingsubsequence)– Bài toán ba lô(backpacker/knapsack)– Bài toán người bán hàng(traveling salesman)INT2203Tìm số Fibonacci thứ n đệ quy••Algorithm Fib(n)Input nOutput số Fibonacci thứ nif n = 0 then return 0else if n = 1 then return 1elsereturn Fib(n – 2) + Fib(n – 1)Fn= Fn-1+ Fn-2F0 =0, F1 =1– 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 …•Thủ tục tính đệ quy trực tiếpthực hiện chậm do tính lặpnhiều lần.F(6) = 8F(5)F(4)F(4)F(3)F(2)F(1)F(0)F(3)F(2)F(1) F(1)F(3)F(2) F(1)F(0) F(1)F(0)INT2203F(2)F(1)F(0)F(2)F(1) F(1)F(0)Phân tích• Có bao nhiêu phép cộng?Fn +11+ 5• Tỉ lệ vàng≈φ=≈ 1.61803...2Fn• Suy ra Fn≈1.6n• Cây đệ quy có các lá bằng 0 hoặc 1, do đó có tổng cộngkhoảng 1.6n phép cộng• Thời gian thực hiện là hàm mũINT2203