首页 > 图书中心 > 组合数学(第3版)

前言

电子计算机的出现是20世纪的大事,它改变了我们这个世界的面貌。可以毫不夸张地说,它的影响遍及所有的角落,几乎无处不感觉到它的存在。数学更不例外。严格地说,电子计算机本身就是近代数学的辉煌成就。将计算机与数学割裂开来,既不合理也不可能。组合学也就是在计算机科学蓬勃发展的刺激下崛起的,从而成为近若干年来最活跃的数学分支。它研究的问题有的可追溯到欧拉和哈密尔顿等18世纪的数学家,但它成为一个新的分支还是近若干年的事。它从与计算机科学相结合中获得了广阔的发展空间,从而也为计算机科学奠定了理论基础。

什么是计算机科学呢?有的学者将它定义为研究算法的一门学科。研究算法无疑是计算机科学的重要领域,也是本丛书的核心内容,贯穿始终。组合学家在20世纪70年代初建立的算法复杂性“NP理论”,至今仍然令无数计算机科学工作者与数学工作者为之折腰。

计算机科学里的组合学内容十分广泛。本丛书涉及组合分析、图论、组合算法、近代密码学、编码理论及算法复杂性等7部分。

组合分析是算法的理论基础。组合分析之于组合算法犹如数学分析于与计算数学,众所周知,前者是后者的理论根基。

图论原来是组合数学这个“家族”的主要成员,只因它已成长壮大,故自立门户独立出去。

算法复杂性的NP理论是近30年的一大成就。研究表明,对于一类叫做NPC类的困难问题,至今都不存在有效算法,但它们难度相当,只要其中任何一个找到多项式解法,则全体都获得解决;或证明它们根本不存在有效办法。不论是前者还是后者都还看不见露到海平面上的桅杆塔,它吸引了众多的有志之士。密码学是其中十分引人入胜的分支。如若设计好的密码,对它的破译等价于某一NPC类困难问题,无疑这样的密码将是牢不可破的。

在计算机网络深入普及的信息时代,信息本身就是时间,就是财富。信息传输通过的是脆弱的公共信道,信息储存于“不设防”的计算机系统中,如何保护信息的安全使之不被窃取乃至于不被篡改或破坏,已成为当今普遍关注的重大问题。密码是有效而且可行的办法。在计算机网络的刺激下,近代密码学便在算法复杂性理论的基础上建立起来了。密码作为一种技术,自从人类有了战争,不久便有了它。但作为一门学科则是近20多年的事。甚至于它已成为其他学科的基础。密码也从此走出“军营”,进入百姓家。

实际中的“优化”问题是大量的,半个多世纪以来它曾经几度辉煌。近来在计算机科学的影响下,又出现了若干闪光点,十分耀眼,引人注目。

实际上密码也是一种编码。如果说密码学研究的编码是保证通信的保密与安全,则编码理论研究的是通信中如何纠错与检错。计算机纠错码是既实用、理论上又饶有趣味的分支。

本丛书是作者在清华大学计算机科学与技术系长期工作的总结。它不是一部长篇记述,而是互相关联又彼此相对独立,因此难免有少量交叉。它们涉及的面如此之广,囿于作者的水平,缺点和错误在所难免,敬请读者不吝指正。谢谢。第3版序言

第3版与第2版不同之点在于将原来第6章的线性规划,换成现在与算法复杂性分析有关的内容,还增加了一些应用实例,删去线性规划是为了给新增加内容让出空间,新增加的部分无疑更贴近计算机科学。

本书各章基本上是互相独立的,比如讲了第1、第2两章后,再讲第5章,也是一种可以采用的方案。

第2章和第6章是由卢华明执笔的。写在“再版”前的话

转眼间《组合数学(算法与分析)》一书(上、下册)出版已快十年了。一本好的科技书总是要通过使用、修改、再使用、再修改几个反复才能臻于完善。出版社和作者都有出修订版的愿望。正好在此期间,原书上册被选作全国计算机专业的教材,这样两者便结合起来进行。本书问世之日,也是再版修订完成之时。读者不难发现“再版”中有相当数量的新增内容,有的虽材料依旧,但已是重新改写过的。

“组合数学”研究的问题源远流长,有的甚至于可追溯到欧拉等著名数学家。然而它之所以成为最活跃的一个数学分支,则是近年来受计算机科学蓬勃发展的刺激和影响。它从计算机的科学研究中获取了广阔的发展空间。本书是原书上册的再版,所以它仅仅是基础理论部分。基础是重要的,但毕竟不是全体。在它的出版后松一口气之余,余下部分的改写便自然而然地提到日程上来了。我计划在新的一册《算法与复杂性分析:组合算法》一书中继续完成它。

版权所有(C)2022 清华大学出版社有限公司 京ICP备10035462号 京公网安备11010802013248号

联系我们 | 网站地图 | 法律声明 | 友情链接 | 盗版举报 | 人才招聘