離散數學
Discrete Mathematics
| 節 | 週一 |
|---|---|
5 13:20–14:10 | 離散數學 MB311（光復） 3 節連堂 |
6 14:20–15:10 | |
7 15:30–16: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 shall (1) introduce the fundamentals and techniques of discrete mathematics and combinatorial reasoning that are so different from the traditional coverage in calculus and differential equations; (2) develop the mathematical maturity of the students by bridging the real world problems and the combinatorial implications, and (3) present adequate modern research topic/open problems and encourage master students to explore and investigate.
無
無備註
Course site: https://sites.google.com/view/sjdmath
1學期作業 平時作業、程式作業若干次 2.考試狀況 小考、期中考 3.評量方法 平時作業、小考與上課參與:35%、期中考:35%、分組報告: 30%
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. 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
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
Ch. 9: Generating Functions
1. Introductory Examples 2. Definition and Examples: Calculational Techniques 3. Partitions of Integers 4. The Exponential Generating Function
- 講授：
- 6
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
Ch. 13: Optimization and Matching
1. Dijkstra’s Shortest-Path Algorithm 2. Minimal Spanning Trees: The Algorithms of Kruskal and Prim 3. Matching Theory
- 講授：
- 3
Ch. 14: Ring and Modular Arithmetic
1. Ring Structures 2. Ring Properties 3. Integers Modulo n 4. Homomorphism and Isomorphism
- 講授：
- 6
Ch 17: Finite Fields and Combinatorial Designs
1. Polynomial Rings 2. Irreduciblle Polynomials: Finite Fields 3. Latin Squares
- 講授：
- 6
| 週次 | 主題 |
|---|---|
| 第 1 週 | Rules of Sum and Product, Permutations, Combinations 2024-09-02(一) |
| 第 2 週 | Combinations, Combinations with Repetition, Binomial theorem 2024-09-09(一) |
| 第 3 週 | Catalan Numbers, Set and Subsets, Set Operations, Laws of Set Theory, Counting and Venn Diagrams 2024-09-16(一) |
| 第 4 週 | Fundamentals of Logic, Logical Implication: Rules of Inference 2024-09-23(一) |
| 第 5 週 | 國慶日 2024-09-30(一) |
| 第 6 週 | Well-Ordering Principle: Mathematical Induction, Recursive Definitions 2024-10-07(一) |
| 第 7 週 | Cartesian Products and Relations, Plain, One-to-One and Onto Functions, Properties of Relations, Computer Recognition: 0-1 Matrices and Directed Graphs 2024-10-14(一) |
| 第 8 週 | Pigeonhole Principle, Composition and Inverse 2024-10-21(一) |
| 第 9 週 | Generating Functions 2024-10-28(一) |
| 第 10 週 | Partitions of Integers, The Exponential Generating Function 2024-11-04(一) |
| 第 11 週 | Midterm Exam. 2024-11-11(一) |
| 第 12 週 | The Division Algorithm, Prime Numbers, The Greatest Common Divisor, The Euclidean Algorithm, The Fundamental Theorem of Arithmetic 2024-11-18(一) |
| 第 13 週 | Equivalence Relations and Partitions, Principle of Inclusion and Exclusion 2024-11-25(一) |
| 第 14 週 | Subgraphs, Complements, and Graph Isomorphism, Graph Isomorphism, Planar Graphs, Hamilton Paths and Cycles Graph Coloring, Euler Trails and Circuits 2024-12-02(一) |
| 第 15 週 | Minimal Spanning Trees: Algorithms of Kruskal and Prim, Transport Networks: The Max-Flow Min-Cut Theorem,Matching Theory 2024-12-09(一) |
| 第 16 週 | Rings, Modular arithmetic, Ring Homomorphisms and Isomorphisms,Polynomial Rings 2024-12-16(一) |
| 第 17 週 | 開國紀念日 2024-12-23(一) |
| 第 18 週 | Group, Hamming matrices, Irreducible Polynomials, Finite Fields, Latin squares, Finite Geometries and Affine Planes 2024-12-30(一) |
R.P. Grimaldi, Discrete and Combinatorial Mathematics, 5th ED., Addison-Wesley, 2003, Reading, Massachusetts. 新月圖書代理
- 地點
- MB311
- 時間
- Monday EFG
- 聯絡方式
- sjshyu@gmail.com