定 价:139 元 本教材已被 1 所学校申请过!
丛书名:经典原版书库
- 作者:[加] 埃德加·古德尔(Edgar Goodaire) 著
- 出版时间:2020/5/1
- ISBN:9787111654643
- 出 版 社:机械工业出版社
- 中图法分类:O157.5
- 页码:461
- 纸张:胶版纸
- 版次:1
- 开本:16开
- 字数:(单位:千字)
《离散数学与图论(英文版 原书第3版)》由离散数学和图论两部分组成,共14章,前七章聚焦于离散数学,后七章聚焦于图论。各章内容均经过多年的课堂实践检验,且在编排上尽量保持独立,有不同教学需求的教师可灵活选择。《离散数学与图论(英文版 原书第3版)》几乎不要求学生有任何背景知识,即便没有微积分和线性代数基础的学生也能轻松学习。
自从本书第一次印刷以来,大量读者询问是否有解题手册.在此先告知一下,确实有供教师使用的完整解题手册,可以从当地销售代表处获得.
本书的内容已经过多年的教学实践检验,可用于两门一学期课程.一门是为(没有图论基础的)大二学生开设的离散数学课程,另一门是为大三学生开设的应用图论课程.相比其他教科书,本书更基础,编排上也更易于理解.例如,为使没有微积分和线性代数基础的学生也能修我们的课程,本书假设学生不具有这些方面的背景知识,尽管本书用一个短小的附录介绍矩阵.书中个别需要用到微积分或线性代数知识的地方也会明确标识出来,除了一个例外,本书实际上不需要读者具有任何背景知识,这个例外就是10.3节,即图的邻接矩阵,其中会用到一点点线性代数的知识,如果愿意,跳过这一节也没关系。
第一门课程的内容为第0~7章,尽管如此,我们发现对于只有35节50分钟的课程而言依然没法涵盖这几章展示的所有主题,调整课时的方法有很多.一种可能是省略第4章(整数),尽管该章是我们最喜欢的内容之一,尤其是对于后续还会继续修数论课程的学生更是如此.另一个办法是跳过第5章中除了数学归纳法以外的所有内容,以及其他一些独立的主题,比如偏序(2.5节)和错排(7.6节)。
第8章介绍算法的基本概念和复杂度,非常适合作为图论课程的绪论.第9N14章的主题是图论,我们的经验是大部分内容适合于33课时的课程,也可以删节9.1节中的谜题、12.5节和12.6节的深度优先搜索及其应用、14.3节的最大流一最小割集定理的应用或者14.4节的匹配.本书第二部分的内容大多是自完备的,教师可以按自己愿意进行删节。
在可能的情况下,本书试图保持各章内容独立于前面的章节.当然,也有一些不可能的情况.例如,在阅读4.4节的同余内容之前,必须理解2.4节的等价关系;而学习13.3节的公用设施设计之前,必须学习10.2节的哈密顿图,可是多数情况下,图论的内容可以独立于前面的章节来学习,像第3章函数概念以及等价关系等知识在许多地方都需要用到,当然,图论中的许多证明还需要用到第5章的数学归纳法。
另一方面,我们在练习题中会安排一些与之前章节内容相关的题目,也会安排只和本章节内容相关的题目.这样大大扩展了教师应对不同教学大纲的可能性,也能恰好为不同学生提供不同难度的练习题.本书最后提供了1200多道题的解题过程,我们希望使用本书的学生能够欣赏这些完整的解题过程而不是简单的答案。
本书的主要目标之一是引领学生既严谨又友善地对待“证明”.0.1节和0.2节作为证明的预备知识也有点难度.有些老师希望书中有更多有关逻辑的主题,为此本书用一整章论述逻辑(第1章),共3小节,涵盖真值表、命题代数和逻辑论证.第3版更新
我们很高兴经常收到本书读者的电子邮件,当然,我们也很感激本书的许多评阅人提出的意见和建议.我们希望人们能从这一版本中看到我们是真心对待他们的谏言的,特别是从下面这些“更新”中:
以前的第1章(“证明”)被拆分为两章,其中,一章是解释性的“证明”;另一章是“逻辑”(包含真值表、命题代数、逻辑论证),也是计算机科学专业的学生更感兴趣的.
新增了7.3节和7.4节,讨论概率.
深度优先搜索的内容原先独立成短小一章,现在移到第12章,这样更合适些.
关于RNA链的11.3节已经完全重写,新增了一个更简单的从完整的酶消化物中回收RNA链的算法.
每节都添加了是非题(所有答案见本书最后).
新增了900多个练习题,并在本书最后附有完整解题过程,鉴于读者请求,我们在有些节的开始处增加了一些更为基础的练习题.
读者很赞赏我们对数学归纳法内容的编排.受此鼓励,我们在这个重要主题上又添加了很多新的练习题,
本书某些地方需要用到线性代数知识,因此我们增加了一个关于矩阵的短小附录.以帮助那些从来没学过或者需要复习一下该主题的读者.
本书还引入了与计算机科学相关的许多应用.
第0章 证明
0.1 复合命题
0.2 数学中的证明
练习题
第1章 逻辑
1.1 真值表
1.2 命题代数
1.3 逻辑论证
练习题
第2章 集合与关系
2.1 集合
2.2 集合上的运算
2.3 二元关系
2.4 等价关系
2.5 偏序
练习题
第3章 函数
3.1 基本术语
3.2 逆与合成
3.3 一一对应与集合的基数
练习题
第4章 整数
4.1 除法算法
4.2 整除性与欧几里得算法
4.3 素数
4.4 同余
4.5 同余的应用
练习题
第5章 归纳法与递归
5.1 数学归纳法
5.2 递归定义的序列
5.3 求解递推关系式:特征多项式
5.4 求解递推关系式:生成函数
练习题
第6章 计数原理
6.1 容斥原理
6.2 加法和乘法规则
6.3 鸽巢原理
练习题
第7章 排列与组合
7.1 排列
7.2 组合
7.3 初等概率
7.4 概率论
7.5 可重复的排列组合
7.6 错排
7.7 二项式定理
练习题
第8章 算法
8.1 什么是算法
8.2 复杂度
8.3 搜索与排序
8.4 排列组合的枚举
练习题
第9章 图
9.1 引人入胜的简介
9.2 定义与基本性质
9.3 同构
练习题
第10章 路径与回路
10.1 欧拉回路
10.2 哈密顿回路
10.3 邻接矩阵
10.4 最短路径算法
练习题
第11章 路径与回路的应用
11.1 中国邮递员问题
11.2 有向图
11.3 RNA链
11.4 锦标赛
11.5 调度问题
练习题
第12章 树
12.1 树及其性质
12.2 生成树
12.3 最小生成树算法
12.4 无环有向图与Bellman算法
12.5 深度优先搜索
12.6 单行道问题
练习题
第13章 平面图与着色
13.1 平面图
13.2 图着色
13.3 回路测试与公用设施设计
练习题
第14章 最大流-最小割集定理
14.1 流与割集
14.2 构造最大流
14.3 应用
14.4 匹配
练习题
附录A 是非题及部分练习题的解题过程
词汇表
索引