Python 演算法教學手冊 Python算法教程

<內容簡介>

 

Python是一種面向對象、解釋型計算機程序設計語言，其應用領域非常廣泛，包括數據分析、自然語言處理、機器學習、科學計算以及推薦系統構建等。

本書用Python語言來講解算法的分析和設計。本書主要關註經典的算法，但同時會為讀者理解基本算法問題和解決問題打下很好的基礎。全書共11章。分別介紹了樹、圖、計數問題、歸納遞歸、遍歷、分解合併、貪心算法、複雜依賴、Dijkstra算法、匹配切割問題以及困難問題及其稀釋等內容。本書在每一章結束的時候均有練習題和參考資料，這為讀者的自我檢查以及進一步學習提供了較多的便利。在全書的結尾，給出了練習題的提示，方便讀者進行查漏補缺。

本書概念和知識點講解清晰，語言簡潔。本書適合對Python算法感興趣的初中級用戶閱讀和自學，也適合高等院校的計算機系學生作為參考教材來閱讀。

 

<作者簡介>

 

Magnus Lie Hetland是一位經驗豐富的Python程序員，他自上世紀90年代以來就一直在使用該語言。同時，他還是挪威科技大學的副教授，有著數十年的算法教學經驗，是《Beginning Python》 一書作者。

 

<目錄>

 

第1章引言1 

1．1這是一本怎麼樣的書2 

1．1．1本書將主要涉及以下內容3 

1．1．2本書還將簡單或部分涉及

以下內容3 

1．1． 3本書不會涉足以下領域3 

1．2為什麼要讀這本書3 

1．3一些準備工作5 

1．4本書主要內容5 

1．5本章小結7 

1．6如果您感興趣7 

1． 7練習題7 

1．8參考資料8 

第2章基礎知識9 

2．1計算領域中一些核心理念9 

2．2漸近記法11 

2．2．1我看不懂這些希臘文12 

2．2 ．2交通規則14 

2．2．3讓我們拿漸近性問題

練練吧16 

2．2．4三種重要情況19 

2．2．5實證式算法評估20 

2．3圖與樹的實現24 

2．3．1鄰接列表及其類似結構26 

2．3．2鄰接矩陣29 

2．3．3樹的實現32 

2．3．4多種表示法35 

2．4請提防黑盒子36 

2．4 ．1隱性平方級操作37 

2．4．2浮點運算的麻煩38 

2．5本章小結41 

2．6如果您感興趣42 

2．7練習題42 

2．8參考資料43 

第3章計數初步46 

3．1求和式的含義46 

3．1．1更多希臘字母47 

3．1．2求和式的運用47 

3．2兩種賽制的故事48 

3．2．1握手問題48 

3． 2．2龜兔賽跑50 

3．3子集與排列組合54 

3．4遞歸與遞歸式56 

3．4．1手動推導57 

3．4．2幾個重要例子59 

3．4．3猜測與檢驗62 

3．4．4主定理：一刀切式的

解決方案65 

3．5這一切究竟是什麼呢67 

3．6本章小結69 

3．7如果您感興趣69 

3．8練習題70 

3．9參考資料71 

第4章歸納、遞歸及歸簡72 

4．1哦，這其實很簡單73 

4．2一而再，再而三74 

4．3魔鏡，魔鏡77 

4．4基於歸納法（與遞歸法）的設計82 

4．4．1尋找最大排列82 

4．4．2明星問題86 

4．4．3拓撲排序問題88 

4．5更強的假設條件92 

4．6不變式與正確性94 

4．7鬆弛法與逐步完善94 

4．8歸簡法+換位法=困難度證明95 

4．9一些解決問題的建議97 

4．10本章小結98 

4．11如果您感興趣98 

4．12練習題99 

4．13參考資料101 

第5章遍歷：算法學中的萬能鑰匙102 

5．1公園漫步109 

5．1．1不允許出現環路109 

5．1．2停止循環遍歷的方式110 

5 ．2繼續深入111 

5．3無限迷宮與最短（不加權）

路徑問題115 

5．4強連通分量120 

5．5本章小結123 

5．6如果您感興趣123 

5．7練習題124 

5．8參考資料125 

第6章分解、合併、解決126 

6．1樹狀問題，即平衡問題126 

6．2經典分治算法129 

6．3折半搜索129 

6．3．1搜索樹的遍歷及其剪枝132 

6．3．2選取算法135 

6．4折半排序137 

排序操作究竟可以有多快140 

6．5三個額外實例140 

6．5．1最近點對問題141 

6．5．2凸包問題142 

6 ．5．3最大切片問題144 

6．6樹的平衡與再平衡145 

6．7本章小結151 

6．8如果您感興趣152 

6．9練習題152 

6．10參考資料153 

第7章貪心有理嗎？請證明154 

7．1步步為營，萬無一失154 

7．2背包問題158 

7．2．1分數背包問題158 

7．2．2整數背包問題159 

7．3哈夫曼算法159 

7．3．1具體算法160 

7．3．2首次貪心選擇162 

7．3．3走完剩餘部分163 

7．3．4最優化歸併164 

7．4最小生成樹問題165 

7．4．1最短邊問題166 

7．4．2其餘部分的相關情況167 

7．4．3 Kruskal算法168 

7．4．4 Prim算法170 

7．5貪心不是問題，問題是

何時貪心173 

7．5．1堅持做到最好173 

7．5． 2盡量做到完美174 

7．5．3做好安全措施175 

7．6本章小結177 

7．7如果您感興趣178 

7．8練習題178 

7．9參考資料179 

第8章複雜依賴及其內存化180 

8．1不要重複自己181 

8．2有向無環圖中的最短路徑問題187 

8．3最長遞增子序列問題190 

8．4序列比對問題193 

8．5背包問題的反擊196 

8．6序列的二元分割199 

8．7本章小結202 

8．8如果您感興趣203 

8．9練習題203 

8．10參考資料204 

第9章Dijkstra及其朋友們

從A到B的旅程206 

9．1擴展知識207 

9．2鬆弛可“瘋狂” 208 

9．3找到隱藏的DAG圖213 

9．4多對多問題216 

9．5 “牽強”的子問題218 

9．6中途相遇220 

9． 7把握未來走向223 

9．8本章小結226 

9．9如果您感興趣227 

9．10練習題228 

9．11參考資料228 

第10章匹配、切割及流量229 

10．1二分圖匹配230 

10．2不相交的路徑233 

10．3最大流問題236 

10．4最小切割集問題240 

10．5最小成本的流及賦值問題241 

10．6一些應用243 

10．7本章小結247 

10．8如果您感興趣247 

10．9練習題248 

10．10參考資料249 

第11章困難問題及其（有限）稀釋250 

11．1重提歸簡251 

11．2不待在肯薩斯州了254 

11．3但目前，我們還是得回

到肯薩斯州255 

11．4我們應從何處開始？

前往何處呢259 

11．5怪物樂園264 

11．5．1背包的返回264 

11．5．2分團與著色266 

11．5．3路徑與環路269 

11．6當困難來臨的時候，聰明人

就開始犯錯272 

11．7盡力尋找解決方案275 

11．8這些故事告訴我們277 

11．9本章小結279 

11．10如果您感興趣279 

11．11練習題280 

11．12參考資料281 

附錄A猛踩油門！令Python加速282 

附錄B一些著名問題與算法286 

問題部分286 

算法與數據結構部分289 

附錄C圖論基礎295 

附錄D習題提示301 

第1章301 

第2章301 

第3章303 

第4章304 

第5章307 

第6章308 

第7章310 

第8章312 

第9章313 

第10章314 

第11章315