//
you're reading...
Các chuyên đề bồi dưỡng học sinh giỏi, Dùng cho thi học sinh giỏi

Lớp 12 – Chuyên đề 2: ĐỘ PHỨC TẠP CỦA BÀI TOÁN

Số tiết: 8
Mục đích:
• Hiểu được khái niệm độ phức tạp tính toán của bài toán;
• Nắm được một số kỹ thuật phân tích độ phức tạp tính toán của bài toán;
• Nắm được khái niệm qui dẫn giữa các bài toán;
• Có kiến thức nhập môn về các bài toán NP-đầy đủ, NP-khó;
• Nắm được danh sách một số bài toán NP-đầy đủ, NP-khó.

TT Nội dung Mức độ cần đạt Chú thích
1 Độ phức tạp của bài toán
Kiến thức:
– Hiểu khái niệm bài toán tính toán;
– Hiểu khái niệm độ phức tạp tính toán của bài toán.
Kĩ năng:
Phân biệt được mức độ phức tạp của các bài toán.
2 Phân tích độ phức tạp tính toán của bài toán Kiến thức:
– Nắm được ý nghĩa của việc đánh giá cận trên, đánh giá cận dưới của bài toán;
– Hiểu được các kĩ thuật đánh giá cận dưới cho độ phức tạp của bài toán nhờ sử dụng mô hình tính toán cây quyết định và lập luận phản biện;
– Hiểu được khái niệm qui dẫn và ứng dụng để so sánh mức độ khó của các bài toán.
Kĩ năng:
Phân tích được độ phức tạp của một số bài toán cụ thể.
3 Nhập môn NP-đầy đủ
Kiến thức:
– Biết khái niệm bài toán dạng quyết định;
– Biết khái niệm bằng chứng ngắn gọn dễ kiểm tra;
– Hiểu được định nghĩa lớp bài toán NP và co-NP, lớp bài toán NP-đầy đủ và NP-khó;
– Biết danh mục một số bài toán NP-khó.
Kĩ năng:
Nhận dạng được các bài toán NP-khó.

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: