2022年《算法概论》读书笔记及读后感

1、算法概论读书笔记 12 计转 1 12130907 李酉辰 第 0 章 本章较为简短,没有深化系统地涉及某些内容；主要以 Fibonacci 数列的例子,让我体 会了递归和递推思想的差别；针对 Fibonacci 数列例子直接递归解法中涉及的重复运算,优 化出递推方式, 呈现了摸索问题中自顶向下与自底向上的不同摸索角度可能产生较大的算法 效率差别,同时模糊表达记忆化搜寻的思想；另外本章较为详细介绍了大 O 复杂度度量标 准； 第 1 章 本章以 RSA 算法为例,细致深化争辩 RSA 算法涉及的相关数论学问,诸如取模运模下的四就运算与逆元概念,取模幂运算,素性检测； 了 算, 在素性检测部分有

2、经典的欧几里德算法, 以极高的概率保证素性检测有效性； 扩展欧几里德算法, 同时引入随机化算法概念, 通过本章的学习,我对过去不曾深化考虑或者说真正考虑的基础性运算有了更深的理 解；之前对乘除运算复杂度总是在以单元操作的概念下以 O（ 1）带过,以后会更加细致地 考虑乘除等基本运算的复杂度；另外,本章以 RSA 为案例,系统地呈现了针对某一问题, 如何从基础性学问入手,一步一步学习案例所需基础学问,并将其整合从而解决案例； 素性检测与素因子分解, 两个看似相去不远的问题, 其复杂性天差地别的现实, 从一般 角度让人们想到的是类似问题的解决难度可能差别很大仅此而已,而 RSA 算法呈现了如何 深

3、化的多想一步,利用这种情形设计出文静的解决方案；这思想很值得我借鉴与利用； 第 2 章 本章介绍分治算法思想,提及分治, 信任每一个学习算法的人都不会生疏,经典的 算 法导论中就已合并排序为例在开篇不久就引入分治概念；本书介绍分治的角度与众不同, 不似导论中总是介绍比较显而易见的可以分治的案例；本书列举了矩阵相乘, 快速傅立 叶变换等数学领域分治的应用案例, 在这些案例之中, 分治的应用许多情形下隐匿的较为深, 并非显而易见, 加大了分析难度； 但是更能让我感受到分治应用之广泛, 可能在学习本章之 前,许多类型的题目我不会想到去向分治的角度摸索, 由于不易看出, 但是本章给我的备忘 录上加了一

4、条： 永久不要忽视分治, 针对生疏题目, 不要轻易就拒绝掉往分治角度摸索的路 线；另外, 通过本章学习, 对于算法复杂度的评估以及依据递推式评估复杂度的才能有了很 大的提高； 第 3 章 学习到本章时, 发觉本章讲解部分只有 15 页,算上习题也不过 20 余页,大致翻看内容, 发觉讲解的是 DFS,便松了一口气,自认为作者真逗,一个 DFS 也用得着单独分出一章来述？岂不知市面上的绝大多数算法书, 就是将 DFS 作为搜寻或图, 树遍历部分的一小节表 叙 可是通过两遍的学习,最终体会到作者的用心良苦及自己过去对 达； DFS 熟识的肤浅； DFS 无论是递归形式,即使是用栈迭代实现都不太难；

5、但是其精髓我认为在于两方一是其在图论中对于连通性, 面, 有无环判定等性质判定的应用, 另一方面是在 DFS 中拜望顶的先, 后操作函数的实现；这两方面前者主要针对无向, 有向图的性质争辩,而后者的应用 点 领域可就不能一言概括了, 针对现实问题许多都可特地设计详细的先, 后操作函数神奇地利 用 DFS 解决；比较简洁而又具有代表性的例子是记录顶点 previsit 与 postvisit 数值应用,的 比如 postvisit 值最小的为汇点, 最大 这两个数值看似简洁但是结合图的特性可谓用处大大, 的为源点, 参考这两个值组成的区间的包含性来判定遍历过程中, 某节点是否为根到某一节 点路径

6、上的祖先节点等； 第 1 页,共 4 页另外细节部分, 拓扑排序和有向图的强连通重量分解思想的相像性争辩, 值得好好品尝； 做练习题过程中, 能体会到假如图模型建立好, 我能够反应到 DFS 针对问题的应用, 但是关 键难点在于依据题目描述如何联想到图模型, 但是这不是说看书能够看会的, 看来只有多做 题慢慢培养这种关联性思维了； 第 4 章 本章内容与上一章承接； 以 BFS 为媒介, 引出了图论中求解顶点的最短距离相关的一列算法,诸如 Dijikstra 算法, Bellman-Ford 算法等；由上一章我们知道, 系 DFS 的应用一般于连通重量, 结合先, 后序操作的算法设计； 而 B

7、FS 的应用一般集中于求解最优化或最短 在 离方面； 距 在做本章练习题过程中, 我更加体会到为什么自己之前看的算法书不少, 而提高却总是 很慢的缘由； 光看书的确是不够的, 每一本算法书都配以大量的习题的确是特别必要的； 也 许对于一本算法书, 你看了一遍两遍甚至三遍, 对于每一章的内容以及例题都已了然, 但是 没有经过大量题目的摸索解答过程, 根本谈不上把握； 如何算作把握了某一算法？许多人会 以把握其设计思想为由搪塞过去, 对于算法的细节往往忽视不谈； 自己过去也总是效仿这一 种做法,好像抠细节是愚蠢之人的做法, 其实不然；我当然不赞成一味深化细节, 但是我们 应当知道算法的某一步骤为何

8、这么设计（这往往是明显的） 新的一个节点 v,假如有 distu distv+lv,u 时,要更新 ,比如在 Dijikstra 中,当扩展到 u 的距离,一般人都不会不懂这个 操作的原理； 但是我们的摸索往往也在这一步停止了； 在做书中题目时, 我发觉有一类题目, 即到某一点的最短距离路径不唯独时,如何确定？摸索了很久,突然豁然开朗,这不就是 Dijikstra 算法中进行 distu 和 distv+lv,u 过程中,显现 distu = distv+lv,u 的情形么？单单 是对于一个比较符号的深化摸索, 我们便有了新的收成, 同时可以将原算法的应用领域扩展 一步；假如没有针对题目的摸索

9、, 会一个算法的精致； 又怎会对算法中一个比较符号的进行分析？又怎会真正体 BFS 作为可获得最优解的一种暴力搜寻算法,可以用于状态空间搜寻,在这一类应用 之 中,关键在于状态节点数据结构的设计,以及分析清楚下一步状态节点扩展所依靠的操作, 分析清楚这两点之后,便可以以 BFS 实现求同时应 解； 另外, 本章算法的应用领域的抽象建模过程较之第 3 章 DFS 部分较为简洁明用的灵敏性自然也不如 DFS；至此经典的暴力搜寻 白； DFS, BFS 部分已经终止； 第 5 章 本章重点介绍贪心算法； 贪心算法并非某一特定的算法, 而是一类算法或者说是一种算 法设计思路； 针对某一类中意贪心算法适

10、用的问题背景, 我们可以通过每一次都挑选当前最 优的策略获得最优解； 当然, 算法的难度并不在于算法实现, 于某一问题的证明,这也是唯独的难点之一； 本章重点介绍了贪心算法的经典范例最小生成树算法（ 而在于对于贪心算法是否适用 Kruskal与 Prim）,以及 Huffman 编码；另外,引入了数据结构并查集的介绍；内容较为简洁懂得,习题难度也不大； 第 6 章 本章内容为动态规划； 动态规划作为经典的一类算法设计策略, 始终以来都是各算法书 籍的重头戏；类似于贪心算法, 动态规划并不是某一种特定的算法,而是一种设计策略；在 算法导论 中,作者以多步决策引入了动态规划概念, 同时指出动态规划

11、适用的情形是问 题同时具有最优子结构和重叠子问题的情形； 而在 算法概论一书中, 作者并没有接受这 种传统的介绍方式；本书接受了一种结构上的抽象,针对动态规划问题的状态对应于节点, 而挑选转换对应为边,将动态规划抽象为 描述了动态规划； DAG（有向无环图） ,从而结合求解最短路径思想 动态规划的一般实现形式：记忆化搜寻（自顶向下） ,递推式自底向上； 第 2 页,共 4 页本章主要范例为 LIS,LCS,背包（单副本,多副本） ,矩阵相乘,最短路及 TSP 以及立集； 类似之前的章节, 在习题中设置了许多范例的变种问题, 通过完成习题使我对这些范 独 例的懂得更为深刻；总而言之,动态规划题目

12、千变万化,唯有大量练习培养思维敏捷性； 第 7 章 本章介绍线性规划；由于之前已经学习过线性规划相关专著,所以这部分过得比较快； 总而言之, 这部分内容具有理论上的意义, 并且做为数学规划其他内容时必需把握的； 但是, 事实上, 实际问题中建模后, 很难显现这种简洁的线性规划模式； 所以这一章算是数学规划 的一个引言； 第 8 章 本章介绍 NP-完全问题；主要要明确以下概念：能够在多项式时间判定某一个解答是否 是原问题的正确解,就是 NP 问题；而在 NP 问题中,如仍能在多项式时间内求解出解,就 是 P 问题；如在 NP 问题中,如不确定能否在多项式时间内求出原问题的解,就是 NP-完全

13、问题；换言之, NP 问题包含 P 问题与 NP-完全问题；所以,许多人不求严谨,老是说 NP 问 题与 P 问题求解难度不同, 实就是想说 NP-完全问题与 P 问题求解难度不同； 另外需要明确, 全部的 NP-完全问题都可以规约为同一个问题； 第 9 章 本章承接上一章,针对 NP-完全问题的难度,提出了一系列不同的解决策略；主要归结 为以下几种：智能化搜寻（剪枝,分支定界） ,近似算法（退而求其次,不要求确定求得最 优解）,局部搜寻中的启示式方法 （涉及进化算法和模拟退火） ；本章算是起到抛砖引玉的作 用,如何求解 NP-完全问题始终是争辩的热点, 由最初的启示式搜寻, 包括书中提及的剪

14、枝, 分支定界, 以及后来的 A* 算法, 到后来逐步进展的进化算法, 虽然始终没有冲破 NP-完全与 P 的界限, 但是从不同的摸索角度都为我们供应了不少在实践中具有实际应用意义的解决方 法；正如书中所说,判定一个问题为 NP-完全问题并不是宣判了该问题的死刑；在 NP-完全 问题的诸多风格的求解方式中,我们更能体会到算法设计领域的博大精深； 第 10 章 本章讲解量子算法,虽然懂得不深,但是本章着实让我大开眼界； 算法概论读书心得 算法概论 的前身是加州高校伯克利分校和加州高校圣迭戈分校本科生的算法课讲义； 经过十年课堂教学的检验, 这本书以其生动好玩的风格, 细心挑选的内容和精确严谨的表

15、达 得到了我的宠爱； 算法是运算机科学的灵魂, 其复杂与抽象让许多初学者望而却步； 这本书 最显著的特点是生动的写作风格： 作者贯穿一条主线, 以讲故事的形式将概念娓娓道来, 非 常易于懂得和消化； 当然, 这本书没有走另一个极端：过分强调语言的生动而忽视了严谨性；恰恰相反,这 本书完善地兼顾了两者；在书中我们看不到许多数学式子,取而代之的是精确的文字表达； 作者认为 这种用严谨的语言代替数学形式化的方法更简洁被同学接受, 由于读者需要知道 的往往是蕴涵在数学公式或者程序代码背后的思想,而正是这些思想促成了精致的算法； 这本书不是一本字典式的百科全书, 而是一本教科书； 因此, 作者合理地挑选了讲授的 内容,用 300 多页的篇幅使同学对这门博大精深的科学有了深刻的熟识 本书共分为四个部 分；其中第一部分是引论和算术运算（这是算法的起源） ,包括复杂度分析,算术运算, 最大公约数,素性测试,散列函数,快速乘法,递归,合并排序,矩阵乘法,仍有在一般算 法书中不多见的 RsA 公钥体制和快速傅里叶变换等内 其次部分是 “传统” 的算法和数据 容； 结构（树和图） ：图的搜寻,连通性,最短路径,最小生成树,堆,赫夫曼编码等；在第三 第 3 页,共 4 页部分里, 作者用新颖的方式介绍了两种强大的运