層級: 課程資料
媒體: 影音 講義



國立清華大學 電機工程學系 趙啟超

關鍵字: 離散數學(Discrete Mathematics) 組合數學(combinatorial mathematics) 計數(enumeration) 圖論(graph theory)

This course gives an introduction to the essentials of discrete and combinatorial mathematics.

High-school mathematics, Calculus (preferred).
        Course Description
This course gives an introduction to the essentials of discrete and 
 combinatorial mathematics.
 ♠ R. P. Grimaldi, Discrete and Combinatorial Mathematics: 
 An Applied Introduction, 5th ed. Boston: Pearson Addison Wesley, 
 R. J. McEliece, R. B. Ash, and C. Ash, Introduction to Discrete Mathematics. 

New York: Random House, 1989.
 N. L. Biggs, Discrete Mathematics, 2nd ed. New York: Oxford University Press, 

 C. L. Liu, Elements of Discrete Mathematics, 2nd ed. New York: McGraw-Hill, 
 C. L. Liu, Introduction to Combinatorial Mathematics. New York: McGraw-Hill, 
 K. H. Rosen, Discrete Mathematics and Its Applications, 8th ed. New York: 
 McGraw-Hill, 2019.
R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics: 
  A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, 1994.
       Course Contents
 ♠  Set theory
   Mathematical induction
   Functions: definitions, pigeonhole principle
   Relations: definitions and properties, equivalence 
     relations, partial orders
  Principles of counting
  Principle of inclusion and exclusion
  Recurrence relations: homogeneous recurrence
    nonhomogeneous recurrence relations
  Generating functions: generating functions for solving
   recurrence relations, generating functions for 
    partitions of integers
  Complexity of algorithms
Graph Theory 
   Introduction: definitions and properties, graph isomorphism, 
     Euler trails and circuits, planar graphs
   Trees: definitions and properties, rooted trees, 
     spanning trees, trees and sorting
   Optimization and matching: shortest-path problem, 
     minimal spanning trees, matching problem, 
     maximum flow problem


前往課程 View Course