0.离散数学介绍.pdfVIP

离散数学 Discrete Mathematics --离散数学介绍 张晓西北工业大学计算机学院 zhangxiao@ 2011-1-10 课程介绍 离散数学，是现代数学的一个重要分支，计算机科 学与技术一级学科的核心课程，是整个计算机学科 的专业基础课。 离散数学是以研究离散量的结构和相互间的关系为 主要目标，其研究对象一般地是有限个或可数个元 素，因此它充分描述了计算机科学离散性的特点。 离散数学是随着计算机科学的发展而逐步建立的， 它形成于七十年代初期，是一门新兴的工具性学 科。 2011-1-10 离散数学 2 离散数学的发展 18世纪以前, 数学基本上是研究离散对象的数量和 空间关系的科学。 之后,因天文学,物理学的发展,如行星轨道,牛顿三 大力学定律等研究,极大地推动了连续数学(以微积 分,数学物理方程, 实、复变函数论为代表)的发 展。 离散对象的研究则处于停滞状态。 20世纪30年代, 图灵提出计算机的理论模型—— 图灵机。 这种模型早于实际制造计算机十多年,现实的计算 机的计算能力, 本质上和图灵机的计算能力一样。 由于在计算机内,机器字长总是有限的, 它代表离散 的数或其它离散对象，因此随着计算机科学和技术 的迅猛发展,离散数学就显得重要。 2011-1-10 离散数学 3 教材及课时 方世昌离散数学(第三版)，西安电子科技大学出 版社 1-13周每周二，四共52学时 课后题时间每周4小时以上 参考资料: 离散数学及其应用(原书第5版)，（美）罗森著，袁崇 义等译/2007年06月/机械工业出版社 /pkujpk/course/lssx/i ndex.htm 北大离散数学 /courses/lssx/longtime/i ndex.htm 北大离散数学 /playlist_show/id_15145 76.html?page=1mode=picascending=1 西工大 王琦老师讲课视频 2011-1-10 离散数学 4 学习内容 第五章及第七章不讲 6.5与6.8不讲 8.5至8.9不讲 2011-1-10 离散数学 5 离散数学的特点 离散数学由多门数学分支组成，每一分支可 以看成是一门独立的学科，它们从不同的角 度出发，研究各种离散量之间数与形的关 系。 概念多、定理多、证明多 （所以要求预习） 作业多（理解并应用） 2011-1-10 离散数学 6 离散数序学习内容 数理逻辑：“证明”在计算科学的某些领域至关重要， 构造证明和写程序的思维过程本质上是一样的。 组合分析：解决问题的重要方面就是计数或枚举对 象。 离散结构：用来表示离散对象以及它们之间关系的抽 象数学结构，包括：集合、排列、关系、树、图。 算法化思维：许多问题都可以通过构造一个可以被程 序实现的算法来解决。它的三个步骤是：构造 （选择 合适的离散模型和操作步骤）、验证 （算法的正确 性）、评估 （时间和空间的复杂性）。 应用和建模：在可以想到的任何研究领域都有离散数 学的应用。计算科学、化学、植物学、动物学、语言 学、地理、经济学等，构造离散模型都是极其