Bài giảng Lý thuyết độ phức tạp: Lý thuyết NP - Đầy đủ - PGS. TSKH Vũ Đình Hòa

Bài giảng "Lý thuyết độ phức tạp: Lý thuyết NP - Đầy đủ" cung cấp cho người đọc các kiến thức: Xác định bài toán, bài toán, thuật toán và độ phức tạp một số khái niệm cơ bản, thuật toán thời gian đa thức và những bài toán không giải được,... Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Lý thuyết độ phức tạp: Lý thuyết NP - Đầy đủ - PGS. TSKH Vũ Đình HòaLÝ THUYẾT ĐỘ PHỨC TẠP LÝ THUYẾT NP - ĐẦY ĐỦ(THE THEORY OF NP - COMPLETENESS) Giáo viên : PGS TSKH Vũ Đình Hoà The theory of NP-Completeness 1 MỞ ĐẦU TÌNH HUỐNG Bạn được làm thuê cho một công ty với tư cách là nhà thiết kế thuật toán. Công ty sẽ tham gia thị trường cạnh tranh “bandersnatch cao cấp”. Có phương pháp nào để tạo ra một tập các quy cách kĩ thuật cho mỗi bài toán của thị trường bandersnatch đặt ra? MỞ ĐẦU PHẢI LÀM GÌ? Xác định chính xác bài toán = tham vấn phòng bandersnatch. Lao vào công việc với đầy bầu nhiệt huyết MỞ ĐẦU KẾT QUẢ Vài tuần trôi qua Giấy tờ tràn ngập Không tìm được bất kì thuật toán nào  phải mất hàng năm để xây dựng một thuật toán cho một modun  Có rất nhiều modun cho bài toán MỞ ĐẦU PHẢI LÀM THẾ NÀO Nếu viết báo cáo rằng “Tôi thật ngu ngốc vì không thể tìm được thuật toán nào” →Bạn sẽ bị sa thải’ Cần chứng minh rằng bài toán được giao là không thể giải dễ dàng được MỞ ĐẦU LỜI KHUYÊN Việc chứng minh tính không thể giải được = chứng minh không tồn tại một thuật toán hữu hiệu. Lý thuyết sau đây chỉ ra rằng cần chứng minh bài toán của bạn là bài toán NP-đầy đủ. Nó có độ khó tương đương với độ khó lớp các bài toán khác mà nhiều chuyên gia phải bó tay. MỞ ĐẦU LỜI KHUYÊN Tính NP-đầy đủ cho ta thấy: →Khả năng tìm ra thuật toán tốt cho bài toán khó. →Cách chuyển hướng tiếp cận: giải gần đúng hoặc tìm lời giải cho những trường hợp đặc biệt BÀI TOÁN, THUẬT TOÁN VÀ ĐỘ PHỨC TẠP MỘT SỐ KHÁI NIỆM CƠ BẢN Một bài toán/vấn đề là gì?: →Một câu hỏi có tính tổng quát cần được trả lời. →Thường chứa một số tham số hay biến tự do chưa được xác định giá trị. →Miêu tả:(1) các tham số, (2) các yêu cầu về câu trả lời. BÀI TOÁN, THUẬT TOÁN VÀ ĐỘ PHỨC TẠP MỘT SỐ KHÁI NIỆM CƠ BẢN Bài toán: →Ví dụ: Bt “Người du lịch”. ٧ Các thành phố C  c1 , c2 ,  , cm  ٧ Các khoảng cách d ci , c j  ? Yêu cầu: tìm hoán vị tròn c 1 , c 2 ,  , c m  m 1 sao cho tổng trọng số cạnh:   d (c ( i ) , c ( i 1) )   d (c ( m ) , c (1) )  i 1 nhỏ nhất. ‫ ٭‬Ý nghĩa: BÀI TOÁN, THUẬT TOÁN VÀ ĐỘ PHỨC TẠP MỘT SỐ KHÁI NIỆM CƠ BẢN Một dữ kiện/input của bài toán: C  c1 , c2 , c3 , c4  c1 d c1 , c2   10 10 5 9 c3 d c1 , c3   5 c2 6 3 d c1 , c4   9 c4 9 d c2 , c3   6 Sắp xếp: c1 , c2 , c4 , c3 d c2 , c4   9 Là lời giải: lengthmin  27 d c3 , c4   3BÀI TOÁN, THUẬT TOÁN VÀ ĐỘ PHỨC TẠP MỘT SỐ KHÁI NIỆM CƠ BẢN Thuật toán: →Gồm các thủ tục “từng bước-từng bước” giải quyết bài toán. →Có thể xem như một chương trình viết bằng ngôn ngữ máy. Một TT giải quyết được bài toán П nếu nó có lời giải cho mọi dữ kiện/input I của bài toán đó. BÀI TOÁN, THUẬT TOÁN VÀ ĐỘ PHỨC TẠP MỘT SỐ KHÁI NIỆM CƠ BẢN Thuật toán: Thế nào là một TT hiệu quả (efficiency)?  Chạy được với tất cả các input.  Thời gian tính toán nhanh nhất. Yêu cầu về thời gian có tính quyết định xem một thuật toán có hiệu quả để đưa vào thực tế hay khôngBÀI TOÁN, THUẬT TOÁN VÀ ĐỘ PHỨC TẠP MỘT SỐ KHÁI NIỆM CƠ BẢN Thuật toán: Yêu cầu về thời gian  Có thể miêu tả hàm một biến (Kích thước của một bài toán cụ thể)  Đo kích thước của bài toán cụ thể theo cách thông thường –Để tínhbài  Ex, mộttoán cách“người chính thương xác thì phải gia đixét ducảlịch” số các khoảng có kích thước cách và độ lớn các khoảng cách giữa các thành phố. là số lượng m các thành phố. BÀI TOÁN, THUẬT TOÁN VÀ ĐỘ PHỨC TẠP MỘT SỐ KHÁI NIỆM CƠ BẢN Lược đồ mã hóa:  Miêu tả đầu vào của một bài toán cụ thể bằng một chuỗi kí tự.  Độ dài đầu vào của trường hợp ...