//
you're reading...
Các chuyên đề bồi dưỡng học sinh giỏi, Dùng cho cấp THPT, Dùng cho thi học sinh giỏi, Giáo trình chuyên Tin học 10

Chuyên đề 4: CÁC CÁCH TIẾP CẬN GIẢI BÀI TOÁN NP-KHÓ

Số tiết: 5
Mục đích:
• Nắm được phát biểu của một số bài toán NP-khó điển hình;
• Nắm được khái niệm thuật toán gần đúng đảm bảo chất lượng lời giải;
• Nắm được một số thuật toán gần đúng để giải các bài toán NP-khó điển hình;
• Nắm được một số thuật toán ngẫu nhiên.

1 Một số bài toán NP-khó điển hình
Kiến thức:
Phát biểu được một số bài toán NP-khó điển hình:
• Bài toán cái túi,
• Bài toán người du lịch,
• Bài toán phủ đỉnh,
• Bài toán đóng thùng,
• Bài toán phủ tập.
2 Các thuật toán gần đúng đảm bảo chất lượng lời giải Kiến thức:
– Hiểu khái niệm thuật toán gần đúng đảm bảo chất lượng lời giải, khái niệm sơ đồ xấp xỉ thời gian đa thức;
– Nắm được một số thụât toán gần đúng để giải các bài toán NP-khó đã giới thiệu.
Kĩ năng:
Cài đặt được các thuật toán đã trình bày.
3 Cách tiếp cận ngẫu nhiên để giải các bài toán NP-khó
Kiến thức:
– Biết kỹ thuật phát triển thuật toán ngẫu nhiên;
– Hiểu thụât toán tạo số ngẫu nhiên và các thuật toán sinh ngẫu nhiên các cấu hình tổ hợp cơ bản.
Kĩ năng:
– Biết vận dụng để xây dựng thuật toán ngẫu nhiên giải các bài toán đã trình bày;
– Cài đặt được các thuật toán đã xét.

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ê

  • 181,058 lượt xem

pascalteacher.nct@gmail.com


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

%d bloggers like this: