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

# 10902離散數學

2021-02-01-2021-06-30

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

https://ocw.nthu.edu.tw/ocw/index.php?page=course&cid=288&