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

Advertisements

About pascalteacher

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

Thảo luận

Không có bình luận

Trả lờ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 Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

Các tác giả

Categories

Tháng Mười 2016
H B T N S B C
« Th9   Th11 »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

Thống kê

  • 157,688 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: