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

Chương mở đầu về lý thuyết tổ hợp giúp người học hiểu được một số kiến thức cơ bản như: Tổ hợp là gì? Sơ lược về lịch sử phát triển của tổ hợp, tập hợp và ánh xạ. 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 mở đầu - Nguyễn Đức Nghĩa Phần thứ nhất LÝ THUYẾT TỔ HỢP Combinatorial Theory Fall 2008Fall 2008 Toán rời rạc 1 Nội dung1. Mở đầu2. Bài toán đếm tổ hợp (Counting Problem)3. Bài toán tồn tại tổ hợp (Existence Problem)4. Bài toán liệt kê tổ hợp (Enumeration Problem)5. Bài toán tối ưu tổ hợp (Combinatorial Optimization Problem) Toán rời rạc 2 0. Mở đầu NỘI DUNG0.1. Tổ hợp là gì?0.2. Sơ lược về lịch sử phát triển của tổ hợp0.3. Tập hợp và ánh xạ Toán rời rạc 3 0.1 Tổ hợp là gì? Đối tượng nghiên cứu Nội dung nghiên cứu Toán rời rạc 4 Đối tượng nghiên cứu của tổ hợp Lýthuyếttổhợpgắnliềnvớiviệcnghiên cứu sựsắpxếp củacácphầntửtrongcác tập hữu hạn và sự phân bố của các phần tửvàocáctậphữuhạn.Mỗicáchsắpxếp hoặcphânbốnhưthếđượcgọilàmộtcấu hìnhtổhợp. Cóthểnóivắntắt: Tổhợplàlýthuyếtvề cáctậphữuhạn. Toán rời rạc 5 Phân loại bài toán Trongcáctàiliệuvềtổhợp,thườnggặpcác dạngbàitoándướiđây: 1.Bàitoánđếmtổhợp(CountingProblem) 2.Bàitoántồntạitổhợp(ExistenceProblem) 3.Bàitoánliệtkêtổhợp(Enumeration Problem) 4.Bàitoántốiưutổhợp(Combinatorial optimizationProblem) Toán rời rạc 6 Bài toán đếm – Counting Problem Đây là các bài toán nhằm trả lời câu hỏi: “Có baonhiêucấuhìnhthoảmãncácđiềukiệncho trước?. Phương pháp đếm thường dựa vào một số nguyên lý cơ bản và một số kết quả đếm các cấuhìnhđơngiản. Bài toán đếm được áp dụng một cách có hiệu quả vào những công việc mang tính chất đánh giá như tính xác suất của một sự kiện, tính độ phứctạpcủamộtthuậttoán,... Toán rời rạc 7 Bài toán tồn tại tổ hợp (Existence Problem) Khácvớibàitoánđếm,trongbàitoántồntạitổ hợp chúng ta cần trả lời câu hỏi: “Tồn tại hay chăngcấuhìnhtổhợpthoảmãncáctínhchấtđã cho?” Rõ ràng nếu có thể đếm được số lượng cấu hìnhtổhợpthoảmãncáctínhchấtđóchothìta cũng giải quyết được bài toán tồn tại tương ứng! Cóthểcoibàitoántồntạinhưtrườnghợpriêng củabàitoánđếmđượckhông? Toán rời rạc 8 Ví dụ Bàitoán phủ bàn cờ quốc tế bởi các quânbàidomino:“Chobàncờquốctếkíchthước8 8bịđục đi2ô ởhaigócđốidiệnvàbộbàidomino, mỗi quân bài phủ kín 2 ô của bàn cờ. Hỏi có thể phủ kín bàn cờ đã cho bởi 31 quân bàidomino?” Toán rời rạc 9Bàn cờ quốc tế và quân bài domino Toán rời rạc 10Bàn cờ quốc tế và quân bài domino Toán rời rạc 11Có thể phủ bàn cờ như vậy bởi 31 quân bài domino?  Bàn cờ còn 62 ô  31 quân bài có thể phủ kín được 62 ô  Về diện tích là có thể phủ được Toán rời rạc 12Không tồn tại cách phủ bàn cờ như vậy bởi 31 quân bài domino!  Chứng minh  Mỗiquânbàiphủkín1ô trắngvàmộtôđen.  Suyrasốlượngôtrắng vàôđenbịphủbởi31 quândominolàbằng nhau.  Thếnhưngsốlượngô trắngvàôđentrênphần cònlạicủabàncờlàkhác nhau  Từđósuyrakhôngtồn tạicáchphủ! Toán rời rạc 13Có bao nhiêu cách phủ bàn cờ bởi 32 quân bài domino?  Sựtồntạicáchphủ làhiểnnhiên.Dễ dàngcóthểchỉravài cáchphủ  Vấnđề“Cóbao nhiêucáchphủ?”  Khôngdễdàngtrả lời! Toán rời rạc 14 C ...