組合數學(英文授課)
Combinatorial Mathematics
| 節 | 週一 |
|---|---|
A 18:30–19:20 | 組合數學(英文授課) EC114（光復） 2 節連堂 |
B 19:30–20:20 |
* 根據陽明交大上課時間表所列
To learn the concepts of combinatorics and its potential applications in computer science. Students are expected to read the prepared course material (lecture notes & recorded videos) at home and do weekly or biweekly homework problems at class. The course website https://sites.google.com/nycu.edu.tw/110-2-combo-math
Linear algebra, Probability, Discrete mathematics
無備註
Students are expected to learn the prepared course material (lecture notes & recorded videos) at home and do homework problems at class. The weekly homework problems will consist of two parts, one that has to be done in class and the other that can be taken home.
Approximately 10~12 homework: 60% Two midterm exams and Final: 40%
The classics
Basic counting, Probabilistic counting, The pigeonhole principle, Generating functions, Recurrence relations
- 講授：
- 12
Topics in graphs
Hall's matching theorem, The max-flow min-cut theorem, The Hungarian algorithm
- 講授：
- 9
Extremal set theory
Intersecting families, Chains and antichains, Blocking set and duality, Hereditary sets, Matroids and approximation
- 講授：
- 9
Advanced topics
Eigenvalues and graph expansions, The Lovász sieve and the local lemma, Random walks
- 講授：
- 9
| 週次 | 主題 |
|---|---|
| 第 1 週 | Basic counting principles |
| 第 2 週 | Probabilistic counting |
| 第 3 週 | Generating functions, The pigeonhole principle |
| 第 4 週 | Recurrence relations |
| 第 5 週 | Hall's marriage theorem |
| 第 6 週 | *** Midterm (I) *** |
| 第 7 週 | The max-flow min-cut theorem |
| 第 8 週 | The Hungarian algorithm for min-cost perfect matching |
| 第 9 週 | Intersecting families, Chains and antichains |
| 第 10 週 | Blocking set and the duality |
| 第 11 週 | Hereditary set, Matroids and approximation |
| 第 12 週 | *** Midterm (II) *** |
| 第 13 週 | Eigenvalues and graph expansions |
| 第 14 週 | The Lovász sieve and the local lemma |
| 第 15 週 | Random walks |
| 第 16 週 | *** Final exam *** |
1. Applied Combinatorics, 6th Ed, Alan Tucker 2. Extremal Combinatorics, 2nd Ed, Stasys Junka.
- 地點
- 教師未提供此項資料
- 時間
- In class, or privately by appointment via email (if necessary)
- 聯絡方式
- 教師未提供此項資料