Tóm tắt 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. Sau đây là tóm tắt của luận văn.
Nội dung trích xuất từ tài liệu:
Tóm tắt 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ÍNHChuyên ngành: Lý thuyết Xác suất và Thống kê toán học Mã số: 60406106 TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC Hà Nội - Năm 2016Mục lục 1Luận văn tốt nghiệp Phạm Thị Thu Hằng Công trình được hoàn thành tại: Trường Đại học Khoa hoc Tự nhiên - Đạihọc Quốc gia Hà Nội Người hướng dẫn khoa học: GS.TSKH Đặng Hùng Thắng Hội đồng chấm luận văn: • Chủ tịch: PGS.TS Trần Hùng Thao - Viện Toán học - Viện Hàn lâm KH và CN Việt Nam • Phản biện 1: TS. Nguyễn Thịnh - Đại học Khoa học Tự Nhiên - ĐHQGHN • Phản biện 2: TS. Ngô Hoàng Long - Đại học Sư phạm Hà Nội • Thư ký: TS. Lê Vỹ - Đại học Khoa học Tự Nhiên - ĐHQGHN • Ủy viên: TS. Trần Mạnh Cường - Đại học Khoa học Tự Nhiên - ĐHQGHN Luận văn đã được bảo vệ trước Hội đồng chấm luận văn thạc sĩ họp tại: KhoaToán-Cơ-Tin học Trường Đại học Khoa học Tự nhiên (ĐHQGHN) vào 15h giờ30 ngày 28 tháng 12 năm 2016 Có thể tìm đọc luận văn tại: - Trung tâm thư viện Đại học Quốc gia Hà Nội 2 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ổ 3Luậ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 4Chươ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 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 n X P {X(i) = j} = Pj , Pj = 1 j=1Đồ 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à đồ 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ủabiế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 ...