MÁY TÍNH, ĐỘ PHỨC TẠP VÀ TÍNH KHÔNG THỂ GIẢI ĐƯỢC

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ácquy 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ấnphòng bandersnatch.• Lao vào công việc với đầy bầu nhiệthuyết.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áncho một modun– Có rất nhiều modun cho bài toán...
Nội dung trích xuất từ tài liệu:
MÁY TÍNH, ĐỘ PHỨC TẠP VÀ TÍNH KHÔNG THỂ GIẢI ĐƯỢCMÁY TÍNH, ĐỘ PHỨC TẠP VÀMÁYTÍNH KHÔNG THỂ GIẢI ĐƯỢC Giảng viên : PGS.TSKH 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 PH• 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ínhNPđầyđủchotathấy: →Khảnăngtìmrathuậttoántốtcho bàitoánkhó. →Cáchchuyểnhướngtiếpcận:giải gầnđúnghoặctìmlờigiảichonhững trườnghợpđặcbiệt BÀITOÁN,THUẬTTOÁNVÀĐỘPHỨCTẠP MỘTSỐKHÁINIỆMCƠ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ÀITOÁN,THUẬTTOÁNVÀĐỘPHỨC TẠP MỘTSỐKHÁINIỆMCƠBẢN• Bàitoán: →Vídụ:Bt“Ngườidulịch”. C = c1 , c2 ,  , cm } { ٧ Cácthànhphố ( ) ٧ Cáckhoảngcách d c ,c i j ?Yêucầu:tìmhoánvịtròncπ1 , cπ2 ,  , cπm m −  1saochotổngtrọngsốcạnh: ∑(cπ( i ) , cπ( i + ) ) + (cπ( m ) , cπ(1) )  d d 1 i =  1nhỏnhất. ‫ ٭‬Ýnghĩa: BÀITOÁN,THUẬTTOÁNVÀĐỘPHỨC TẠP MỘTSỐKHÁINIỆMCƠBẢN• Mộtdữkiện/inputcủabàitoán: c1 C ={c1 , c2 , c3 , c4 } d ( 1 , c2 ) = 5 9 c 10 10 c3 d ( 1 , c3 ) = 6 c 5 c2 3 c4 d ( 1 , c4 ) = c 9 9 d (c2 , c3 ) =6 c1 , c2 , c4 , c3 Sắp d ( 2 , c4 ) = c 9 xếp: Là lời giải: lengthmin = 27 d ( 3 , c4 ) = c 3 BÀITOÁN,THUẬTTOÁNVÀĐỘPHỨC TẠP MỘTSỐKHÁINIỆMCƠ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 đó. toán BÀITOÁN,THUẬTTOÁNVÀĐỘPHỨC TẠP MỘTSỐKHÁINIỆMCƠBẢN• Thuậttoán: ThếnàolàmộtTThiệuquả(efficiency)? – Chạyđượcvớitấtcảcácinput. – Thờigiantínhtoánnhanhnhấ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ông BÀITOÁN,THUẬTTOÁNVÀĐỘPHỨC TẠP MỘTSỐKHÁINIỆMCƠBẢN• Thuậttoán:Yêucầuvềthờigian – Cóthểmiêutảhàmmộtbiến(Kíchthướccủamộtbài toáncụthể) – Đokíchthướccủabàitoáncụthểtheocáchthông thường – Ex,bàitoán“ngườithươnggiađidulịch”cókích –Đểướclmst cáchngmcxác thì phải xét cả số các khoảng th tính à ộốlượ chính ácthànhphố. cách và độ lớn các khoảng cách giữa các thành phố. BÀI ...