算法基础：打开算法之门（双色版）

    《算法导论》作者托马斯 H. 科尔曼面向大众读者的算法著作    理解计算机科学中关键算法的简明读本，帮助您开启算法之门    你想知道你的GPS是如何在几秒钟内从看起来无数多条可能路径中找到到达目的地的快捷路径的吗？当你在网上购物时，你的信用卡账号是如何被保护的呢？答案均是算法。本书是关于计算机算法基础的指南。在本书中，作者展示了计算机如何通过算法解决问题。

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

托马斯·H. 科尔曼（Thomas H. Cormen）
达特茅斯学院计算机科学系荣休教授，2009年7月到2015年7月期间担任达特茅斯学院计算机科学系主任。他是《算法导论》的合著者之一。目前的研究兴趣包括算法工程、并行计算、具有高延迟的加速计算。他分别于1993年、1986年获得麻省理工学院电子工程和计算机科学博士、硕士学位，师从查尔斯· E. 雷瑟尔森教授。由于在计算机教育领域的突出贡献，科尔曼教授荣获2009年ACM杰出教员奖。

目  录

译者序
前言

第1章  什么是算法以及为什么应该关注算法  / 1
  1.1  正确性  / 2
  1.2  资源利用  / 4
  1.3  针对非计算机专业人士的计算机算法  / 6
  1.4  针对计算机专业人士的计算机算法  / 7
  1.5  拓展阅读  / 9

第2章  如何描述和评估计算机算法  / 11
  2.1  如何描述计算机算法  / 11
  2.2  如何描述运行时间  / 19
  2.3  循环不变式  / 24
  2.4  递归  / 26
  2.5  拓展阅读  / 28

第3章  排序算法和查找算法  / 29
  3.1  二分查找  / 32
  3.2  选择排序  / 37
  3.3  插入排序  / 41
  3.4  归并排序  / 46
  3.5  快速排序  / 56
  3.6  小结  / 65
  3.7  拓展阅读  / 68

第4章  排序算法的下界和如何超越下界  / 69
  4.1  基于排序的规则  / 70
  4.2  基于比较排序的下界  / 71
  4.3  使用计数排序超越下界  / 72
  4.4  基数排序  / 79
  4.5  拓展阅读  / 81

第5章  有向无环图  / 82
  5.1  有向无环图  / 85
  5.2  拓扑排序  / 86
  5.3  如何表示有向图  / 90
  5.4  拓扑排序的运行时间  / 92
  5.5  PERT图表中的关键路径  / 92
  5.6  有向无环图中的最短路径  / 97
  5.7  拓展阅读  / 102

第6章  最短路径  / 103
  6.1  Dijkstra算法  / 105
  6.2  BellmanFord算法  / 117
  6.3  FloydWarshall算法  / 123
  6.4  拓展阅读  / 133

第7章  字符串算法  / 134
  7.1  最长公共子序列  / 135
  7.2  字符串转换  / 141
  7.3  字符串匹配  / 151
  7.4  拓展阅读  / 159

第8章  密码学基础  / 160
  8.1  简单替代密码  / 161
  8.2  对称密钥加密  / 163
  8.3  公钥加密  / 167
  8.4  RSA加密系统  / 170
  8.5  混合加密系统  / 180
  8.6  计算随机数  / 181
  8.7  拓展阅读  / 182

第9章  数据压缩  / 183
  9.1  赫夫曼编码  / 185
  9.2  传真机  / 193
  9.3  LZW压缩  / 194
  9.4  拓展阅读  / 206

第10章  难？问题  / 207
  10.1  棕卡车问题  / 207
  10.2  P、NP和NP完全类  / 212
  10.3  可判定问题和归约  / 214
  10.4  主问题  / 218
  10.5  NP完全问题例析  / 220
  10.6  总体策略  / 238
  10.7  前景  / 241
  10.8  不可判定问题  / 244
  10.9  小结  / 246
  10.10  拓展阅读  / 247

参考文献  / 248
索引  / 250