Khóa học Khoa học Máy tính CPSC 469/569 của Đại học Yale về Thuật toán Ngẫu nhiên. Phù hợp để sử dụng làm tài liệu bổ sung cho khóa học nhập môn sau đại học hoặc đại học nâng cao về thuật toán ngẫu nhiên. Thảo luận về các công cụ từ lý thuyết xác suất, bao gồm biến ngẫu nhiên và kỳ vọng, đối số ràng buộc hợp, ràng buộc nồng độ, ứng dụng của martingale và chuỗi Markov, và Bổ đề Địa phương Lovász. Các chủ đề thuật toán bao gồm phân tích các thuật toán ngẫu nhiên cổ điển như Quicksort và FIND của Hoare, cấu trúc dữ liệu cây ngẫu nhiên, băm, lấy mẫu Monte Carlo chuỗi Markov, đếm xấp xỉ ngẫu nhiên, khử ngẫu nhiên, điện toán lượng tử, và một số ví dụ về thuật toán phân tán ngẫu nhiên.

Abstract:

Lecture notes for the Yale Computer Science course CPSC 469/569 Randomized Algorithms. Suitable for use as a supplementary text for an introductory graduate or advanced undergraduate course on randomized algorithms. Discusses tools from probability theory, including random variables and expectations, union bound arguments, concentration bounds, applications of martingales and Markov chains, and the Lovász Local Lemma. Algorithmic topics include analysis of classic randomized algorithms such as Quicksort and Hoare's FIND, randomized tree data structures, hashing, Markov chain Monte Carlo sampling, randomized approximate counting, derandomization, quantum computing, and some examples of randomized distributed algorithms.

Ngôn ngữ:	eng
Tác giả:	James Aspnes
Thông tin nhan đề:	Notes on Randomized Algorithms
Nhà xuất bản:	IT eBooks
Loại hình:	Tài nguyên giáo dục mở / Bộ sưu tập: Công nghệ thông tin
Bản quyền:	https://creativecommons.org/share-your-work/use-remix/cc-licenses/#by-sa
Nguồn gốc:	https://it-ebooks.dev/books/other/notes-on-randomized-algorithms
Mô tả vật lý:	539tr
Năm xuất bản:	2024