Luận văn Thạc sĩ Khoa học máy tính: Thuật toán xấp xỉ ứng dụng vào một số bài toán lớp NP

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ả.
Nội dung trích xuất từ tài liệu:
Luận văn Thạc sĩ Khoa học máy tính: Thuật toán xấp xỉ ứng dụng vào một số bài toán lớp NP ĐẠI HỌC THÁI NGUYÊNTRƯỜ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ÊNTRƯỜ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âusắc tới thầy giáo hướng dẫn TS. Vũ Vinh Quang đã tận tình hướng dẫn và đưara nhiều ý kiến đóng góp cho em trong suốt quá trình thực hiện và hoàn thànhluậ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ựctiế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ủamình, tuy nhiên sẽ không tránh khỏi những thiếu sót. Em rất mong nhận đượcsự 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êurõ nguồn gốc trong danh mục tài liệu tham khảo và được chỉ rõ tham khảotrong 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ôixin chịu hoàn toàn trách nhiệm. HỌC VIÊN Nguyễn Hữu Chuyên iii MỤC LỤCLỜI CẢM ƠN ............................................................................................................ ILỜI CAM ĐOAN .................................................................................................... IIDANH MỤC CÁC BẢNG ....................................................................................... VDANH MỤC CÁC HÌNH ........................................................................................ VLỜI MỞ ĐẦU ............................................................................................................1CHƯƠNG 1................................................................................................................2MỘT SỐ KIẾN THỨC CƠ BẢN ............................................................................21.1 Thuật toán ............................................................................................................2 1.1.1 Khái niệm bài toán ........................................................................................2 1.1.2. Khái niệm thuật toán ....................................................................................2 1.1.3. Các yêu cầu của thuật toán ..........................................................................2 1.1.4 Các phương pháp mô tả thuật toán ..............................................................31.2. Độ phức tạp của thuật toán ...............................................................................4 1.2.1. Chi phí phải trả cho một quá trình tính toán ..............................................4 1.2.2. Thời gian thực hiện giải thuật .....................................................................4 1.2.3. Độ phức tạp của thuật toán ..........................................................................5 1.2.4. Các qui tắc xác định độ phức tạp thuật toán ..............................................61.3. Vấn đề phân lớp các bài toán. ...........................................................................61.4 Mô hình Bài toán Knapsack ...............................................................................7 Hình 1.1 Bài toán xếp ba lô dạng 0-1 ...................................................................8CHƯƠNG 2..............................................................................................................13MỘT SỐ THUẬT TOÁN XẤP XỈ ........................................................................132.1 Khái niệm về thuật toán xấp xỉ ..................................... ...