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?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 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ÁY TÍNH, ĐỘ PHỨC TẠP VÀ TÍNH KHÔNG THỂ GIẢI ĐƯỢC Giảng viên : VŨ ĐÌNH HÒA 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 | MÁY TÍNH, ĐỘ PHỨC TẠP VÀ TÍNH KHÔNG THỂ GIẢI ĐƯỢC Giảng viên : VŨ ĐÌNH HÒA 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ác khoảng cách ? Yêu cầu: tìm hoán vị tròn sao cho tổng trọng số cạnh: 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: 10 9 9 5 6 3 Sắp xếp: Là lời giải: 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 .
