課程名稱:

隨機方法論 (The Probabilistic Method)

先修課程:

機率,演算法

課程目標:

使同學了解機率在演算法,計算理論,組合數學等相關領域之應用. 並熟悉其證明方法.

主要教科書:

The Probabilistic Method, 2nd Ed, Noga Alon and Joel Spencer.

Reference:

Randomized Algorithms, by Motwani and Raghava, and handouts. .

課程內容:

本課程將包涵下列內容:
  1. The Basic Method
  2. Linearity of Expection
  3. Alternations
  4. The Second Moment
  5. The Local Lemma
  6. Correlation Inequalities
  7. Martingales
  8. The Poisson Paradigm
  9. Pseudorandomness
  10. Random graphs
  11. Circuit Complexity
  12. Discrepancy
  13. Geometry
  14. Codes, Games and Entropy
  15. Derandomization