Timtailieu.net 
Phân tích tư tưởng của nhân dân qua đoạn thơ: Những người vợ nhớ chồng… Những cuộc đời đã hóa sông núi ta trong Đất nước của Nguyễn Khoa Điềm
3403
1
0
9 trang
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. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Thiết kế và đánh giá thuật toán: Lập trình động - TS. Lê Nguyên KhôiThiết Kế & Đánh Giá Thuật ToánLập Trình ĐộngTS. Lê Nguyên KhôiTrường Đại Học Công Nghệ - ĐHQGHNNội DungKỹ thuật thiết kế dưới lên (bottom-up) Một số bài toán tiêu biểu1Chia Để Trị - Nhắc LạiKỹ thuật thiết kế thuật toánÝ tưởngThiế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 nhauGiả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ớnVí dụSắp xếp gộp (merge sort)Sắp xếp nhanh (quick sort)Tính số Fibonacci2Lập Trình ĐộngKỹ thuật thiết kế thuật toánÝ tưởngThiế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ớnXây dựng lời giải bài toán lớn dựa trên lời giải bàitoán nhỏVí dụSắp xếp chèn (insertion sort)Tính số Fibonacci3Lập Trình ĐộngBài toán có tính chấtCác bài toán con gối nhau (overlapping) Cấu trúc con tối ưu (optimal structure) Lờigiả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 cục4
