Bài giảng Toán rời rạc (Phần I: Lý thuyết tổ hợp): Chương 3 (tt) - Nguyễn Đức Nghĩa

Chương 3 - Bài toán liệt kê tổ hợp. Những nội dung chính được trình bày trong chương này gồm có: Giới thiệu bài toán, thuật toán và độ phức tạp, phương pháp sinh, thuật toán quay lui. 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 Toán rời rạc (Phần I: Lý thuyết tổ hợp): Chương 3 (tt) - Nguyễn Đức Nghĩa Phần thứ nhấtLÝ THUYẾT TỔ HỢP Combinatorial Theory Fall 2009 Toán rời rạc 1 Nội dungChương 0. Mở đầuChương 1. Bài toán đếmChương 2. Bài toán tồn tạiChương 3. Bài toán liệt kê tổ hợpChương 4. Bài toán tối ưu tổ hợp Toán rời rạc 2 Chương 3BÀI TOÁN LIỆT KÊ Toán rời rạc 3 NỘI DUNG1. Giới thiệu bài toán2. Thuật toán và độ phức tạp3. Phương pháp sinh4. Thuật toán quay lui Toán rời rạc 4 GiíithiÖubµito ¸n Bàitoánđưaradanhsáchtấtcảcấuhìnhtổhợp thoả mãn mộtsố tínhchấtchotrước đượcgọi làbàitoánliệtkêtổhợp. Dosốlượngcấuhìnhtổhợpcầnliệtkêthường làrấtlớnngaycảkhikíchthướccấuhìnhchưa lớn: • Sốhoánvịcủanphầntửlàn! • Sốtậpconmphầntửcủanphầntửlàn!/(m!(n m)! Dođó ầncóquanniệmthếnàolàgiảibài toánliệtkêtổhợp 5 GiíithiÖubµito ¸n Bài toán liệt kê tổ hợp là giải được nếu như ta có thể xác định một thuật toán để theođócóthểlầnlượtxâydựngđượctất cảcáccấuhìnhcầnquantâm. Mộtthuậttoánliệtkêphảiđảmbảo2yêu cầucơbản: • Khôngđượclặplạimộtcấuhình, • khôngđượcbỏsótmộtcấuhình. 6 Chương 3. Bài toán liệt kê1. Giới thiệu bài toán2. Thuật toán và độ phức tạp3. Phương pháp sinh4. Thuật toán quay lui Toán rời rạc 7 Khái niệm bài toán tính toán Định nghĩa. Bài toán tính toán F là ánh xạ từ tập các xâu nhị phânđộdàihữuhạnvàotậpcácxâunhịphânđộdàihữuhạn:F:{0,1}* {0,1}*. Vídụ: Mỗisốnguyênxđềucóthểbiểudiễndướidạngxâunhịphânlà cáchviếttronghệđếmnhịphâncủanó. Hệphươngtrìnhtuyếntính Ax=bcóthểbiểudiễndướidạngxâu làghépnốicủacácxâubiểudiễnnhịphâncủacácthànhphầncủa matrậnAvàvectơb. Đathứcmộtbiến:P(x)=a0+a1x+...+anxn,hoàntoànxácđịnhbởidãysố n,a0,a1,...,an,màđểbiểudiễndãy sốnàychúngtacóthểsửdụngxâunhịphân. 8 Khái niệm thuật toán Địnhnghĩa. Tahiểuthuậttoángiảibàitoánđặtralà một thủ tục xác định bao gồm một dãy hữu hạn các bướccầnthựchiệnđểthuđượcđầurachomộtđầu vàochotrướccủabàitoán. Thuậttoáncócácđặctrưngsauđây: • Đầu vào (Input): Thuật toán nhận dữ liệu vào từ một tập nàođó. • Đầu ra (Output): Với mỗi tập các dữ liệu đầu vào, thuật toánđưaracácdữliệutươngứngvớilờigiảicủabàitoán. • Chínhxác(Precision):Cácbướccủathuậttoánđượcmôtả chínhxác. 9 Khái niệm thuật toán• Hữu hạn (Finiteness): Thuật toán cần phải đưa được đầu ra sau một số hữu hạn (có thể rất lớn) bướcvớimọiđầuvào.• Đơn trị (Uniqueness): Các kết quả trung gian của từngbướcthựchiệnthuậttoánđượcxácđịnhmột cáchđơntrịvàchỉphụthuộcvàođầuvàovàcáckết quảcủacácbướctrước.• Tổngquát (Generality):Thuậttoáncóthểápdụng đểgiảimọibàitoáncódạngđãcho. 10 Độ phức tạp của thuật toán Độ phức tạp tính toán của thuật toán được xác định như là lượngtàinguyêncácloạimàthuậttoánđòihỏisửdụng. Cóhailoạitàinguyênquantrọngđólàthờigianvàbộnhớ. Việctínhchínhxácđượccácloạitàinguyênmàthuậttoánđòi hỏilàrấtkhó.Vìthếtaquantâmđếnviệcđưaracácđánhgiá sátthựcchocácđạilượngnày. Tronggiáotrìnhnàytađặcbiệtquantâmđếnđánhgiáthờigian cầnthiếtđểthựchiệnthuậttoánmàtasẽgọilà thờigiantính củathuậttoán. 11 Độ phức tạp của thuật toán Rõràng:Thờigiantínhphụthuộcvàodữliệuvào. Ví dụ: Việc nhân hai số nguyên có 3 chữ số đòi hỏi thời gian kháchẳnsovớiviệcnhânhaisốnguyêncó3*109chữsố! Địnhnghĩa.Tagọikíchthướcdữliệuđầuvào(hayđộdàidữ liệuvào)làsốbítcầnthiếtđểbiểudiễnnó. Ví dụ: Nếu x, y là đầu vào cho bài toán nhân 2 số nguyên, thì kíchthướcdữliệuvàocủabàitoánlàn= log|x| + log|y| . Ta sẽ tìm cách đánh giá thời gian tính của thuật toán bởi một hàmcủađộdàidữliệuvào. ...