Toán rời rạc 2 counting
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây [842.19 KB, 81 trang ]
Học viện Công nghệ Bưu chính Viễn thông
Khoa Công nghệ thông tin 1
Toán rời rạc 1
Bài toán đếm
Ngô Xuân Bách
Nội dung
Giới thiệu bài toán
Các nguyên lý đếm cơ bản
Quy về bài toán con
Hệ thức truy hồi
Phương pháp hàm sinh
Bài tập
2
//www.ptit.edu.vn
Giới thiệu bài toán đếm
Bài toán đếm
o
o
Là bài toán đếm xem có bao nhiêu cấu hình tổ hợp có thể được
tạo ra với những quy tắc đã nêu?
Lời giải thường phụ thuộc vào một số tham số ban đầu và người
ta cố gắng biều diễn những phụ thuộc này bằng những công thức
toán học
Nguyên tắc chung giải bài toán đếm
o
Để đếm các cấu hình đã cho, người ta tìm cách đưa về các cấu
hình quen thuộc bằng cách thiếp lập một quan hệ 1-1 giữa chúng
Ứng dụng của bài toán đếm trong khoa học máy tính
o
o
3
Ước lượng số phép toán thực hiện trong một giải thuật, chương
trình máy tính
Ước lượng độ phức tạp thời gian và không gian của giải thuật
//www.ptit.edu.vn
Các phương pháp giải quyết bài toán đếm
Sử dụng các nguyên lý đếm cơ bản: nguyên lý cộng,
nguyên lý nhân, nguyên lý bù trừ
Qui về các bài toán con: Phân tích lời giải bài toán
đếm phức tạp thành những bài toán con. Trong đó, mỗi
bài toán con có thể giải được bằng các nguyên lý đếm cơ
bản
Sử dụng hệ thức truy hồi: Xây dựng công thức tính số
nghiệm tổng quát bất kỳ dựa vào biểu diễn các số hạng
biết trước
Phương pháp hàm sinh: Sử dụng hàm sinh của một
dãy số để đếm các cấu hình tổ hợp
4
//www.ptit.edu.vn
Nội dung
Giới thiệu bài toán
Các nguyên lý đếm cơ bản
Quy về bài toán con
Hệ thức truy hồi
Phương pháp hàm sinh
Bài tập
5
//www.ptit.edu.vn
Nguyên lý cộng [nhắc lại]
Nếu 𝐴 và 𝐵 là hai tập rời nhau thì
𝐴∪𝐵 = 𝐴 + 𝐵
Nếu *𝐴1 , 𝐴2 , … , 𝐴𝑘 + là một phân hoạch của tập hợp 𝑋 thì
𝑋 = 𝐴1 + 𝐴2 + ⋯ + 𝐴𝑘
Nếu có 𝐾 việc, việc thứ 𝑖 thực hiện bằng 𝑛𝑖 cách và thực
hiện một cách tuần tự. Khi đó sẽ có 𝑛1 + 𝑛2 +. . + 𝑛𝐾 cách
thực hiện một trong 𝐾 việc nêu trên.
6
//www.ptit.edu.vn
Ví dụ 1
Bài toán: Giả sử 𝑁, 𝑀 là hai số tự nhiên đã xác định giá
trị. Hãy cho biết giá trị của 𝑆 sau khi thực hiện đoạn
chương trình.
𝑆 = 0;
for [𝑖 = 1; 𝑖