組合數學
Combinatorial Mathematics
學期
112-2
學分
3
學分
當期課號
515610
永久課號
CSCS20035
開課單位
資訊工程學系
授課教師
高孟駿
校區
光復
類別
選修
上課時間表
| 節 | 週一 |
|---|---|
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. Course website: https://sites.google.com/nycu.edu.tw/112-2-combo-math/
先修科目
Linear Algebra, Probability, Discrete Mathematics
教學方式
The class will be given via premade video recordings (to be played at class) with in-class explanations. Students are expected to read the lecture notes & slides and do homework problems spontaneously in order to fully understand the concepts.
評分方式
Approximately 5 Handwritten Homework: 20% Approximately 4 Program Assignments: 20% Two Midterm Exams and Final: 60%
課程大綱
- The classics
- Topics in graphs
- Extremal set theory
- Advanced topics
週次計畫
| 週次 | 主題 |
|---|---|
| 第 1 週 | Probabilistic method |
| 第 2 週 | The Pigeonhole principle |
| 第 3 週 | Miscellaneous topics in counting |
| 第 4 週 | The Lovasz sieve and the local lemma |
| 第 5 週 | Supplement: The Algorithmic Lovasz local lemma |
| 第 6 週 | *** Midterm (I) *** |
| 第 7 週 | System of distinct representativesHall's marriage theorem |
| 第 8 週 | Maximum bipartite matching |
| 第 9 週 | Weighted bipartite matching The Hungarian algorithm for min-cost perfect matching |
| 第 10 週 | The max-flow min-cut theorem |
| 第 11 週 | *** Midterm (II) *** |
| 第 12 週 | Intersecting families, Chains and antichains |
| 第 13 週 | Blocking set and the duality |
| 第 14 週 | Eigenvalues and graph expansions |
| 第 15 週 | Supplement: Random walks |
| 第 16 週 | *** Final exam *** |
| 第 17 週 | |
| 第 18 週 |
教科書
1. Applied Combinatorics, 6th Ed, Alan Tucker 2. Extremal Combinatorics, 2nd Ed, Stasys Junka.
Office Hours
- 時間
- In class or by appointment via email (if necessary)