《离散数学》教学大纲

课程代码

045100011

课程名称

离散数学

英文名称

Discrete Mathematics

课程类别

专业基础课

课程性质

必修

学时

总学时:64 实验学时:0 实习学时:0 其他学时:20(Mooc线上学时)

学分

4

开课学期

第一学期

开课单位

计算机科学与工程学院

适用专业

计算机科学与技术、网络工程、信息安全

授课语言

中文

先修课程

课程对毕业要求的支撑

本课程对学生达到如下毕业要求有如下贡献:

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

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

设计/开发解决方案:能够设计针对复杂与计算机相关工程问题的解决方案,设计满足特定需求的系统、单元(部件)或工艺流程,并能够在设计环节中体现创新意识,考虑社会、健康、安全、法律、文化以及环境等因素。

课程目标

完成课程后,学生将具备以下能力:

1)掌握离散数学的基本理论和基本知识;

2)掌握各种离散结构的描述方法、性质、推理证明方法及应用;

3)了解和掌握用离散结构的理论和方法对实际系统进行描述、分析和研究的方法。

课程简介

离散数学用数学语言描述离散系统的状态、关系和变化过程,是计算机科学与技术的形式化描述语言,是进行逻辑推理和数量分析的工具,学习离散数学可以培养学生的计算思维与逻辑推理能力、综合运用专业知识解决计算机复杂工程问题能力。离散数学是计算机科学与技术领域重要的基础课程,本课程讲授的数理逻辑,集合、函数和关系,图论三部分内容,广泛应用于计算机的后续专业课程中。学习离散数学为掌握计算机专业领域知识,及将来从事计算机科学技术的研究和工程实践打下坚实的理论基础。


教学内容与学时分配

绪论: 课程目的、意义与内容组织、学时安排介绍    1学时

教学要求:掌握学习离散数学课程的主要目的与任务,了解离散数学课程在国家信息技术发展中的作用,在计算机科学技术发展中的作用。


第一部分  数理逻辑

教学要求:

掌握数理逻辑的基本理论和基本知识,掌握命题演算,谓词演算的基本概念,命题符号化方法,推理证明方法,了解逻辑公理系统。

1、命题演算                                10学时

 (1)命题与联结词               2学时

 (2)命题公式及其分类           1学时

 (3)命题演算的关系式           2学时

 (4)范式     

 (5)析取范式和合取范式         1学时

 (6)主析取范式和主合取范式     1学时

 (7)命题演算的推理             

 (8)推理理论                   1学时

 (9)推理证明方法               2学时

重点:命题的概念,联结词的定义,命题的符号化表示,命题逻辑的关系式,命题逻辑的推理理论和证明方法;

难点:命题的符号化表示,命题逻辑的关系式的证明,命题逻辑的推理和证明


2、谓词逻辑                                10学时

 (1)谓词逻辑的基本概念         2学时

 (2)谓词公式                   2学时

 (3)谓词演算的关系式           3学时

 (4)谓词演算的推理             3学时

重点:谓词逻辑的概念,量词,用谓词逻辑表示命题,谓词逻辑的等价式与蕴含式,谓词逻辑的推理。

难点:命题的谓词逻辑符号化表示,谓词逻辑的量词的使用,谓词逻辑的推理。


第二部分 集合、关系和函数

教学要求:

掌握集合论的基本理论和基本知识,掌握集合,关系,函数的基本概念,关系的定义、性质、运算、判定和证明方法,函数的定义,反函数和复合函数,了解集合基数,等势的概念。  

1、集合                                           2学时

 (1)集合及其表示,集合间的关系,集合的运算   1学时

 (2)自然数,集合的特征函数                   1学时

重点:集合间关系的表示,集合运算的表示,集合关系式的证明,集合的幂集,自然数

2、关系                                           13学时

 (1)关系的概念                 1学时

 (2)关系的表示                 1学时

 (3)关系的运算                 1学时

关系的性质                 

 (4)关系性质                   2学时

 (5)关系性质的判断和证明       2学时

 (6)关系的闭包                 2学时

等价关系和等价类           

 (7)等价关系                   1学时

 (8)等价类、商集、划分         1学时

偏序关系                   

 (9)偏序关系和哈斯图           1学时

 (10)偏序集                    1学时

重点:关系的定义和表示,关系的逆运算和复合运算,关系的性质的判断和证明,关系的闭包,等价关系和等价类,偏序关系合偏序集。

难点:关系的定义,关系的性质的判断和证明,关系的运算,等价关系和偏序关系的判断和证明.

3、函数                                        6学时

 (1)函数的基本概念             

函数的定义                       0.5学时

特殊函数,单射、满射和双射函数   1.5学时

 (2)复合函数和反函数                 2学时

 (3)集合的基数                       2学时   

重点:函数的概念,单射、满射和双射函数,复合函数,反函数;

难点:函数的定义,单射、满射和双射函数的判断和证明,复合函数和反函数。


第三部分 图论

教学要求:

掌握图论的基本理论和基本知识,掌握图的基本概念及其表示,掌握欧拉图,哈密尔顿图树,平面图,二分图等图模型的定义、性质及判定、证明方法,并了解有关应用。

1、图论                                     8学时

1)图的概念                   

无向图和有向图               0.5学时

度的概念,图论的基本定理     1.5学时

图的分类                     1学时

子图和补图                   0.5学时

图的同构                     0.5学时             

2)通路、回路和连通           

通路和回路                 1学时

连通的概念                 1学时

3)图的表示                    1.5学时

4)图的运算                    0.5学时                   

重点:度的概念,图论的基本定理,图的表示,图的分类,图的同构,通路、回路和连通的概念

难点:图的概念、各类图的定义,图的同构的判断,图的连通性

2、特殊图                                    9学时

1)欧拉图与哈密尔顿图         

欧拉图                     1学时

哈密顿图                   1学时

2)带权图                     

旅行商问题                 0.5学时

最短路径问题               1学时

中国邮路问题               1学时

3)匹配和二分图               

匹配                       0.5学时

二分图                     1学时

4)平面图

平面图的定义               1学时

平面图的欧拉公式           1学时

对偶图与图的着色           1学时

重点:欧拉图、哈密尔顿图、平面图、二分图的定义和判定

难点:欧拉图、哈密尔顿图、平面图和二分图的判定,求最短路径的Dijkstra算法,中国邮路算法。

3、树                                        5学时

1)树的定义与特性             1.5学时

2)生成树                     1学时

3)根树

根树,有序根树的遍历       1学时

4)根树的应用

前缀码                     0.5学时

最优二元树和霍夫曼编码     1学时

重点:树的定义,生成树,最小生成树,根树,有序根树的遍历,最优二元树。

难点: 掌握树的定义和性质,求最优二元树的霍夫曼算法

实验教学(包括上机学时、实验学时、实践学时)

教学方法

课程教学以课堂教学、mooc学习、作业等共同实施。

考核方式

本课程注重过程考核,考核形式、考核内容、课程目标、成绩比例为:

1)平时作业和课堂表现(占总成绩的20%

选做教材部分习题,考查学生对基础知识和基本理论的掌握和应用能力;课程目标123

2)期中考试和平时测试(占总成绩的30%

选择在线测验、课堂测验的形式,考查学生对基础知识和基本概念的掌握能力;课程目标12

3)期末考试(闭卷)(占总成绩的50%

采用笔试闭卷方式,考查学生对基础知识和基本理论的掌握,重点考查运用离散数学理论解决问题的能力;课程目标123

教材及参考书

现用教材:陈琼,马千里,周育人等,离散数学及其应用,机械出版社,2014

主要参考资料:

[1] 屈婉玲,耿素云,张立昂,离散数学,高等教育出版社,2010

[2]  Kenneth N.Rosen, Discrete Mathematics and its applications, 机械工业出版社,2018

制定人及制定时间

陈琼 陈伟能 马千里 胡劲松  201948


 “Discrete Mathematics” Syllabus

Course Code

045100011

Course Title

Discrete Mathematics

Course Category

Specialty Basic Courses

Course Nature

Compulsory Course

Class Hours

64

Credits

4

Semester

The first semester

Institute

School of Computer Science

ProgramOriented

Computer Science and Engineering, Network Engineering, Information Secirity

Teaching Language

Chinese

Prerequisites

None

 Student Outcomes

 (Special Training Ability)

 Engineering Knowledge: An ability to apply knowledge of mathematics, science, engineering fundamentals and engineering specialization to the solution of complex engineering problems.

 Problem Analysis: An ability to identify, formulate and analyze complex engineering problems, reaching to substantiated conclusions using basic principles of mathematics, science, and engineering.

 Design / Development Solutions: An ability to design solutions for complex engineering problems and innovatively design systems, components or process that meet specific needs with societal, public health, safety, legal, cultural and environmental considerations.


Course Objectives

Through this course, students will be expected to develop mathematical experience and maturity, and to enhance their abilities to read, create and analyze mathematical arguments.  The course will provide the mathematical background necessary for many computer science courses and give a range of useful problem solving skills.

Course Description

It’s a course for computer majors. The course provides an introduction to discrete concepts and their properties and applications. Topics included are logic, predicate calculus, induction, methods of proof, basic set theory, functions, relations, graph theory and tree.

Teaching Content and Class Hours Distribution

Introduction:                                 1 credit hour

Introduce the purpose, significance of learning discrete mathematics and the content of the course.

Teaching Requirements: To master the main objectives and tasks of the course and understand the role of discrete mathematics course in the development of national information technology and computer science and technology.  

Part I.  Logic  (20 credit hours )

Teaching requirements:

Grasp the basic theory and basic knowledge of logic, master the basic concepts of propositional calculus, predicate calculus, and proof methods.

  1. Propositional logic                     10 credit hours

  1. Propositions and connectives          2

  2. Logical Expressions                 2

  3. Propositional Equivalence            2

  4. Normal form                       1

  5. Method of proof                    3

Key points:  proposition, logical operators, translating sentences into logical expressions, logically equivalent,methods of proof

Difficulties: translating sentences into logical expressions, methods of proof ,


  1. Predicate logic                          10 credit hours

  1. predicates                           2

  2. Quantifiers                          2

  3. Rules of inference                    3

  4. Introduction of proof                  3


Key points:  predicates, quantifiers, rules of inference

 Difficulties: quantifiers, translating sentences into logical expressions, rules of inference

Part II. Sets,Functions and Relations (21 credit hours )

Teaching requirements:

Master the basic theory of set theory , and the basic concepts of sets, relations and functions.

  1. Sets                                2 credit hours

  1. Sets and its representation , Set Operations - union, intersection, complement, difference                      1

  2. The natural number set                  1  

Key points: sets and its representation, power sets , natural number

  1. Relations                          13 credit hours

  1. Relations and their application             1

  2. Representing relations                    2  

  3. The operations of relations                1  

  4. The properties of relations                 2

  5. Closures of relations                      2

  6. Equivalence relations, Equivalence classes    2

  7. Partial relations                          2

The key points:: the definition and representation of relations, the inverse operations and compound operations of relations, the judgment and proof of the properties of relations, the closure of relations, equivalence relations and equivalence classes, partial order relations, posets.

The difficulties: the definition of relations, the judgment and proof of the properties of relations, the operations of relations, the equivalence relation , partial relations, Congruence, partitions

  1. Functions                            6 credit hours

  1. Definition of functions                  0.5    

  2. Special function, injective, surjective and bijective function

1.5

  1. Compound functions and inverse functions  2  

  2. The cardinal number of the set            2  

Key points: the concept of function, injective, surjective and bijective function, compound function, inverse function;

Difficulties: function definition, One-to-one , onto, inverse, the compound function.

Part III.  Graph Theory22 credit hours

Teaching requirements:

Master the basic ideas of graph theory, understanding the definitions of Euler and Hamilton paths, bipartite graph, planar graph and tree, and learning some applications of graphs.

  1. Graph                                       8 credit hours

  1. Graphs and graph models                       2

  2. Graph terminology and special types of Graphs      2

  3. Representing graphs and Graph isomorphism        2

  4. Connectivity                                  2

Key points: Graphs and graph models, Representing graphs and Graph isomorphism, Connectivity

Difficulties: Graphs models, Graph isomorphism, Connectivity,

  1. Special Graph                              9 credit hours

  1. Euler and Hamilton paths                   2

  2. Shortest path problems                     2

  3. Match and Bipartite graphs                  2

  4. Planar graphs                             2

  5. Graph coloring                            1

Key points: Graphs and graph models, Representing graphs and Graph isomorphism, Connectivity, Shortest path problems, Euler and Hamilton paths, Planar graphs,

Difficulties: Graphs models, Graph isomorphism, Connectivity, Shortest path problems,

  1. Trees                                       5 credit hours

  1. Trees, binary trees                         2

  2. Spanning trees, Minimum spanning trees.      1

  3. Root tree, Traversal, Huffman algorithm       2

Key points: Trees, Spanning trees, Traversal of tree, Huffman algorithm

Difficulties: Minimum Spanning trees, Huffman algorithm

Experimental Teaching

None

Teaching Method

Classroom teaching, Mooc learning, homeworks and so on.

Examination Method

Course grades will be based 20% on homeworks and presentation, 30% on the online test and 50% on the final examination (closed).

Teaching Materials and Reference Books

Textbook:

Chen QiongMa QianliZhou YurenDiscrete Mathematics and its applicationsChina Machine Press2014

Reference books:

[1] Qu WanlingGen SuyunZhang LiangDiscrete MathematicsHigher Education Press2010

[2]  Kenneth N. Rosen, Discrete Mathematics and its applications, China Machine Press2018

Prepared by Whom and When

Chen Qiong, Ma Qianli, Chen Weineng, Hu Jinsong, 2019/04/08


专业课程思政建设内容

课程名称

离散数学

任课教师

陈琼、陈伟能、马千里、胡劲松

职称

副教授、教授

学院

计算机科学与工程学院

育人目标

1.让学生了解离散数学在计算机科学中的作用,在实现中国梦中的作用,树立为中华民族的伟大复兴努力学习、努力奋斗的决心。

2.实现离散数学课程知识教学与立德树人教育的有机融合;激发学生“实干兴邦”的爱国奋斗精神。

教学特色

介绍离散数学在计算机科学、信息技术、管理科学等的应用,介绍应用离散数学理论知识解决实际问题。通过演绎推理的准确性和严密性,引导学生建立脚踏实地、诚信做人的人生观和价值观。

预期成效

1.学生能认识离散数学课程对学习计算机科学的重要意义,对科学技术发展的重要作用;

2.了解到人工智能、高科技离不开离散数学,激发学生的爱国情怀,使学生树立正确的价值观和人生观,自觉地为中华民族的复兴而努力学习。