课程代码

045101111

课程名称

离散数学

英文名称

Discrete Mathematics

课程类别

专业基础课

课程性质

必修

学时

总学时：64  实验学时：0

学分

4.0

开课学期

第二学期

开课单位

计算机科学与工程学院

适用专业

计算机科学与技术创新班、联合班

授课语言

英文授课

先修课程

无

课程对毕业要求的支撑

本课程帮助学生提升以下方面的能力：

 №1.工程知识：能够将数学、自然科学、工程基础和专业知识用于解决计算机复杂工程问题。

 №2.问题分析：能够应用数学、自然科学和工程科学的基本原理，识别、表达、并通过文献研究分析计算机复杂工程问题，以获得有效结论。

课程目标

1. 期望学生培养基本的数学能力并提高他们的解决问题的能力。[1、2、4]

2. 该课程为计算机科学课程提供必要的数学背景。[1、2]

课程简介

本课程是当代数学的一个分支，它发展了推理和解决问题的能力并强调了证明的重要性。课程的主题包括逻辑、集合论、关系、计数、图论和抽象代数。它是理解计算机系统的基础。本课程面向有能力并有兴趣更深入更快速地学习离散数学概念的学生。

教学内容与学时分配

1. 简介(1学时)

• 研究离散数学的动机

• 离散数学的基本概念

2. 逻辑与证明(14学时)

-逻辑命题逻辑和等价性(4学时)

• 命题

• 命题操作符

• 复合命题

• 逻辑等价性

• 德摩根定律

-谓词和量词(5学时)

• 谓词

• 量词

• 限制量词

• 量词的优先级

• 量词逻辑等价

• 嵌套量词

-推理和证明(5学时)

• 推理和等价之间的区别

• 推理规则

• 正式证明

• 非正式证明

要点：逻辑证明

难点：嵌套量词，推理规则

3. 集(8学时)

-集和操作(4学时)

• 集

• 幂集

• 笛卡儿积

• 使用集合符号和量词

• 量词的真值集

• 势

-函数(4学时)

• 函数

• 一对一函数

• 递增函数

• 递减函数

• 函数组成

要点：逆，组成

难点：势

4. 关系(16学时)

-关系和属性(4学时)

• 关系的定义

• 关系表示方法

• 关系操作

• 关系属性

-相等和闭包(6学时)

• 等价关系

• 等价类

• 分区

• 反射性闭包

• 对称性闭包

• 传递性闭包

-偏序关系(6学时)

• 偏序关系

• 全序关系

• 词典序

• 哈斯图

• 最小/最大元素

• 极小/极大元素

• 下限/上限

• 最大的下限/最小上限

要点：关系类型及其特征

难点：关系特征

5. 计数(3学时)

• 基本计数原则

• 乘法/加法原理

• 包容排斥原则

• 排列/组合

• 将对象分配到框中

• 生成排列和组合

• 鸽巢原理

• 广义鸽巢原理

要点：基本计数技术

难点：／

6. 高级计数（6学时）

• 复发关系

• 使用循环关系建模

• 线性常系数非齐次递推关系

• 生成函数

• 计数问题和生成函数

• 使用生成函数来解决循环关系

要点：递归，生成函数

难点：解决递归关系

7. 图论（6学时）

• 图

• 欧拉通路和回路

• 汉密尔顿通路和回路

• 着色图

• 传输网络

要点：连通性，算法

难点：图的论证

8. 抽象代数（10学时）

• 半群，幺半群，群体，交换群，子群

• 科斯特，拉格朗日定理

• 群同态和同构，循环群

• 格和布尔代数

• 环和场

要点：群，格和布尔代数

难点：抽象思维

实验教学（包括上机学时、实验学时、实践学时）

无

教学方法

讲座，辅导，作业，讨论，中期考试，考试

考核方式

考勤：10%

作业：10%

期中考试：30%

期末考试（闭卷）：50%

教材及参考书

现用教材：Rosen, Kenneth h., Discrete Mathematics and Its Applications, 2 ed, McGraw/Hill

制定人及制定时间

陈百基，2019年4月14日

Course Code

045101111

Course Title

Discrete Mathematics

Course Category

Specialty Basic Courses

Course Nature

Compulsory Course

Class Hours

Total: 64   Lab Hours: 0

Credits

4.0

Semester

Secondary Semester

Institute

School of Computer Science and Engineering

Program Oriented

Innovation Class

Teaching Language

English

Prerequisites

/

Student Outcomes

 (Special Training Ability)

This course helps student to enhance their ability in the following aspect:

1. Engineering Knowledge: An ability to apply knowledge of English, solid knowledge of professional basic principles, methods and means of computer science and technology for solving complex engineering problems, to well prepare the required knowledge applied to the computer science and technology research & development and engineering practice through computer systems analysis, modeling and calculation and any other aspects of the advanced approach.

2. Problem Analysis: An ability to creatively use the basic principles of computer science to solve the problems encountered in the computer field.

Course Objectives

1. The students are expected to develop fundamental mathematical ability and to enhance their problem solving skills.[1,2,4]

2. The course provides the essential mathematical background for computer science courses.[1,2]

Course Description

This course is a branch of contemporary mathematics that develops reasoning and problem-solving abilities, with an emphasis on proof. Topics include Logic, Set Theory, Relation, Counting, Graph Theory and Abstract Algebra. It is the foundation for the rigorous understanding of computer systems. This course is intended for students capable of and interested in progressing through the concepts of discrete mathematics in more depth and at an accelerated rate.

Teaching Content and Class Hours Distribution

(1) Introduction (1 teaching hour)

• Motivation of studying Discrete Mathematics

• Basic concept in discrete mathematics

(2) Logic and Proof(14 teaching hours)

- Propositional Logic and Equivalences (4 teaching hours)

• Proposition

• Propositional Operator

• Compound Proposition

• Logical Equivalences

• De Morgan's Laws

- Predicates and Quantifiers(5 teaching hours)

• Predicates

• Quantifiers

• Quantifiers with Restricted Domains

• Precedence of Quantifiers

• Logical Equivalences Involving Quantifiers

• Nested Quantifiers

- Rules of Inference and Proofs(5 teaching hours)

• Difference between inference and equivalences

• Inference rules

• Formal proofs

• Informal proofs

Key points: Logical proof

Difficulties:Nested Quantifier, Inference rules

(3) Set(8 teaching hours)

- Sets and Operations(4 teaching hours)

• Set

• The Power Set

• Cartesian Products

• Using Set Notation with Quantifiers

• Truth Sets of Quantifiers

• Cardinality

- Functions(4 teaching hours)

• Functions

• One-to-One Functions

• Onto Functions

• Inverse Functions

• Composition of Functions

Key points: Inverse, Composition

Difficulties:Cardinality

(4) Relation(16 teaching hours)

- Relations and Properties(4 teaching hours)

• Definition of relation

• Representation of Relation

• Operators of Relation

• Properties of Relation

- Equivalence and Closures(6 teaching hours)

• Equivalence Relations

• Equivalence Class

• Partition

• Reflexive Closure

• Symmetric Closure

• Transitive Closure

- Partial Orderings(6 teaching hours)

• Partial Order

• Total Order

• Lexicographic Order

• Hasse Diagrams

• Minimal/Maximal Element

• Least/Greatest Element

• Lower/Upper Bound

• Greatest Lower/Least Upper Bound

Key points: Types of relation and theirs characteristics

Difficulties:Characteristic of relation

(5) Counting(3 teaching hours)

• Basic Counting Principles

• Multiplication / Addition Principle

• Inclusion-Exclusion Principle

• Permutation / Combination

• Distributing Objects into Boxes

• Generating Permutations & Combinations

• Pigeonhole Principle

• Generalized Pigeonhole Principle

Key points: basic counting technique

Difficulties:/

(6) Advanced Counting(6 teaching hours)

• Recurrence Relations

• Modeling with Recurrence Relations

• Linear Nonhomogeneous Recurrence Relations with Constant Coefficients

• Generating Functions

• Counting Problems and Generating Functions

• Using Generating Functions to Solve Recurrence Relations

Key points: Recurrence, Generating Function

Difficulties:Solving Recurrence Relation

(7) Graph Theory(6 teaching hours)

• Graphs

• Euler Paths and Circuits

• Hamiltonian Paths and Circuits

• Coloring Graphs

• Transport Networks

Key points: Connectivity, Algorithm

Difficulties:Proof in Graph

(8) Abstract Algebra(10 teaching hours)

• Semigroups, monoids, groups, commutative groups, subgroups

• Cosets, Lagrange theorem

• Group homomorphism and isomorphism, cyclic groups

• Lattices and Boolean Algebra

• Ring and Field

Key points: Group, Lattices and Boolean Algebra

Difficulties:Abstract thinking

Experimental Teaching

/

Teaching Method

Lecture, tutorial, assignment, discussion, mid-term tests, Examination

Examination Method

Participation: 10%

Assignment: 10%

Mid-Term Test: 30%

Final Exam (Close Book): 50%

Teaching Materials and Reference Books

Rosen, Kenneth h., Discrete Mathematics and Its Applications, 2 ed, McGraw/Hill

Prepared by Whom and When

Patrick P.K. Chan, 2019/4/14