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

10902離散數學Discrete Mathematics

2021-02-01-2030-12-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

【課程版書與作業】