2022年《算法概論》讀書(shū)筆記及讀后感

1、算法概論讀書(shū)筆記 12 計(jì)轉(zhuǎn) 1 12130907 李酉辰 第 0 章 本章較為簡(jiǎn)短,沒(méi)有深化系統(tǒng)地涉及某些內(nèi)容；主要以 Fibonacci 數(shù)列的例子,讓我體 會(huì)了遞歸和遞推思想的差別；針對(duì) Fibonacci 數(shù)列例子直接遞歸解法中涉及的重復(fù)運(yùn)算,優(yōu) 化出遞推方式, 呈現(xiàn)了摸索問(wèn)題中自頂向下與自底向上的不同摸索角度可能產(chǎn)生較大的算法 效率差別,同時(shí)模糊表達(dá)記憶化搜尋的思想；另外本章較為詳細(xì)介紹了大 O 復(fù)雜度度量標(biāo) 準(zhǔn)； 第 1 章 本章以 RSA 算法為例,細(xì)致深化爭(zhēng)辯 RSA 算法涉及的相關(guān)數(shù)論學(xué)問(wèn),諸如取模運(yùn)模下的四就運(yùn)算與逆元概念,取模冪運(yùn)算,素性檢測(cè)； 了 算, 在素性檢測(cè)部分有

2、經(jīng)典的歐幾里德算法, 以極高的概率保證素性檢測(cè)有效性； 擴(kuò)展歐幾里德算法, 同時(shí)引入隨機(jī)化算法概念, 通過(guò)本章的學(xué)習(xí),我對(duì)過(guò)去不曾深化考慮或者說(shuō)真正考慮的基礎(chǔ)性運(yùn)算有了更深的理 解；之前對(duì)乘除運(yùn)算復(fù)雜度總是在以單元操作的概念下以 O（ 1）帶過(guò),以后會(huì)更加細(xì)致地 考慮乘除等基本運(yùn)算的復(fù)雜度；另外,本章以 RSA 為案例,系統(tǒng)地呈現(xiàn)了針對(duì)某一問(wèn)題, 如何從基礎(chǔ)性學(xué)問(wèn)入手,一步一步學(xué)習(xí)案例所需基礎(chǔ)學(xué)問(wèn),并將其整合從而解決案例； 素性檢測(cè)與素因子分解, 兩個(gè)看似相去不遠(yuǎn)的問(wèn)題, 其復(fù)雜性天差地別的現(xiàn)實(shí), 從一般 角度讓人們想到的是類似問(wèn)題的解決難度可能差別很大僅此而已,而 RSA 算法呈現(xiàn)了如何 深

3、化的多想一步,利用這種情形設(shè)計(jì)出文靜的解決方案；這思想很值得我借鑒與利用； 第 2 章 本章介紹分治算法思想,提及分治, 信任每一個(gè)學(xué)習(xí)算法的人都不會(huì)生疏,經(jīng)典的 算 法導(dǎo)論中就已合并排序?yàn)槔陂_(kāi)篇不久就引入分治概念；本書(shū)介紹分治的角度與眾不同, 不似導(dǎo)論中總是介紹比較顯而易見(jiàn)的可以分治的案例；本書(shū)列舉了矩陣相乘, 快速傅立 葉變換等數(shù)學(xué)領(lǐng)域分治的應(yīng)用案例, 在這些案例之中, 分治的應(yīng)用許多情形下隱匿的較為深, 并非顯而易見(jiàn), 加大了分析難度； 但是更能讓我感受到分治應(yīng)用之廣泛, 可能在學(xué)習(xí)本章之 前,許多類型的題目我不會(huì)想到去向分治的角度摸索, 由于不易看出, 但是本章給我的備忘 錄上加了一

4、條： 永久不要忽視分治, 針對(duì)生疏題目, 不要輕易就拒絕掉往分治角度摸索的路 線；另外, 通過(guò)本章學(xué)習(xí), 對(duì)于算法復(fù)雜度的評(píng)估以及依據(jù)遞推式評(píng)估復(fù)雜度的才能有了很 大的提高； 第 3 章 學(xué)習(xí)到本章時(shí), 發(fā)覺(jué)本章講解部分只有 15 頁(yè),算上習(xí)題也不過(guò) 20 余頁(yè),大致翻看內(nèi)容, 發(fā)覺(jué)講解的是 DFS,便松了一口氣,自認(rèn)為作者真逗,一個(gè) DFS 也用得著單獨(dú)分出一章來(lái)述？豈不知市面上的絕大多數(shù)算法書(shū), 就是將 DFS 作為搜尋或圖, 樹(shù)遍歷部分的一小節(jié)表 敘 可是通過(guò)兩遍的學(xué)習(xí),最終體會(huì)到作者的用心良苦及自己過(guò)去對(duì) 達(dá)； DFS 熟識(shí)的膚淺； DFS 無(wú)論是遞歸形式,即使是用棧迭代實(shí)現(xiàn)都不太難；

5、但是其精髓我認(rèn)為在于兩方一是其在圖論中對(duì)于連通性, 面, 有無(wú)環(huán)判定等性質(zhì)判定的應(yīng)用, 另一方面是在 DFS 中拜望頂?shù)南? 后操作函數(shù)的實(shí)現(xiàn)；這兩方面前者主要針對(duì)無(wú)向, 有向圖的性質(zhì)爭(zhēng)辯,而后者的應(yīng)用 點(diǎn) 領(lǐng)域可就不能一言概括了, 針對(duì)現(xiàn)實(shí)問(wèn)題許多都可特地設(shè)計(jì)詳細(xì)的先, 后操作函數(shù)神奇地利 用 DFS 解決；比較簡(jiǎn)潔而又具有代表性的例子是記錄頂點(diǎn) previsit 與 postvisit 數(shù)值應(yīng)用,的 比如 postvisit 值最小的為匯點(diǎn), 最大 這兩個(gè)數(shù)值看似簡(jiǎn)潔但是結(jié)合圖的特性可謂用處大大, 的為源點(diǎn), 參考這兩個(gè)值組成的區(qū)間的包含性來(lái)判定遍歷過(guò)程中, 某節(jié)點(diǎn)是否為根到某一節(jié) 點(diǎn)路徑

6、上的祖先節(jié)點(diǎn)等； 第 1 頁(yè),共 4 頁(yè)另外細(xì)節(jié)部分, 拓?fù)渑判蚝陀邢驁D的強(qiáng)連通重量分解思想的相像性爭(zhēng)辯, 值得好好品嘗； 做練習(xí)題過(guò)程中, 能體會(huì)到假如圖模型建立好, 我能夠反應(yīng)到 DFS 針對(duì)問(wèn)題的應(yīng)用, 但是關(guān) 鍵難點(diǎn)在于依據(jù)題目描述如何聯(lián)想到圖模型, 但是這不是說(shuō)看書(shū)能夠看會(huì)的, 看來(lái)只有多做 題慢慢培養(yǎng)這種關(guān)聯(lián)性思維了； 第 4 章 本章內(nèi)容與上一章承接； 以 BFS 為媒介, 引出了圖論中求解頂點(diǎn)的最短距離相關(guān)的一列算法,諸如 Dijikstra 算法, Bellman-Ford 算法等；由上一章我們知道, 系 DFS 的應(yīng)用一般于連通重量, 結(jié)合先, 后序操作的算法設(shè)計(jì)； 而 B

7、FS 的應(yīng)用一般集中于求解最優(yōu)化或最短 在 離方面； 距 在做本章練習(xí)題過(guò)程中, 我更加體會(huì)到為什么自己之前看的算法書(shū)不少, 而提高卻總是 很慢的緣由； 光看書(shū)的確是不夠的, 每一本算法書(shū)都配以大量的習(xí)題的確是特別必要的； 也 許對(duì)于一本算法書(shū), 你看了一遍兩遍甚至三遍, 對(duì)于每一章的內(nèi)容以及例題都已了然, 但是 沒(méi)有經(jīng)過(guò)大量題目的摸索解答過(guò)程, 根本談不上把握； 如何算作把握了某一算法？許多人會(huì) 以把握其設(shè)計(jì)思想為由搪塞過(guò)去, 對(duì)于算法的細(xì)節(jié)往往忽視不談； 自己過(guò)去也總是效仿這一 種做法,好像摳細(xì)節(jié)是愚蠢之人的做法, 其實(shí)不然；我當(dāng)然不贊成一味深化細(xì)節(jié), 但是我們 應(yīng)當(dāng)知道算法的某一步驟為何

8、這么設(shè)計(jì)（這往往是明顯的） 新的一個(gè)節(jié)點(diǎn) v,假如有 distu distv+lv,u 時(shí),要更新 ,比如在 Dijikstra 中,當(dāng)擴(kuò)展到 u 的距離,一般人都不會(huì)不懂這個(gè) 操作的原理； 但是我們的摸索往往也在這一步停止了； 在做書(shū)中題目時(shí), 我發(fā)覺(jué)有一類題目, 即到某一點(diǎn)的最短距離路徑不唯獨(dú)時(shí),如何確定？摸索了很久,突然豁然開(kāi)朗,這不就是 Dijikstra 算法中進(jìn)行 distu 和 distv+lv,u 過(guò)程中,顯現(xiàn) distu = distv+lv,u 的情形么？單單 是對(duì)于一個(gè)比較符號(hào)的深化摸索, 我們便有了新的收成, 同時(shí)可以將原算法的應(yīng)用領(lǐng)域擴(kuò)展 一步；假如沒(méi)有針對(duì)題目的摸索

9、, 會(huì)一個(gè)算法的精致； 又怎會(huì)對(duì)算法中一個(gè)比較符號(hào)的進(jìn)行分析？又怎會(huì)真正體 BFS 作為可獲得最優(yōu)解的一種暴力搜尋算法,可以用于狀態(tài)空間搜尋,在這一類應(yīng)用 之 中,關(guān)鍵在于狀態(tài)節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì),以及分析清楚下一步狀態(tài)節(jié)點(diǎn)擴(kuò)展所依靠的操作, 分析清楚這兩點(diǎn)之后,便可以以 BFS 實(shí)現(xiàn)求同時(shí)應(yīng) 解； 另外, 本章算法的應(yīng)用領(lǐng)域的抽象建模過(guò)程較之第 3 章 DFS 部分較為簡(jiǎn)潔明用的靈敏性自然也不如 DFS；至此經(jīng)典的暴力搜尋 白； DFS, BFS 部分已經(jīng)終止； 第 5 章 本章重點(diǎn)介紹貪心算法； 貪心算法并非某一特定的算法, 而是一類算法或者說(shuō)是一種算 法設(shè)計(jì)思路； 針對(duì)某一類中意貪心算法適

10、用的問(wèn)題背景, 我們可以通過(guò)每一次都挑選當(dāng)前最 優(yōu)的策略獲得最優(yōu)解； 當(dāng)然, 算法的難度并不在于算法實(shí)現(xiàn), 于某一問(wèn)題的證明,這也是唯獨(dú)的難點(diǎn)之一； 本章重點(diǎn)介紹了貪心算法的經(jīng)典范例最小生成樹(shù)算法（ 而在于對(duì)于貪心算法是否適用 Kruskal與 Prim）,以及 Huffman 編碼；另外,引入了數(shù)據(jù)結(jié)構(gòu)并查集的介紹；內(nèi)容較為簡(jiǎn)潔懂得,習(xí)題難度也不大； 第 6 章 本章內(nèi)容為動(dòng)態(tài)規(guī)劃； 動(dòng)態(tài)規(guī)劃作為經(jīng)典的一類算法設(shè)計(jì)策略, 始終以來(lái)都是各算法書(shū) 籍的重頭戲；類似于貪心算法, 動(dòng)態(tài)規(guī)劃并不是某一種特定的算法,而是一種設(shè)計(jì)策略；在 算法導(dǎo)論 中,作者以多步?jīng)Q策引入了動(dòng)態(tài)規(guī)劃概念, 同時(shí)指出動(dòng)態(tài)規(guī)劃

11、適用的情形是問(wèn) 題同時(shí)具有最優(yōu)子結(jié)構(gòu)和重疊子問(wèn)題的情形； 而在 算法概論一書(shū)中, 作者并沒(méi)有接受這 種傳統(tǒng)的介紹方式；本書(shū)接受了一種結(jié)構(gòu)上的抽象,針對(duì)動(dòng)態(tài)規(guī)劃問(wèn)題的狀態(tài)對(duì)應(yīng)于節(jié)點(diǎn), 而挑選轉(zhuǎn)換對(duì)應(yīng)為邊,將動(dòng)態(tài)規(guī)劃抽象為 描述了動(dòng)態(tài)規(guī)劃； DAG（有向無(wú)環(huán)圖） ,從而結(jié)合求解最短路徑思想 動(dòng)態(tài)規(guī)劃的一般實(shí)現(xiàn)形式：記憶化搜尋（自頂向下） ,遞推式自底向上； 第 2 頁(yè),共 4 頁(yè)本章主要范例為 LIS,LCS,背包（單副本,多副本） ,矩陣相乘,最短路及 TSP 以及立集； 類似之前的章節(jié), 在習(xí)題中設(shè)置了許多范例的變種問(wèn)題, 通過(guò)完成習(xí)題使我對(duì)這些范 獨(dú) 例的懂得更為深刻；總而言之,動(dòng)態(tài)規(guī)劃題目

12、千變?nèi)f化,唯有大量練習(xí)培養(yǎng)思維敏捷性； 第 7 章 本章介紹線性規(guī)劃；由于之前已經(jīng)學(xué)習(xí)過(guò)線性規(guī)劃相關(guān)專著,所以這部分過(guò)得比較快； 總而言之, 這部分內(nèi)容具有理論上的意義, 并且做為數(shù)學(xué)規(guī)劃其他內(nèi)容時(shí)必需把握的； 但是, 事實(shí)上, 實(shí)際問(wèn)題中建模后, 很難顯現(xiàn)這種簡(jiǎn)潔的線性規(guī)劃模式； 所以這一章算是數(shù)學(xué)規(guī)劃 的一個(gè)引言； 第 8 章 本章介紹 NP-完全問(wèn)題；主要要明確以下概念：能夠在多項(xiàng)式時(shí)間判定某一個(gè)解答是否 是原問(wèn)題的正確解,就是 NP 問(wèn)題；而在 NP 問(wèn)題中,如仍能在多項(xiàng)式時(shí)間內(nèi)求解出解,就 是 P 問(wèn)題；如在 NP 問(wèn)題中,如不確定能否在多項(xiàng)式時(shí)間內(nèi)求出原問(wèn)題的解,就是 NP-完全

13、問(wèn)題；換言之, NP 問(wèn)題包含 P 問(wèn)題與 NP-完全問(wèn)題；所以,許多人不求嚴(yán)謹(jǐn),老是說(shuō) NP 問(wèn) 題與 P 問(wèn)題求解難度不同, 實(shí)就是想說(shuō) NP-完全問(wèn)題與 P 問(wèn)題求解難度不同； 另外需要明確, 全部的 NP-完全問(wèn)題都可以規(guī)約為同一個(gè)問(wèn)題； 第 9 章 本章承接上一章,針對(duì) NP-完全問(wèn)題的難度,提出了一系列不同的解決策略；主要?dú)w結(jié) 為以下幾種：智能化搜尋（剪枝,分支定界） ,近似算法（退而求其次,不要求確定求得最 優(yōu)解）,局部搜尋中的啟示式方法 （涉及進(jìn)化算法和模擬退火） ；本章算是起到拋磚引玉的作 用,如何求解 NP-完全問(wèn)題始終是爭(zhēng)辯的熱點(diǎn), 由最初的啟示式搜尋, 包括書(shū)中提及的剪

14、枝, 分支定界, 以及后來(lái)的 A* 算法, 到后來(lái)逐步進(jìn)展的進(jìn)化算法, 雖然始終沒(méi)有沖破 NP-完全與 P 的界限, 但是從不同的摸索角度都為我們供應(yīng)了不少在實(shí)踐中具有實(shí)際應(yīng)用意義的解決方 法；正如書(shū)中所說(shuō),判定一個(gè)問(wèn)題為 NP-完全問(wèn)題并不是宣判了該問(wèn)題的死刑；在 NP-完全 問(wèn)題的諸多風(fēng)格的求解方式中,我們更能體會(huì)到算法設(shè)計(jì)領(lǐng)域的博大精深； 第 10 章 本章講解量子算法,雖然懂得不深,但是本章著實(shí)讓我大開(kāi)眼界； 算法概論讀書(shū)心得 算法概論 的前身是加州高校伯克利分校和加州高校圣迭戈分校本科生的算法課講義； 經(jīng)過(guò)十年課堂教學(xué)的檢驗(yàn), 這本書(shū)以其生動(dòng)好玩的風(fēng)格, 細(xì)心挑選的內(nèi)容和精確嚴(yán)謹(jǐn)?shù)谋?/p>

15、達(dá) 得到了我的寵愛(ài)； 算法是運(yùn)算機(jī)科學(xué)的靈魂, 其復(fù)雜與抽象讓許多初學(xué)者望而卻步； 這本書(shū) 最顯著的特點(diǎn)是生動(dòng)的寫(xiě)作風(fēng)格： 作者貫穿一條主線, 以講故事的形式將概念娓娓道來(lái), 非 常易于懂得和消化； 當(dāng)然, 這本書(shū)沒(méi)有走另一個(gè)極端：過(guò)分強(qiáng)調(diào)語(yǔ)言的生動(dòng)而忽視了嚴(yán)謹(jǐn)性；恰恰相反,這 本書(shū)完善地兼顧了兩者；在書(shū)中我們看不到許多數(shù)學(xué)式子,取而代之的是精確的文字表達(dá)； 作者認(rèn)為 這種用嚴(yán)謹(jǐn)?shù)恼Z(yǔ)言代替數(shù)學(xué)形式化的方法更簡(jiǎn)潔被同學(xué)接受, 由于讀者需要知道 的往往是蘊(yùn)涵在數(shù)學(xué)公式或者程序代碼背后的思想,而正是這些思想促成了精致的算法； 這本書(shū)不是一本字典式的百科全書(shū), 而是一本教科書(shū)； 因此, 作者合理地挑選了講授的 內(nèi)容,用 300 多頁(yè)的篇幅使同學(xué)對(duì)這門博大精深的科學(xué)有了深刻的熟識(shí) 本書(shū)共分為四個(gè)部 分；其中第一部分是引論和算術(shù)運(yùn)算（這是算法的起源） ,包括復(fù)雜度分析,算術(shù)運(yùn)算, 最大公約數(shù),素性測(cè)試,散列函數(shù),快速乘法,遞歸,合并排序,矩陣乘法,仍有在一般算 法書(shū)中不多見(jiàn)的 RsA 公鑰體制和快速傅里葉變換等內(nèi) 其次部分是 “傳統(tǒng)” 的算法和數(shù)據(jù) 容； 結(jié)構(gòu)（樹(shù)和圖） ：圖的搜尋,連通性,最短路徑,最小生成樹(shù),堆,赫夫曼編碼等；在第三 第 3 頁(yè),共 4 頁(yè)部分里, 作者用新穎的方式介紹了兩種強(qiáng)大的運(yùn)