zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

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

Chia sẻ: Năm Tháng Tĩnh Lặng | Ngày: | Loại File: PDF | Số trang:7

Báo xấu

162
lượt xem 12
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nội dung chính của bài giảng "Phân tích và thiết kế thuật toán: Hàm sinh và ứng dụng" gồm có: Chuỗi lũy thừa, dùng hàm sinh giải hệ thức truy hồi, hàm sinh của dãy xác suất. Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Phân tích và thiết kế thuật toán: Hàm sinh và ứng dụng - Phạm Thế Bảo

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

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.