算法設計與分析(第5版·微課視頻版)

呂國英，山西大學教授，全國優秀教師，民進會員，畢業於山東大學。長期從事算法設計與分析、程序設計語言和數據結構等方面的研究和教學工作。主持的“算法設計課程群教學研究與改革實踐”榮獲山西省政府教學成果一等獎。2010-2020年指導學生獲“全國軟件專業人才設計與開發大賽”一等獎5項，2015年指導學生獲“華北五省（市、自治區）及港澳臺大學生計算機應用大賽”一等獎。曾主持山西省研究生教育改革研究課題“算法設計與分析課程碩本銜接教學研究”。

 

目錄

 

 

 

第1篇引入篇

 

第1章算法概述

1.1用電腦求解問題與算法

 

1.1.1用電腦求解問題的步驟

 

1.1.2算法及其要素和特性

 

1.1.3算法設計及基本方法

 

1.2算法設計步驟及描述

 

1.2.1算法描述簡介

 

1.2.2本書算法描述約定

 

1.2.3一個簡單問題的求解過程

 

1.2.4從算法到程序

 

1.3現代常用算法概覽

 

1.3.1數據壓縮及算法

 

1.3.2數據加密及算法

 

1.3.3人工智能及算法

 

1.3.4並行計算及算法

 

1.3.5搜索引擎及算法

 

第2章算法分析基礎

 

2.1算法分析體系及計量

 

2.1.1算法分析的評價體系

 

2.1.2算法的時間復雜性

 

2.1.3算法的空間復雜性

 

2.2算法分析實例

 

2.2.1非遞歸算法分析

 

2.2.2遞歸算法分析

 

2.3提高算法質量

 

2.4問題復雜度及分類

 

2.4.1問題時間復雜度的上界和下界

 

2.4.2NP完全問題

 

 

第2篇基礎篇

 

第3章算法基本工具和優化技巧

3.1循環與遞歸

 

3.1.1循環設計要點

 

3.1.2遞歸設計要點

 

3.1.3遞歸與循環的比較

 

3.2算法與數據結構

 

3.2.1原始信息與處理結果的對應存儲

 

3.2.2數組使信息有序化

 

3.2.3數組記錄狀態信息

 

3.2.4高精度數據存儲及運算

 

3.2.5構造趣味矩陣

 

3.2.6一維與二維的選擇

 

 

 

 

 

3.3優化算法的基本技巧

 

3.3.1算術運算的妙用

 

3.3.2標志量的妙用

 

3.3.3信息數字化

 

3.4優化算法的數學模型

 

3.4.1楊輝三角形的應用

 

3.4.2最大公約數的應用

 

3.4.3公倍數的應用

 

3.4.4斐波那契數列的應用

 

3.4.5特徵根求解遞推方程

 

習題

 

第3篇核心篇

 

第4章基本的算法策略

4.1迭代算法

 

4.1.1遞推算法

 

4.1.2倒推算法

 

4.1.3用迭代算法解方程

 

4.2蠻力法

 

4.2.1枚舉法

 

4.2.2其他範例

 

4.3分而治之算法

 

4.3.1分而治之算法框架

 

4.3.2典型二分法

 

4.3.3二分法的相似問題

 

4.3.4二分法的獨立問題

 

4.3.5二分法的歸並問題

 

4.3.6非等分分治

 

4.4貪婪算法

 

4.4.1可絕對貪婪問題

 

4.4.2相對或近似貪婪問題

 

4.4.3貪婪算法設計框架

 

4.5動態規劃

 

4.5.1認識動態規劃

 

4.5.2動態規劃算法設計框架

 

4.5.3突出階段性的動態規劃應用

 

4.5.4突出遞推的動態規劃應用

 

4.6算法策略間的比較

 

4.6.1不同算法策略特點小結

 

4.6.2算法策略間的關聯

 

4.6.3算法策略側重的問題類型

 

習題

 

第5章圖的搜索算法

 

5.1圖搜索概述

 

5.1.1圖及其術語

 

5.1.2圖搜索及其術語

 

5.2廣度優先搜索

 

5.2.1廣度優先算法框架

 

5.2.2廣度優先搜索的應用

 

5.3深度優先搜索

 

5.3.1深度優先算法框架

 

5.3.2深度優先搜索的應用

 

5.4回溯法

 

5.4.1認識回溯法

 

5.4.2回溯算法框架

 

5.4.3應用1——基本的回溯搜索

 

5.4.4應用2——排列及排列樹的回溯搜索

 

5.4.5應用3——最優化問題的回溯搜索

 

5.5分支限界法

 

5.5.1分支搜索算法

 

5.5.2分支限界搜索算法

 

5.5.3算法框架

 

 

5.6圖的搜索算法小結

 

習題

 

第4篇應用篇

 

第6章概率算法

6.1概述

 

6.2統計模擬

 

6.2.1數值計算方法

 

6.2.2考慮正確概率的算法——蒙特卡羅算法

 

6.3隨機序列提高算法的平均復雜度——舍伍德算法

 

6.4隨機生成答案並檢測答案正確性——拉斯維加斯算法

 

第7章自然語言處理及算法

 

7.1中文分詞中的算法

 

7.1.1中文分詞概述

 

7.1.2基於詞表的分詞算法

 

7.2詞性標註中的算法

 

7.2.1詞性標註概述

 

7.2.2基於轉換的錯誤驅動的詞性標註方法

 

7.3命名實體識別中的算法

 

7.3.1命名實體識別概述

 

7.3.2基於CRF的命名實體識別算法

 

7.4中文信息處理中的語義應用

 

7.4.1語義知識概述

 

7.4.2語義知識庫介紹

 

7.4.3語義應用步驟

 

習題

 

第8章算法設計實踐

 

8.1循環賽日程表(4種)

 

8.2求3個數的最小公倍數(4種)

 

8.3猴子選大王(4種)

 

8.4最大子段和問題(5種)

 

8.5背包問題(11種)

 

8.5.1與利潤無關的背包問題

 

8.5.2與利潤有關的背包問題

 

8.6主元素問題（5種）

 

附錄“算法設計與分析”課程設計大綱

 

參考文獻