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

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.
Nội dung trích xuất từ tài liệu:
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ỘITRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ----------------------- PHẠM THỊ THU HẰNGMỘT SỐ MÔ HÌNH XÁC SUẤTTRONG 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ỘITRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ----------------------- PHẠM THỊ THU HẰNGMỘT SỐ MÔ HÌNH XÁC SUẤTTRONG KHOA HỌC MÁY TÍNHChuyê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 2015Mụ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 ứngdụ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íchxá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ácsuấ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 trongxá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àycung 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ậttoá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ảnxí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 dungcũ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ònrấ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 ĐặngHù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ổ 2Luận văn tốt nghiệp Phạm Thị Thu Hằngbộ 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ướngdẫ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 3Chương 1Xác suất trong lý thuyết tổ hợpvà đồ 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ònsố hiệu của mỗi đỉnh và nối các đỉnh bởi một đường thẳng hoặc cong nếucó 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. Ở đâyta 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ị trongHì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ạnhA = {(i, X(i)), i = 1, . . . , n} trong đó X(i) là các biến ngẫu nhiên độc lập thỏamã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 đỉnhcòn lại của đồ thị (bao gồm cả i), trong đó xác suất để đỉnh j được chọn là Pj , 4Luậ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.3sau đó 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à 5Luậ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 ...