Về các bài toán NP c 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ạmNội dung chi tiết: Về các bài toán NP c và một số phương pháp giải
Về các bài toán NP c 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 Về các bài toán NP c 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ù Về các bài toán NP c 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. VVề các bài toán NP c 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 Về các bài toán NP c 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 Về các bài toán NP c 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ệVề các bài toán NP c 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 Về các bài toán NP c 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 Về các bài toán NP c 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ấVề các bài toán NP c 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 Về các bài toán NP c 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 Về các bài toán NP c 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ảVề các bài toán NP c 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 Về các bài toán NP c 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ÁI NĨẸ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 dinhMáy Turing là một máy lính trừu tượng mô ta các quá trinh tính toán trên máy lính.Máy Turing có hai loại: M Về các bài toán NP c và một số phương pháp giải áy Turing lâl định (Deterministic Turing Machine) và Máy Turing không tâl định (Nondeterministic Turing Machine) được mò ta như sau:Máy Turing tat địnVề các bài toán NP c và một số phương pháp giải
hMô la cách làm việc cua máy:Máy Turing tat định gôm một bộ điều khiên hừu hạn trạng thái, một đâu đọc và ghi. một bang vô hạn được chia thành lừ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 Về các bài toán NP c và một số phương pháp giải xâu Input dược dặt trên mộ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). Về các bài toán NP c 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 : KhoGọi ngay
Chat zalo
Facebook