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

离散数学》双语课程教学大纲 一、课程编号：040510 二、课程类型：必修 课程学时：理论教学 72学时 / 4.5学分。 适用专业：信息与计算科学专业。 先修课程：线性代数、概率论、高等数学等。 后续课程：编译原理、操作系统、数据结构、数据库等。 三、课程性质与任务 《离散数学》是信息与计算科学中基础理论的核心课程。该课程采用双语教学形式，教材是国外原版英语教材。通过本课程的学习，主要培养学生的抽象思维能力、严密的逻辑推理能力、阅读外文科技文献能力和专业英语写作能力。并为学生今后处理离散信息、离散建模、软件开发、计算机硬件系统设计、程序设计的时间和空间复杂度分析等提供理论指导基础，是学生从事信息科学的实际工作必备数学工具。 四、教学主要内容及学时分配 授课内容教学要求课时1.Fundamentals 1.1.Sets and subsets 1.2.Operations on sets 1.5.Boolean matrix掌握62 Logic 2.1.Propositions and logical operations 2.2.Conditional?Statements 2.3.Methods of proof掌握 103.Counting 3.1.Permutations 3.2.Combinations 3.3.Pigeonhole principle掌握64.Relations and Digraphs4.1.Product sets 4.1.Product sets and Partitions 4.2.Relations and Digraphs 4.3.Paths in Relations and Digraphs 4.4.Properties of relations? 4.5.Equivalence relations 4.7.Operations on relations 4.8.Transitive closure and Warshall’s Algorithm?掌握205.Functions 5.1.Functions 5.2.Functions for computer science 5.3.Growth of functions 5.4.Permutation Functions 掌握66.Order relations and structures 6.1.Partially ordered sets 6.2.Extremal elements of partially ordered sets掌握67.Trees 7.1.Trees 7.2.Labeled Trees 7.3.Tree searching 7.4.Undirected Trees 7.5.Minimal spanning trees掌握68.Topics in Graph theory 8.1.Graphs 8.2.Euler paths and circuits 8.3.Hamiltonian paths and circuits 8.5.matching problems 8.6.coloring graphs? 掌握8五、教学基本要求 了解离散数学所涵盖的内容及背景思想；理解离散数学组的数学思想和基本概念。掌握离散数学常用的基本方法、手段、技巧，并具备一定的分析论证能力和较强的利用离散数学解决实际问题能力。具体要求有： （1 ）理解子集、空集、全集、集合相等、幂集等基本概念；掌握集合的两种表示法。 （2） 熟练掌握集合的交、并、差补运算；能通过文氏图理解与掌握集合的有关运算；了解包含排斥定理及其简单应用。 （3） 熟练掌握集合运算的基本定律，并能熟练地应用这些定律证明集合恒等式。 （4） 掌握逻辑代数的基本理论和方法，理解命题﹑复合命题及真值表的概念，熟练掌握逻辑运算符‘非’﹑‘合取’ ﹑‘析取’﹑ ‘蕴涵’﹑及‘存在’﹑‘任意’等量词的定义及使用；理解条件语句的概念；理解等价。掌握一些常见的逻辑推理方法。 （5） 熟练掌握乘法原理﹑加法原理﹑排列﹑组合﹑鸽笼原理及递归式，会用组合计数思想的方法计算简单的古典概率问题。 （6） 理解序偶与笛卡尔积的概念；理解 n 元组与 n 个集合笛卡尔集的概念。深刻理解关系的基本概念；掌握二元关系的关系矩阵与关系图。熟练掌握关系的自反性、对称性、反对称性和传递性四种性质并熟练掌握其求法。深刻理解二元关系的自反闭包、对称闭包和传递闭包的概念并熟练掌握其求法。熟练掌握等价关系的判定与相关等价类的求法。了解关系的计算机表示﹑关系的运算﹑传递闭包及Warshall算法。 （7）