//
you're reading...
Các chuyên đề bồi dưỡng học sinh giỏi, Chủ đề quy hoạch động

Chuyên đề 1. THUẬT TOÁN QUY HOẠCH ĐỘNG

( Dynamic programming algorithm)
Số tiết: 15


Nội dung


1. Bài toán có thể giải bằng thuật toán QHĐ

Kiến thức:
• Biết nguyên lí tối ưu, đặc trưng các bài toán có thể giải bằng thuật toán QHĐ, đặc trưng chính của thuật toán QHĐ.
• Phân biệt sự giống và khác nhau căn bản giữa thuật toán QHĐ và Đệ quy
Kĩ năng:
Nhận biết được bài toán cụ thể có thể giải được bằng QHĐ hay không. Thông qua ví dụ để minh họa lí thuyết.

2. Thuật toán QHĐ

Kiến thức:
• Hiểu các bước cần thực hiện khi xây dựng thuật toán QHĐ
• Hiểu các khái niệm cơ bản: cở sở, bảng phương án, công thức truy hồi, các truy vết để tìm nghiệm.
Kĩ năng:
Xây dựng được thuật toán QHĐ để giải bài toán cụ thể. Các ví dụ ban đầu nên chọn bài toán dễ tìm thuật toán QHĐ để giải.

3 Một số bài toán thường gặp được giải bằng QHĐ

– Bài toán dãy con đơn điệu tăng dài nhất;
– Bài toán xâu con chung dài nhất;
– Bài toán biến đổi xâu;
– Bài toán cái túi;
– Bài toán lũy thừa một số;
– Bài toán nhân các ma trận;
– Bài toán chia đa giác thành các tam giác;
Kiến thức:
Với mỗi bài toán cụ thể, hiểu cách xác định các khái niệm cơ bản của QHĐ.
Kĩ năng
Cài đặt được chương trình và thử nghiệm chương trình với các bộ dữ liệu khác nhau. – Nên yêu cầu HS hiểu thấu đáo cách xác định các khái niệm cơ bản trước khi cài đặt chương trình.
– GV có thể tùy chọn các bài toán cụ thể khác để thay thế cho các bài toán nêu ở cột bên.


Bài giảng quy hoạch động


  1. Bài giảng quy hoạch động 1
  2. Bài giảng quy hoạch động 2
  3. Bài giảng quy hoạch động – Lê Minh Hoàng

Bài tập quy hoạch động


  1. Bài tập quy hoạch động
  2. _
  3. _

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Tháng Mười 2016
M T W T F S S
« Sep   Nov »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

A bellezza di a natura (C☺rsica)

Southern White-faced Owl D75_5752.jpg

2016 Lake Yamanaka winter Fuji

More Photos

Thống kê

  • 78,768 lượt xem

%d bloggers like this: