組合數學(英文授課)
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
- Topics in graphs
- Extremal set theory
- Advanced topics
| 週次 | 主題 |
|---|---|
| 第 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)