離散數學

This course intends to cover four basic areas in the study of computer science: discrete methods, combinatorics, graph theory and finite algebraic structures. We shall (1) introduce the fundamentals and techniques of discrete mathematics and combinatorial reasoning that are so different from the traditional coverage in calculus and differential equations; (2) develop the mathematical maturity of the students by bridging the real world problems and the combinatorial implications, and (3) present adequate modern research topic/open problems and encourage master students to explore and investigate.

無

無備註

Course site: https://sites.google.com/site/sjdmath/home

1學期作業 平時作業、程式作業若干次 2.考試狀況 小考、期中考 3.評量方法 平時作業、小考與上課參與:35%、期中考:35%、分組報告: 30%

• Ch. 3: Set Theory

  1. Set and Subsets 2. Set Operations and Laws of Set Theory 3. Counting and Venn Diagrams

  講授：

  3

• Ch. 4: Properties of Integers

  1. Well-Ordering Principle: Mathematical Induction 2. Recursive Definitions

  講授：

  3

• Ch. 5: Relations and Functions

  1. Cartesian Products and Relations 2. Functions: Plain and One-to-One 3. Onto Functions: Strrling Numbers 4. Pigeonhole Principle 5. Composition and Inverse 6. Computational Complexity

  講授：

  6

• Ch. 9: Generating Functions

  1. Introductory Examples 2. Definition and Examples: Calculational Techniques 3. Partitions of Integers 4. The Exponential Generating Function

  講授：

  6

• Ch. 7: Relations: Second Round

  1 Relations Revisited: Properties of Relations 2 Computer Recognition: Zero-One Matrices and Directed Graphs 3 Partial Orders: Hasse Diagrams 4 Equivalence Relations and Partitions

  講授：

  4

• Ch. 8: The Principle of Inclusion and Exclusion

  1 The Principle of Inclusion and Exclusion 2 Generalizations of the Principle 3 Derangements: Nothing Is in Its Right Place 4 Rook Polynomials 5 Arrangements with Forbidden Positions

  講授：

  4

• Secret Sharing

  1. Shamir’s interpolation 2. Blakey’s geometrical method 3. Chinese remainder theory-based approaches 4. Shyu-Tsai’s Latin square method

  講授：

  6

• Visual Cryptography

  1. Threshold schemes 2. Hierarchical schemes 3. General access schemes

  講授：

  3

• Ch. 11: An Introduction to Graph Theory

  1 Definitions and Examples 2 Subgraphs, Complements, and Graph Isomorphism 3 Vertex Degree: Euler Trails and Circuits 4 Planar Graphs 5 Hamilton Paths and Cycles 6 Graph Coloring and Chromatic Polynomials

  講授：

  4

• Ch. 13: Optimization and Matching

  1 Dijkstra’s Shortest-Path Algorithm 2 Minimal Spanning Trees: The Algorithms of Kruskal and Prim 3 Matching Theory

  講授：

  3

• Ch. 1: Basic Principles of Counting

  1. Rules of Sum and Product 2. Permutations 3. Combinations 4. Combinations with Repetition 5. Catalan Numbers

  講授：

  9

R.P. Grimaldi, Discrete and Combinatorial Mathematics, 5th ED., Addison-Wesley, 2003, Reading, Massachusetts. 新月圖書代理

地點

MB312

時間

Monday EFG

聯絡方式

sjshyu@gmail.com