算法导论第四版

  |  

摘要: 算法导论第四版介绍

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


introduction-to-algorithm-4th

本文介绍一下算法导论第四版。本书的第四版是去年出来的,新增了机器学习算法等内容,还是有不少更新的。本书完整下载链接如下

在 mit 的网站上有一些随书资源:mit资源链接,比较有用的事一些代码,以及部分题目解答。

本文首先简要介绍一下这本书,然后对目录做一些记录,以后有需要的时候可以快速找到需要的章节。

简介

《Introduction to Algorithm》是由 Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford Stein 编写,MIT 出版的一本介绍、分析当代计算机算法的图书。一般用四位作者姓的首字母组成的 CLRS 代表此书。

本书将严谨性和全面性融为一体,深入讨论各类算法,并着力使这些算法的设计分析能为各个层次的读者接受。

全书各章自成体系,可以作为独立的学习单元。算法以伪代码的形式描述;说明和解释力求浅显易懂,不失深度和数学严谨性。

本书在 2012 年出了第三版,当时第3版的主要变化为:

  • 新增了van Emde Boas树和多线程算法,并且将矩阵基础移至附录。
  • 修订了递归式(现在称为“分治策略”)那一章的内容,更广泛地覆盖分治法。
  • 移除两章很少讲授的内容:二项堆和排序网络。
  • 修订了动态规划和贪心算法相关内容。
  • 流网络相关材料现在基于边上的全部流。
  • 由于关于矩阵基础和Strassen算法的材料移到了其他章,矩阵运算这一章的内容所占篇幅更小。
  • 修改了对Knuth-Morris-Pratt字符串匹配算法的讨论。
  • 新增100道练习和28道思考题,还更新并补充了参考文献。

第四版中被删除的第三版内容

删除内容这里做个记录,需要的时候可以看第三版。

  • Fibonacci heaps(第3版 $19)
  • van Emde Boas trees(第3版 $20)
  • computational geometry(第3版 $33)
  • the maximum-subarray problem
  • implementing pointers and objects(第3版 $10-3)
  • perfect hashing(第3版 $11-5)
  • randomly built binary search trees(第3版 $12-4)
  • matroids(第3版 $15-4)
  • push-relabel algorithms for maximum flow(第3版 $26-4)
  • the iterative fast Fourier transform method
  • the details of the simplex algorithm for linear programming(第3版 $29-3)
  • integer factorization

第四版中更新的第三版内容和新增内容

一些新增或更新内容这里也做个汇总

  • Chap3:
    • giving an overview of asymptotic notation before delving into the formal definitions
  • Chap4:
    • underwent substantial changes to improve its mathematical foundation and make it more robust and intuitive.
    • The notion of an algorithmic recurrence was introduced
    • the topic of ignoring floors and ceilings in recurrences was addressed more rigorously
    • The second case of the master theorem incorporates polylogarithmic factors
    • a rigorous proof of a “continuous” version of the master theorem is now provided
    • present the powerful and general Akra-Bazzi method (without proof).
  • Chap9:
    • The deterministic order-statistic algorithm is slightly different
    • the analyses of both the randomized and deterministic order-statistic algorithms have been revamped.
  • Chap10:
    • In addition to stacks and queues, discusses ways to store arrays and matrices.
  • Chap11:
    • a modern treatment of hash functions
    • linear probing as an efficient method for resolving collisions when the underlying hardware implements caching to favor local searches.
  • Chap15:
    • To offline caching into a full section.
  • Chap16:
    • a more intuitive explanation of the potential functions to analyze table doubling and halving.
  • Chap17:
    • augmenting data structures was relocated from Part III to Part V.
  • Chap25:
    • a new chapter about matchings in bipartite graphs.
    • It presents algorithms to find a matching of maximum cardinality
    • solve the stable-marriage problem
    • find a maximum-weight matching (known as the “assignment problem”).
  • Chap26:
    • task-parallel computing has been updated with modern terminology
  • Chap27:
    • online algorithms, is another new chapter.
    • In an online algorithm, the input arrives over time, rather than being available in its entirety at the start of the algorithm.
    • describes several examples of online algorithms
      • determining how long to wait for an elevator before taking the stairs
      • maintaining a linked list via the move-to-front heuristic
      • evaluating replacement policies for caches.
  • Chap29:
    • we removed the detailed presentation of the simplex algorithm, as it was math heavy without really conveying many algorithmic ideas.
    • The chapter now focuses on the key aspect of how to model problems as linear programs
    • the essential duality property of linear programming.
  • chap32:
    • adds structure of suffix arrays.
  • Chap33:
    • machine learning, is the third new chapter.
    • several basic methods used in machine learning:
      • clustering to group similar items together
      • weighted-majority algorithms
      • gradient descent to find the minimizer of a function
  • Chap34:
    • summarizes strategies for reductions to show that problems are NP-hard.
  • Chap35:
    • polynomial-time The proof of the approximation algorithm for the set-covering problem.

Part1 基础知识

  • 1 算法在计算中的作用
  • 2 算法基础
    • 2.1 插入排序
    • 2.2 分析算法
    • 2.3 设计算法
      • 2.3.1 分治法
      • 2.3.2 分析分治算法
  • 3 函数的增长
    • 3.1 渐近记号
    • 3.2 标准记号与常用函数
  • 4 分治策略
    • 4.1 最大子数组问题
    • 4.2 矩阵乘法的Strasse
    • 4.3 用代入法求解递归式
    • 4.4 用递归树方法求解递归式
    • 4.5 用主方法求解递归式
    • 4.6 证明主定理
      • 4.6.1 对b的幂证明主定理
      • 4.6.2 向下取整和向
    • (新增)4.7 Akra-Bazzi recurrences
  • 5 概率分析和随机算法
    • 5.1 雇用问题
    • 5.2 指示器随机变量
    • 5.3 随机算法
    • 5.4 概率分析和指示器随机变量的进一步使用
      • 5.4.1 生日悖论
      • 5.4.2 球与箱子
      • 5.4.3 特征序列
      • 5.4.4 在线雇用问题

Part2 排序和顺序统计量

  • 6 堆排序
    • 6.1 堆
    • 6.2 维护堆的性质
    • 6.3 建堆
    • 6.4 堆排序算法
    • 6.5 优先队列
  • 7 快速排序
    • 7.1 快速排序的描述
    • 7.2 快速排序的性能
    • 7.3 快速排序的随机化
    • 7.4 快速排序分析
      • 7.4.1 最坏情况分析
      • 7.4.2 期望运行时间
  • 8 线性时间排序
    • 8.1 排序算法的下界
    • 8.2 计数排序
    • 8.3 基数排序
    • 8.4 桶排序
  • 9 中位数和顺序统计量
    • 9.1 最小值和最大值
    • 9.2 期望为线性时间的选择算法
    • 9.3 最坏情况为线性时间的选择算法

Part3 数据结构

  • 10 基本数据结构
    • 10.1 栈和队列
    • 10.2 链表
    • 10.3 有根树的表示
  • 11 散列表
    • 11.1 直接寻址表
    • 11.2 散列表
    • 11.3 散列函数
      • 11.3.1 除法散列法
      • 11.3.2 乘法散列法
      • 11.3.3 全域散列法
    • 11.4 开放寻址法
    • (新增)11.5 Practical considerations
  • 12 二叉搜索树
    • 12.1 什么是二叉搜索树
    • 12.2 查询二叉搜索树
    • 12.3 插入和删除
  • 13 红黑树
    • 13.1 红黑树的性质
    • 13.2 旋转
    • 13.3 插入
    • 13.4 删除

Part4 高级设计和分析技术

  • 14 动态规划
    • 14.1 钢条切割
    • 14.2 矩阵链乘法
    • 14.3 动态规划原理
    • 14.4 最长公共子序列
    • 14.5 最优二叉搜索树
  • 15 贪心算法
    • 15.1 活动选择问题
    • 15.2 贪心算法原理
    • 15.3 赫夫曼编码
    • (新增)15.4 Offline caching
  • 16 摊还分析
    • 16.1 聚合分析
    • 16.2 核算法
    • 16.3 势能法
    • 16.4 动态表
      • 16.4.1 表扩张
      • 16.4.2 表扩张和收缩

Part5 高级数据结构

  • 17 数据结构的扩张
    • 17.1 动态顺序统计
    • 17.2 如何扩张数据结构
    • 17.3 区间树
  • 18 B树
    • 18.1 B树的定义
    • 18.2 B树上的基本操作
    • 18.3 从B树中删除关键字
  • 19 用于不相交集合的数据结构
    • 19.1 不相交集合的操作
    • 19.2 不相交集合的链表表示
    • 19.3 不相交集合森林
    • 19.4 带路径压缩的按秩合并的分析

Part6 图算法

  • 20 基本的图算法
    • 20.1 图的表示
    • 20.2 广度优先搜索
    • 20.3 深度优先搜索
    • 20.4 拓扑排序
    • 20.5 强连通分量
  • 21 最小生成树
    • 21.1 最小生成树的形成
    • 21.2 Kruskal算法和Prim算法
  • 22 单源最短路径
    • 22.1 Bellman-Ford算法
    • 22.2 有向无环图中的单源最短路径问题
    • 22.3 Dijkstra算法
    • 22.4 差分约束和最短路径
    • 22.5 最短路径性质的证明
  • 23 所有结点对的最短路径问题
    • 23.1 最短路径和矩阵乘法
    • 23.2 Floyd-Warshall算法
    • 23.3 用于稀疏图的Johnson算法
  • 24 最大流
    • 24.1 流网络
    • 24.2 Ford-Fulkerson方法
    • 24.3 最大二分匹配
  • (新增)25 Matchings in Bipartite Graphs
    • (新增)25.1 Maximum bipartite matching (revisited)
    • (新增)25.2 The stable-marriage problem
    • (新增)25.3 The Hungarian algorithm for the assignment problem

Part7 专题

  • 26 多线程算法
    • 26.1 动态多线程基础
    • 26.2 多线程矩阵乘法
    • 26.3 多线程归并排序
  • (新增)27 Online Algorithms
    • (新增)27.1 Waiting for an elevator
    • (新增)27.2 Maintaining a search list
    • (新增)27.3 Online caching
  • 28 矩阵运算
    • 28.1 求解线性方程组
    • 28.2 矩阵求逆
    • 28.3 对称正定矩阵和最小二乘逼近
  • 29 线性规划
    • 29.1 标准型和松弛型
    • 29.2 将问题表达为线性规划
    • 29.3 对偶性
  • 30 多项式与快速傅里叶变换
    • 30.1 多项式的表示
    • 30.2 DFT与FFT
    • 30.3 高效FFT实现
  • 31 数论算法
    • 31.1 基础数论概念
    • 31.2 最大公约数
    • 31.3 模运算
    • 31.4 求解模线性方程
    • 31.5 中国余数定理
    • 31.6 元素的幂
    • 31.7 RSA公钥加密系统
    • 31.8 素数的测试
    • (新增)31.9 整数的因子分解
  • 32 字符串匹配
    • 32.1 朴素字符串匹配算法
    • 32.2 Rabin-Karp算法
    • 32.3 利用有限自动机进行字符串匹配
    • 32.4 Knuth-Morris-Pratt算法
    • (新增)32.5 Suffix arrays
  • (新增)33 Machine-Learning Algorithms
    • (新增)33.1 Clustering
    • (新增)33.2 Multiplicative-weights algorithms
    • (新增)33.3 Gradient descent
  • 34 NP完全性
    • 34.1 多项式时间
    • 34.2 多项式时间的验证
    • 34.3 NP完全性与可归约性
    • 34.4 NP完全性的证明
    • 34.5 NP完全问题
      • 34.5.1 团问题
      • 34.5.2 顶点覆盖问题
      • 34.5.3 哈密顿回路问题
      • 34.5.4 旅行商问题
      • 34.5.5 子集和问题
  • 35 近似算法
    • 35.1 顶点覆盖问题
    • 35.2 旅行商问题
      • 35.2.1 满足三角不等式的旅行商问题
      • 35.2.2 一般旅行商问题
    • 35.3 集合覆盖问题
    • 35.4 随机化和线性规划
    • 35.5 子集和问题

Part8 附录:数学基础知识

  • A 求和
    • A.1 求和公式及其性质
    • A.2 确定求和时间的界
  • B 集合等离散数学内容
    • B.1 集合
    • B.2 关系
    • B.3 函数
    • B.4 图
    • B.5 树
      • B.5.1 自由树
      • B.5.2 有根树和有序树
      • B.5.3 二叉树和位置树
  • C 计数与概率
    • C.1 计数
    • C.2 概率
    • C.3 离散随机变量
    • C.4 几何分布与二项分布
    • C.5 二项分布的尾部
  • D 矩阵
    • D.1 矩阵与矩阵运算
    • D.2 矩阵基本性质

Share