課程名稱 |
機率方法 The Probability Method |
開課學期 |
101-2 |
授課對象 |
理學院 數學系 |
授課教師 |
張鎮華 |
課號 |
MATH5701 |
課程識別碼 |
221 U5100 |
班次 |
|
學分 |
3 |
全/半年 |
半年 |
必/選修 |
選修 |
上課時間 |
星期三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) |
|