Bài giảng Cơ sở dữ liệu giải thuật: Bài 11 - Thiết kế thuật toán

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