TOCEC
邏輯學,數學,工程
層級: 課程資料
媒體: 影音 講義

10902離散數學

2021-02-01-2021-06-30

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

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

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


【先修課程】
        Prerequisites
High-school mathematics, Calculus (preferred).
 
  
 【課程說明】
        Course Description
This course gives an introduction to the essentials of discrete and 
 combinatorial mathematics.
 
   
 
【指定用書】
        Textbook
 ♠ R. P. Grimaldi, Discrete and Combinatorial Mathematics: 
 An Applied Introduction, 5th ed. Boston: Pearson Addison Wesley, 
 2004.
 
 
 
【參考書籍】
       References
 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, 

2002.
 C. L. Liu, Elements of Discrete Mathematics, 2nd ed. New York: McGraw-Hill, 
 1985.
 C. L. Liu, Introduction to Combinatorial Mathematics. New York: McGraw-Hill, 
 1968.
 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
Fundamentals 
   Logic
 ♠  Set theory
   Mathematical induction
   Functions: definitions, pigeonhole principle
   Relations: definitions and properties, equivalence 
     relations, partial orders
Enumeration 
  Principles of counting
  Principle of inclusion and exclusion
  Recurrence relations: homogeneous recurrence
   relations, 
    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
https://ocw.nthu.edu.tw/ocw/index.php?page=course&cid=288&
https://www.youtube.com/playlist?list=PLS0SUwlYe8cyaHfrgAVaaKVNkwLYNsTA2