本书以算法设计与分析的理论、方法和技术为主线,系统地介绍分治方法、动态规划方法和贪心方法、最小值最大值方法、搜索方法、随机算法、近似算法和在线算法等算法设计技术,和循环不变量方法、反例方法、平摊分析方法、概率分析方法、近似度分析方法和竞争度分析方法等算法分析技术。在介绍这些理论、方法和技术的同时,还介绍计算几何、图论、元素选取、最大流、顶点覆盖和匹配等领域的一些基本算法。全书强调问题特征分析、基本算法和算法设计技术的有机结合构成典型的算法设计过程。书中配置了大量习题,以期读者能够在实践过程中加深对算法设计与分析方法的理解并提高算法设计与分析的速度。
本书讲解透彻、分析严谨、深入浅出地讲解算法设计与分析的理论、方法和技术,并提供大量算法设计与分析的实例,使得读者在阅读过程中能够清晰地掌握思路、理清脉络,培养自身以算法设计和分析为手段时间高效、空间高效地解决问题的意识和能力。
本书可以作为计算机相关专业本科生、研究生教材,也可供从事算法设计与分析工作的工程技术人员参考。
本书是作者在多年从事算法设计与分析课程教学和研究的基础上编写而成,系统地介绍了算法设计与分析的理论、方法和技术,包括分治算法、动态规划算法、贪心算法、最小值最大值方法、搜索策略、随机算法、近似算法和在线算法等算法设计技术,以及循环不变量方法、反例方法、平摊分析方法、概率分析方法、近似度分析方法和竞争度分析方法等算法分析技术。书中提供了大量算法设计与分析的实例,使得读者在阅读过程中能够清晰地理解概念、理清脉络,培养自身以算法设计和分析为手段、高效地解决问题的意识和能力。
本书特色:
线索清晰,内容精炼。以算法设计与分析的基本方法为主线,每种方法均先介绍原理,再列举若干典型算法设计实例说明方法的各个侧面,并舍弃了先修课程已经学过的算法,使得读者能够将更多的注意力转移到掌握算法设计方法上。
讲解透彻,分析严谨。对每个算法,均力争展示算法设计的自然过程,即从问题的蛮力算法入手,严谨地分析和证明计算问题的特征,再利用问题的特征逐步得到问题的高效算法,最后对算法进行严谨的分析,这样做有利于培养读者的创新意识和研究能力。
由浅入深,结构灵活。对每章内容的安排均由易到难、由简到繁,逐渐深入,这有利于读者循序渐进地掌握各种算法设计方法的本质和难点,也有利于教师根据实际情况对较难、较深的内容进行取舍。
算法设计与分析是计算机科学永恒不变的主题,是计算机专业的核心课程之一。这门课程旨在培养学生以算法设计和分析为手段,时间高效、空间高效地解决问题的意识和能力,以及简洁、清晰、准确表达算法及其分析过程的技能,提高学生的算法修养,培养创新意识,培育研究能力。通过这门课程的学习,学生可以理解算法和算法复杂度的概念,掌握评判算法优劣的标准,较系统地掌握分治算法、动态规划算法、贪心算法、搜索策略、随机算法、近似算法和在线算法等算法设计技术,掌握循环不变量方法、反例方法、平摊分析方法、概率分析方法、近似度分析方法和竞争度分析方法等算法分析技术,为进一步深造打下良好的算法基础。
为实现上述培养目标,作者结合自己多年从事算法设计与分析课程教学和研究的经验,精心地选取和组织了这门课程的教学内容。全书以算法设计与分析方法为主线,分为11章,着重强调对算法设计与分析基本技术的掌握,舍弃了在数据结构、集合论与图论等先修课程中学生已经掌握的基本算法,包括绝大部分排序算法、字符串匹配算法和基本图论算法。第1章是绪论,建立算法的概念并阐述算法设计和分析的目的和意义。第2章是数学基础,总结全书算法分析过程中使用的主要数学工具和数学结论,便于在后续章节中着重于算法设计和分析的过程,尽量避免复杂的数学推导过程。第3~5章介绍算法设计与分析的基本技术,包括分治算法、动态规划算法和贪心算法。第6章介绍平摊分析技术及其应用。第7章介绍最大值最小值方法,讨论网络流和匹配等图论问题的算法。第8~10章介绍难解问题的三种处理方法,包括树的搜索策略、随机算法、近似算法。第11章介绍在线算法和竞争度分析。
对每一种算法设计与分析技术,均先通过简单的例子介绍技术的原理和要点,再通过一系列的例子阐述使用该技术时需要注意的各个侧面。例如,第3章的一系列算法设计实例着重强调利用分治算法求解问题时划分阶段、递归求解阶段和合并阶段需要注意的问题。第4章的一系列算法设计实例除阐明动态规划的要点之外,还展示了各种典型的优化子结构,等等。
本书还特别强调算法设计过程依赖于对问题的分析和对问题特征的把握,即算法设计通常从求解问题的蛮力算法开始,逐步观察和分析问题的特征并结合恰当的算法设计技术,逐渐设计出高效的算法。每章均包含了这样的算法设计实例,以引导读者建立从蛮力法入手,逐步分析问题特征,再利用问题特征设计算法的思维过程,让读者理解问题特征分析、基本算法和算法设计与分析之间的关系,体会从无到有、精益求精的算法设计过程,培养创新意识和研究能力。
本书还配备了大量的习题,以期学生在实践过程中加深对算法设计与分析方法的理解并提高算法设计与分析的速度。部分习题来自参考文献,部分习题来自科研实践,还有部分习题来自多年教学实践的总结。作者希望学生在完成习题的过程中,首先能够确切地理解计算问题。部分习题专门为这一目的设置,只要理解了计算问题,适当修改已有的算法即可解决。此外,作者希望学生能够仔细、完备地阐明求解习题得到的算法以及对算法的分析。写出算法及其分析过程会让被忽略的难点或问题彻底暴露,这个过程还可以排除那些不相干的想法。算法设计和分析过程往往需要多次重复书写才能得到一个清晰、简洁的结果。比较好的做法是:获得算法及其分析之后将它放在一旁,提交之前再看看它是否仍然是完备的、令人信服的和易于理解的。书写算法并完成对算法的分析可以培养学生简洁、清晰、准确地表达自己的能力,而这恰恰是一项非常有用的技能。
在过去的几十年中,专家和学者们编著了许多与算法设计与分析相关的教材。这些著作给本书的编写提供了参考和借鉴,在这里向相关作者表示感谢。同时,也感谢哈尔滨工业大学多年来提供的教学和研究机会,并感谢学生、朋友和家人的鞭策及支持。
由于作者水平有限,书中不当之处在所难免,敬请读者批评指正。如果读者有任何建议或意见,可以发送电子邮件至luojizhou@hit.edu.cn。
作者
2014年6月
计算机\算法
本书是作者在多年从事算法设计与分析课程教学和研究的基础上编写而成的,系统地介绍了算法设计与分析的理论、方法和技术,包括分治算法、动态规划算法、贪心算法、最小值最大值方法、搜索策略、随机算法、近似算法和在线算法等算法设计技术,以及循环不变量方法、反例方法、平摊分析方法、概率分析方法、近似度分析方法和竞争度分析方法等算法分析技术。书中提供了大量算法设计与分析的实例,使得读者在阅读过程中能够清晰地理解概念、掌握思路、理清脉络,培养自身以算法设计和分析为手段,高效地解决问题的意识和能力。
本书特点
● 线索清晰,内容精炼。以算法设计与分析的基本方法为主线,每种方法均先介绍原理,再举若干典型算法设计实例说明方法的各个侧面,并舍弃了先修课程已经学过的算法,使得读者能够将更多的注意力放到掌握算法设计方法上。
● 讲解透彻,分析严谨。对每个算法,均力争展示算法设计的自然过程,即从问题的蛮力算法入手,严谨地分析和证明计算问题的特征,再利用问题的特征逐步得到问题的高效算法,最后对算法进行严谨的分析,这样做有利于培养读者的创新意识和研究能力。
● 由浅入深,结构灵活。对每章内容的安排均由易到难、由简到繁,逐渐深入,这有利于读者循序渐进地掌握各种算法设计方法的本质和难点,也有利于教师根据实际情况对较难、较深的内容进行取舍。
骆吉洲:暂无
前言
教学建议
第1章绪论
11算法在计算机科学体系中的地位
111计算机理论模型和计算问题的分类
112利用计算机求解问题
113计算机科学的知识体系
114算法是计算机科学的重要主题
115算法设计与分析的意义
12算法的概念
13算法分析
131算法正确性分析
132算法复杂度分析
14算法设计方法
习题
第2章数学基础
21复杂度函数的阶
211函数阶的定义
212函数阶的性质
22标准符号和通用函数
221flour函数和ceiling函数
222求和
23递归方程
231常系数线性递归方程
232非常系数线性递归方程
233生成函数
234分治算法递归方程
习题
第3章分治算法
31分治算法原理
32大整数乘法
33Strassen矩阵乘法
34快速傅里叶变换
35最邻近点问题
36平面点集的凸包
361求解凸包问题的蛮力算法
362GrahamScan算法
363凸包问题的分治算法
37基于剪枝搜索方法的分治算法
371剪枝搜索方法
372线性时间选择算法
373二元线性规划的线性时间算法
3741圆心问题的线性时间算法
习题
第4章动态规划算法
41动态规划原理
42最长公共子序列
43矩阵链乘法
4401背包问题
45最优二叉搜索树
46评注
习题
第5章贪心算法
51贪心算法的基本原理
52活动选择问题
53哈夫曼编码问题
54最小生成树问题
541Kruskal算法
542Prim算法
55贪心算法的理论基础
551拟阵
552加权拟阵上的贪心算法
56单位时间任务调度问题
习题
第6章平摊分析
61平摊分析方法
611聚集方法
612会计方法
613势能方法
62动态表性能的平摊分析
621动态表及其操作
622动态表的扩张
623动态表扩张和收缩
63斐波那契堆及其操作代价的平摊分析
631斐波那契堆
632斐波那契堆操作算法及其平摊代价
633斐波那契堆最大度的上界
64并查集及其操作代价的平摊分析
641并査集及其基本性质
642阿克曼函数及其逆函数
643并查集上操作序列代价的平摊分析
习题
第7章最大值最小值方法
71网络流
711最大流问题和最小割问题
712FordFulkerson算法
713EdmondsKarp算法
714推送复标算法
715复标前置算法
72匹配算法
721匹配与覆盖
722最大二分匹配
723一般图上的最大匹配
724最大权值二分匹配
725稳定二分匹配
习题
第8章树的搜索策略
81问题解空间的树表示
82典型搜索策略
821广度优先搜索
822深度优先搜索
823爬山法
824最佳优先搜索
825分支限界法
83分支限界法的应用
831用分支限界法求解人员分配问题
832用分支限界法求解旅行商问题
833用分支限界法求解01背包问题
84A*算法及其应用
85博弈树和αβ剪枝
851博弈树及其评估
852αβ剪枝
习题
第9章随机算法
91随机算法概述
92数值随机算法
921随机投点法
922平均值方法
93随机选择和拉斯维加斯算法
931随机选择算法
932拉斯维加斯算法
94快速排序和舍伍德算法
941快速排序算法描述
942快速排序算法的性能分析
943随机快速排序算法
944舍伍德算法
95素数测试和蒙特卡罗算法
951素数测试随机算法
952蒙特卡罗算法
96最小割随机算法
习题
第10章近似算法
101近似算法的性能分析
102基于组合优化的近似算法
1021顶点覆盖问题的近似算法
1022装箱问题的近似算法
1023最短并行调度问题的近似算法
1024旅行商问题的近似算法
1025子集和问题的完全多项式近似模式
103基于贪心思想的近似算法
1031集合覆盖问题的近似算法
1032不相交路径问题的近似算法
104基于局部搜索的近似算法
1041最大割问题的近似算法
1042设施定位问题的近似算法
105基于动态规划的近似算法
105101背包问题的完全多项式近似模式
1052装箱问题的多项式近似模式
106基于线性规划的近似算法
1061线性规划及对偶定理
1062加权集合覆盖问题的线性规划表示
1063舍入法及随机舍入法
1064对偶拟合方法
1065原偶模式
107不可近似性
1071鸿沟归约与不可近似性
1072PCP定理
1073MAX3SAT问题的不可近似性
1074α,β鸿沟归约与不可近似性
习题
第11章在线算法
111在线算法与竞争度分析
112欧几里得最小生成树问题的在线算法
1121在线贪心算法
1122在线随机算法
113凸包在线算法
114线性链表在线更新算法
115最短并行调度在线算法
习题
参考文献