TAILIEUCHUNG - Bài giảng Toán rời rạc (Phần I: Lý thuyết tổ hợp): Chương 2(tt) - Nguyễn Đức Nghĩa
Trong chương trước, ta đã tập trung chú ý vào việc đếm số các cấu hình tổ hợp. Trong những bài toán đó sự tồn tại của các cấu hình là hiển nhiên và công việc chính là đếm số phần tử thoả mãn tính chất đặt ra. Tuy nhiên, trong rất nhiều bài toán tổ hợp, việc chỉ ra sự tồn tại của một cấu hình thoả mãn các tính chất cho trước là hết sức khó khăn. Trong tổ hợp xuất hiện một vấn đề thứ hai rất quan trọng là: xét sự tồn tại của các cấu hình tổ hợp với các tính chất cho trước - bài toán tồn tại tổ hợp. | Toỏn rời rạc Phần thứ nhất Lí THUYẾT TỔ HỢP Combinatorial Theory Fall 2009 Toỏn rời rạc Nội dung Chương 0. Mở đầu Chương 1. Bài toỏn đếm Chương 2. Bài toỏn tồn tại Chương 3. Bài toỏn liệt kờ tổ hợp Chương 4. Bài toỏn tối ưu tổ hợp Toỏn rời rạc Chương 2. BÀI TOÁN TỒN TẠI Giới thiệu bài toỏn Cỏc kỹ thuật chứng minh cơ bản Nguyờn lý Dirichlet Định lý Ramsey Toỏn rời rạc 1. Giới thiệu bài toỏn Trong chương trước, ta đã tập trung chú ý vào việc đếm số các cấu hình tổ hợp. Trong những bài toán đó sự tồn tại của các cấu hình là hiển nhiên và công việc chính là đếm số phần tử thoả mãn tính chất đặt ra. Tuy nhiên, trong rất nhiều bài toán tổ hợp, việc chỉ ra sự tồn tại của một cấu hình thoả mãn các tính chất cho trước là hết sức khó khăn. Chẳng hạn, khi một kỳ thủ cần phải tính toán các nước đi của mình để giải đáp xem liệu có khả năng thắng hay không, Một người giải mật mã cần tìm kiếm chìa khoá giải cho một bức mật mã mà anh ta không biết liệu đây có đúng là bức điện thật được mã hoá của đối phương hay không, hay chỉ là bức mật mã giả của đối phương tung ra nhằm đảm bảo an toàn cho bức điện thật . Trong tổ hợp xuất hiện một vấn đề thứ hai rất quan trọng là: xét sự tồn tại của các cấu hình tổ hợp với các tính chất cho trước - bài toán tồn tại tổ hợp. Nhiều bài toán tồn tại tổ hợp đã từng thách thức trí tuệ nhân loại và đã là động lực thúc đẩy sự phát triển của tổ hợp nói riêng và toán học nói chung. Toỏn rời rạc Bài toỏn về 36 sĩ quan Bài toán này được Euler đề nghị, nội dung của nó như sau: “Có một lần người ta triệu tập từ 6 trung đoàn mỗi trung đoàn 6 sĩ quan thuộc 6 cấp bậc khác nhau: thiếu úy, trung uý, thượng uý, đại uý, thiếu tá, trung tá về tham gia duyệt binh ở sư đoàn bộ. Hỏi rằng có thể xếp 36 sĩ quan này thành một đội ngũ hình vuông sao cho trong mỗi một hàng ngang cũng như mỗi một hàng dọc đều có đại diện của cả 6 trung đoàn và của cả 6 cấp bậc sĩ quan.” Toỏn rời rạc Bài toỏn về 36 sĩ quan Sử dụng: A, B, C, D, E, F để chỉ các phiên hiệu trung đoàn, a, b,
đang nạp các trang xem trước
