離散數學

Discrete Mathematics serves as the mathematical foundation of Computer Science and is the counterpart of Calculus. Systematic technique of counting, enumerating, arranging and identification of subsets of a finite set and basic theory of Theoretical Computer Sciences will be introduced in this course.

Calculus I, Linear Algebra I

無備註

Use ppt and e3 system.

appearance and weekly web quizzes: 20% appearance in TA class and homeworks 20% midterm 30% final 30%

• 1. Permutations, Combinations, and Combinatorial Reasoning

  Permutations, Combinations, Combination of multi-set, Permutations of multi-set, Combinatorial reasoning

• 2. The Pigeonhole Principle and Inclusion-Exclusion Principle

  Pigeonhole principle, Inclusion-Exclusion Principle

• 3. Generating Functions

  Ordinary Generating Functions, Exponential Generating Functions

• 4. Recurrence Relations and Special Counting Sequences

  General Properties, General Linear Recurrences, Non-homogeneous Linear Recurrences, Special Counting Sequences

• 5. Asymptotics

  Complexity Notations, Stirling's formula

• 6. Language, Grammar, Automata and Turing Machines

  Language, Grammar, Automata, Nondeterministic Automata, Turing Machine, Nondeterministic Turing Machine

• 7. Trees, Prüfer codes, and Minimum Spanning Trees

  Trees, Prüfer codes, Minimum Spanning Trees, Kruskal's Algorithm, Prim's Algorithm

Lecture Notes will be provided. The following book is for the purpose of English reading ability training only: 1. Mathematical Thinking, Problem-Solving and Proofs by John P. D'Angelo and Douglas B. West (Chapters 4, 9, 10, 11, 12) 2. Discrete Mathematics with Applications by Susanna S. Epp (Chapters 11, 12) 3. Introductory Combinatorics by Richard A. Brualdi

地點

SA 350

時間

Send an e-mail to me to make appointment or any time when you find me in my office.

聯絡方式

weng@math.nctu.edu.tw (03)5731610