Phân J . Lv tlntvêr tổ hợp
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 ,...
h) 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 ]ý thuyết, thì bây giờ nó ngày càng khả
thi 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 lố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
irong 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ô' ỉẻ đầ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 vi tích phân, phương trình vi phân, phương trình toán lý...
298 trang
25460
Free
