第0章 离散数学概述

《第0章 离散数学概述》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学概述离散数学课程名称离散数学DiscreteMathematics离散数学结构DiscreteMathematicalStructures开课单位：华南师范大学计算机学院授课人：陈振洲Email：chenzhenzhou@scnu.edu.cn课程要求按时上课积极完成课后作业考核方式：考试成绩:70％平时成绩:30％（包括考勤和作业）离散数学，是现代数学的一个重要分支，计算机科学与技术一级学科的核心课程，是整个计算机学科的专业基础课。离散数学是以研究离散量的结构和相互间的关系为主要目标，其研究对象一般地是有限个或可数个元素，因此它充分描述了计算机科学离散

2、性的特点。离散数学是随着计算机科学的发展而逐步建立的，它形成于七十年代初期，是一门新兴的工具性学科。课程简介离散数学(DiscreteMathematics)：现代数学的重要分支计算机科学基础理论的核心课程"研究离散结构的数学分科。"--《辞海》79年版,P355离散数学：研究离散量的结构及其相互间关系的数学分支。离散的概念连续的印象：“剪不断，理还乱，是离愁，恰似一江春水向东流”——南唐李煜（李后主）词离散的印象：“枯藤老树昏鸦，小桥流水人家，古道西风瘦马，夕阳西下，断肠人在天涯”——元朝马致远（引自《离散数学导引》（清华大学数学系马振华）后续

3、课程数据结构操作系统编译理论算法分析系统结构容错判断机器定理证明数据库原理人工智能…………离散数学的发展18世纪以前,数学基本上是研究离散对象的数量和空间关系的科学。之后,因天文学,物理学的发展,如行星轨道,牛顿三大力学定律等研究,极大地推动了连续数学(以微积分,数学物理方程,实、复变函数论为代表)的发展。离散对象的研究则处于停滞状态。20世纪30年代,图灵提出计算机的理论模型——图灵机。这种模型早于实际制造计算机十多年,现实的计算机的计算能力,本质上和图灵机的计算能力一样。由于在计算机内,机器字长总是有限的,它代表离散的数或其它离散对象，因此随着计算机科学和技

4、术的迅猛发展,离散数学就显得重要。数理逻辑：“证明”在计算科学的某些领域至关重要，构造一个证明和写一个程序的思维过程在本质上是一样的。组合分析：解决问题的一个重要方面就是计数或枚举对象。离散结构：用来表示离散对象以及它们之间关系的抽象数学结构，包括：集合、排列、关系、树、图。算法化思维：许多问题都可以通过构造一个可以被程序实现的算法来解决。它的三个步骤是：构造（选择合适的离散模型和操作步骤）、验证（算法的正确性）、评估（时间和空间的复杂性）。应用和建模：在可以想到的任何研究领域都有离散数学的应用。计算科学、化学、植物学、动物学、语言学、地理、经济学等，构造离散模

5、型都是极其有用的解决问题的方法。教学内容集合论数理逻辑图论代数结构计算机求解的基本模式是：实际问题数学建模算法设计编程实现离散数学为数学建模打下知识基础、为算法设计提供具体指导离散数学结构实际上就是通用的抽象的模式的集合。告诉你各种模式的本质特征和它们之间的关系，以及选用它们的策略；告诉你哪些问题是可解的，哪些是当前在图灵机模型上无（最优）解的，哪些是可以得到近似/较优解的。简而言之，离散数学的作用就在于训练运用离散结构作为问题的抽象模型、构造算法、解决问题的能力。关系型数据库的设计（关系代数）表达式解析（树）优化编译器的构造（闭包）编译技术、程序设计语言

6、（代数结构）Lisp和Prolog、人工智能、自动推理、机器证明（数理逻辑）网络路由算法（图论）游戏中的人工智能算法（图论、树、博弈论）专家系统（集合论、数理逻辑—知识和推理规则的计算机表达）软件工程—团队开发—时间和分工的优化（图论—网络、划分）(各种)算法的构造、正确性的证明和效率的评估（离散数学的各分支）逻辑学是一门研究思维形式及思维规律的科学，也就是研究推理过程的规律的科学。逻辑规律就是客观事物在人的主观意识中的反映。逻辑学分为辩证逻辑与形式逻辑两种，辩证逻辑是以辩证法认识论的世界观为基础的逻辑学，形式逻辑主要是对思维的形式结构和规律进行研究的类似于语法

7、的一门工具性学科。思维的形式结构包括了概念、判断和推理之间的结构和联系，其中概念是思维的基本单位，通过概念对事物是否具有某种属性进行肯定或否定的回答，这就是判断；由一个或几个判断推出另一判断的思维形式，就是推理。用数学方法来研究推理的规律称为数理逻辑。这里所指的数学方法，就是引进一套符号体系的方法，在其中表达和研究推理的规律。数理逻辑简介通常认为数理逻辑是由莱布尼兹(Leibniz)创立的。数理逻辑的内容包括：证明论、模型论、递归论、公理化集合论。数理逻辑的应用在形式语义学、程序设计方法学和软件工程领域。在逻辑程序设计方面。在数据库理论方面。在程序自动生成、自

8、动转换等的理论和技术研究