27/03/2008
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
Giới thiệu • 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: gọi a, b, c là số táo của các bạn A, B, C được chia. Ta có:
12
c
(*)
2 c
2
⎧ + + = a b ⎪⎪⎪ ≥⎪⎪ a 4 ⎨ ⎪ ≥⎪ ≥⎪⎪⎪ ≥ ≥ b 5 ⎪⎩
Số cách chia táo chính là số nghiệm của phương trình (*)
Phạm Thế Bảo
1
27/03/2008
• Hay gọi G={a+b+c=12/ a≥4, b ≥2, 5≥c ≥2}. Thì
=
=
a x k
|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| (cid:198) cần tìm |H| (cid:198) chính là hệ số của x12 trong phương trình f(x)=(x4+x5+ )(x2+x3+ )(x2+ +x5) f(x)=(x +x +...)(x +x +...)(x + ... +x ) ∑ + + k a b c x
∑
=
k
8
≤ ≤∞ a ≤ ≤∞ b ≤ ≤ c
4 2 2
5
Khi k=12 thì ak chính là giá trị cần tìm (cid:198) mục tiêu
của bài toán là tìm khai triển của f(x).
ể
Phạm Thế Bảo
Chuỗi lũy thừa
∞
n
∈
C
vôùi a
a z n
n
∑
• Xét chuỗi lũy thừa nếu
=
n
0
n
k
hoäi tuï veà G(z) thì chuoãi hoäi tuï vaø
S z ( ) n
a z k
= ∑
k
0
=
∞
n
z
a
G(z)=
n
n=0
n=0. Hàm sinh của dãy này là
∞
n
a z n
∑ • Cho dãy số {an}∞ ∑ ∑ chuỗi . h ỗi
=
n
0
Phạm Thế Bảo
2
27/03/2008
• 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
5
6
b b
a a
c c
∑ ∑
a
4
2
2
b
c
=
=
=
4
2
3
4
2
2
3
2
4
f z ( ) ( ) f z z
8
2
3
2
3
) (1 ) (1 ) (1 z z z z z z ⎞ ⎛ ∑ ∑ ∑ ∑ z ⎟ ⎜ ⎟ ⎜ ⎠ ⎝ 3 z z z ⎞ ⎟ ⎟ ⎠ 2 z z + + + + z + + + = ⎞ ⎛ ⎟ ⎜ ⎟ ⎜ ⎠ ⎝ z + + + + ⎛ = ⎜ ⎜ ⎝ z
4 2 ) (1
5
4
8
8
4
(1 ) z z z z z = z + + + + z + + + z
5 2 ) ( ) (1
3 3
2 ⎞ ⎛ ⎟ ⎜ ⎟ ⎜ ⎠ ⎝ ⎠ ⎝
4
4
( (1 ) ) z z z = − − z = ) ) (1 ( z z z z 1 − 1 − 1 − 1 − 1 z − ⎛ ⎜ ⎜ ⎝ ⎝ ⎞ ⎟ ⎟ ⎠ ⎠
5 2 ) (1
3
Phạm Thế Bảo
Theo chuỗi lũy thừa ta có:
4
k
2
2
k
1
...
z
z
z
+
=
+
... + +
+
3
2
+ k
(1
)
1 z −
⎞ ⎟ ⎠
⎛ ⎜ ⎝
⎞ ⎟ ⎠
⎞ ⎟ ⎠
3 ⎛ ⎛ ⎞ ⎜ ⎜ ⎟ 1 ⎝ ⎠ ⎝ ó hệ ố ủ
⎛ ⎜ ⎝ 4 t
Nên ta có hệ số của z4 trong chuỗi này là Nê t h ỗi à là
6
1 14
=
1 − =
1 − =
− =
4
6! 4!2!
5*6 2
⎛ ⎜ ⎝
⎞ ⎟ ⎠
Vậy có 14 cách giải bài toán chia táo.
Phạm Thế Bảo
3
z z (1 ) ⇒ − − caàn xaùc ñònh heä soá c uûa z trong ) (1 1 z −
27/03/2008
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
đ
ủ th ật t á là ô
độ hứ t
0
• Trong quá trình phân tích thuật toán, chúng ta tì tìm được độ phức tạp của thuật toán là công thức truy hồi.Ví dụ: =
x 0
0
5
=
=
a 1
n
1 −
hay
n
2
6
n
0
2
−
+
= ∀ ≥
=
a 0 a n
a 5 n
a n
2
1 −
−
x n
x k
2 + ∑ n
+ 2
0k 0 k =
• 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
4
27/03/2008
Hàm sinh của dãy xác suất
∞
1 1
k
• Xét biến A có thể lấy các giá trị 0, 1, 2, ... Với thì hì
ấ là
k
0
=
=∑ ∑ xác suất là p0, p1, p2, ... Với pi≥0 và á Với ≥0 à p hàm sinh của dãy xác suất (phân bố) là
∞
k
G z ( )
p z k
= ∑
0
k
=
ét th ật t á
hất t
ố lớ
• Ví dụ xét thuật toán tìm số lớn nhất trong Ví d tì 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
0 0 n-1
thực hiện α: • Tối thiểu: Tối thiểu: • Tối đa: • 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 6
{a[0], a[1], a[0]} (cid:198) có ? tổ hợp thứ tự với xác suất ngang nhau là ?1/6 với xác suất ngang nhau là ? 1/6
Phạm Thế Bảo
5
27/03/2008
Vị trí
Số lần gán
Trung bình
=5/6
A[0] < A[1] < A[2] A[0] < A[2] < A[1] A[1] < A[0] < A[2] A[1] < A[2] < A[0] A[2] < A[0] < A[1] A[2] < A[1] < A[0]
2 1 1 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à ∞
1
=∑ p n k ,
k
0
=
Phạm Thế Bảo
∞
k
G z ( ) n
p z , n k
= ∑
0
k
=
• Hàm sinh • Gọi B là biến cố an lớn nhất trong {a1, a2, ..., an}
(
P B = )
(xaùc suaát taïi böôùc thöù n coù 1 pheùp gaùn)
1 n
vaø P(B)=1-P(B)=
(xaùc suaát taïi böôùc thöù n khoâng coù pheùp gaùn)
n-1 n
)
P B P A B (
).
(
/
)
P B P A B (
).
(
/
)
=
+
coù P(A
n
n
n
vaø P(A /B)=p n
n-1,k-1
, P(A / B)=p n
n-1,k
⇒
=
p
p
+
p
n,k
n-1,k-1
n-1,k
1 n
n-1 n
Phạm Thế Bảo
6
27/03/2008
• 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.
k
k
p
z
p
z
=
+
G z ( ) n
n
k
n
k
1,
1
1,
−
−
−
∑
∑
n-1 n
k
1
=
1 n z
1
G
=
1 ( ) ( ) z
1
n n
−
k 1 = n + − n truy hoài ...
1
2
1
z
z
z
...
=
+ 2
n + − 1 n −
⎞ ⎛ ⎟ ⎜ ⎠ ⎝
⎞ ⎟ ⎠
⎛ ⎜ ⎝
⎞ ⎟ ⎠
⎛ ⎜ ⎝
1
1
1
z
k
k
z ( ) ( )
1 1
=
=
+
+
=
maø ta coù ø t ù
kg
z k
− k
− k
1 k
z
neân
laø haøm sinh cuûa da
õy xaùc suaát
n + − n haïng töû thöù k: k + − k k 1 + − k
n
n
mean g
)
(
)
⇒
=
=
mean(G
k
n
∑
∑
1 k
2
k
k
=
2 = Phạm Thế Bảo
Q
3 t
• Quay lại bài toán khi n=3 ta có ó l i bài t á khi mean(G3) = 1/2 +1/3 =5/6
Phạm Thế Bảo
7
