Bài giảng Pascal

Trong thực tế, có một sốbài toán yêu cầu chỉrõ: trong một tập các đối tượng cho trước có bao nhiêu đối tượng thoảmãn những điều kiện nhất định. Bài toán đó gọi là bài toán đếm cấu hình tổ hợp. Trong lớp các bài toán đếm, có những bài toán còn yêu cầu chỉrõ những cấu hình tìm được thoả mãn điều kiện đã cho là những cấu hình nào. Bài toán yêu cầu đưa ra danh sách các cấu hình có thể có gọi là bài toán liệt kê tổhợp. Đểgiải bài toán liệt kê, cần phải xác định được một thuật toán đểcó thểtheo đó lần lượt xây dựng được tất cảcác cấu hình đang quan tâm. Có nhiều phương pháp liệt kê, nhưng chúng cần phải đáp ứng được hai yêu cầu dưới đây: • Không được lặp lại một cấu hình • Không được bỏsót một cấu hình Có thểnói rằng, phương pháp liệt kê là phương kếcuối cùng đểgiải được một sốbài toán tổhợp hiện nay. Khó khăn chính của phương pháp này chính là sựbùng nổtổhợp. Đểxây dựng 1tỷcấu hình (con sốnày không phải là lớn đối với các bài toán tổhợp - Ví dụliệt kê các cách xếp n≥13 người quanh một bàn tròn) và giảthiết rằng mỗi thao tác xây dựng mất khoảng 1giây, ta phải mất quãng 31năm mới giải xong. Tuy nhiên cùng với sựphát triển của máy tính điện tử, bằng phương pháp liệt kê, nhiều bài toán tổhợp đã tìm thấy lời giải. Qua đó, ta cũng nên biết rằng chỉnên dùng phương pháp liệt kê khi không còn một phương pháp nào kháctìm ra lời giải. Chính những nỗ lực giải quyết các bài toán thực tếkhông dùng phương pháp liệt kê đã thúc đẩy sựphát triển của nhiều ngành toán học. Cuối cùng, những tên gọi sau đây, tuy vềnghĩa không phải đồng nhất, nhưng trong một sốtrường hợp người ta có thểdùng lẫn nghĩa của nhau được. Đó là: • Phương pháp liệt kê • Phương pháp vét cạntrên tập phương án • Phương pháp duyệt toàn bộ