離散數學(英文授課)
Discrete Mathematics
學期
109-2
學分
3
學分
當期課號
1180
永久課號
DCP1244
開課單位
資訊學院共同課程
授課教師
葉宗泰
校區
光復
類別
必修
上課時間表
| 節 | 週二 | 週五 |
|---|---|---|
3 10:10–11:00 | 離散數學(英文授課) EC016 2 節連堂 | |
4 11:10–12:00 | ||
7 15:30–16:20 | 離散數學(英文授課) EC016 |
* 根據陽明交大上課時間表所列
概述
1. Students are expected to use mathematical reasoning to comprehend mathematical arguments and learn basic concepts of mathematical logic and proof 2. Students will learn to use counting to perform combinatorial analysis 3. Students will learn basic concepts of sets, permutations, relations, graphs, and tree discrete structures
先修科目
basic high school mathematics
教學方式
https://people.cs.nctu.edu.tw/~ttyeh/course/2021_Spring/DCP1244/outline.html
評分方式
Coursework assignment: 8 homework Exam: 8 Quizzes Evaluation: (tentative) There will be 8 quizzes (70%) and 8 homework (30%)
課程大綱
- Chap1: Logic and Proofs
- Chap 2: Sets, Functions, Sequences, and Sums
- Chap 3,4: Algorithms and the Integers
- Chap 5: Induction and Recursion
- Chap 6: Counting
- Chap 8: Advanced Counting Techniques
- Chap 9: Relations
- Chap 10: Graphs
- Chap 11: Trees
- Chap 12: Boolean Algebra
週次計畫
| 週次 | 主題 |
|---|---|
| 第 1 週 | 1.1 Proposition Logic 1.2 Proposition Equivalences 1.3 Predicates and Quantifiers |
| 第 2 週 | 1.4 Nested Quantifiers 1.5 Rules of Inference 1.6 Introduction to Proofs |
| 第 3 週 | 1.7 Proof Methods and Strategy 2.1 Sets 2.2 Set Operations |
| 第 4 週 | 2.3 Functions 2.4 Sequences and Summations 4.1 Divisibility and Modular Arithmetic |
| 第 5 週 | 4.2 Integer Representations and Algorithms 4.3 Primes and Greatest Common Divisors 4.4 Solving Congruences |
| 第 6 週 | 5.1 Mathematical Induction 5.2 Strong Induction and Well-Ordering |
| 第 7 週 | 5.3 Recursive Definitions and Structural Induction 5.4 Recursive Algorithms |
| 第 8 週 | 6.1 The Basics of Counting 6.2 The Pigeonhole Principle 6.3 Permutations and Combinations 6.4 Binomial Coefficients |
| 第 9 週 | 6.5 Generalized Permutations and Combinations 6.6 Generating Permutations and Combinations |
| 第 10 週 | 8.1 Recurrence Relations 8.2 Solving Linear Recurrence Relations |
| 第 11 週 | 8.3 Divide-and-Conquer Algorithms and Recurrence Relations 8.4 Generating Functions 8.5 Applications of Inclusion-Exclusion |
| 第 12 週 | 9.1 Relations and Their Properties 9.2 n-ary Relations and Their Applications 9.3 Representing Relations |
| 第 13 週 | 9.4 Closures of Relations 9.5 Equivalence Relations 9.6 Partial Orderings |
| 第 14 週 | 10.1 Graphs and Graph Models 10.2 Graph Terminology and Special Types of Graphs 10.3 Representing Graphs and Graph Isomorphism |
| 第 15 週 | 10.4 Connectivity 10.5 Euler and Hamilton Paths 10.6 Shortest Path Problems |
| 第 16 週 | 10.8 Graph Coloring 11.3 Tree Traversal 11.4 Spanning Trees |
| 第 17 週 | 11.5 Minimum Spanning Trees 12.1 Boolean Functions 12.3 Logic Gates |
| 第 18 週 | Bonus Exams |
教科書
Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th ed., 2018, McGraw-Hill Inc.
Office Hours
- 地點
- TBA
- 時間
- TBA
- 聯絡方式
- ttyeh@cs.nctu.edu.tw