Giới thiệu giáo trình ” Toán Rời Rạc – Học Liệu Số Ebooks PDF ”
1. MỞ ĐẦU
1.1. Sơ lược về tổ hợp
Tổ hợp như là một lĩnh vực của toán học rời rạc, xuất hiện vào đâu thế kỷ 17. Trong một thời gian dài, dường như tổ hợp nằm ngoài guồng máy phát triển của toán học cũng như ứng dụng của nó. Tình thế bắt đầu đổi khác khi xuất hiện các máy tính và cùng với nó là sự phát triển của toán hữu hạn. Hiện nay lý thuyết tổ hợp được áp dụng trong nhiều lĩnh vực khác nhau: lý thuyết số, hình học hữu hạn, biểu diễn nhóm, đại số không giao hoán, quá trình ngẫu nhiên, thống kê xác suất, quy hoạch thực nghiệm, …
1.1.1. Các bài toán tổng quát
Tổ hợp đụng chạm đến nhiều vấn đề khác nhau của toán học, do đó khó có thể định nghĩa nó một cách hình thức. Nói chung, lý thuyết tổ hợp gắn liền với việc nghiên cứu phân bố các phần tử vào các tập hợp. Thông thường, các phần tử này là hữu hạn và việc phân bố chúng phải thoả mãn những điều kiện nhất định nào đấy, tuỳ theo yêu cầu của bài toán cần nghiên cứu. Mỗi cách phân bố như thế được gọi là một cấu hình tổ hợp.
Trong các tài liệu về tổ hợp, thường gặp các dạng bài toán dưới đây:
a) Bài toán đếm: đây là các bài toán nhằm trả lời câu hỏi “có bao nhiêu cấu hình thoả mãn điều kiện đã nêu ?”. 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ấu hình đơn giả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ức tạp của một thuật toán, …
b) Bài toán liệt kê: bài toán này quan tâm đến tất cả cấu hình có thể có được, vì thế lời giải của nó cân được biểu diễn dưới dạng thuật toán “vét cạn” tất cả các cấu hình. Lời giải trong từng trường hợp cụ thể sẽ được máy tính điện tử giải quyết theo thuật toán đã nêu. Bài toán liệt kê được làm “nến” cho nhiều bài toán khác. Hiện nay, một số bài toán đếm, tối ưu, tồn tại vẫn chưa có cách nào giải, ngoài cách giải liệt kê. Nếu trước đây, cách giải liệt kê còn mang nặng tính lý thuyết, thì bây giờ nó ngày càng khả thì nhờ sự phát triển nhanh chóng của máy tính điện tử.
c) Bài toán tối ưu: khác với bài bài toán liệt kê, bài toán tối ưu chỉ quan tâm đến một cấu hình “tốt nhất” theo một nghĩa nào đấy. Đây là bài toán có nhiều ứng dụng trong thực tiễn và lý thuyết tổ hợp đã đóng góp một phần đáng kể trong việc xây dựng được những thuật toán hữu hiệu.
d) Bài toán tồn tại: nếu như trong các bài toán trên, việc tốn tại các cấu hình là hiển nhiên thì trong bài toán này, vấn đề “có hay không có” cấu hình còn là điều nghi vấn. Các bài toán loại này thường bị kẹt trong tình huống nan giải: không chỉ ra được cấu hình nào nhưng cũng không khẳng định được là chúng không tồn tại. Lịch sử toán học thường để lại những bài toán khó trong lĩnh vực này và việc cố gắng giải quyết chúng đã thúc đấy không ít sự phát triển của nhiều ngành toán học,
1.1.2. Vài nét về lịch sử
Có thể nói tư duy về tổ hợp ra đời từ rất sớm. Vào thời nhà Chu, người ta đã biết đến các hình vẽ có liên quan đến những hình vuông thần bí. Thời cổ Hy lạp, nhà triết học Kxenokrat, sống ở thế kỷ thứ 4 trước công nguyên, đã biết cách tính số các từ khác nhau, lập từ một bảng chữ cái cho trước. Nhà toán học Pitagor và các học trò của ông đã tìm ra được nhiều con số có các tính chất đặc biệt, chẳng hạn số 36 không những là tổng của 4 số chấn và 4 số lẻ đầu tiên mà còn là tổng lập phương của 3 số tự nhiên đấu tiên. Một định lý nổi tiếng của trường phái này là định lý về độ dài các cạnh của một tam giác vuông, và từ đó họ đã tìm ra các số mà bình phương của một số này bằng tổng bình phương của hai số khác. Việc tìm ra được các số như vậy, đòi hỏi phải có một nghệ thuật tổ hợp nhất định. Tuy nhiên, có thể nói rằng, lý thuyết tổ hợp được hình thành như một ngành toán học mới, vào quãng thế kỷ 17 bằng một loạt các công trình nghiên cứu nghiêm túc của các nhà toán học xuất sắc như Pascal, Fermat, Leibnitz, Euler, … Mặc dù vậy, trong suốt hai thế kỷ rưỡi, vai trò quan trọng trong việc nghiên cứu thế giới tự nhiên vẫn thuộc về các ngành toán học cổ điển như toán giải tích, các phép tính vì tích phân, phương trình vi phân, phương trình toán lý…
Trong thời gian hiện nay, mối tương quan giữa toán học hữu hạn và toán học cổ điển đã có nhiều thay đổi, đặc biệt từ khi máy tính điện từ ra đời và phát triển. Nhiều bài toán nổi tiếng đã được giải trên máy tính bằng những thuật toán của toán hữu hạn. Các lĩnh vực trừu tượng của toán học như đại số lôgic, ngôn ngữ hình thức,… đã trở thành khoa học ứng dụng để xây dựng các ngôn ngữ lập trình cho máy tính. Trong thời đại phát triển của toán học hữu hạn, vai trò của lý thuyết tổ hợp cũng khác xưa. Từ lĩnh vực nghiên cứu các trò chơi tiêu khiển, hay phân tích giải mã các bức thư cổ, tổ hợp đã chuyển sang lĩnh vực toán ứng dụng với sự phát triển mạnh mẽ.
