離散數學
Discrete Mathematics
學期
112-2
學分
3
學分
當期課號
516708
永久課號
SCMA10026
開課單位
應用數學系
授課教師
阮志豪
校區
光復
類別
必修
上課時間表
| 節 | 週二 | 週四 |
|---|---|---|
2 09:00–09:50 | 離散數學 SA320 | |
5 13:20–14:10 | 離散數學 SA320 2 節連堂 | |
6 14:20–15:10 |
* 根據陽明交大上課時間表所列
概述
Course description: This is an introduction to discrete mathematics, an area that studies finite sets and their relations. It has many applications in and connections with other topics in mathematics and beyond, including computer science. The main emphases of this course are on techniques of counting and basic combinatorial structures.
先修科目
Calculus I, Linear Algebra I
教學方式
Use e3 system.
評分方式
10% appearance, 30% homework, 30% midterm, 30% final.
課程大綱
- 1. What is Combinatorics
- 2. Permutations and Combinations
- 3.The Pigeonhole Principle
- 4. The Binomial Coefficients
- 5. The Inclusion-Exclusion Principle
- 6. Recurrence Relations and Generating Functions
- 7. Special Counting Sequences
- 8. Partially ordered sets and other relations
- 9. Introduction to Graph Theory*
週次計畫
| 週次 | 主題 |
|---|---|
| 第 1 週 | Introduction to combinatorics with examples; counting principles |
| 第 2 週 | Permutations and combinations of finite sets, permutations of multisets |
| 第 3 週 | Combinations of special multisets; generating permutations, combinations, and subsets |
| 第 4 週 | Pigeonhole principle (simple form and strong form) and examples; introduction to Ramsey theory |
| 第 5 週 | Ramsey theory (cont.), binomial coefficients and theorem, binomial identities, generalized binomial theorem |
| 第 6 週 | Multinomial theorem; inclusion-exclusion principle and examples, combinations of multisets, derangements |
| 第 7 週 | Fibonacci sequence as an example of recurrence sequences and generating functions |
| 第 8 週 | More on Fibonacci sequence; Midterm 11/4 |
| 第 9 週 | Ordinary and exponential generating functions |
| 第 10 週 | Exponential generating function of derangement numbers; homogeneous linear recurrence |
| 第 11 週 | Non-homogeneous linear recurrence; Catalan numbers |
| 第 12 週 | Stirling numbers and the twelvefold way |
| 第 13 週 | Partition numbers; equivalence relation and basic poset theory |
| 第 14 週 | Mirsky and Dilworth theorems; basic notions in graph theory |
| 第 15 週 | Minimum spanning trees and Kruskal's algorithm; Matrix-Tree Theorem, Cayley formula and Prufer sequences |
| 第 16 週 | Final exam 6/6 |
教科書
R. A. Brualdi, Introductory Combinatorics, 5th Edition, PEARSON
Office Hours
- 地點
- SA341
- 時間
- Send an e-mail to me to make appointment (not available: M78, R34)
- 聯絡方式
- chyuen@math.nctu.edu.tw