Bài giảng Cơ sở dữ liệu giải thuật: Bài 11 - Thiết kế thuật toán làm rõ các chiến lược thiết kế thuật toán, thuật toán tiêu biểu, quy hoạch động, cấu trúc chung của phương pháp quy hoạch động, bài toán ba lô. | Bài 11: Thi t k thu t toán Gi ng viên: Hoàng Th i p Khoa Công ngh Thông tin – i h c Công Ngh Các chi n lư c thi t k thu t toán • Chia- -tr (Divide-and-conquer) • – Chia bài toán thành các bài toán kích thư c nh có th gi i quy t c l p. Sau ó k t h p nghi m các bài toán kích thư c nh thành nghi m bài toán g c – Thu t toán quy • Quy ho ch ng (Dynamic programming) – 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 c gi i cùng m t bài toán con b ng cách lưu nghi m các bài toán con trong m t b ng – Thu t toán l p diepht@vnu Tham ăn (Greedy method) – Th c hi n t ng bư c m t. T i m i bư c, ch n phương án ư c xem là t t lúc ó. – Không ph i t t c các thu t toán tham ăn u cho k t qu t i ưu toàn c c • Các chi n lư c khác – Quay lui – Thu t toán ng u nhiên 2 Thu t toán tiêu bi u • Chia- -tr – Tìm ki m nh phân (binary search) – S p x p tr n (merge sort) – S p x p nhanh (quick sort) • Quy ho ch ng – Tìm dãy con tăng dài nh t (longest increasing subsequence) – Bài toán ba lô (backpacker/knapsack) – Bài toán ngư i bán hàng (traveling salesman) diepht@vnu – Tìm dãy con chung c a hai dãy s (longest common subsequence) • Tham ăn – Xây d ng mã Huffman (Huffman encoding) – Tìm cây bao trùm nh nh t (minimum spanning tree) 3 1. Fibonacci(n) diepht@vnu 4 Tìm s Fibonacci th n • • Algorithm Fib(n) Input n Output s Fibonacci th n if n = 0 then return 0 else if n = 1 then return 1 else return Fib(n – 2) + Fib(n – 1) Fn= Fn-1+ Fn-2 F0 =0, F1 =1 – 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 • quy Th t c tính quy tr c ti p th c hi n ch m do tính l p nhi u l n. F(6) = 8 F(5) F(4) F(4) F(3) F(2) F(1) diepht@vnu F(3) F(2) F(1) F(1) F(3) F(2) F(1) F(0) F(1) F(0) F(2) F(1) F(2) F(1) .
