Nội dung chính của luận văn là nghiên cứu cơ sở toán học của các thuật toán gần đúng giải lớp các bài toán thuộc lớp NP và NPC, tìm hiểu chi tiết các bước mô tả thuật toán và các yêu cầu thiết kế các thuật toán. Trên cơ sở các thuật toán đã nghiên cứu, luận văn phân tích một số các bài toán thuộc lớp NP, NPC, xây dựng lời giải đúng và gần đúng, đánh giá kết quả. | ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN HỮU CHUYÊN THUẬT TOÁN XẤP XỈ ỨNG DỤNG VÀO MỘT SỐ BÀI TOÁN LỚP NP LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH Thái Nguyên 2020 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN HỮU CHUYÊN THUẬT TOÁN XẤP XỈ ỨNG DỤNG VÀO MỘT SỐ BÀI TOÁN LỚP NP LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH Chuyên ngành KHOA HỌC MÁY TÍNH Mã số 84 8 01 01 Người hướng dẫn TS. Vũ Vinh Quang Thái Nguyên - 2020 i LỜI CẢM ƠN Để hoàn thành luận văn này trước tiên em xin được gửi lời cảm ơn sâu sắc tới thầy giáo hướng dẫn TS. Vũ Vinh Quang đã tận tình hướng dẫn và đưa ra nhiều ý kiến đóng góp cho em trong suốt quá trình thực hiện và hoàn thành luận văn này. Em cũng xin được gửi lời cảm ơn đến các thầy giáo cô giáo Trường Đại học Công nghệ Thông tin và Truyền thông Đại học Thái Nguyên trực tiếp giảng dạy và truyền đạt những kiến thức quý báu cho em trong suốt quá trình học tập tại trường. Mặc dù đã cố gắng hoàn thành luận văn trong phạm vi và khả năng của mình tuy nhiên sẽ không tránh khỏi những thiếu sót. Em rất mong nhận được sự cảm thông và chỉ bảo của quý thầy cô và các bạn. Em xin chân thành cảm ơn. ii LỜI CAM ĐOAN Tôi xin cam đoan Luận văn Thuật toán xấp xỉ ứng dụng vào một số bài toán lớp NP là do tôi thực hiện dưới sự hướng dẫn trực tiếp của thầy TS. Vũ Vinh Quang. Các kết quả số liệu nêu trong luận văn là trung thực. Tất cả những tham khảo từ những nghiên cứu liên quan đều được nêu rõ nguồn gốc trong danh mục tài liệu tham khảo và được chỉ rõ tham khảo trong tài liệu nào. Mọi sao chép không hợp lệ và vi phạm quy chế đào tạo tôi xin chịu hoàn toàn trách nhiệm. HỌC VIÊN Nguyễn Hữu Chuyên iii MỤC LỤC LỜI CẢM ƠN . I LỜI CAM ĐOAN . II DANH MỤC CÁC BẢNG . V DANH MỤC CÁC HÌNH . V LỜI MỞ ĐẦU .1 CHƯƠNG MỘT SỐ KIẾN THỨC CƠ BẢN .2 Thuật toán .2 Khái niệm bài toán .2 . Khái niệm thuật toán .2 . Các yêu cầu của thuật toán .2 Các phương pháp mô tả thuật toán .3 . Độ phức tạp của .
