zunia.vn

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

zunia.vn

» Luận Văn - Báo Cáo

» Thạc sĩ - Tiến sĩ - Cao học

Luận văn Thạc sĩ Khoa học: Một số mô hình xác suất trong khoa học máy tính

Chia sẻ: Na Na | Ngày: | Loại File: PDF | Số trang:118

Báo xấu

171
lượt xem 21
download

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

Trong luận văn này, tác giả muốn giới thiệu các loại mô hình và phân tích xác suất hữu dụng nhất trong khoa học máy tính. Giả sử với một hàm mở đầu trong xác suất, tác giả trình bày một số đề tài quan trọng như phương pháp xác suất, xích Markov, mô phỏng MCMC và quá trình Poisson không dừng.

Chủ đề:

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

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học: Một số mô hình xác suất trong khoa học máy tính

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ----------------------- PHẠM THỊ THU HẰNG MỘT SỐ MÔ HÌNH XÁC SUẤT TRONG KHOA HỌC MÁY TÍNH LUẬN VĂN THẠC SĨ KHOA HỌC Hà Nội - Năm 2015
ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ----------------------- PHẠM THỊ THU HẰNG MỘT SỐ MÔ HÌNH XÁC SUẤT TRONG KHOA HỌC MÁY TÍNH Chuyên ngành: Lý thuyết Xác suất và Thống kê toán học Mã số: 60406106 LUẬN VĂN THẠC SĨ KHOA HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: GS.TSKH. ĐẶNG HÙNG THẮNG Hà Nội - Năm 2015
Mục lục 1
LỜI NÓI ĐẦU Trong những năm gần đây, xác suất đã phát triển đa dạng và có nhiều ứng dụng quan trọng trong lĩnh vực khoa học máy tính. Ví dụ, các chủ đề liên quan đến thuật toán như thuật toán ngẫu nhiên, thuật toán ước lượng và phân tích xác suất của thuật toán đều sử dụng phương pháp xác suất. Trong luận văn này, tôi muốn giới thiệu các loại mô hình và phân tích xác suất hữu dụng nhất trong khoa học máy tính. Giả sử với một hàm mở đầu trong xác suất, tôi trình bày một số đề tài quan trọng như phương pháp xác suất, xích Markov, mô phỏng MCMC và quá trình Poisson không dừng. Luận văn này cung cấp nhiều ví dụ và bài tập mô tả các đề tài như thuật toán sắp xếp, thuật toán tìm kiếm và biểu đồ ngẫu nhiên, bài toán tự sắp xếp theo danh sách, phản xích, phân hoạch cực đại và cực tiểu trong đồ thị và nhiều đề tài khác. Cấu trúc luận văn được chia làm 3 chương chính: • Chương 1 đưa ra các ví dụ hay trong khoa học máy tính, đồng thời trình bày phương pháp xác suất và một số cách ứng dụng phương pháp này. • Chương 2 viết về xích Markov trên không gian trạng thái rời rạc, phương pháp Monte Carlo và xích Markov Monte Carlo (MCMC). • Chương 3 giới thiệu một số lớp quá trình Poisson, từ đó nghiên cứu bài toán phân loại biến cố của một quá trình Poisson không dừng và bài toán xác định phân phối có điều kiện của thời điểm đến. Trong khuôn khổ của luận văn này, do sự hạn hẹp về thời gian cũng như năng lực của bản thân, vì vậy không thể tránh khỏi những hạn chế về nội dung cũng như việc trình bầy. Tôi nhận thấy xác suất trong khoa học máy tính còn rất nhiều điều thú vị khác nữa và tôi rất mong có dịp trình bầy đầy đủ hơn. Luận văn được hoàn thành dưới sự hướng dẫn tận tâm của GS.TSKH Đặng Hùng Thắng. Tôi xin được bày tỏ lòng biết ơn và kính trọng sâu sắc của mình đến thầy. Qua đây tôi xin chân thành gửi lời cảm ơn tới các thầy cô trong Tổ 2
Luận văn tốt nghiệp Phạm Thị Thu Hằng bộ môn Xác suất thống kê và Ban Chủ nhiệm khoa Toán - Cơ - Tin học Trường Đại học Khoa học Tự nhiên - Đại học Quốc gia Hà Nội đã chỉ bảo và hướng dẫn tận tình giúp tôi hoàn thành luận văn này! Rất mong nhận được ý kiến đóng góp của các thầy cô và các bạn! Hà Nội, tháng 11/2015 Phạm Thị Thu Hằng 3
Chương 1 Xác suất trong lý thuyết tổ hợp và đồ thị 1.1 Các ví dụ 1.1.1 Đồ thị ngẫu nhiên Mỗi đồ thị bao gồm hai yếu tố: tập V là tập hợp các đỉnh (hay nút) và A là tập hợp các cặp đỉnh gọi là cạnh (hoặc cung). Ta thường khoanh tròn số hiệu của mỗi đỉnh và nối các đỉnh bởi một đường thẳng hoặc cong nếu có cạnh tạo bởi hai đỉnh đó. Ví dụ, một đồ thị có V = {1, 2, 3, 4, 5, 6} và A={(1, 2), (1, 4), (1, 5), (2, 3), (2, 5), (3, 5), (5, 6)} được mô tả trong Hình 1.1. Ở đây ta chỉ xét các đồ thị không có hướng, tức là ta không định hướng các cạnh của đồ thị. Một chuỗi các đỉnh i, i1 , i2 , . . . , ik , j trong đó (i, i1 ), (i1 , i2 ), . . . , (ik−1 , ik ), (ik , j) là các cạnh được gọi là một đường đi từ đỉnh i tới đỉnh j . Hình 1.2 biểu thị một đường đi từ đỉnh 1 tới đỉnh 6. Một đồ thị được coi là liên thông nếu có một đường đi giữa mọi cặp đỉnh của đồ thị. Đồ thị như trong Hình 1.1 và 1.2 là đồ thị liên thông còn đồ thị trong Hình 1.3 không phải đồ thị liên thông. Giờ hãy xem xét đồ thị với tập hợp đỉnh V = {1, 2, . . . , n} và tập hợp cạnh A = {(i, X(i)), i = 1, . . . , n} trong đó X(i) là các biến ngẫu nhiên độc lập thỏa mãn Xn P {X(i) = j} = Pj , Pj = 1 j=1 Nói cách khác, từ mỗi đỉnh i ta chọn ra ngẫu nhiên một đỉnh trong số n đỉnh còn lại của đồ thị (bao gồm cả i), trong đó xác suất để đỉnh j được chọn là Pj , 4
Luận văn tốt nghiệp Phạm Thị Thu Hằng Hình 1.1: Đồ thị Hình 1.2: Đường đi từ 1 tới 6: 1, 2, 3, 5, 6. Hình 1.3 sau đó ta nối đỉnh i với đỉnh vừa chọn bởi một cung. Đồ thị vừa xây dựng là một đồ thị ngẫu nhiên. Chúng ta sẽ tính xác suất để đồ thị ngẫu nhiên này là 5
Luận văn tốt nghiệp Phạm Thị Thu Hằng đồ thị liên thông. Để tìm được xác suất này, ta chọn một đỉnh, giả sử đỉnh 1 và lần theo chuỗi các đỉnh 1, X(1), X 2 (1), . . . , trong đó X n (1) = X(X n−1 (1)) để xác định giá trị của biến ngẫu nhiên N là chỉ số k nhỏ nhất sao cho X k (1) không là một đỉnh mới. Tức là, N = min(k : X k (1) ∈ {1, X(1), . . . , X k−1 (1)}) Đồng thời, gọi N X −1 W = P1 + PX i (1) i=1 Nói cách khác, N là số đỉnh tiếp xúc trong chuỗi 1, X(1), X 2 (1), . . . trước khi một đỉnh xuất hiện hai lần còn W là tổng các xác suất của các đỉnh này. (xem Hình 1.4). Hình 1.4 Để tính toán xác suất đồ thị này liên thông, ta lấy điều kiện với N : n X Xác suất đồ thị liên thông = P (đồ thị liên thông|N = k)P (N = k). k=1 Bây giờ, với điều kiện N = k , các đỉnh 1, X(1), . . . , X k−1 (1) liên thông với nhau và không còn cạnh nào khác xuất phát từ các đỉnh này tới các đỉnh còn lại của đồ thị. Nói cách khác, ta có thể hợp k đỉnh này lại làm một siêu đỉnh. Không có cạnh nào xuất phát từ siêu đỉnh này và xác suất để một đỉnh ở ngoài đi vào siêu đỉnh này là W . Ta sẽ cần đến kết quả sau. Bổ đề 1.1.1. Xét một đồ thị ngẫu nhiên gồm các đỉnh 0, 1, . . . , r, và các cạnh (i, Yi ), i = 1, . . . , r, trong đó Yi là các biến ngẫu nhiên độc lập và r X P {Yi = j} = Qj , j = 0, ..., r, Qj = 1 j=0 Khi đó, 6
Luận văn tốt nghiệp Phạm Thị Thu Hằng P {đồ thị liên thông} = Q0 . Đồ thị ngẫu nhiên ở trên bao gồm r đỉnh thông thường (đánh số từ 1 đến r) và một đỉnh đặc biệt (đánh số 0); cứ mỗi đỉnh thông thường có một cạnh độc lập đi qua đỉnh j với xác suất Qj ; không có cạnh nào xuất phát từ đỉnh đặc biệt. Chứng minh. : Để chứng minh, ta sử dụng phương pháp quy nạp theo r, bổ đề hiển nhiên đúng khi r = 1, giả sử bổ đề đúng với mọi giá trị nhỏ hơn r. Xem xét Y1 nếu Y1 = 1 thì dễ thấy đồ thị là không liên thông. Nếu Y1 = 0 thì đỉnh 1 và 0 có thể coi là một đỉnh đơn lẻ và trường hợp này không thay đổi nếu ta có r − 1 đỉnh thông thường và một đỉnh đặc biệt, trong đó cứ mỗi đỉnh thông thường có một cạnh đi qua đỉnh đặc biệt với xác suất Q0 + Q1 . Nếu Y1 = j 6= 0, 1 thì bằng cách coi đỉnh 1 và j là một đỉnh đơn lẻ, kết quả này vẫn không thay đổi nếu ta có r − 1 đỉnh thông thường và một đỉnh đặc biệt, trong đó mỗi đỉnh thông thường có một cạnh đi qua đỉnh đặc biệt với xác suất Q0 . Do vậy, từ giả thiết quy nạp, chúng ta thấy:  0, nếu j = 1 P {đồ thị là liên thông|Y1 = j} = Q0 + Q1 , nếu j = 0 nếu j 6= 0, 1  Q0 , Lấy xác suất với điều kiện với Y1 ta có: r X P {đồ thị là liên thông} = P {đồ thị là liên thông|Y1 = j}Qj j=0 = (Q0 + Q1 )Q0 + Q0 (1 − Q0 − Q1 ) = Q0 và giả thiết quy nạp là đúng. Trở lại với đồ thị ngẫu nhiên ban đầu, coi tập hợp đỉnh 1, . . . , X N −1 (1) là một đỉnh đặc biệt của Bổ đề 1.1.1 ta có: P {đồ thị là liên thông|N, 1, . . . , X N −1 (1)} = W Lấy kỳ vọng thu được kết quả sau: Mệnh đề 1.1.1. P{đồ thị liên thông} = E[W] Từ lập luận ở trên ta nhận thấy nếu thực hiện một dãy các phép thử đa thức độc lập với xác suất P1 , . . . , Pn thì với điều kiện kết quả ban đầu là 1, kỳ vọng 7
Luận văn tốt nghiệp Phạm Thị Thu Hằng của tổng các xác suất của tất cả kết quả riêng biệt thu được đến trước khi có một kết quả bị lặp lại bằng với xác suất để đồ thị ngẫu nhiên liên thông. Điều này vẫn đúng nếu ta thay kết quả bân đầu là 1 bởi một kết quả ban đầu bất kì khác (khi phân tích đồ thị ngẫu nhiên, chúng ta đã có thể bắt đầu bằng bất cứ chuỗi đỉnh i, X(i), X 2 (i), . . . nào), vì thế, với mỗi dãy phép thử đa thức ta có kì vọng của tổng các xác suất của các kết quả thu được cho đến trước khi có một kết quả lặp lại là độc lập với kết quả đầu tiên. Đây là một phát hiện không hiển nhiên chút nào. Trong phần còn lại của mục này, chúng ta sẽ tập trung phân tích trường hợp đặc biệt trong đó cạnh xuất phát từ mỗi đỉnh có thể đến mọi đỉnh của đồ thị với cùng xác suất 1 Pj = , j = 1, . . . , n n . Hệ quả sau cho ta công thức tính xác suất đồ thị liên thông trong trường hợp đặc biệt này. Hệ quả 1.1.1. Khi Pj = 1/n, n−1 (n − 1)! X nj P {đồ thị là liên thông} = nn j! j=0 Chứng minh. Vì W = N/n, ta có: 1 E[W ] = E[N ] n n−1 1X = P (N > i) n i=0 n−1 1 X (n − 1)...(n − i) = n ni i=0 n−1 1 X (n − 1)! = n (n − i − 1)!ni i=0 n−1 (n − 1)! X nn−1−i = nn (n − i − 1)! i=0 n−1 (n − 1)! X nj = nn j! j=0 8
Luận văn tốt nghiệp Phạm Thị Thu Hằng Để thu được ước lượng đơn giản xác suất để đồ thị là liên thông khi n lớn, ta thấy nếu X là một biến Poisson ngẫu nhiên với trị số trung bình n thì n−1 i −n X n P {X < n} = e i! i=0 Tuy nhiên, vì một biến Poisson ngẫu nhiên có trị số trung bình n có thể được coi là tổng của n biến Poisson ngẫu nhiên độc lập với trị số trung bình bằng 1, điều này được suy ra từ định lý giới hạn trung tâm rằng một biến ngẫu nhiên có một phân phối xấp xỉ chuẩn với trị số trung bình n. Xác suất của biến ngẫu nhiên thông thường nhỏ hơn trị số trung bình của nó là 1/2, hay : 1 P {X < n} v 2 Do đó với n lớn n−1 i X n en v i! 2 i=0 Từ Hệ quả 1.1.1 ta thấy với n lớn, (n − 1)!en n!en P {đồ thị là liên thông} v = 2nn 2nn+1 Do vậy, bằng cách sử dụng công thức tiệm cận Stirling trong đó chỉ ra rằng: √ n! v nn+1/2 e−n 2π ta thấy, với n lớn √ 2π P {đồ thị là liên thông} v √ 2 n Từ đó chúng ta thu được Hệ quả sau. p Hệ quả 1.1.2. Với n lớn, P {đồ thị là liên thông} v π/2n Một đồ thị được coi là bao gồm r thành phần nếu các đỉnh của nó có thể được phân chia vào r tập hợp con sao cho mỗi tập hợp con liên thông và không có cạnh nào được tạo thành bởi các đỉnh thuộc các tập hợp con khác nhau. (Do đó, đồ thị liên thông là đồ thị có một thành phần đơn lẻ.) Gọi C là số thành phần trong đồ thị ngẫu nhiên ta đang xem xét, chúng ta sẽ tính giá trị kỳ vọng của nó. Trước hết, chúng ta sẽ chứng minh rằng mỗi thành phần phải chứa đúng một chu trình, trong đó chu trình là một cạnh của cặp 9
Luận văn tốt nghiệp Phạm Thị Thu Hằng (i, i) hoặc một chuỗi của cạnh của cặp (i, i1 ), (i1 , i2 ), . . . , (ik , i) với các đỉnh riêng biệt i, i1 , i2 , . . . , ik . Ví dụ, đồ thị trong Hình 1.5 là một chu trình. Dễ dàng thấy một đồ thị liên thông có số cạnh bằng số đỉnh chỉ chứa duy nhất một chu trình. Vì trong đồ thị ngẫu nhiên xuất phát từ mỗi đỉnh có duy nhất một cạnh nên một thành phần chứa k đỉnh chỉ có đúng k cạnh và do đó chỉ có duy nhất một chu trình. Với S ⊂ {1, . . . , n} thì S là một chu trình nếu tồn tại một chu trình mà các đỉnh của nó là đỉnh của S . Do đó, nếu ta lấy I(S) = 1, nếu S là 1 chu trình 0, ngược lại thì E[C] = E số của chu trình " # X = E I(S) s X = E[I(S)] s Nếu S gồm một đỉnh đơn lẻ, tức là S = {1}, thì S sẽ là một chu trình nếu X(1) = 1. Do đó, E[I({1})] = P {X(1) = 1} = 1/n Nếu S gồm k > 1 đỉnh, tức là S = {1, . . . , k}, thì S sẽ tạo thành một chu trình nếu 1, X(1), . . . , X k−1 (1) là các giá trị khác nhau trong S và X k (1) = 1. Do vậy, k−1k−2 1 (k − 1)! E[I(S)] = ... = n n n nk n Kết quả là, do có k tập hợp con kích thước k , ta thấy rằng n X n (k − 1)! E[C] = k nk k=1 1.1.2 Thuật toán Tìm kiếm và Sắp xếp nhanh Giả sử chúng ta muốn sắp xếp một tập hợp n giá trị khác nhau cho trước x1 , x2 , . . . , xn . Thuật toán sắp xếp nhanh được xác định theo cách như sau : Khi n = 2, thuật toán so sánh hai giá trị và xếp chúng theo thứ tự thích hợp. Khi n > 2, gọi xi là giá trị được chọn, khi đó tất cả các giá trị khác được so sánh với 10
Luận văn tốt nghiệp Phạm Thị Thu Hằng xi . những giá trị nhỏ hơn xi được đặt vào một nhóm phân cách bởi dấu ngoặc bên trái xi còn những giá trị lớn hơn xi thì đặt bên phải, lặp lại thuật toán với mỗi nhóm này cho tới khi tất cả các giá trị được sắp xếp. Ví dụ, giả sử chúng ta muốn sắp xếp 10 giá trị khác nhau như sau: 5, 9, 3, 10, 11, 14, 8, 4, 17, 6 Một trong những giá trị này được lựa chọn, giả sử là 10. Chúng ta sẽ so sánh từng giá trị với 10, đặt những giá trị nhỏ hơn 10 vào một nhóm bên trái 10 và đặt những giá trị lớn hơn 10 vào bên phải 10 ta được {5, 9, 3, 8, 4, 6}, 10, {11, 14, 17} Giờ chúng ta hãy nhìn vào một nhóm chứa nhiều hơn một giá trị, giả sử nhóm bên trái và chọn một giá trị trong đó như 6 chẳng hạn. So sánh từng giá trị trong ngoặc với 6 và xếp các giá trị nhỏ hơn vào một nhóm bên trái 6 và giá trị lớn hơn và bên phải 6 {5, 3, 4}, 6, {9, 8}, 10, {11, 14, 17} Nếu chúng ta xem xét nhóm ngoài cùng bên trái và chọn giá trị 4 để so sánh thì thu được {3}, 4, {5}, 6, {9, 8}, 10, {11, 14, 17} Thuật toán tiếp tục cho tới khi không còn tập hợp nào chứa nhiều hơn một giá trị. Bằng trực giác có thể thấy được trường hợp xấu nhất xảy ra khi giá trị so sánh được chọn là một giá trị tuyệt đối, hoặc là giá trị nhỏ nhất, hoặc là giá trị lớn nhất trong nhóm. Trong trường hợp này, dễ thấy số lượng phép so sánh cần thiết là n(n − 1)/2. Tuy nhiên, thuật toán sẽ hữu dụng hơn bằng cách xác định số lượng so sánh trung bình cần thiết khi giá trị so sánh được chọn ngẫu nhiên. Giả sử mỗi giá trị so sánh được chọn trong ngoặc có thể là bất cứ giá trị nào . Gọi X là số phép so sánh cần sử dụng. Để tính E[X], trước hết ta biểu diễn X thành tổng các biến ngẫu nhiên khác theo cách sau. Đầu tiên, ta đánh dấu cho các giá trị được sắp xếp: 1 biểu thị giá trị nhỏ nhất, 2 biểu thị giá trị nhỏ nhì, cứ như vậy cho tới hết. Khi đó, với 1 ≤ i < j ≤ n, lấy I(i, j) bằng 1, nếu i và j được so sánh trực tiếp và bằng 0 nếu i và j không được so sánh trực tiếp. Tính 11
Luận văn tốt nghiệp Phạm Thị Thu Hằng tổng các biến này với i < j cho ta tổng số phép so sánh. Đó là j−1 n X X X= I(i, j) j=2 i=1 tức là j−1 n X X E[X] = E[ I(i, j)] j=2 i=1 j−1 n X X = E[I(i, j)] j=2 i=1 j−1 n X X = P { i và j được so sánh } j=2 i=1 Để tính xác suất để i và j được so sánh, chú ý rằng giá trị i, i + 1, . . . , j − 1, j ban đầu cùng nằm trong một nhóm (vì tất cả các giá trị ban đầu đều cùng trong nhóm) và sẽ vẫn cùng nhóm nếu giá trị so sánh được chọn đầu tiên không nằm giữa i và j . Ví dụ, nếu số được so sánh lớn hơn j thì tất cả các giá trị i, i + 1, . . . , j − 1, j sẽ cùng nằm trong nhóm bên trái số đó còn nếu số được so sánh nhỏ hơn i thì tất cả sẽ cùng nằm trong nhóm bên phải. Do đó, tất cả các giá trị i, i + 1, . . . , j − 1, j sẽ vẫn cùng nhóm cho tới khi một trong số các giá trị này được chọn làm giá trị so sánh. Nếu giá trị so sánh này không phải là i và j thì khi so sánh với nó, i sẽ nằm trong nhóm bên trái còn j thì thuộc nhóm bên phải, do đó i và j sẽ không bao giờ được so sánh. Biết rằng giá trị so sánh là một trong các giá trị nằm giữa i và j nên nó có thể là bất cứ giá trị nào trong j − i + 1 giá trị còn lại, do đó xác suất để hoặc i hoặc j được so sánh là 2/(j − i + 1). Ta có thể rút ra kết luận: 2 P {i và j được so sánh} = j−i+1 12
Luận văn tốt nghiệp Phạm Thị Thu Hằng Từ đó ta thấy, j−1 n X X 2 E[X] = j−i+1 j=2 i=1 j n X X 1 = 2 bằng cách cho k=j-i+1 k j=2 k=2 n X n X 1 = 2 qua việc trao đổi thứ tự của tổng k k=2 j=k n X n−k+1 = 2 k k=2 n X 1 = 2(n + 1) − 2(n − 1) k k=2 Áp dụng công thức tiệm cận cho n lớn n X 1 v log(n) k k=2 Ta thấy (bỏ qua giới hạn tuyến tính 2(n − 1) thuật toán sắp xếp nhanh yêu cầu trung bình khoảng 2n log(n) phép so sánh để sắp xếp n giá trị. 1.1.2.1 Thuật toán tìm kiếm Tiếp tục giả sử một tập hợp gồm n giá trị khác nhau x1 , x2 , . . . , xn nhưng lần này, mục đích của chúng ta là tìm giá trị nhỏ thứ k trong số đó. Thuật toán tìm kiếm khá giống với thuật toán sắp xếp nhanh, cả hai cùng bắt đầu bằng cách chọn ngẫu nhiên một giá trị rồi so sánh từng giá trị còn lại với nó và đặt các giá trị nhỏ hơn vào trong nhóm bên trái và giá trị lớn hơn vào nhóm bên phải. Giả sử r − 1 giá trị được đặt trong nhóm bên trái, có ba khả năng xảy ra : 1. r=k 2. rk Trong trường hợp (1), giá trị nhỏ thứ k là giá trị so sánh và thuật toán kết thúc. Trong trường hợp (2), vì giá trị nhỏ thứ k là giá trị nhỏ thứ (k − r) trong 13
Luận văn tốt nghiệp Phạm Thị Thu Hằng (n − r) giá trị trong nhóm bên phải nên quá trình bắt đầu lại với một giá trị trong nhóm này. Trong trường hợp (3), quá trình bắt đầu lại bằng cách tìm kiếm giá trị nhỏ thứ k trong r − 1 giá trị ở nhóm bên trái. Đặt X là số so sánh thuật toán sử dụng. Như trong phân tích thuật toán sắp xếp nhanh ở trên, coi 1 là giá trị nhỏ nhất,2 là giá trị nhỏ thứ hai,. . . và quy ước I(i, j) bằng 1 nếu i và j được so sánh trực tiếp và bằng 0 nếu i và j không được so sánh trực tiếp. Khi đó j−1 n X X X= I(i, j) j=2 i=1 và j−1 n X X E[X] = P {i và j được so sánh } j=2 i=1 Để tìm được xác suất để i và j được so sánh, chúng ta xem xét các trường hợp sau : Trường hợp 1: i < j ≤ k Trong trường hợp này, i, j, k sẽ vẫn cùng nhóm cho tới khi một trong các giá trị i, i + 1, . . . , k được chọn làm giá trị so sánh. Nếu giá trị được chọn hoặc là i hoặc là j thì cặp giá trị sẽ được so sánh, nếu không, chúng sẽ không được so sánh. Vì giá trị so sánh có thể là bất cứ giá trị nào trong k − i + 1 giá trị này, chúng ta thấy : 2 P {i và j được so sánh} = k−i+1 Trường hợp 2: i ≤ k < j Trong trường hợp này, i, j, k vẫn nằm trong cùng nhóm cho tới khi một trong j − i + 1 giá trị i, i + 1, . . . , j được chọn làm giá trị so sánh. Nếu giá trị được chọn là i hoặc j thì cặp giá trị sẽ được so sánh và ngược lại. Do đó, 2 P {i và j được so sánh} = j−i+1 Trường hợp 3: k < i < j Trong trường hợp này, 2 P {i và j được so sánh} = j−k+1 Từ đó ta có j−1 k X n X k n j−1 1 X 1 X 1 X X 1 E[X] = + + 2 k−i+1 j−i+1 j−k+1 j=2 i=1 j=k+1 i=1 j=k+2 i=k+1 14
Luận văn tốt nghiệp Phạm Thị Thu Hằng Để ước lượng giá trị trên khi n và k lớn, đặt k = αn với 0 < α < 1. Có j−1 k X k−1 Xk X 1 X 1 = k−i+1 k−i+1 j=2 i=1 i=1 j=i+1 k−1 X k−i = k−i+1 i=1 k X j−1 = j j=2 v k − log(k) v k = αn Tương tự, n X k n X 1 X 1 1 = + ... + j−i+1 j−k+1 j j=k+1 i=1 j=k+1 Xn v (log(j) − log(j − k)) j=k+1 Z n Z n−k v log(x)dx − log(x)dx k 1 v n log(n) − n − (αn log(αn) − αn) −(n − αn) log(n − αn) + (n − αn) v n[−α log(α) − (1 − α) log(1 − α)] Tương tự như trên n j−1 X X 1 v n − k = n(1 − α) j−k+1 j=k+2 i=k+1 Ta thấy E[X] v 2n[1 − α log(α) − (1 − α) log(1 − α)] Do đó, số phép so sánh trung bình thuật toán tìm kiếm cần là công thức tuyến tính của số giá trị. 1.1.3 Mô hình danh sách tự tổ chức Xem xét n phần tử e1 , . . . , en ban đầu được sắp xếp theo một trật tự. Tại mỗi thời điểm có một yêu cầu đối với một trong số các phần tử này; ei được yêu cầu 15
Luận văn tốt nghiệp Phạm Thị Thu Hằng độc lập với trước đó, xác suất Pi . Sau khi đáp ứng được yêu cầu, phần tử này được chuyển lên đầu danh sách. Ví dụ, nếu trật tự hiện tại là e1 , e2 , e3 , e4 và e3 được yêu cầu thì trật tự sau đó là e3 , e1 , e2 , e4 . Chúng ta sẽ xác định vị trí kỳ vọng của phần tử được yêu cầu với giả thiết quá trình này diễn ra trong thời gian dài. Đặt R là vị trí phần tử được yêu cầu, ta sẽ tìm E[R] phần tử được chọn bằng cách kiểm tra điều kiện với Y . Ta có Xn E[R] = E[R|Y = ei ]Pi i=1 n X = E[ vị trí của ei | Y = ei ]Pi i=1 Xn = E[ vị trí của ei ]Pi (1.1) i=1 Dấu bằng cuối cùng dựa trên cơ sở vị trí của ei và biến cố ei được yêu cầu độc lập với nhau. Điều này có được do xác suất để ei được yêu cầu là Pi cho dù hiện tại ei có ở vị trí nào đi nữa. Tuy nhiên, ta thấy X vị trí của ei = 1 + Ii,j j6=i trong đó 1, nếu ej đứng trước ei Ii,j = 0, ngược lại ta thu được X E[vị trí của ei ] = 1 + E[Ii,j ] j6=i X =1+ P {ej đứng trước ei } (1.2) j6=i Để xác định P {ej đứng trước ei }, ta thấy ej đứng trước ei nếu lần yêu cầu cuối cùng với một trong hai phần tử này là lần yêu cầu với ej . Tuy nhiên, biết rằng một lần yêu cầu có thể yêu cầu hoặc ei hoặc ej nên xác suất để ej được yêu cầu là Pj P (ej | ei hoặc ej ) = Pi + Pj Do đó, P {ej đứng trước ei } = Pj /(Pi + Pj ). Từ kết quả (??) và (??) ta có Xn X Pj E[R] = 1 + Pi P i + Pj i=1 j6=i 16
Luận văn tốt nghiệp Phạm Thị Thu Hằng 1.1.4 Sinh hoán vị ngẫu nhiên Ta nói rằng vec-tơ X(1), . . . , X(n) ngẫu nhiên là hoán vị ngẫu nhiên của giá trị 1, . . . , n nếu P {(X(1), . . . , X(n)) = (i1 , ...in )} = 1/n! cho tất cả n! hoán vị i1 , . . . , in của 1, . . . , n. Khi đó, một hoán vị ngẫu nhiên có thể là bất cứ hoán vị nào trong n! hoán vị của 1, . . . , n. Giả sử trong phần này X(1), . . . , X(n) là một hoán vị ngẫu nhiên. Ví dụ 1.1.1. Bài toán đối sánh Giả sử mỗi người trong n người tham gia bữa tiệc đóng góp chiếc mũ của họ. Số mũ này được tổng hợp lại để sau đó mỗi người ngẫu nhiên chọn một chiếc. Nếu ta xác định một chiếc mũ bằng người sở hữu nó và gọi X(i) là chiếc mũ được chọn bởi người i thì giả sử người chọn mũ có thể chọn bất cứ chiếc mũ nào còn lại vào thời điểm chọn thì X(1), . . . , X(n) là một hoán vị ngẫu nhiên. Gọi X 1 (i) = X(i) và với j > 1: X j (i) = X(X j−1 (i)) Ví dụ, trong bài toán đối sánh, X 2 (i) sẽ là chiếc mũ được chọn bởi người có chiếc mũ được chọn bởi người i. Nếu X k (i) = i thì chuỗi i, X(i), . . . , X k−1 (i) được gọi là một chu trình. Ví dụ với n = 6, và X(1) = 2, X(2) = 4, X(3) = 6, X(4) = 1, X(5) = 5, X(6) = 3 khi đó 1, 2, 4 3, 6 5 đều là chu trình. Lưu ý rằng một chu trình là một chuỗi tuần hoàn mà trong đó nó có thể bắt đầu tại bất cứ giá trị nào. Nếu X k (i) = i thì i, X(i), . . . , X k−1 (i) và X j (i), . . . , X k−1 (i), i, X(i), . . . , X j−1 (i) là phép biểu diễn của cùng một chu trình. Ngoài ra, mỗi giá trị 1, . . . , n là một phần tử của đúng một chu trình. Ví dụ 1.1.2. Trong bài toán đối sánh, 1, 5, 3 là một chu trình nếu người 1 chọn mũ của người 5, người 5 chọn mũ của người 3 và người 3 chọn mũ của người 1. Các chu trình 1, 5, 3 5, 3, 1 3, 1, 5 được coi là một chu trình. 17
Luận văn tốt nghiệp Phạm Thị Thu Hằng Nếu X(i) = i ta nói rằng i là một điểm cố định của hoán vị. Trong bài toán đối sánh, i là điểm cố định nếu người i chọn đúng chiếc mũ của mình. Bây giờ chúng ta sẽ tính toán hàm phân phối xác suất số điểm cố định của một hoán vị ngẫu nhiên. Trước hết chúng ta phải tìm xác suất để không có điểm cố định nào. Gọi En là biến cố không có điểm cố định trong hoán vị ngẫu nhiên n giá trị (một hoán vị ngẫu nhiên mà không có điểm cố định nào được gọi là Xáo trộn), và Pn = P (En ). Để tìm Pn , gọi C là chiều dài chu trình chứa một giá trị thiết lập, giả sử 1. Kiểm tra điều kiện với C được n X Pn = P (En | C = k)P {C = k} (1.3) k=1 bây giờ P {C = k} = P {X(1) 6= 1, X 2 (1) 6= 1, ..., X k−1 (1) 6= 1, X k (1) = 1} n−1n−2 n−k+1 1 = ... n n−1 n−k+2n−k+1 1 = (1.4) n Khi đó, kích thước của chu trình chứa một giá trị thiết lập có thể là bất cứ giá trị nào trong số các giá trị 1, . . . , n. Vì C = 1 tương đương với X(1) = 1, ta thấy P (En | C = 1) = 0 (1.5) Giả sử C = k > 1, gọi S là chu trình chứa giá trị 1. Vì S là một chu trình nên nếu i ∈ / S thì X(i) ∈ / S . Biết rằng C = k , do đó vec-tơ ngẫu nhiên X(i), i ∈ / S , là một hoán vị của n − k giá trị không thuộc chu trình. Vì thế với k > 1 thì P (En | C = k) = Pn−k , k>1 (1.6) Thay thế kết quả từ (??), (??), (??) vào (??) ta được n 1X Pn = Pn−k n k=2 tương đương với n X nPn = Pn−k k=2 18

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.09: Bộ Luận Văn Tốt Nghiệp Chuyên Ngành Quản Trị Kinh Doanh

81 tài liệu

1643 lượt tải

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.