離散數學
Discrete Mathematics
| 節 | 週二 | 週五 |
|---|---|---|
3 10:10–11:00 | 離散數學 EC015 2 節連堂 | |
4 11:10–12:00 | ||
7 15:30–16:20 | 離散數學 EC015 |
* 根據陽明交大上課時間表所列
1. To demonstrate to students how mathematics can be applied to solve nontrivial real-life problems 2. To gain more experience with mathematical thinking, arguments and proof techniques, which are essential in reasoning about computation 3. To learn about a number of different discrete structures (e.g., sets, relations, graphs, trees, etc.) that provide the mathematical formalizations for many computational problems 4. To hope that students will not only learn some powerful mathematical tools but also develop their ability to perceive, to formulate, and to solve mathematical problems 5. To provide a gateway to more advanced courses in any computer science courses, including data structures, algorithm, database automata theory, computer security, etc.
basic high school mathematics
http://www.cis.nctu.edu.tw/~wuuyang/Lecture/lecture.DiscMath.html.
作業部份: 5 homeworks. 考試部份: 1 midterm exam and 1 final exam. 評量部份: (tentative) There will be two exams (40% each) and many short homeworks (15%). Classroom discussion counts as 5% toward the final score.
- Chap1: Logic and Proofs
- Chap 2: Sets, Functions, Sequences, and Sums
- Chap 3: Algorithms and the Integers
- Chap 4: Induction and Recursion
- Chap 5: Counting
- Chap 7: Advanced Counting Techniques
- Chap 8: Relations
- Chap 9 Graphs
- Chap 10: Trees
| 週次 | 主題 |
|---|---|
| 第 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 3.4 The Integers and Division |
| 第 5 週 | 3.5 Primes and Greatest Common Divisors 3.6 Integers and Algorithms |
| 第 6 週 | 3.7 Applications of Number Theory 4.1 Mathematical Induction 4.2 Strong Induction and Well-Ordering |
| 第 7 週 | 4.3 Recursive Definitions and Structural Induction 4.4 Recursive Algorithms |
| 第 8 週 | 5.1 The Basics of Counting 5.2 The Pigeonhole Principle 5.3 Permutations and Combinations 5.4 Binomial Coefficients |
| 第 9 週 | Midterm exam 5.5 Generalized Permutations and Combinations |
| 第 10 週 | 5.6 Generating Permutations and Combinations 7.1 Recurrence Relations 7.2 Solving Linear Recurrence Relations |
| 第 11 週 | 7.3 Divide-and-Conquer Algorithms and Recurrence Relations 7.4 Generating Functions 7.5 Inclusion-Exclusion 7.6 Applications of Inclusion-Exclusion |
| 第 12 週 | 8.1 Relations and Their Properties 8.2 n-ary Relations and Their Applications 8.3 Representing Relations |
| 第 13 週 | 8.4 Closures of Relations 8.5 Equivalence Relations 8.6 Partial Orderings |
| 第 14 週 | 9.1 Graphs and Graph Models 9.2 Graph Terminology and Special Types of Graphs |
| 第 15 週 | 9.3 Representing Graphs and Graph Isomorphism 9.4 Connectivity 9.5 Euler and Hamilton Paths |
| 第 16 週 | 9.6 Shortest-Path Problems 10.1 Introduction to Trees 10.2 Applications of Trees |
| 第 17 週 | 10.3 Tree Traversal 10.4 Spanning Trees 10.5 Minimum Spanning Trees |
| 第 18 週 | Final Exam |
Kenneth H. Rosen, Discrete Mathematics and Its Applications, 7th ed., McGraw-Hill Inc.
- 地點
- EC 332B (my office).
- 時間
- 2CD
- 聯絡方式
- 03-5712121 ext 56614.