Bài giảng Thiết kế và đánh giá thuật toán: Lập trình động - TS. Lê Nguyên Khôi

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