本书以算法设计与分析的理论、方法和技术为主线，系统地介绍分治方法、动态规划方法和贪心方法、最小值最大值方法、搜索方法、随机算法、近似算法和在线算法等算法设计技术，和循环不变量方法、反例方法、平摊分析方法、概率分析方法、近似度分析方法和竞争度分析方法等算法分析技术。在介绍这些理论、方法和技术的同时，还介绍计算几何、图论、元素选取、最大流、顶点覆盖和匹配等领域的一些基本算法。全书强调问题特征分析、基本算法和算法设计技术的有机结合构成典型的算法设计过程。书中配置了大量习题，以期读者能够在实践过程中加深对算法设计与分析方法的理解并提高算法设计与分析的速度。
本书讲解透彻、分析严谨、深入浅出地讲解算法设计与分析的理论、方法和技术，并提供大量算法设计与分析的实例，使得读者在阅读过程中能够清晰地掌握思路、理清脉络，培养自身以算法设计和分析为手段时间高效、空间高效地解决问题的意识和能力。
本书可以作为计算机相关专业本科生、研究生教材，也可供从事算法设计与分析工作的工程技术人员参考。

本书是作者在多年从事算法设计与分析课程教学和研究的基础上编写而成，系统地介绍了算法设计与分析的理论、方法和技术，包括分治算法、动态规划算法、贪心算法、最小值最大值方法、搜索策略、随机算法、近似算法和在线算法等算法设计技术，以及循环不变量方法、反例方法、平摊分析方法、概率分析方法、近似度分析方法和竞争度分析方法等算法分析技术。书中提供了大量算法设计与分析的实例，使得读者在阅读过程中能够清晰地理解概念、理清脉络，培养自身以算法设计和分析为手段、高效地解决问题的意识和能力。

本书特色：
线索清晰，内容精炼。以算法设计与分析的基本方法为主线，每种方法均先介绍原理，再列举若干典型算法设计实例说明方法的各个侧面，并舍弃了先修课程已经学过的算法，使得读者能够将更多的注意力转移到掌握算法设计方法上。
讲解透彻，分析严谨。对每个算法，均力争展示算法设计的自然过程，即从问题的蛮力算法入手，严谨地分析和证明计算问题的特征，再利用问题的特征逐步得到问题的高效算法，最后对算法进行严谨的分析，这样做有利于培养读者的创新意识和研究能力。
由浅入深，结构灵活。对每章内容的安排均由易到难、由简到繁，逐渐深入，这有利于读者循序渐进地掌握各种算法设计方法的本质和难点，也有利于教师根据实际情况对较难、较深的内容进行取舍。

算法设计与分析是计算机科学永恒不变的主题，是计算机专业的核心课程之一。这门课程旨在培养学生以算法设计和分析为手段，时间高效、空间高效地解决问题的意识和能力，以及简洁、清晰、准确表达算法及其分析过程的技能，提高学生的算法修养，培养创新意识，培育研究能力。通过这门课程的学习，学生可以理解算法和算法复杂度的概念，掌握评判算法优劣的标准，较系统地掌握分治算法、动态规划算法、贪心算法、搜索策略、随机算法、近似算法和在线算法等算法设计技术，掌握循环不变量方法、反例方法、平摊分析方法、概率分析方法、近似度分析方法和竞争度分析方法等算法分析技术，为进一步深造打下良好的算法基础。
　　为实现上述培养目标，作者结合自己多年从事算法设计与分析课程教学和研究的经验，精心地选取和组织了这门课程的教学内容。全书以算法设计与分析方法为主线，分为11章，着重强调对算法设计与分析基本技术的掌握，舍弃了在数据结构、集合论与图论等先修课程中学生已经掌握的基本算法，包括绝大部分排序算法、字符串匹配算法和基本图论算法。第1章是绪论，建立算法的概念并阐述算法设计和分析的目的和意义。第2章是数学基础，总结全书算法分析过程中使用的主要数学工具和数学结论，便于在后续章节中着重于算法设计和分析的过程，尽量避免复杂的数学推导过程。第3~5章介绍算法设计与分析的基本技术，包括分治算法、动态规划算法和贪心算法。第6章介绍平摊分析技术及其应用。第7章介绍最大值最小值方法，讨论网络流和匹配等图论问题的算法。第8~10章介绍难解问题的三种处理方法，包括树的搜索策略、随机算法、近似算法。第11章介绍在线算法和竞争度分析。
　　对每一种算法设计与分析技术，均先通过简单的例子介绍技术的原理和要点，再通过一系列的例子阐述使用该技术时需要注意的各个侧面。例如，第3章的一系列算法设计实例着重强调利用分治算法求解问题时划分阶段、递归求解阶段和合并阶段需要注意的问题。第4章的一系列算法设计实例除阐明动态规划的要点之外，还展示了各种典型的优化子结构，等等。
　　本书还特别强调算法设计过程依赖于对问题的分析和对问题特征的把握，即算法设计通常从求解问题的蛮力算法开始，逐步观察和分析问题的特征并结合恰当的算法设计技术，逐渐设计出高效的算法。每章均包含了这样的算法设计实例，以引导读者建立从蛮力法入手，逐步分析问题特征，再利用问题特征设计算法的思维过程，让读者理解问题特征分析、基本算法和算法设计与分析之间的关系，体会从无到有、精益求精的算法设计过程，培养创新意识和研究能力。
　　本书还配备了大量的习题，以期学生在实践过程中加深对算法设计与分析方法的理解并提高算法设计与分析的速度。部分习题来自参考文献，部分习题来自科研实践，还有部分习题来自多年教学实践的总结。作者希望学生在完成习题的过程中，首先能够确切地理解计算问题。部分习题专门为这一目的设置，只要理解了计算问题，适当修改已有的算法即可解决。此外，作者希望学生能够仔细、完备地阐明求解习题得到的算法以及对算法的分析。写出算法及其分析过程会让被忽略的难点或问题彻底暴露，这个过程还可以排除那些不相干的想法。算法设计和分析过程往往需要多次重复书写才能得到一个清晰、简洁的结果。比较好的做法是：获得算法及其分析之后将它放在一旁，提交之前再看看它是否仍然是完备的、令人信服的和易于理解的。书写算法并完成对算法的分析可以培养学生简洁、清晰、准确地表达自己的能力，而这恰恰是一项非常有用的技能。
　　在过去的几十年中，专家和学者们编著了许多与算法设计与分析相关的教材。这些著作给本书的编写提供了参考和借鉴，在这里向相关作者表示感谢。同时，也感谢哈尔滨工业大学多年来提供的教学和研究机会，并感谢学生、朋友和家人的鞭策及支持。
　　由于作者水平有限，书中不当之处在所难免，敬请读者批评指正。如果读者有任何建议或意见，可以发送电子邮件至luojizhou@hit.edu.cn。
作者
2014年6月

计算机\算法

本书是作者在多年从事算法设计与分析课程教学和研究的基础上编写而成的，系统地介绍了算法设计与分析的理论、方法和技术，包括分治算法、动态规划算法、贪心算法、最小值最大值方法、搜索策略、随机算法、近似算法和在线算法等算法设计技术，以及循环不变量方法、反例方法、平摊分析方法、概率分析方法、近似度分析方法和竞争度分析方法等算法分析技术。书中提供了大量算法设计与分析的实例，使得读者在阅读过程中能够清晰地理解概念、掌握思路、理清脉络，培养自身以算法设计和分析为手段，高效地解决问题的意识和能力。
本书特点
● 线索清晰，内容精炼。以算法设计与分析的基本方法为主线，每种方法均先介绍原理，再举若干典型算法设计实例说明方法的各个侧面，并舍弃了先修课程已经学过的算法，使得读者能够将更多的注意力放到掌握算法设计方法上。
● 讲解透彻，分析严谨。对每个算法，均力争展示算法设计的自然过程，即从问题的蛮力算法入手，严谨地分析和证明计算问题的特征，再利用问题的特征逐步得到问题的高效算法，最后对算法进行严谨的分析，这样做有利于培养读者的创新意识和研究能力。
● 由浅入深，结构灵活。对每章内容的安排均由易到难、由简到繁，逐渐深入，这有利于读者循序渐进地掌握各种算法设计方法的本质和难点，也有利于教师根据实际情况对较难、较深的内容进行取舍。

骆吉洲：暂无

前言
教学建议
第1章绪论
11算法在计算机科学体系中的地位
111计算机理论模型和计算问题的分类
112利用计算机求解问题
113计算机科学的知识体系
114算法是计算机科学的重要主题
115算法设计与分析的意义
12算法的概念
13算法分析
131算法正确性分析
132算法复杂度分析
14算法设计方法
习题
第2章数学基础
21复杂度函数的阶
211函数阶的定义
212函数阶的性质
22标准符号和通用函数
221flour函数和ceiling函数
222求和
23递归方程
231常系数线性递归方程
232非常系数线性递归方程
233生成函数
234分治算法递归方程
习题
第3章分治算法
31分治算法原理
32大整数乘法
33Strassen矩阵乘法
34快速傅里叶变换
35最邻近点问题
36平面点集的凸包
361求解凸包问题的蛮力算法
362GrahamScan算法
363凸包问题的分治算法
37基于剪枝搜索方法的分治算法
371剪枝搜索方法
372线性时间选择算法
373二元线性规划的线性时间算法
3741圆心问题的线性时间算法
习题
第4章动态规划算法
41动态规划原理
42最长公共子序列
43矩阵链乘法
4401背包问题
45最优二叉搜索树
46评注
习题
第5章贪心算法
51贪心算法的基本原理
52活动选择问题
53哈夫曼编码问题
54最小生成树问题
541Kruskal算法
542Prim算法
55贪心算法的理论基础
551拟阵
552加权拟阵上的贪心算法
56单位时间任务调度问题
习题
第6章平摊分析
61平摊分析方法
611聚集方法
612会计方法
613势能方法
62动态表性能的平摊分析
621动态表及其操作
622动态表的扩张
623动态表扩张和收缩
63斐波那契堆及其操作代价的平摊分析
631斐波那契堆
632斐波那契堆操作算法及其平摊代价
633斐波那契堆最大度的上界
64并查集及其操作代价的平摊分析
641并査集及其基本性质
642阿克曼函数及其逆函数
643并查集上操作序列代价的平摊分析
习题
第7章最大值最小值方法
71网络流
711最大流问题和最小割问题
712FordFulkerson算法
713EdmondsKarp算法
714推送复标算法
715复标前置算法
72匹配算法
721匹配与覆盖
722最大二分匹配
723一般图上的最大匹配
724最大权值二分匹配
725稳定二分匹配
习题
第8章树的搜索策略
81问题解空间的树表示
82典型搜索策略
821广度优先搜索
822深度优先搜索
823爬山法
824最佳优先搜索
825分支限界法
83分支限界法的应用
831用分支限界法求解人员分配问题
832用分支限界法求解旅行商问题
833用分支限界法求解01背包问题
84A*算法及其应用
85博弈树和αβ剪枝
851博弈树及其评估
852αβ剪枝
习题
第9章随机算法
91随机算法概述
92数值随机算法
921随机投点法
922平均值方法
93随机选择和拉斯维加斯算法
931随机选择算法
932拉斯维加斯算法
94快速排序和舍伍德算法
941快速排序算法描述
942快速排序算法的性能分析
943随机快速排序算法
944舍伍德算法
95素数测试和蒙特卡罗算法
951素数测试随机算法
952蒙特卡罗算法
96最小割随机算法
习题
第10章近似算法
101近似算法的性能分析
102基于组合优化的近似算法
1021顶点覆盖问题的近似算法
1022装箱问题的近似算法
1023最短并行调度问题的近似算法
1024旅行商问题的近似算法
1025子集和问题的完全多项式近似模式
103基于贪心思想的近似算法
1031集合覆盖问题的近似算法
1032不相交路径问题的近似算法
104基于局部搜索的近似算法
1041最大割问题的近似算法
1042设施定位问题的近似算法
105基于动态规划的近似算法
105101背包问题的完全多项式近似模式
1052装箱问题的多项式近似模式
106基于线性规划的近似算法
1061线性规划及对偶定理
1062加权集合覆盖问题的线性规划表示
1063舍入法及随机舍入法
1064对偶拟合方法
1065原偶模式
107不可近似性
1071鸿沟归约与不可近似性
1072PCP定理
1073MAX3SAT问题的不可近似性
1074α,β鸿沟归约与不可近似性
习题
第11章在线算法
111在线算法与竞争度分析
112欧几里得最小生成树问题的在线算法
1121在线贪心算法
1122在线随机算法
113凸包在线算法
114线性链表在线更新算法
115最短并行调度在线算法
习题
参考文献