Tiểu Luận Chỉnh hợp và tổ hợp suy rộng

Chỉnh hợp và tổ hợp suy rộng

Mục lục

1. Lời mở đầu 2

2. Cơ sở phép đếm . 5

3. Chỉnh hợp 13

4. Hoán vị . 15

5. Tổ hợp 19

6. Thuật toán liệt kê các hoán vị của các kí tự trong xâu 23

7. Một số nội dung mở rộng 24

8. Tài liệu tham khảo 32

9. Lời kết thúc 33

10. Nhận xét của giáo viên phụ trách 33

Lời mở đầu

Lý thuyết tổ hợp là 1 phần quan trọng của toán rời rạc chuyên nghiên cứu sự

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 thỏa mãn những điều kiện nhất định nào đó tùy 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ế gọi là một cấu

hình tổ hợp.Chủ đề này đã được nghiên cứu vào thế kỉ 17,khi những câu hỏi về tổ

hợp được đưa ra trong các công trình nghiên cứu hay các trò chơi may rủi.Liệt

kê,đếm các đối tượng có những tính chất nào đólaf một phần quan trọng của lý

thuyết tổ hợp.Chúng ta cần phải đếm các đối tượng để giải nhiều bài toán khác

nhau.Hơn nữa các kĩ thuật đếm được dùng rất nhiều khi tính xác suất của các

biến cố hay trong đánh giá độ phức tạp của thuật toán.

Trong bài tiểu luận này chúng tôi sẽ trình bày các nội dung cơ bản về chỉnh hợp

và tổ hợp suy rộng cùng với các vấn đề liên quan . Cuối báo cáo là thuật toán liệt

kê tất cả các hoán vị của các kí tự trong một xâu ( Với files chương trình và mã

nguồn đi kèm trong CD).

Mục đính của bài tiểu luận :

· Cung cấp kiến thức cơ bản về hoán vị, tổ hợp và chỉnh hợp suy rộng

· Minh họa thuật toán liệt kê các hoán vị của các kí tự trong một xâu cho

trước.