Thiết Kế & Đánh Giá Thuật Toán<br />
Lập Trình Động<br />
TS. Lê Nguyên Khôi<br />
Trường Đại Học Công Nghệ - ĐHQGHN<br />
<br />
Nội Dung<br />
Kỹ thuật thiết kế dưới lên (bottom-up)<br />
Một số bài toán tiêu biểu<br />
<br />
<br />
1<br />
<br />
Chia Để Trị - Nhắc Lại<br />
<br />
<br />
<br />
Kỹ thuật thiết kế thuật toán<br />
Ý tưởng<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
Thiết kế trên xuống (top-down design)<br />
Chia bài toán lớn thành bài toán nhỏ không giao nhau<br />
Giải các bài toán nhỏ (theo phương pháp đệ quy)<br />
Gộp lời giải bài toán nhỏ thành lời giải bài toán lớn<br />
<br />
Ví dụ<br />
<br />
<br />
<br />
<br />
Sắp xếp gộp (merge sort)<br />
Sắp xếp nhanh (quick sort)<br />
Tính số Fibonacci<br />
2<br />
<br />
Lập Trình Động<br />
<br />
<br />
<br />
Kỹ thuật thiết kế thuật toán<br />
Ý tưởng<br />
<br />
<br />
<br />
<br />
<br />
<br />
Thiết kế dưới lên (bottom-up design)<br />
Lần lượt giải bài toán từ nhỏ nhất đến lớn<br />
Xây dựng lời giải bài toán lớn dựa trên lời giải bài<br />
toán nhỏ<br />
<br />
Ví dụ<br />
<br />
<br />
<br />
Sắp xếp chèn (insertion sort)<br />
Tính số Fibonacci<br />
<br />
3<br />
<br />
Lập Trình Động<br />
<br />
<br />
Bài toán có tính chất<br />
Các bài toán con gối nhau (overlapping)<br />
Cấu trúc con tối ưu (optimal structure)<br />
<br />
<br />
Lời<br />
<br />
giải tối ưu của bài toán con có thể sử dụng để<br />
xây dựng lời giải tối ưu cho bài toán toàn cục<br />
<br />
4<br />
<br />