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

 

 

 

課程版書與作業