计算机科学组合学丛书序 电子计算机的出现是20世纪的大事，它改变了我们这个世界的面貌。可以毫不夸张地说，它的影响遍及所有角落，几乎无处不感觉到它的存在。数学更不例外。严格地说，电子计算机本身就是近代数学的辉煌成就。将计算机与数学割裂开来，既不合理也不可能。组合学也就是在计算机科学蓬勃发展的刺激下而崛起的，从而成为近若干年来最活跃的数学分支。它研究的问题有的可追溯到Euler和Hamiltan等18世纪的数学家，但它成为新的分支还是近若干年的事。它从与计算机科学相结合中获得了广阔的发展空间，从而也为计算机科学奠定了理论基础。 什么是计算机科学呢?有的学者将它定义为研究算法的一门学科。研究算法无疑是计算机科学的重要领域，也是本丛书的核心内容，贯穿始终。组合学家在20世纪70年代初建立的算法复杂性“NP理论”，至今仍然令无数计算机科学工作者与数学工作者为之折腰。 计算机科学里的组合学内容十分广泛。本丛书涉及组合分析、图论、组合算法、近代密码学、组合优化、编码理论及算法复杂性等7部分。 组合分析是算法的理论基础。组合分析之与组合算法犹如数学分析之与计算数学，众所周知，前者是后者的理论根基。 图论原本是组合数学这个“家族”的主要成员，只因它已成长壮大，故自立门户独立出去。 算法复杂性的NP理论是近三十年的一大成就。研究表明对于一类叫做NPC类的困难问题，至今都没找到有效算法，但它们难度相当，只要其中任何一个找到多项式解法，则全体都获得解决；或证明它们根本不存在有效办法。不论是前者还是后者都还看不见露到海平面上的桅杆塔，它吸引了众多的有志之士。密码学是其中十分引人入胜的分支。如若设计好的密码，对它的破译等价于某一NPC类困难问题，无疑这样的密码将是牢不可破的。 在计算机网络深入普及的信息时代，信息本身就是时间，就是财富。信息的传输通过的是脆弱的公共信道，信息储存于“不设防”的计算机系统中，如何保护信息的安全使之不被窃取及不至于被篡改或破坏，已成为当今被普遍关注的重大问题。密码是有效而且可行的办法。在计算机网络的刺激下，近代密码学便在算法复杂性理论的基础上建立起来了。密码作为一种技术，自从人类有了战争，不久便有了它。但作为一门学科则是近二十多年的事。甚至于它已成为其他学科的基础。密码也从此走出“军营”，进入百姓家。 实际中的“优化”问题是大量的，半个多世纪以来它曾经几度辉煌。近来在计算机科学的影响下，又出现了若干闪光点，十分耀眼，引人注目。 实际上密码也是一种编码。如果说密码学研究的编码是保证通信的保密与安全，则编码理论研究的是通信中如何纠错与检错。计算机纠错码是既实用、理论上又饶有趣味的分支。 本丛书是作者在清华大学计算机科学与技术系长期工作的总结。它不是一部“长篇”记述，而是互相关联又彼此相对独立，因此难免有少量交叉。它们涉及的面如此之广，囿于作者的水平，缺点和错误在所难免，敬请读者不吝指正。 作 者前 言 线性规划最初是美国军方为解决其运输等后勤问题而提出来的。自从1947年G.B.Dantzig公开了他的单纯形法以来，其应用范围日益扩大，几乎遍及经济规划、工业生产和商业活动等各个方面。单纯形法始终扮演着光彩夺目的角色。线性规划也作为运筹学的主要内容受到普遍重视，以至于许多高等院校的数学系、经济管理系以及系统工程等专业都把它列为一门必修课。 线性规划在其发展过程中有几件事值得一提，一方面是受到管理思维的影响，经济活动已不是像“经济人”那样一味地追求“利润极大”、“开支极小”，代之以决策时考虑“普遍感到满意”，目标规划就是在这个基础上被提出来的。它还属线性规划的范畴，但比传统的单目标规划灵活，值得大力推动以扩大其应用。 另一方面随着计算机科学的蓬勃发展，计算复杂性理论新军兴起，引人入胜，单纯形法虽然表现甚佳，但它的复杂性究竟如何？这时Minty和Klee举出一个例子证明单纯形法在最坏情况下属于指数型算法。20世纪70年代末，前苏联数学家Xaчиян提出线性规划的椭球算法，从理论上证明了线性规划属于多项式型问题，然而椭球算法的实际效果极差，徒有理论价值。不久Bell实验室的Karmarkar又提出一个新的多项式算法理论，并证明其复杂性分析能力比Xaчиян的椭球算法要好。但人们相信该算法还有进一步改善的潜力，经20世纪80年代以来多人的努力，似乎由此形成的“内点法”在超大型问题方面解题速度要快于单纯形法。 线性规划中的整数规划，其难度要大得多，其中有不少涉及NP理论的命题，本书将适当介绍。 本书主要由卢华明执笔。囿于作者的水平，缺点和错误在所难免，敬请指正！ 编者2008年7月

• 暂无课件
• 暂无样章
• 暂无网络资源

扫描二维码
下载APP了解更多

版权图片链接