前言
本书是根据我多年来讲授离散数学的经验和兴趣写成的。对学生而言,我的目的是为他们提供内容准确且可读性强的教材,清晰地介绍并展示离散数学中的概念和技术。对于那些爱怀疑的学生,我的目标是展示离散数学的相关性和实用性。对于计算机科学专业的学生,我希望为他们将来的学习提供一切必需的数学基础。而对于数学专业的学生,我希望帮助他们理解重要的数学概念,并且意识到为什么这些概念对应用来说很重要。最重要的是,希望本书既能达到这些目标,又不含太多的水分。

对教师而言,我的目的是利用数学中行之有效的教学技术来设计一个灵活而全面的教学工具:只要有本书在手,教师就能迅速地从中筛选内容,以最适合特定学生的方式有效地开展离散数学的教学工作。希望我已经实现了这些目标。

在过去的30年中,本书取得了极大的成功,被世界各地超过100万名学生使用,并被翻译成多种语言,对此我感到非常欣慰。此次第8版所做的许多改进,正是得益于大量读者的反馈和建议。在这些读者中,既有来自北美600多所学校的师生,又有来自全球各地众多高校的读者,他们都曾将本书成功用作教材。由于所收到的这些反馈,以及在不断更新中所投入的大量精力,我才能够在每次升级时显著提高本书的吸引力和有效性。

本教材是为一学期或两学期的离散数学入门课程而设计的,适用于数学、计算机科学、工程等各类专业的学生。大学代数是唯一要求的先修课程,不过,要想真正学好离散数学,还是需要有一定的数学素养。本书的设计目标是满足各种类型离散数学入门课程的需求,内容高度灵活且非常全面。我希望本书不仅是一本成功的教科书,而且成为学生在日后的学习和职业生涯中可以参考的有价值的资源。

离散数学课程的目标

离散数学课程有多个目标。学生应该学会一系列特定的数学知识并知道怎样应用它们,更重要的是,这门课应教会学生怎样运用数学逻辑思维。为了达到这些目标,本教材特别强调数学推理以及问题求解的不同方法。本书中,五个重要主题将交织在一起:数学推理,组合分析,离散结构,算法思维,以及应用与建模。一门成功的离散数学课程应该小心谨慎地融合并平衡所有五个主题。

●数学推理。学生必须理解数学推理以便阅读、领会并构造数学论证。本书开篇即讨论数理逻辑,这为后续讨论证明方法打下了基础。本书描述了构造证明的方法与技巧两个方面。本书特别强调数学归纳法,不仅给出了这种证明技术的许多不同类型的实例,还详细地解释了数学归纳法为什么是一种有效的证明技术。

●组合分析。一个重要的解题技巧就是计数或枚举对象。本书中关于枚举的讨论从计数的基本技术着手。重点是运用组合分析方法来解决计数问题并分析算法,而不是简单地应用公式。

●离散结构。离散数学课程应该教会学生如何处理离散结构,即表示离散对象以及对象之间关系的抽象数学结构。这些离散结构包括集合、置换、关系、图、树和有限状态机等。

●算法思维。有些类型的问题可以通过算法的规范说明来求解。当一个算法被清楚地描述后,就可以编写计算机程序来实现之。该活动涉及的数学部分包括该算法的规范说明、正确性的验证,以及执行算法所需要的计算机内存和时间分析等,这些在本书中均有阐述。算法将采用自然语言 原书采用英语,而中译版则采用汉语。——译者注和一种易于理解的伪代码形式来描述。

●应用与建模。离散数学在几乎每个可以想到的研究领域中都有应用。许多应用涉及本书提到的计算机科学和数据网络,还有一些应用涉及更为广泛的领域,如化学、生物学、语言学、地理学、商业和互联网等。这些是离散数学的自然而又重要的应用,而非人为编造的。用离散数学来建模是一项十分重要的问题求解技巧,学生可通过一些练习来自己构造模型,从而掌握这一技巧。

第8版中的变化

虽然第7版已经是一本极具影响力的教材,但许多教师还是提出了一些修改请求,以使本书更适于教学。我花了大量的时间和精力来满足这些请求,努力以自己的方式改进本书并使之紧跟最新发展。

第8版的修改基于20多位正式审稿人的意见、学生和教师的反馈以及我自己的见解,希望新版本能成为一个更加有效的教学工具。第8版中所做的大量更新是为了帮助学生更好地学习这些内容。我增加了额外的解释和例子以便阐述那些学生经常感到困难的内容,增加了知识性的和富有挑战性的新练习,还增加了一些与Internet、计算机科学以及数学生物学等密切相关的应用。在开发人员的努力下,本书配套网站现在提供了很多工具,可以帮助学生掌握关键概念并探索离散数学世界。此外,还提供了有效和全面的学习和评估工具,以作为教科书的补充。

我希望教师能仔细阅读新版,以了解如何满足自己的教学需求。要列出所有更新是不切实际的,不过,我将给出概要性的描述,包括一些关键更新及其所带来的好处,这对读者来说或许是有益的。

本书新版对许多内容进行了完善、更新、补充和润色,所有这一切都是为了使本书成为现代离散数学课程的更加有效的教学工具。之前使用过本教材的教师会发现这次更新遍及全书,其中最值得注意的修订如下。

全书范围的更新

●对内容编排的完善贯穿全书,重点是使之更清晰,以便帮助学生阅读和理解概念。

●通过增加细节和解释来改进证明,同时提醒读者注意所采用的证明方法。

●新增例题,用于满足审稿人提出的需求,或是对新内容进行解释。有些例题可以在书中找到,有些例题则只在配套网站上提供。

●新增练习,有知识性的也有富有挑战性的,用于满足教师提出的需求或配合新内容。同时,还有些练习是为了完善或拓宽已有的练习。

●引入了更多的小标题以便将章节划分成更小的部分。

●极大地扩展了在线资源,以为教师和学生提供广泛的支持。后面会给出关于这些资源的详细描述。

主题方面的更新

●逻辑。引入了若干逻辑谜题。一道新例题解释了如何将n皇后问题建模为可满足性问题,这是一个简明易懂的例子。

●集合论。在正文中引入了多重集的概念(之前是在练习中引入的)。

●算法。新版讨论了字符串匹配算法,这是一个应用很广的重要算法,可用于拼写检查、关键字搜索、字符串匹配以及计算生物学。此外,还给出了求解字符串匹配练习的蛮力算法。

●数论。新版包含有关素数及其猜想的最新数值发现和理论发现。在正文中论述了扩展欧几里得算法和一遍(one-pass)算法(之前是在练习中介绍的)。

●密码学。由于在云计算中的重要性,新版涵盖了同态加密的概念。

●数学归纳法。扩展了数学归纳法证明的模板,并将其放在数学归纳法证明的例题之前。

●计数方法。扩充了用于计数的除法法则的讨论。

●数据挖掘。在n元关系一节讨论了数据挖掘中的一个关键概念——关联规则。另外,在练习中还引入了雅卡尔指数,可用于计算两个集合之间的距离。

●图论应用。添加了一道新例题,解释语义网络是如何工作的。这是人工智能中的一个重要结构,可以用图来建模。

●人物传记。新的人物传记包括怀尔斯、婆什迦罗、瓦列·普金、阿达马、张益唐和金特里。原有的传记也做了一些扩展和更新。这次更新是多方面的,包括具有历史意义的东方数学家、19世纪和20世纪的主要研究人员,以及目前活跃的21世纪的数学家和计算机科学家。

本书特色

易理解性。实践证明,本书对于初学者来说是易读易懂的。书中绝大部分内容不需要比大学代数更多的数学预备知识,需要额外帮助的学生可以在配套网站找到相应工具,以将数学素养提升到本书要求的水准。书中少数几处需要用到微积分知识的地方都已注明。大多数学生应该很容易理解用于表示算法的伪代码,无论是否正式学过程序设计语言。本书不要求正规计算机科学方面的预备知识。

每章都是从易于理解和易于领会的水平开始。一旦详细介绍了基本数学概念,就会给出稍难一些的内容以及在其他研究领域中的应用。

灵活性。为了便于灵活使用,本书做了精心的设计。各章对之前章节的依赖程度都被降到最低。每章分成长度大致相等的若干节,每节又根据内容划分成若干小节以方便教学。教师可以利用章节划分灵活地安排讲课进度。

写作风格。本书的写作风格是直接而又实用的。书中使用准确的数学语言,但没有采用过多的形式化与抽象,在数学命题中的记号和词语表达间做了精心的平衡。

数学严谨性和准确性。书中所有定义和定理的陈述都十分谨慎,这样学生可以欣赏语言的准确性和数学所需的严谨性。证明则是先由动机引入,然后再慢慢展开,并且所有步骤都经过了详细论证。证明中用到的公理及其所导出的基本性质在附录中均有描述,这呈现给学生一个清晰的概念,即在证明中他们能够做出何种假设。本书解释并大量使用了递归定义。

例题。全书共有超过800道例题,用来阐述概念、建立不同主题之间的关联以及介绍应用。在大部分例题中,首先提出问题,然后再以适量的细节给出解法。

应用。本书中的应用展示了离散数学在解决现实世界中的问题时的实用性。这些应用涉及广泛的领域,包括计算机科学、数据网络、心理学、化学、工程学、语言学、生物学、商业和互联网。

算法。离散数学的结论常常要用算法来表述,故书中多数章节都介绍了一些关键算法。这些算法采用文字叙述,同时也采用一种易于理解的结构化伪代码来描述。关于伪代码的描述和说明在附录C中给出。对于本书中的所有算法,都简要分析了其计算复杂度。

历史资料。书中对许多主题的背景做了简要介绍,并给出了89位数学家和计算机科学家的简短传记。这些科学家为离散数学做出过重要贡献,传记中介绍了他们的生活、事业和成就,同时配有照片(如果有的话)。

此外,我们还提供了一些历史资料,作为对正文中历史资料的补充。我们做了大量努力以使得本书能够反映新的发现。

关键术语和结论。每章最后列出关键术语和结论。关键术语只列出学生必须学会的那些,而非该章中定义的每个术语。

练习。书中包含4200多道练习题,涵盖大量不同类型的问题。不仅提供了足够多的简单练习用于培养基本技能,还提供了大量中等难度的练习和许多具有挑战性的练习。练习的叙述清晰而无歧义,并按难易程度进行了分级。练习中还包含一些特殊的讨论来展开正文中没有涉及的新概念,使得学生能够通过自己的努力来发现新的想法。

那些比平均难度稍难的练习用一个星号(*)标记,而那些更具挑战性的练习则用两个星号(**)来标记。需要用微积分知识求解的练习会明确指出。有些练习的结果要在正文中用到,我们用符号来标识这类题目。本书最后给出了所有奇数编号练习的答案或解题纲要。答案中大部分证明的步骤都十分清晰。

复习题。每章后面都有一组复习题。设计这些问题是为了帮助学生重点学习该章最重要的概念和技术。要回答这些复习题,学生必须写出较长的答案,而不是仅做一些计算或给出简答。

补充练习。每章后面都有一组丰富多样的补充练习。这些练习通常比每节后面的练习难度更大。补充练习旨在强化该章中的概念,并把不同主题更有效地综合起来。

计算机课题。每章后面还有一组计算机课题。全书共有大约150道计算机课题,用于将学生在计算和离散数学中所学到的内容联系起来。对于那些从数学角度或程序设计角度来看难度超过平均水平的计算机课题,我们用一个星号(*)标记,而那些非常具有挑战性的题目则用两个星号(**)标记。

计算和探索。每章后面都有一组计算和探索性的问题,共有大约120道。完成这些练习需要借助现有的软件工具,诸如学生或教师自己编写的程序,或像Maple或Mathematica这样的数学计算软件包。这些练习大多为学生提供了通过计算来发现一些新事实或想法的机会。(其中一些练习在配套的在线练习册《探索离散数学》(Exploring Discrete Mathematics)中也有讨论。)

写作课题。每章后面都有一组写作课题,要完成这类题目,学生需要参考数学方面的文献。有些题目本质上是关于历史知识的,需要学生查找原始资料;其他题目则将带领学生通往新内容和新思想。这些练习旨在向学生展示正文中没有深入探讨的想法,通过把数学概念和写作过程结合起来,帮助学生面对未来可能的研究领域。(在网络版或印刷版的《学生解题指南》(Student’s Solutions Guide)中可以找到为这些题目准备的参考文献。)

附录。本书有三个附录。附录A介绍实数和正整数的公理,并解释如何利用这些公理直接证明事实。附录B介绍指数函数和对数函数,复习课程中常用的一些基本内容。附录C则介绍正文中用来描述算法的伪代码。

推荐读物。在附录后还提供了一份针对全书及各章的推荐读物。这些推荐读物包括难度不超过本书的书籍、更难些的书籍、阐述性的文章以及发表离散数学新发现的原始文章。其中一些是多年前出版的经典读物,而另一些是在最近几年才出版的。本书的网站中包含许多有价值资源的链接,可以作为对这些推荐读物的补充。

怎样使用本书

本书经过了精心写作和编排,以支持不同层次以及侧重点不同的离散数学课程。下表列出了核心章节和可选章节。为大学二年级学生开设一学期的离散数学入门课程可以以本书核心章节为基础,其他章节可由教师取舍。两学期的入门课程可以在核心章节上外加所有可选的数学章节。强调计算机科学的课程则可以涵盖部分或全部计算机科学章节。教师可以在本书网站上的《教师资源手册》(Instructor’s Resource Guide)中找到离散数学课程教学大纲样本,以及针对本书章节的教学建议。

章节核心章节计算机科学可选章节数学可选章节

11.1~1.8(视需要)

22.1~2.4,2.6(视需要)2.5

33.1~3.3(视需要)

44.1~4.4(视需要)4.5,4.6

(续)

章节核心章节计算机科学可选章节数学可选章节

55.1~5.35.4,5.5

66.1~6.36.66.4,6.5

77.17.47.2,7.3

88.1,8.58.38.2,8.4,8.6

99.1,9.3,9.59.29.4,9.6

1010.1~10.510.6~10.8

1111.111.2,11.311.4,11.5

1212.1~12.4

1313.1~13.5

使用本书的教师可以选用或略去每节最后有挑战性的例题及练习来调整课程的难度。右侧的各章依赖图展示的是强依赖性。星号表示该章只有部分相关小节是学习后续章节所必需的。弱依赖关系不再列出。更多详细信息可以在《教师资源手册》中找到。

教辅资源

 关于本书教辅资源,只有使用本书作为教材的教师才可以申请,需要的教师可向麦格劳·希尔教育出版公司北京代表处申请,电话010-57997618/7600,传真010-59575582,电子邮件instructorchina@mheducation.com。——编辑注

《学生解题指南》。这本可以单独购买的学生手册包含所有奇数编号练习的完整解答。这些解答解释了为什么要用某种特定的方法以及为什么这种方法管用。对于有些问题,还给出了一两种其他可能的解法,以说明一个问题可以用多种不同方法来求解。指南的内容还包括:为每章后面的写作课题推荐的参考文献;关于如何撰写证明的指南;在离散数学学习中学生常犯的各类错误;为每章提供的考试样例及解答,以帮助学生准备考试。

《教师资料手册》。本手册在网站上提供,教师也可以申请印刷版,手册中包含书中所有偶数编号练习的完整解答。手册的内容还包括:关于如何讲授本书每章内容的建议,包括每节中应强调的重点以及如何组织内容;为每章提供的考试样例,以及一个包含1500多道考试题目的可选试题库,对于所有考试样例及试题库中的题目都给出了解答;针对不同的侧重点以及不同学生能力水平的课程教学大纲样本。

致谢

感谢所有将本书用作教材的教师和学生,他们来自不同的学校,并向我提供了很多有价值的反馈和有益的建议。正是有了他们的反馈,才使本书变得更为出色。特别感谢Jerrold Grossman和Dan Jordan,作为第8版的技术评审,他们以“鹰眼”般敏锐的目光确保了本书的准确性。在本书出版过程中的各个阶段,他们两位多次审阅了本书的每个角落,帮助消除了之前勘误表中的错误,并防止出现新的错误。

感谢Dan Jordan为《学生解题指南》和《教师资源手册》做出的贡献。他在更新这些教辅资源方面完成了令人钦佩的工作。感谢Jerrold Grossman,他是本书前7版教辅资源的作者,并为Dan提供了非常有价值的帮助。还要感谢许许多多曾经为本书创建并维护在线资源的人。特别感谢Dan Jordan和Rochus Boerner,他们所做的大量工作解决了配套网站的诸多问题(后面会介绍这个网站)。

感谢第8版以及所有之前版本的审稿人。他们给予我许多有益的批评和鼓励,希望这一版不会辜负他们的期望。自从本书第1版出版以来,已经有超过200位审稿人,其中有许多来自美国以外的国家。近期审稿人列表如下。

近期审稿人



感谢阅读过本书的学生,他们提供了很多建议并报告了一些勘误。在蒙茅斯大学时,曾经上过我的离散数学课程的学生,包括本科生和研究生,从方方面面帮助我改进了书中内容。

还要感谢麦格劳-希尔高等教育(本书的出版商)的工作人员,以及Aptara的生产人员。我还想感谢兰登书屋原来的编辑Wayne Yuhasz,以及本书之前的许多编辑,他们的见解和技巧是本书成功的有力保障。

我想对产品经理Nora Devlin表示深深的谢意,她所完成的工作已远远超出了既定的职责。她不仅能力出众,而且责任心强,努力解决了新版本开发过程中出现的各种问题。

还要感谢Peggy Selle,作为内容产品经理,她管理着本书的生产过程。她全程跟踪本书的流程,并帮助解决生产过程中出现的许多问题。感谢Aptara的高级产品经理Sarita Yadav和她的同事,他们的努力工作确保了本书的生产质量。

我还要对麦格劳-希尔高等教育的科学、工程和数学(SEM)部门的同仁表示感谢,他们对新版本以及相关的媒体内容给予了大力支持,包括:

●Mike Ryan,高等教育副总裁,负责作品统筹和学习内容管理

●Kathleen McMahon,数学与物理科学部门常务主管

●Caroline Celano,数学部门主管

●Alison Frederick,市场经理

●Robin Reed,首席产品开发师

●Sandy Ludovissey,采购人

●Egzon Shaqiri,设计师

●Tammy Juran,评估内容项目经理

●Cynthia Northrup,数字内容部门主管

●Ruth Czarnecki-Lichstein,业务产品经理

●Megan Platt,编辑协调人

●Lora Neyens和Jolynn Kilburg,项目经理

●Lorraine Buczek,内容授权专家



Kenneth H. Rosen


按 Ctrl+p 打印本页】【关闭