Bài giảng Phân tích và thiết kế thuật toán - Phạm Thế Bảo - Chương 4: Hàm sinh và ứng dụng

27/03/2008
1
HÀM SINH VÀ ỨNG DỤNG
Phạm Thế Bảo
Khoa Toán – Tin học 
Trường Đại học Khoa học Tự nhiên Tp.HCM
• Bài toán: có 12 trái táo chia cho 03 bạn A, B, C. Theo
qui định: A lấy ít nhất 04 trái, B và C lấy ít nhất 02 trái,
C không lấy quá 05 trái. Vậy, có bao nhiêu cách chia?
Giới thiệu
Giải: gọi a, b, c là số táo của các bạn A, B, C được
chia. Ta có: 12
4
2
 (*)
a b c
a
b
⎧ + + =⎪⎪⎪ ≥⎪⎪⎨⎪ ≥⎪
Số cách chia táo chính là số nghiệm của phương trình (*)
5 2c⎪⎪ ≥ ≥⎪⎩
Phạm Thế Bảo
27/03/2008
2
• Hay gọi G={a+b+c=12/ a≥4, b ≥2, 5≥c ≥2}. Thì 
|G|=số lời giải. Ta đặt H={xa+b+c/ a,b,c∈N, xa+b+c = x12, 
a≥4, b ≥2, 5≥c ≥2} thì |G|= |H|Æ cần tìm |H|Æ chính 
là hệ số của x12 trong phương trình 
f(x)=(x4+x5+ )(x2+x3+ )(x2+ +x5)... ... ... 
=
Khi k=12 thì ak chính là giá trị cần tìm Æ mục tiêu 
ể
4 8
2
2 5
a b c k
k
a k
b
c
x a x+ +
≤ ≤∞ =
≤ ≤∞
≤ ≤
=∑ ∑
của bài toán là tìm khai tri n của f(x).
Phạm Thế Bảo
• Xét chuỗi lũy thừa nếu
Chuỗi lũy thừa
0
n vôùi a
n
n
n
a z C
∞
=
∈∑
• Cho dãy số {an}∞n=0. Hàm sinh của dãy này là 
h ỗi
0
( )
n
n=0
 hoäi tuï veà G(z) thì chuoãi hoäi tuï vaø
G(z)= a
n
k
n k
k
n
S z a z
z
=
∞
= ∑
∑
∞∑c u . 
0
n
n
n
a z
=
Phạm Thế Bảo
27/03/2008
3
• Quay lại bài toán chia táo. Thay vì 4≤a≤∞ và 
2≤b≤∞ ta cũng có thể viết 4≤a≤8 và 2≤b≤6. 
Thì:
8 6 5
( ) a b cf ⎛ ⎞⎛ ⎞⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟∑ ∑ ∑
4 2 2
4 2 3 4 2 2 3 4 2 2 3
8 2 3 4 2 2 3
25 4
8 8 5 2 4
3
(1 ) (1 ) (1 )
(1 ) (1 )
1 1 1(1 ) (1 )
( )
=
a b c
z z z z
z z z z z z z z z z z z z z
z z z z z z z z
z zz z z z
= = =
= ⎝ ⎠⎝ ⎠⎝ ⎠
= + + + + + + + + + + +
= + + + + + + +
⎛ ⎞ ⎛ ⎞− − = − −⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠1 1 1
 caàn xaùc ñònh heä soá c
z z z− − −
⇒ 5 2 4 31(1 ) (1 ) (1 )
4uûa z trong z z
z
− − −
Phạm Thế Bảo
Theo chuỗi lũy thừa ta có:
Nê t ó hệ ố ủ 4 t h ỗi à là
2
3
3 4 21 1 ... ...
1 2(1 )
kkz z z
kz
⎛ + ⎞⎛ ⎞ ⎛ ⎞ ⎛ ⎞= + + + + +⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟− ⎝ ⎠ ⎝ ⎠ ⎝ ⎠⎝ ⎠
n a c s c a z rong c u n y 
Vậy có 14 cách giải bài toán chia táo.
6 6! 5*61 1 1 14
4 4!2! 2
⎛ ⎞= − = − = − =⎜ ⎟⎝ ⎠
Phạm Thế Bảo
27/03/2008
4
Tương tự cho bài toán:
Xét tập hợp {1,2, ...,15} có bao nhiêu tập 
con có 04 phần tử mà không chứa 02 số liên 
tiếp nhau. Vị trí các phền tử trong một tập con 
không quan trọng, ví dụ: {4,7,9,12} và 
{9,12,4,7} là như nhau.
Phạm Thế Bảo
Dùng hàm sinh giải hệ thức truy hồi
• Trong quá trình phân tích thuật toán, chúng ta 
tì đ độ hứ t ủ th ật t á là ôm ược p c ạp c a u o n c ng 
thức truy hồi.Ví dụ: 
0
0 11
1 2
0
0
0 5
2 2 6 5 0 2
2
 hay n
n n nn k
k
x
a a
n a a a nx x
n
−
− −
=
= = =+ − + = ∀ ≥= + ∑
• Chúng ta sẽ dùng hàm sinh để tìm nghiệm (độ 
phức tạp của thuật toán)
Phạm Thế Bảo
27/03/2008
5
Hàm sinh của dãy xác suất
• Xét biến A có thể lấy các giá trị 0, 1, 2, ... Với
á ấ là Với ≥0 à hì1∞∑x c su t p0, p1, p2, ... pi v t
hàm sinh của dãy xác suất (phân bố) là
Ví d ét th ật t á tì ố lớ hất t
0
k
k
p
=
=
0
( ) kk
k
G z p z
∞
=
= ∑
• ụ x u o n m s n n rong
mảng (ví dụ 3 – phần đánh giá bằng công cụ
toán học cơ bản).
Phạm Thế Bảo
• Có thể thấy độ phức tạp là O(n). Vậy số lần 
thực hiện α:
• Tối thiểu: 0 
• Tối đa: n-1
• Trung bình: ?
Nếu xét n=3, dữ liệu là một dãy số đôi một phân biệt 
{a[0], a[1], a[0]} Æ có ? tổ hợp thứ tự 
với xác suất ngang nhau là ?
6
1/6 
Phạm Thế Bảo
27/03/2008
6
Vị trí Số lần gán Trung bình
A[0] < A[1] < A[2]
A[0] < A[2] < A[1]
A[1] < A[0] < A[2]
A[1] < A[2] < A[0]
2
1
1
0 =5/6
A[2] < A[0] < A[1]
A[2] < A[1] < A[0]
1
0
Dùng hàm sinh tính giá trị trung bình của α.
Giả sử mỗi n, gọi An là số lần thực hiện α thì 0≤An≤n-1. 
Với mỗi k gọi pn,k là xác suất để Ak =k. 
Có pn,k ≥0, ∀k∈{0,1,2,...,n-1} và
,
0
1n k
k
p
∞
=
=∑
Phạm Thế Bảo
• Hàm sinh
• Gọi B là biến cố an lớn nhất trong {a1, a2, ..., an} 
,
0
( ) kn n k
k
G z p z
∞
=
= ∑
1( ) (xaùc suaát taïi böôùc thöù n coù 1 pheùp gaùn)P B =
n-1vaø P(B)=1-P(B)= (xaùc suaát taïi böôùc thöù n khoâng coù pheùp gaùn)
n
n
) ( ). ( / ) ( ). ( / )n
n n-1,k-1 n n-1,k
coù P(A
vaø P(A /B)=p , P(A / B)=p
n nP B P A B P B P A B= +
1
n,k n-1,k-1 n-1,k
n-1 p p + p
nn
⇒ =
Phạm Thế Bảo
27/03/2008
7
• Tại bước thứ n có 01 phép gán thì n-1 bước trước đó có k-1 phép gán.
• Tại bước thứ n không có phép gán thì n-1 bước trước đó có k phép gán.
1, 1 1,
1 1
1
1( )
1 ( )
n-1= + 
n
k k
n n k n k
k k
n
G z p z p z
n
z n G z
− − −
= =
+ −=
∑ ∑
1 2 1...
1 2
1 1 1( ) 1
truy hoài ...
=
haïng töû thöù k:
1ø t ù
n
z n z n z
n n
z k z k k
−
+ − + − +⎛ ⎞ ⎛ ⎞ ⎛ ⎞⎜ ⎟ ⎜ ⎟ ⎜ ⎟−⎝ ⎠ ⎝ ⎠ ⎝ ⎠
+ − − −
1
kg ma a co k
neân laø haøm sinh cuûa da
z
k k k k
z k
k
= = + + =
+ −
2 2
1) ( )n
õy xaùc suaát
 mean(G
n n
k
k k
mean g
k= =
⇒ = =∑ ∑
Phạm Thế Bảo
Q l i bài t á khi 3 t ó• uay ạ o n n= a c
mean(G3) = 1/2 +1/3 =5/6
Phạm Thế Bảo