离散数学》双语课程教学大纲.doc

离散数学双语课程教学大纲一、课程编号：040510二、课程类型：必修课程学时：理论教学 72学时 / 4.5学分。适用专业：信息与计算科学专业。先修课程：线性代数、概率论、高等数学等。后续课程：编译原理、操作系统、数据结构、数据库等。三、课程性质与任务 离散数学是信息与计算科学中基础理论的核心课程。该课程采用双语教学形式，教材是国外原版英语教材。通过本课程的学习，主要培养学生的抽象思维能力、严密的逻辑推理能力、阅读外文科技文献能力和专业英语写作能力。并为学生今后处理离散信息、离散建模、软件开发、计算机硬件系统设计、程序设计的时间和空间复杂度分析等提供理论指导基础，是学生从事信息科学的实际工作必备数学工具。四、教学主要内容及学时分配授课内容教学要求课时1.Fundamentals1.1.Sets and subsets1.2.Operations on sets 1.5.Boolean matrix掌握62 Logic2.1.Propositions and logical operations2.2.ConditionalStatements2.3.Methods of proof掌握103.Counting3.1.Permutations3.2.Combinations3.3.Pigeonhole principle掌握64.Relations and Digraphs4.1.Product sets 4.1.Product sets and Partitions4.2.Relations and Digraphs4.3.Paths in Relations and Digraphs4.4.Properties of relations4.5.Equivalence relations 4.7.Operations on relations4.8.Transitive closure and Warshalls Algorithm掌握205.Functions5.1.Functions5.2.Functions for computer science5.3.Growth of functions 5.4.Permutation Functions 掌握66.Order relations and structures6.1.Partially ordered sets6.2.Extremal elements of partially ordered sets掌握67.Trees7.1.Trees7.2.Labeled Trees7.3.Tree searching 7.4.Undirected Trees7.5.Minimal spanning trees掌握68.Topics in Graph theory8.1.Graphs8.2.Euler paths and circuits 8.3.Hamiltonian paths and circuits8.5.matching problems8.6.coloring graphs 掌握8五、教学基本要求了解离散数学所涵盖的内容及背景思想；理解离散数学组的数学思想和基本概念。掌握离散数学常用的基本方法、手段、技巧，并具备一定的分析论证能力和较强的利用离散数学解决实际问题能力。具体要求有：（1 ）理解子集、空集、全集、集合相等、幂集等基本概念；掌握集合的两种表示法。 （2） 熟练掌握集合的交、并、差补运算；能通过文氏图理解与掌握集合的有关运算；了解包含排斥定理及其简单应用。 （3） 熟练掌握集合运算的基本定律，并能熟练地应用这些定律证明集合恒等式。 （4） 掌握逻辑代数的基本理论和方法，理解命题复合命题及真值表的概念，熟练掌握逻辑运算符非合取 析取 蕴涵及存在任意等量词的定义及使用；理解条件语句的概念；理解等价。掌握一些常见的逻辑推理方法。（5） 熟练掌握乘法原理加法原理排列组合鸽笼原理及递归式，会用组合计数思想的方法计算简单的古典概率问题。（6） 理解序偶与笛卡尔积的概念；理解 n 元组与 n 个集合笛卡尔集的概念。深刻理解关系的基本概念；掌握二元关系的关系矩阵与关系图。熟练掌握关系的自反性、对称性、反对称性和传递性四种性质并熟练掌握其求法。深刻理解二元关系的自反闭包、对称闭包和传递闭包的概念并熟练掌握其求法。熟练掌握等价关系的判定与相关等价类的求法。了解关系的计算机表示关系的运算传递闭包及Warshall算法。（7） 理解映射、满射、单射、双射的概念并熟练掌握其判定方法；了解复合映射与逆映射的概念及求法。 （8） 理解有向树，无向树，根数，标定树的定义及性质；掌握极小生成树算法；了解生成树搜索法。（9） 理解无向图，哈密顿圈及哈密顿路，传输网络，匹配问题，图的着色的定义及性质；掌握欧拉环游及欧拉通路，最大流问题的定义性质及算法。掌握有关哈密顿图的一些必要和充分条件。六、对学生课外作业的要求本课程概念多、比较抽象、定理证明和应用有一定难度，为了学生进一步理解课堂教学内容，拟布置一定数量的课外习题为宜，教师批改作业本的 2/3, 并安排时间上习题课。各章节习题量分布如下： 序号 内 容 习题量 1 Fundamentals 12 2 Logic 16 3 Counting 8 4 Relations and Digraphs 20 5 Functions 10 6 Order Relations and Structures 8 7 Trees6 8Topics in Graph Theory16七、教材及主要参考书主教材： 离散数学结构（第五版 影印版） I