算法设计与分析 (2008 年度畅销榜NO.1488 )

为了适应培养21世纪计算机人才的需要，结合我国高等院校教育工作的现状，立足培养学生能跟上国际计算机科学技术的发展水平，更新教学内容和教学方法，本书以算法设计策略为知识单元，系统地介绍计算机算法的设计方法与分析技巧，以期为计算机科学与技术学科的学生提供广泛而坚实的计算机算法基础知识。 \r\n 本书内容丰富，观点新颖，理论联系实际。采用Java语言描述算法，简明清晰、结构紧凑，可读性强。本书可以作为高等院校计算机专业本科生和研究生学习计算机算法设计的教材，也可供广大工程技术人员和自学读者学习参考。

第1章 算法引论\r\n\r\n1.1 算法与程序\r\n1.2 表达算法的抽象机制\r\n1.3 描述算法\r\n1.4 算法复杂性分析\r\n小结\r\n习题\r\n\r\n第2章 递归与分治策略\r\n\r\n2.1 速归的概念\r\n2.2 分治法的基本思想\r\n2.3 二分搜索技术\r\n2.4 大整数的乘法\r\n2.5 Strassen矩阵乘法\r\n2.6 棋盘覆盖\r\n2.7 合并排序\r\n2.8 快速排序\r\n2.9 线性时间选择\r\n2.10 最接近点对问题\r\n2.11 循环赛日程表\r\n小结\r\n习题\r\n\r\n第3章 动态规划\r\n\r\n3.1 矩阵连乘问题\r\n3.2 动态规划算法的基本要素\r\n3.3 最长公共子序列\r\n3.4 凸多边形最优三角剖分\r\n3.5 多边形游戏\r\n3.6 图像压缩\r\n3.7 电路布线\r\n3.8 流水作业调度\r\n3.9 0-1背包问题\r\n3.10 最优二叉搜索树\r\n小结\r\n习题\r\n\r\n第4章 贪心算法\r\n\r\n4.1 活动安排问题\r\n4.2 贪心算法的基本要素\r\n4.2.1 贪心选择性质\r\n4.2.2 最优子结构性质\r\n4.2.3 贪心算法与动态规划算法的差异\r\n4.3 最优装载\r\n4.4 哈夫曼编码\r\n4.4.1 前缀码\r\n4.4.2 构造哈夫曼编码\r\n4.4.3 哈夫曼算法的正确性\r\n4.5 单源最短路径\r\n4.5.1 算法基本思想\r\n4.5.2 算法的正确性和计算复杂性\r\n4.6 最小生成树\r\n4.6.1 最小生成树性质\r\n4 6.2 Prim算法\r\n4.6.3 Kruskal算法\r\n4.7 多机调度问题\r\n4.8 贪心算法的理论基础\r\n4.8.1 拟阵\r\n4.8.2 带权拟阵的贪心算法\r\n4.8.3 任务时间表问题\r\n小结\r\n习题\r\n\r\n第5章 回溯法\r\n\r\n5.1 回溯法的算法框架\r\n5.1.1 问题的解空间\r\n5.1.2 回溯法的基本思想\r\n5.1.3 递归回溯\r\n5.1.4 迭代回溯\r\n5.1.5 子集树与排列树\r\n5.2 装载问题\r\n5.3 批处理作业调度\r\n5.4 符号三角形问题\r\n5.5 n后问题\r\n5.6 0-1背包问题\r\n5.7 最大团问题\r\n5.8 图的m着色问题\r\n5.9 旅行售货员问题\r\n5.10 圆排列问题\r\n5.11 电路板排列问题\r\n5.12 连续邮资问题\r\n5.13 回溯法的效率分析\r\n小结\r\n习题\r\n\r\n第6章 分支限界法\r\n\r\n6.1 分支限界法的基本思想\r\n6.2 单源最短路径问题\r\n6.3 装载问题\r\n6.4 布线问题\r\n6.5 0-1背包问题\r\n6.6 最大团问题\r\n6.7 旅行售货员问题\r\n6.8 电路板排列问题\r\n6.9 批处理作业调度\r\n小结\r\n习题\r\n\r\n第7章 概率算法\r\n\r\n7.1 随机数\r\n7.2 数值概率算法\r\n7.2.1 用随机投点法计算л值\r\n7.2.2 计算定积分\r\n7.2.3 解非线性方程组\r\n7.3 舍伍德算法\r\n7.3.1 线性时间选择算法\r\n7.3.2 跳跃表\r\n7.4 拉斯维加斯算法\r\n7.4.1 n后问题\r\n7.4.2 整数因子分解\r\n7.5 蒙特卡罗算法\r\n7.5.1 蒙特卡罗算法的基本思想\r\n7.5.2 主元素问题\r\n7.5.3 素数测试\r\n小结\r\n习题\r\n\r\n第8章 NP完全性理论\r\n\r\n8.1 计算模型\r\n8.1.1 随机存取机RAM\r\n8.1.2 随机存取存储程序机RASP\r\n8.1.3 RAM模型的变形与简化\r\n8.1.4 图灵机\r\n8.1.5 图灵机模型与RAM模型的关系\r\n8.1.6 问题变换与计算复杂性归约\r\n8.2 P类与NP类问题\r\n8.2.1 非确定性图灵机\r\n8.2.2 P类与NP类语言\r\n8.2.3 多项式时间验证\r\n8.3 NP完全问题\r\n8.3.1 多项式时间变换\r\n8.3.2 Cook定理\r\n8.4 一些典型的NP完全问题\r\n8.4.1 合取范式的可满足性问题\r\n8.4.2 3元合取范式的可满足性问题\r\n8.4.3 团问题\r\n8.4.4 顶点覆盖问题\r\n8.4.5 子集和问题\r\n8.4.6 哈密顿回路问题\r\n8.4.7 旅行售货员问题\r\n小结\r\n习题\r\n\r\n第9章 近似算法\r\n\r\n9.1 近似算法的性能\r\n9.2 顶点覆盖问题的近似算法\r\n9.3 旅行售货员问题近似算法\r\n9.3.1 具有三角不等式性质的旅行售货员问题\r\n9.3.2 一般的旅行售货员问题\r\n9.4 集合覆盖问题的近似算法\r\n9.5 子集和问题的近似算法\r\n9.5.1 子集和问题的指数时间算法\r\n9.5.2 子集和问题的完全多项式时间近似格式\r\n小结\r\n习题\r\n\r\n第10章 算法优化策略\r\n\r\n10.1 算法设计策略的比较与选择\r\n10.1.1 最大子段和问题的简单算法\r\n10.1.2 最大子段和问题的分治算法\r\n10.1.3 最大子段和问题的动态规划算法\r\n10.1.4 最大子段和问题与动态规划算法的推广\r\n10.2 动态规划加速原理\r\n10.2.1 货物储运问题\r\n10.2.2 算法及其优化\r\n10.3 问题的算法特征\r\n10.3.1 贪心策略\r\n10.3.2 对贪心策略的改进\r\n10.3.3 算法三部曲\r\n10.3.4 算法实现\r\n10 3.5 算法复杂性\r\n10.4 优化数据结构\r\n10.4.1 带权区间最短路问题\r\n10.4.2 算法设计思想\r\n10.4.3 算法实现方案\r\n10.4.4 并查集\r\n10.4.5 可并优先队列\r\n10.5 优化搜索策略\r\n小结\r\n习题\r\n\r\n参考文献

21世纪是知识经济的时代, 是人才竞争的时代. 随着21世纪的到来, 人类已步入信息社会, 信息产业正成为全球经济的主导产业. 计算机科学与技术在信息产业中占据了最重要的地位, 这就对培养21世纪高素质创新型计算机专业人才提出了迫切的要求.

为了培养高素质创新型人才, 必须建立高水平的教学计划和课程体系. 在20多年跟踪分析ACM和IEEE计算机课程体系的基础上, 紧跟计算机科学与技术的发展潮流, 及时制定并修正教学计划和课程体系是尤其重要的. 计算机科学与技术的发展对高水平人才的要求, 需要我们从总体上优化课程结构, 精炼教学内容, 拓宽专业基础, 加强教学实践, 特别注重综合素质的培养, 形成“基础课程精深, 专业课程宽新”的格局.

为了适应计算机科学与技术学科发展和计算机教学计划的需要, 要采取多种措施鼓励长期从事计算机教学和科技前沿研究的专家教授积极参与计算机专业教材的编著和更新, 在教材中及时反映学科前沿的研究成果与发展趋势, 以高水平的科研促进教材建设. 同时适当引进国外先进的原版教材.

为了提高教学质量, 需要不断改革教学方法与手段, 倡导因材施教, 强调知识的总结. 梳理. 推演和挖掘, 通过加快教案的不断更新, 使学生掌握教材中未及时反映的学科发展新动向, 进一步拓广视野. 教学与科研相结合是培养学生实践能力的有效途径. 高水平的科研可以为教学提供最先进的高新技术平台和创造性的工作环境, 使学生得以接触最先进的计算机理论. 技术和环境. 高水平的科研还可以为高水平人才的素质教育提供良好的物质基础. 学生在课题研究中不但能了解科学研究的艰辛和科研工作者的奉献精神, 而且能熏陶和培养良好的科研作风, 锻炼和培养攻关能力和协作精神.

进入21世纪, 我国高等教育进入了前所未有的大发展时期, 时代的进步与发展对高等教育质量提出了更高. 更新的要求. 2001年8月, 教育部颁发了《关于加强高等学校本科教学工作, 提高教学质量的若干意见》. 文件指出, 本科教育是高等教育的主体和基础, 抓好本科教学是提高整个高等教育质量的重点和关键. 随着高等教育的普及和高等学校的扩招, 在校大学本科计算机专业学生的人数将大量上升, 对适合21世纪大学本科计算机科学与技术学科课程体系要求的, 并且适合中自学生学习的计算机专业教材的需求量也将急剧增加. 为此, 中国计算机学会和清华大学出版社共同规划了面向全国高等院校计算机专业本科生的“21世纪大学本科计算机专业系列教材”. 本系列教材借鉴美国ACM和IEEE／CS最新制定的《Computing Curricula 2001》(简称CC2001)课程体系, 反映当代计算机科学与技术学科水平和计算机科学技术的新发展. 新技术, 并且结合中国计算机教育改革成果和中国国情.

中国计算机学会教育专业委员会和全国高等学校计算机教育研究会, 在清华大学出版社的大力支持下, 跟踪分析CC200l, 并结合中国计算机科学与技术学科的发展现状和计算机教育的改革成果, 研究出了《中国计算机科学与技术学科教程2002》(China Computing Curricula 2002, 简称CCC2002), 该项研究成果对中国高等学校计算机科学与技术学科教育的改革和发展具有重要的参考价值和积极的推动作用.

“21世纪大学本科计算机专业系列教材”正是借鉴美国ACM和IEEE／CS CC2001课程体系, 依据CCC2002基本要求组织编写的计算机专业教材. 相信通过这套教材的编写和出版, 能够在内容和形式上显著地提高我国计算机专业教材的整体水平, 继而提高我国大学本科计算机专业的教学质量, 培养出符合时代发展要求的具有较强国际竞争力的高素质创新型计算机人才.

中国工程院院士

国防科学技术大学教授

21世纪大学本科计算机专业系列教材编委会名誉主任

2002年7月

以最少的成本. 最快的速度. 最好的质量开发出适合各种应用需求的软件, 必须遵循软件工程的原则, 设计出高效率的程序. 一个高效率的程序不仅需要“编程小技巧”, 更需要合理的数据组织和清晰高效的算法. 这正是计算机科学领域里数据结构与算法设计所研究的主要内容. 一些著名的计算机科学家在有关计算机科学教育的论述中指出, 计算机科学是一种创造性思维活动, 其教育必须面向设计. 算法设计与分析正是一门面向设计, 处于计算机科学与技术学科核心地位的教育课程. 通过对计算机算法系统的学习与研究, 理解和掌握算法设计的主要方法, 培养对算法的计算复杂性进行正确分析的能力, 为独立地设计算法和对给定算法进行复杂性分析奠定坚实的理论基础. 这些对从事计算机系统结构. 系统软件和应用软件研究与开发的科技工作者都是非常重要和必不可少的. 为了适应培养21世纪计算机人才的需要, 结合我国高等院校教育工作的现状, 立足培养学生能跟上国际计算机科学技术的发展水平, 更新教学内容和教学方法, 本书以算法设计策略为知识单元, 系统地介绍计算机算法的设计方法与分析技巧, 以期为计算机学科的学生提供广泛坚实的计算机算法基础知识.

全书共分10章. 首先在第1章中介绍了算法的基本概念, 接着对算法的计算复杂性和算法的描述作了简要的阐述. 然后围绕设计算法常用的基本设计策略组织了第2章至第10章的内容.

第2章介绍递归与分治策略, 这是设计有效算法最常用的策略, 必须掌握的方法.

第3章介绍动态规划算法, 以具体实例详述动态规划算法的设计思想. 适用性以及算法的设计要点.

第4章介绍贪心算法, 这也是一种重要的算法设计策略, 它与动态规划算法的设计思想有一定的联系, 但其效率更高. 按贪心算法设计出的许多算法能产生最优解. 其中有许多典型问题和典型算法可供学习和使用.

第5章和第6章分别介绍了回溯法和分支限界法. 这两章所介绍的算法适合于处理难解问题, 其解题的思想各具特色, 值得学习和掌握.

第7章介绍了概率算法, 对许多难解问题提供了高效的解决途径, 是有很高实用价值的算法设计策略.

第8章介绍NP完全性理论. 首先介绍了计算模型, 确定性和非确定性图灵机.

然后进一步深入介绍NP完全性理论. 这一章是全书理论性最强的一章, 难度较大, 适合于高年级本科生或研究生学习.

第9章介绍了解NP难问题的近似算法, 这是当前计算机算法领域的热门研究课题, 具有很高的实用价值.

第10章通过实例介绍算法设计中常用的算法优化策略.

在本书各章的论述中, 首先介绍一种算法设计策略的基本思想, 然后从解决计算机科学与应用中出现的实际问题入手, 由简到繁地描述几个精典的精巧算法, 同时对每个算法所需要的时间和空间进行分析. 这样使读者既能学到常用的精巧算法, 又能通过对算法设计策略的反复应用, 牢固掌握这些算法设计的基本策略, 以期收到融会贯通之效. 在为各种算法设计策略选择用于展示其设计思想与技巧的具体应用问题时, 本书有意重复选择某些经典问题, 使读者能深刻地体会到一个问题可以用多种设计策略求解. 同时通过对解同一问题的不同算法的比较, 更容易体会到每一个具体算法的设计要点. 随着本书内容的逐步展开, 读者也将进一步感受到综合应用多种设计策略可以更有效地解决问题.

本书采用面向对象的Java语言作为表述手段, 在保持Java优点的同时, 尽量使算法的描述简明. 清晰. 为了加深对知识的理解, 各章配有难易适当的习题, 以适应不同程度读者练习的需要.

福州大学“211工程”计算机与信息工程重点学科实验室为本书的写作提供了优良的设备与工作环境. 南京大学宋方敏教授和福州大学傅清祥教授在百忙之中认真审阅了全书, 提出了许多宝贵的改进意见. 在此, 谨向每一位曾经关心和支持本书编写工作的各方面人士表示衷心的谢意!

由于作者的知识和写作水平有限, 书稿虽几经修改, 仍难免有缺点和错误. 热忱欢迎同行专家和读者的批评指正, 使本书在使用中不断改进, 日臻完善.

作 者

2003年1月