Đang chuẩn bị liên kết để tải về tài liệu:
Bài giảng Lý thuyết độ phức tạp: Lý thuyết NP - Đầy đủ - PGS. TSKH Vũ Đình Hòa (tt)

Bài giảng "Lý thuyết độ phức tạp: Lý thuyết NP - Đầy đủ" trình bày các nội dung: Bài toán quyết định, ngôn ngữ và lược đồ mã hóa, máy Turing tất định và lớp P, tính toán không tất định và lớp NP, mối quan hệ giữa lớp P và lớp NP,. nội dung chi tiết. | LÝ THUYẾT ĐỘ PHỨC TẠP LÝ THUYẾT NP - ĐẦY ĐỦ THE THEORY OF NP - COMPLETENESS Giáo vê PGS TSKH Vũ Đình Hoà The theory of NP-Completeness 1 NỘI DUNG 1. Bài toán quyết định 2. Ngôn ngữ và lược đồ mã hóa 3. Máy Turing tất định và lớp P 4. Tính toán không tất định và lớp NP 5. Mối quan hệ giữa lớp P và lớp NP 6. Phép dẫn thời gian đa thức và lớp NPC 7. Thuyết Cook The theory of NP-Completeness 2 1. BÀI TOÁN QUYET ĐỊNH Bài toán quyết định Decision Problem - DP là bài toán chỉ có câu trả lời là có hoặc không hay còn gọi là trả lời nhị phân . 1 -1 9 1 A J r 1 1 A 1 A 1 r 1 V J Môi thê hiện của bài toán nghĩa là môi trường hợp cá biệt của bài toán có một trả lời. l I A T V J 1 J r k 4- 1 T r 4- 9 1 Ă V . . V Một bài toán quyêt định n đơn giản bao gồm một tập 1 r J 1 Ẳ 1 V A J V 1 r i 1 Ẳ 1 V hợp Dn các thê hiện và tập con Yn c Dn là các thê hiện đúng The theory of NP-Completeness