Luận văn thạc sĩ: Về các bài toán NPC và một số phương pháp giải

➤ Gửi thông báo lỗi ⚠️ Báo cáo tài liệu vi phạm

Loại tài liệu: PDF

Số trang: 68 Trang

Tài liệu: ✅ ĐÃ ĐƯỢC PHÊ DUYỆT

TẢI VỀ

Nội dung chi tiết: Luận văn thạc sĩ: Về các bài toán NPC và một số phương pháp giải

Luận văn thạc sĩ: Về các bài toán NPC và một số phương pháp giải

ĐẠI HỌC THÁI NGUYÊN TRUÔNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNGTRẢN THỊ DƯƠNGVÈ CÁC BÀI TOÁN NP-C VÀ MỌT SỐ PHI ONG PHÁP GIAIChuyên ngành : Kho

Luận văn thạc sĩ: Về các bài toán NPC và một số phương pháp giải oa học máy tínhMà số: 60480101LUẬN VĂN THẠC sỉ KHOA HỌC MÁY TÍNHThái Nguyên - 20141MỞ ĐÀUNgày nay. cùng với sự phát triển mạnh mè cùa khoa học và công

nghệ, dặc biệt lả máy tính, người ta có khả năng giãi quyết dược nhiều bài toán rất phức lạp.Tuy nhiên, còn những vấn dề là “không giãi dược” cho dù Luận văn thạc sĩ: Về các bài toán NPC và một số phương pháp giải

kỹ thuật máy linh có phát triền và cùng có nliừng van đề được xcm là “quá phức lạp”, vượt mọi khá năng tinh toán thực te vi mất quá nhiều thời gian. V

Luận văn thạc sĩ: Về các bài toán NPC và một số phương pháp giải

iệc nghiên cứu về độ phức lạp cua thuật toán đà cho phép chúng ta phần loại được các lớp bài loan iheo từng mức độ phức lạp khác nhau. và chi ra ranh

ĐẠI HỌC THÁI NGUYÊN TRUÔNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNGTRẢN THỊ DƯƠNGVÈ CÁC BÀI TOÁN NP-C VÀ MỌT SỐ PHI ONG PHÁP GIAIChuyên ngành : Kho

Luận văn thạc sĩ: Về các bài toán NPC và một số phương pháp giải - c (NP - đầy đù) là một lớp các bài toán quyết định. Một bãi toán L là NP - c nếu nó nam trong lớp NP (lời giai cho L có thê được kiêm chứng trong th

ời gian đa thức) và là NP -I lard (mọi bãi toán trong NP đều cỏ thè quy ve I. trong thời gian da thức).Mặc dù bất ki lời giãi nào cho mỗi bài toán đều Luận văn thạc sĩ: Về các bài toán NPC và một số phương pháp giải

cỏ the dược kiêm chứng nhanh chóng, hiện chưa cỏ cách nào tìm ra dược lời giải dó một cách hiệu qua. Thời gian thực thi cua tai ca các thuật toán hiệ

Luận văn thạc sĩ: Về các bài toán NPC và một số phương pháp giải

n lại cho những bài loán nãy đều tăng rất nhanh theo kích thước bài toán. Vi vậy ngay cà nhừng tnrờng hợp có kích thước tương đồi lớn đà đòi hoi thời

ĐẠI HỌC THÁI NGUYÊN TRUÔNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNGTRẢN THỊ DƯƠNGVÈ CÁC BÀI TOÁN NP-C VÀ MỌT SỐ PHI ONG PHÁP GIAIChuyên ngành : Kho

Luận văn thạc sĩ: Về các bài toán NPC và một số phương pháp giải năng kiếm chửng nhanh chóng lời giai (NP) dường như có liên hệ với khá nảng tim kiêm nhanh chóng lời giãi (p). Hiện vần chưa biết được nếu mọi bài toá

n trong NP đều có the được giãi quyết nhanh chóng hay không (đây chính là bài toán p so với2NP). Tuy nhiên, nếu bắt ki một bài toán nào trong NP - c c Luận văn thạc sĩ: Về các bài toán NPC và một số phương pháp giải

ó thể được giải quyết nhanh chóng, thi theo định nghĩa cùa NP - c, mọi bài toán trong NP đêu có thể dược giãi quyết nhanh chỏng.Các bài toán NP- c xuấ

Luận văn thạc sĩ: Về các bài toán NPC và một số phương pháp giải

t hiện thường xuyên trong thực tế nên. mặc dù chưa có giai thuật trong thời gian đa thức cho chủng, các nhà nghiên cửu vẫn tim cách giãi quyết chủng t

ĐẠI HỌC THÁI NGUYÊN TRUÔNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNGTRẢN THỊ DƯƠNGVÈ CÁC BÀI TOÁN NP-C VÀ MỌT SỐ PHI ONG PHÁP GIAIChuyên ngành : Kho

Luận văn thạc sĩ: Về các bài toán NPC và một số phương pháp giải lớp NP- c là một trong nhũng bài toán mớ của khoa học máy tính hiện nay. Vi vậy em dà chọn dề tài: Vê các bài toán NP-C và một so phương pháp ỊỊÌài đ

ê làm luận văn lot nghiệp.Cấu trúc cua luận văn gồm: Phần mở đâu. phân kết luận và 3 chương nội dung, cụ thê:Chương 1; Khái niệm các lớp bài toán p. N Luận văn thạc sĩ: Về các bài toán NPC và một số phương pháp giải

P, NP-C.Trong chương này em giới thiệu chung về các lớp bài toán p. NP, NP -c. minh họa bang các vi dụ cụ thế và dưa ra moi quan hệ giừa lớp p. NP vả

Luận văn thạc sĩ: Về các bài toán NPC và một số phương pháp giải

NP-C('hương 2: Phương pháp tham vã phương pháp nhánh cận giãi một so bài toán NP-CTrong chương này em trinh bây phương pháp tham giai bài toán vê đô t

ĐẠI HỌC THÁI NGUYÊN TRUÔNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNGTRẢN THỊ DƯƠNGVÈ CÁC BÀI TOÁN NP-C VÀ MỌT SỐ PHI ONG PHÁP GIAIChuyên ngành : Kho

Luận văn thạc sĩ: Về các bài toán NPC và một số phương pháp giải ài đặt thuật toán nhánh cận giãi bài toán Ba lô.Chương 1: KHÁT NIỆM CÁC LỚP BÀI TOÁN p, NP, NP - c1.1. Vài khái niệm cơ bân của lý thuyêt độ phức tạp1

.1.1 Mày Turin}* tât định và không tât tlịnhMáy Turing là một máy lính trừu tượng mô la các quá trinh tinh toán trên máy lính.Máy Turing có hai loại: Luận văn thạc sĩ: Về các bài toán NPC và một số phương pháp giải

Máy Turing lâl định (Deterministic Turing Machine) và Máy Turing không lâl định (Nondeterministic Turing Machine) được mô la như sau:Máy Turing tat đị

Luận văn thạc sĩ: Về các bài toán NPC và một số phương pháp giải

nhMô la cách làm việc cua máy:Máy Turing lai định gôm một bộ điều khiên hữu hạn trạng ihái. một đàu đọc và ghi. một băng vô hạn được chia thành từng ò

ĐẠI HỌC THÁI NGUYÊN TRUÔNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNGTRẢN THỊ DƯƠNGVÈ CÁC BÀI TOÁN NP-C VÀ MỌT SỐ PHI ONG PHÁP GIAIChuyên ngành : Kho

Luận văn thạc sĩ: Về các bài toán NPC và một số phương pháp giải ột băng, dó lả chuỗi ký hiệu có chiều dài hừu hạn dược chọn từ một bộ chừ cái. Những ô còn lại cứa bảng vô hạn theo cà hai bên phải và trải, chứa một

kỷ hiệu dặc biệt là kỷ hiệu trống ( diền tà trạng thãi ô không có ký hiệu nào).Có một dầu dọc - ghi luôn chí vào một trong các ô của băng. Ta nói rang Luận văn thạc sĩ: Về các bài toán NPC và một số phương pháp giải

máy l uring đang đọc - ghi ô dó. Lúc khởi hoạt, dầu dọc - ghi nằm

ĐẠI HỌC THÁI NGUYÊN TRUÔNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNGTRẢN THỊ DƯƠNGVÈ CÁC BÀI TOÁN NP-C VÀ MỌT SỐ PHI ONG PHÁP GIAIChuyên ngành : Kho