Nội dung của bản luận văn bao gồm ba chương, trình bày cụ thể như sau: Trình bày tóm tắt những kiến thức cơ bản và trọng tâm về lý thuyết thuật toán như máy Turing đơn định, máy Turing không đơn định, thuật toán, độ phức tạp thuật toán; Gồm có ba phần chính trình bày về khái niệm bài toán, danh sách các bài toán quan trọng và khái niệm độ phức tạp của bài toán; Gồm có hai phần chính trình bày lớp các bài toán P, NP và lớp bài toán NP-đầy đủ. | ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN - Nguyễn Thế Quyền TÌM HIỂU ĐỘ PHỨC TẠP MỘT SỐ THUẬT TOÁN LUẬN VĂN THẠC SĨ KHOA HỌC Hà Nội Năm 2013 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN - Nguyễn Thế Quyền TÌM HIỂU ĐỘ PHỨC TẠP MỘT SỐ THUẬT TOÁN Chuyên ngành Bảo đảm toán học cho máy tính và hệ thống tính toán Mã số LUẬN VĂN THẠC SĨ KHOA HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC . Nguyễn Hữu Ngự Hà Nội Năm 2013 MỤC LỤC MỞ ĐẦU . 3 CHƢƠNG 1. KIẾN THỨC CHUẨN BỊ . 4 . Máy Turing. 4 . Máy Turing. 4 . Máy Turing tất định . 5 . Máy Turing không tất định . 7 . Khái niệm thuật toán . 8 . Khái niệm thuật toán . 8 . Ví dụ về thuật toán. 9 . Luận đề Church-Turing . 10 . Độ phức tạp của thuật toán . 11 . Độ phức tạp về thời gian . 11 . Ví dụ cách tính độ phức tạp . 12 CHƢƠNG 2. BÀI TOÁN VÀ ĐỘ PHỨC TẠP CỦA BÀI TOÁN . 14 . Bài toán là gì . 14 . Một số bài toán quan trọng . 15 . Độ phức tạp của bài toán . 20 CHƢƠNG 3. PHÂN LỚP CÁC BÀI TOÁN THEO ĐỘ PHỨC TẠP . 21 . Lớp các bài toán P NP và mối quan hệ giữa lớp P và lớp NP . 21 . Lớp P . 21 . Lớp NP . 21 . Mối quan hệ giữa lớp P và NP . 21 . Lớp các bài toán NPC. . 21 . Phép dẫn với thời gian đa thức . 21 . Lớp các bài toán NPC . 22 . Mối quan hệ giữa các lớp bài toán P NP và NPC . 22 . Một số bài toán lớp NPC. 23 1 Bài toán SAT. Định lý Cook . 23 2 Bài toán 3SATIFIABILITY 3SAT . 30 3 Bài toán 3-DIMENSIONAL MATCHING 3DM . 33 4 Bài toán VERTEX COVER VC . 37 5 Bài toán CLIQUE . 39 6 Bài toán HAMILTON CIRCUIL HC . 39 7 Bài toán PARTITION . 39 8 Bài toán TRAVELING SALEMAN TSP . 39 KẾT LUẬN . 41 TÀI LIỆU THAM KHẢO . 42 MỞ ĐẦU Lý thuyết độ phức tạp là một lĩnh vực trung tâm của khoa học máy tính với các kết quả liên quan chặt chẽ với sự phát triển và sử dụng các thuật toán. Nghiên cứu về lý thuyết độ phức tạp sẽ giúp chúng ta hiểu biết sâu sắc và khám phá ra ranh giới của những vấn để có thể tính toán với các nguồn
