課程資訊
課程名稱
機率方法
The Probability Method 
開課學期
101-2 
授課對象
理學院  數學研究所  
授課教師
張鎮華 
課號
MATH5701 
課程識別碼
221 U5100 
班次
 
學分
全/半年
半年 
必/選修
選修 
上課時間
星期三1(8:10~9:00)星期五1,2(8:10~10:00) 
上課地點
天數101天數101 
備註
總人數上限:30人 
Ceiba 課程網頁
http://ceiba.ntu.edu.tw/1012_Prob_Method 
課程簡介影片
 
核心能力關聯
本課程尚未建立核心能力關連
課程大綱
為確保您我的權利,請尊重智慧財產權及不得非法影印
課程概述

The probability Method has recently been developed intensively and become one of the most powerful and widely used tools applied in Combinatorics. The basic Probability Method can be described as follows: In order to prove the existence of a combinatorial structure with certain properties, we construct an appreciate probability space and show that a randomly chosen element in this space has the desired properties with positive probability. This method was initiated by Paul Erdos, who contributed so much to its development over the last fifty years.

In this one-semester course, we shall teach methods as well as topics in the Probability Method applicable to Combinatorics using the famous textbook by Alon and Spencer. For the part of methods, we will touch basic method, linearity of expectation, alterations, second moment, Local Lemma, correlation inequalities, martingales and tight concentration, the Poisson paradigm, pseudo-randomness etc. For the part of topics, we shall touch random graphs, circuit complexity, discrepancy, geometry, cods, games and entropy, de-randomization etc. 

課程目標
The purpose of this one-semester course is to introduce the basic knowledge for the Probability Method applicable to Combinatorics. 
課程要求
 
預期每週課後學習時數
 
Office Hours
每週三 15:20~17:20 
參考書目
N. Alon and J. H. Spencer, The Probability Method, Third Edition, John Wiley &
Sons, New York, 2008. 
指定閱讀
 
評量方式
(僅供參考)
   
課程進度
週次
日期
單元主題
第1週
2/20,2/22  The Basic Method 
第2週
2/27,3/01  The Basic Method 
第3週
3/06,3/08  Linearity and Expectation 
第4週
3/13,3/15  Linearity and Expectation 
第5週
3/20,3/22  Alterations 
第6週
3/27,3/29  Alterations 
第7週
4/03,4/05  The Second Moment (Holiday) 
第8週
4/10,4/12  The Second Moment 
第9週
4/17,4/19  The Local Lemma ***** Midterm Exam on 4/19 (You may come to the class at 6:00 if you wish.) 
第10週
4/24,4/26  The Local Lemma 
第11週
5/01,5/03  Correlation Inequalities 
第12週
5/08,5/10  Correlation Inequalities 
第13週
5/15,5/17  Martingales and Tight Concentration 
第14週
5/22,5/24  Martingales and Tight Concentration 
第15週
5/29,5/31  The Poisson Paradigm 
第16週
6/05,6/07  The Poisson Paradigm 
第17週
6/12,6/14  Pseudorandomness ********* Final exam on 6/14 (Friday)