離散數學
Discrete Mathematics
| 節 | 週一 |
|---|---|
7 15:30–16:20 | 離散數學 MB312（光復） 3 節連堂 |
8 16:30–17:20 | |
9 17:30–18:20 |
* 根據陽明交大上課時間表所列
This course intends to cover four basic areas in the study of computer science: discrete methods, combinatorics, graph theory and finite algebraic structures. We will (1) introduce the topics and techniques of discrete mathematics and combinatorial reasoning; (2) develop the mathematical maturity of the students through the study of an area that is so different from the traditional coverage in calculus and differential equations, and (3) present an adequate survey of topics for the computer science students who will be taking more advanced courses.
無
無備註
Course Web: https://sites.google.com/view/sjdmath/home?authuser=0
In-class Participation and Homework Assignments: 35% Midterm Exam.: 35% Group Presentation: 35%
Ch. 1: Basic Principles of Counting
1. Rules of Sum and Product 2. Permutations 3. Combinations 4. Combinations with Repetition 5. Catalan Numbers
- 講授：
- 9
Ch. 3: Set Theory
1. Set and Subsets 2. Set Operations and Laws of Set Theory 3. Counting and Venn Diagrams
- 講授：
- 3
Ch. 4: Properties of Integers
1. Well-Ordering Principle: Mathematical Induction 2. Recursive Definitions
- 講授：
- 3
Ch. 5: Relations and Functions
1. Cartesian Products and Relations 2. Functions: Plain and One-to-One 3. Onto Functions: Strrling Numbers 4. Pigeonhole Principle 5. Composition and Inverse 6. Computational Complexity
- 講授：
- 6
Ch. 9: Generating Functions
1. Introductory Examples 2. Definition and Examples: Calculational Techniques 3. Partitions of Integers 4. The Exponential Generating Function
- 講授：
- 6
Midterm
- 其他：
- 3
Ch. 7: Relations: Second Round
1 Relations Revisited: Properties of Relations 2 Computer Recognition: Zero-One Matrices and Directed Graphs 3 Partial Orders: Hasse Diagrams 4 Equivalence Relations and Partitions
- 講授：
- 4
備註：Group presentation
Ch. 8: The Principle of Inclusion and Exclusion
1 The Principle of Inclusion and Exclusion 2 Generalizations of the Principle 3 Derangements: Nothing Is in Its Right Place 4 Rook Polynomials 5 Arrangements with Forbidden Positions
- 講授：
- 4
備註：Group presentation
Ch. 11: An Introduction to Graph Theory
1 Definitions and Examples 2 Subgraphs, Complements, and Graph Isomorphism 3 Vertex Degree: Euler Trails and Circuits 4 Planar Graphs 5 Hamilton Paths and Cycles 6 Graph Coloring and Chromatic Polynomials
- 講授：
- 4
備註：Group presentation
Ch. 12: Trees
1 Definitions, Properties, and Examples 2 Rooted Trees 3 Trees and Sorting 4 Weighted Trees and Prefix Codes
- 講授：
- 4
備註：Group presentation
Ch. 13: Optimization and Matching
1 Dijkstra’s Shortest-Path Algorithm 2 Minimal Spanning Trees: The Algorithms of Kruskal and Prim 3 Matching Theory
- 其他：
- 4
備註：Group presentation
Ch. 16: Coding Theory
1 RSA Cryptosystem 2 Elements of Coding Theory 3 The Hamming Metric 4 The Parity-Check and Generator Matrices
- 講授：
- 4
備註：Group presentation
Ch. 16: Coding Theory
1 RSA Cryptosystem 2 Elements of Coding Theory 3 The Hamming Metric 4 The Parity-Check and Generator Matrices
- 講授：
- 4
備註：Group presentation
| 週次 | 主題 |
|---|---|
| 第 1 週 | Rules of Sum and Product, Permutations, Combinations |
| 第 2 週 | Combinations, Combinations with Repetition |
| 第 3 週 | Catalan Numbers, Set and Subsets |
| 第 4 週 | Set Operations, Laws of Set Theory, Counting and Venn Diagrams |
| 第 5 週 | Well-Ordering Principle: Mathematical Induction, Recursive Definitions |
| 第 6 週 | Cartesian Products and Relations, Plain, One-to-One and Onto Functions |
| 第 7 週 | Pigeonhole Principle, Composition and Inverse, Computational Complexity |
| 第 8 週 | Generating Functions |
| 第 9 週 | Partitions of Integers, The Exponential Generating Function |
| 第 10 週 | Midterm Exam. |
| 第 11 週 | Properties of Relations, Computer Recognition: 0-1 Matrices and Directed Graphs |
| 第 12 週 | Equivalence Relations and Partitions, Principle of Inclusion and Exclusion |
| 第 13 週 | Subgraphs, Complements, and Graph Isomorphism, Graph Isomorphism, |
| 第 14 週 | Planar Graphs, Hamilton Paths and Cycles; Graph Coloring, Euler Trails and Circuits |
| 第 15 週 | Definition and Examples of Trees, Trees and Sorting, Weighted Trees and Prefix Codes, Dijkstra's Shortest-Path Algorithm |
| 第 16 週 | Trees and Sorting, Weighted Trees and Prefix Codes, Dijkstra’s Shortest-Path Algorithm |
| 第 17 週 | Minimal Spanning Trees: Algorithms of Kruskal and Prim, RSA Cryptosystem |
| 第 18 週 | Elements of Coding Theory, Hamming Metric, Parity-Check and Generator Matrices |
R.P. Grimaldi, Discrete and Combinatorial Mathematics, 5th ED., Addison-Wesley, 2003, Reading, Massachusetts. 新月圖書代理
- 地點
- MB311
- 時間
- 1 GHI
- 聯絡方式
- sjshyu@gmail.com