離散數學

Discrete Mathematics

學期

111-1

學分

0 學分

當期課號

537614

永久課號

MGIM30046

開課單位

資訊管理研究所

授課教師

徐熊健

校區

光復

類別

選修

上課時間表

節	週一
5 13:20–14:10	離散數學 MB311（光復） 3 節連堂
6 14:20–15:10
7 15:30–16:20

* 根據陽明交大上課時間表所列

概述

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/view/sjdmath

評分方式

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

課程大綱

Ch. 1: Basic Principles of Counting

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

講授：

9
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. 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
Ch. 9: Generating Functions

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

講授：

6
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. 14: Ring and Modular Arithmetic

1. Ring Structures 2. Ring Properties 3. Integers Modulo n 4. Homomorphism and Isomorphism

講授：

6
Ch 17: Finite Fields and Combinatorial Designs

1. Polynomial Rings 2. Irreduciblle Polynomials: Finite Fields 3. Latin Squares

講授：

6

週次計畫

週次	主題
第 1 週	Rules of Sum and Product, Permutations, Combinations 9/12
第 2 週	Combinations, Combinations with Repetition, Binomial theorem 9/19
第 3 週	Catalan Numbers, Set and Subsets, Set Operations, Laws of Set Theory, Counting and Venn Diagrams 9/26
第 4 週	Fundamentals of Logic, Logical Implication: Rules of Inference 10/3
第 5 週	國慶日 10/10
第 6 週	Well-Ordering Principle: Mathematical Induction, Recursive Definitions 10/17
第 7 週	Cartesian Products and Relations, Plain, One-to-One and Onto Functions, Properties of Relations, Computer Recognition: 0-1 Matrices and Directed Graphs 10/24
第 8 週	Pigeonhole Principle, Composition and Inverse 10/31
第 9 週	Generating Functions 11/7
第 10 週	Partitions of Integers, The Exponential Generating Function 11/14
第 11 週	Midterm Exam. 11/21
第 12 週	The Division Algorithm, Prime Numbers, The Greatest Common Divisor, The Euclidean Algorithm, The Fundamental Theorem of Arithmetic 11/28
第 13 週	Equivalence Relations and Partitions, Principle of Inclusion and Exclusion 12/5
第 14 週	Subgraphs, Complements, and Graph Isomorphism, Graph Isomorphism, Planar Graphs, Hamilton Paths and Cycles; Graph Coloring, Euler Trails and Circuits 12/12
第 15 週	Minimal Spanning Trees: Algorithms of Kruskal and Prim, Transport Networks: The Max-Flow Min-Cut Theorem, Matching Theory 12/19
第 16 週	Rings, Modular arithmetic, Ring Homomorphisms and Isomorphisms, Polynomial Rings 12/26
第 17 週	開國紀念日 1/2
第 18 週	Group, Hamming matrices, Irreducible Polynomials, Finite Fields, Latin squares, Finite Geometries and Affine Planes 1/9

教科書

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

Office Hours

地點: MB311
時間: Monday EFG
聯絡方式: sjshyu@gmail.com