四、參考書籍 (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
o Logic
o Set theory
o Mathematical induction
o Functions: definitions, pigeonhole principle
o Relations: definitions and properties, equivalence relations, partial orders
Enumeration
o Principles of counting
o Principle of inclusion and exclusion
o Recurrence relations: homogeneous recurrence relations, nonhomogeneous recurrence relations
o Generating functions: generating functions for solving recurrence relations, generating functions for enumeration, partitions of integers
o Complexity of algorithms
Graph Theory
o Introduction: definitions and properties, graph isomorphism, Euler trails and circuits, planar graphs
o Trees: definitions and properties, rooted trees, spanning trees, trees and sorting
o Optimization and matching: shortest-path problem, minimal spanning trees, matching problem, maximum flow problem
六、成績考核 (Grading)
Homework 20%, two midterm exams 50%, final exam 30%.
七、可連結之網頁位址 (Web Page)
https://www.ee.nthu.edu.tw/ccc/eecs2060.html
八、數位學習平台 (E-Learning)
https://lms.nthu.edu.tw
(加簽相關事宜說明請見七之課程網頁下方)