🎲 隨機演算法
探討機率工具、隨機化技巧、以及各種隨機演算法的設計與分析
📖 課程筆記
隨機演算法導論
什麼是隨機演算法？為什麼要使用隨機性？Las Vegas 與 Monte Carlo 的差異
Minimax Theorem 與 Yao's Principle
von Neumann Minimax Theorem、Mixed Strategy、Yao's Principle 與演算法 lower bound
賽局論基礎
Zero-sum game、payoff matrix、pure strategy、VR/VC、saddle point
隨機快速排序與選擇
Randomized QuickSort 期望 O(n log n)，Randomized Select 期望 O(n)
隨機複雜度類別
從 Turing Machine 到 P/NP，再到隨機複雜度類別 RP/BPP/ZPP
機率基礎工具
機率公理、條件機率、Bayes 定理、期望值線性、常見分佈
Karger's Min-Cut Algorithm
用隨機邊收縮找最小割，分析成功率與重複次數
Chernoff Bound
對獨立 0/1 隨機變數的和，給出比 Chebyshev 更緊的尾部機率上界
📚 主題架構
機率工具 (Probability Tools)
- Markov Inequality
- Chebyshev Inequality
- Chernoff Bound
- Union Bound
隨機化技巧 (Randomization Techniques)
- Randomized Quicksort
- Randomized Selection
- Las Vegas vs Monte Carlo
雜湊與資料結構 (Hashing & Data Structures)
- Universal Hashing
- Bloom Filter
- Count-Min Sketch
進階主題 (Advanced Topics)
- Randomized Rounding
- Derandomization
- Random Walks