算法基础 打开算法之门pdf

《算法导论》作者托马斯 H. 科尔曼面向大众读者的算法著作

理解计算机科学中关键算法的简明读本，帮助您开启算法之门

你想知道你的GPS是如何在几秒钟内从看起来无数多条可能路径中找到到达目的地的快捷路径的吗？当你在网上购物时，你的信用卡账号是如何被保护的呢？答案均是算法。本书是关于计算机算法基础的指南。在本书中，作者展示了计算机如何通过算法解决问题。

读者将学习到什么是计算机算法，如何描述计算机算法，以及如何评估计算机算法。读者还将学习到在计算机中查找信息的简单方法；在计算机中将信息按照某个预定的顺序重排（“排序”）；如何解决那些在计算机中能使用一种被称为“图”的数学结构来建模的基本问题（可用于对道路网建模，针对任务间的依赖建模，以及金融套利交易建模）；如何解决关于字符串（例如DNA结构）的问题；密码学的基本原理；数据压缩的基本原理；甚至那些至今还没有人得出如何借助计算机在一段合理的时间内求解的问题。

算法基础 打开算法之门 内容简介

读者将理解什么是计算机算法，如何描述它们，以及如何来评估它们。这些计算机算法将提供：利用计算机搜索信息的简单方式；解决各种排序问题的方法；利用有向无环图和短路径法来解决基本问题的方法（可用于建模公路网络，任务间的依赖以及金融关系；解决字符串（例如DNA结构）问题的方法；密码学背后的基本原理；数据压缩的基础知识；以及甚至一些没有人能够理解如何在计算机上用相当长的时间来解决的问题。

算法基础 打开算法之门 目录

Algorithms Unlocked

出版者的话

译者序

前言

第1章什么是算法以及为什么应该关注算法1

1.1正确性2

1.2资源利用3

1.3针对非计算机专业人士的计算机算法5

1.4针对计算机专业人士的计算机算法6

1.5拓展阅读7

第2章如何描述和评估计算机算法9

2.1如何描述计算机算法9

2.2如何描述运行时间16

2.3循环不变式19

2.4递归21

2.5拓展阅读23

第3章排序算法和查找算法24

3.1二分查找26

3.2选择排序31

3.3插入排序34

3.4归并排序38

3.5快速排序47

3.6小结55

3.7拓展阅读57

第4章排序算法的下界和如何超越下界58

4.1基于排序的规则58

4.2基于比较排序的下界59

4.3使用计数排序超越下界60

4.4基数排序66

4.5拓展阅读68

第5章有向无环图69

5.1有向无环图72

5.2拓扑排序72

5.3如何表示有向图76

5.4拓扑排序的运行时间77

5.5PERT图表中的关键路径78

5.6有向无环图中的最短路径82

5.7拓展阅读86

第6章最短路径87

6.1Dijkstra算法89

6.2BellmanFord算法98

6.3FloydWarshall算法103

6.4拓展阅读112

第7章字符串算法114

7.1最长公共子序列114

7.2字符串转换120

7.3字符串匹配128

7.4拓展阅读135

第8章密码学基础136

8.1简单替代密码137

8.2对称密钥加密138

8.3公钥加密142

8.4RSA加密系统144

8.5混合加密系统153

8.6计算随机数153

8.7拓展阅读154

第9章数据压缩156

9.1哈夫曼编码158

9.2传真机165

9.3LZW压缩166

9.4拓展阅读176

第10章难？问题177

10.1棕卡车问题177

10.2P、NP和NP完全类181

10.3可判定问题和归约183

10.4主问题186

10.5NP完全问题例析188

10.6总体策略203

10.7前景206

10.8不可判定问题208

10.9小结210

10.10拓展阅读211

参考文献212

索引214

算法基础 打开算法之门 精彩文摘

让我们从我经常被问到的一个问题开始：“什么是算法？”

一个常见的回答是，“完成一个任务所需的一系列步骤。”在日常生活中经常会碰到算法。刷牙的时候会执行一个算法：打开牙膏盖，拿出牙刷，持续执行挤牙膏操作直到足量的牙膏涂在你的牙刷上，盖上牙膏盖，将牙刷放到嘴的1/4处，上下移动牙刷N秒，等等。如果你必须乘通勤车去工作，乘通勤车也是一个算法。诸如此类。

但是本书是关于运行在计算机上的算法的，或者更概括地来讲，是关于运行在计算设备上的算法的。正如你日常所运行的算法会影响你每天的生活一样，在计算机上运行的算法也会影响你的生活。你使用过GPS来寻找旅行路线吗？它运行一种称为“最短路径”的算法以寻求路线。你在网上购买商品吗？那么你会使用（应该正在使用）一个运行加密算法的安全网站。当你在网上购买商品时，它们是由一个私营快递公司发货的吗？它使用算法将包裹分配给不同的卡车，然后确定每个司机发件的顺序。算法运行在各种设备上―在你的笔记本上，服务器上，智能手机上，嵌人式系统上〔例如你的车中，你的微波炉中，或者气候控制系统中）―无处不在！