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 />