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