算法設計與分析(2021年清華大學出版社出版的圖書)

《算法設計與分析》是2021年清華大學出版社出版的圖書。

基本介紹

• 書名：算法設計與分析
• 作者：王秋芬
• 出版社：清華大學出版社
• 出版時間：2021年2月1日
• 開本：16 開
• 裝幀：平裝
• ISBN：9787302570721

內容簡介

本書主講貪心算法、分治算法、動態規划算法、回溯算法、網路流、隨機化算法、近似算法，側重用具體實例圖解演示算法運行過程及python語言實現。本書特色：深入淺出地從問題分析，到數據結構選擇、算法設計、Python實戰，提供問題解決的全程式指導；提供實例構造、詳細圖解，帶領學習者直觀、形象地逐步運行算法，看到算法單步運行結果；提供算法的Python語言實現，讓算法在學習者心裡落地生根。本書適用於計算機、大數據等相關專業本科教材，以及從事計算機領域的教學、科研人員，ACM程式設計大賽的算法愛好者。

圖書目錄

目錄

第1章算法概述

1.1什麼是算法

1.2為什麼學習算法

1.3算法的描述方式

1.4算法設計的一般過程

1.5算法分析

1.5.1算法分析的概念

1.5.2時間複雜度和空間複雜度

1.5.3漸近複雜性態

1.5.4漸近意義下的記號

1.5.5算法的運行時間T(n)建立的依據

1.5.6算法所占用的空間S(n)建立的依據

1.6遞推方程求解方法

1.6.1疊代法

1.6.2遞歸樹

1.6.3差消法

1.6.4主方法

第2章貪心算法——貪心不足

2.1概述

2.1.1貪心算法的本質

2.1.2貪心算法的基本要素

2.2活動安排問題

2.2.1問題分析——貪心策略

2.2.2算法設計

2.2.3實例構造

2.2.4算法分析

2.2.5Python實戰

2.3單源最短路徑問題

2.3.1問題分析——貪心策略

2.3.2算法設計

2.3.3實例構造

2.3.4算法分析

2.3.5Python實戰

2.4哈夫曼編碼

2.4.1問題分析——貪心策略

2.4.2算法設計

2.4.3實例構造

2.4.4算法分析

2.4.5Python實戰

2.5最小生成樹——Prim算法

2.5.1問題分析——貪心策略

2.5.2算法設計

2.5.3實例構造

2.5.4算法分析

2.5.5Python實戰

2.6最小生成樹——Kruskal算法

2.6.1問題分析——貪心策略

2.6.2算法設計

2.6.3實例構造

2.6.4算法分析

2.6.5Python實戰

2.7背包問題

2.7.1問題分析——貪心策略

2.7.2算法設計

2.7.3實例構造

2.7.4算法分析

2.7.5Python實戰

第3章分治算法——分而治之

3.1概述

3.1.1分治算法的本質

3.1.2分治算法的求解步驟

3.2二分查找

3.2.1問題分析——分與治的方法

3.2.2算法設計

3.2.3實例構造

3.2.4算法分析

3.2.5Python實戰

3.3選第二大元素

3.3.1問題分析——分與治的方法

3.3.2算法設計

3.3.3實例構造

3.3.4算法分析

3.3.5Python實戰

3.4循環賽日程表

3.4.1問題分析——分與治的方法

3.4.2算法設計

3.4.3實例構造

3.4.4算法分析

3.4.5Python實戰

3.5合併排序

3.5.1問題分析——分與治的方法

3.5.2算法設計

3.5.3實例構造

3.5.4算法分析

3.5.5Python實戰

3.6快速排序

3.6.1問題分析——分與治的方法

3.6.2算法設計

3.6.3實例構造

3.6.4算法分析

3.6.5Python實戰

3.7線性時間選擇——找第k小問題

3.7.1問題分析——分與治的方法

3.7.2算法設計

3.7.3實例構造

3.7.4算法分析

3.7.5Python實戰

第4章動態規劃

4.1概述

4.1.1動態規劃的基本思想

4.1.2動態規劃的求解步驟

4.1.3動態規劃的基本要素

4.2矩陣連乘問題

4.2.1問題分析——遞歸關係

4.2.2算法設計

4.2.3實例構造

4.2.4算法分析

4.2.5Python實戰

4.3凸多邊形最優三角剖分

4.3.1問題分析——遞歸關係

4.3.2算法設計

4.3.3實例構造

4.3.4算法分析

4.3.5Python實戰

4.4最長公共子序列問題

4.4.1問題分析——遞歸關係

4.4.2算法設計

4.4.3實例構造

4.4.4算法分析

4.4.5Python實戰

4.5加工順序問題

4.5.1問題分析——遞歸關係

4.5.2算法設計

4.5.3實例構造

4.5.4算法分析

4.5.5Python實戰

4.601背包問題

4.6.1問題分析——遞歸關係

4.6.2算法設計

4.6.3實例構造

4.6.4算法分析

4.6.5算法的改進

4.6.6Python實戰

4.7最優二叉查找樹

4.7.1問題分析——遞歸關係

4.7.2算法設計

4.7.3實例構造

4.7.4算法分析

4.7.5Python實戰

第5章回溯法——深度優先搜尋

5.1概述

5.2典型的解空間結構

5.2.1子集樹

5.2.2排列樹

5.2.3滿m叉樹

5.301背包問題——子集樹

5.3.1問題分析——解空間及搜尋條件

5.3.2算法設計

5.3.3實例構造

5.3.4算法的改進

5.3.5算法分析

5.3.6Python實戰

5.4最大團問題——子集樹

5.4.1問題分析——解空間及搜尋條件

5.4.2算法設計

5.4.3實例構造

5.4.4算法分析

5.4.5Python實戰

5.5批處理作業調度問題——排列樹

5.5.1問題分析——解空間及搜尋條件

5.5.2算法設計

5.5.3實例構造

5.5.4算法分析

5.5.5Python實戰

5.6旅行商問題——排列樹

5.6.1問題分析——解空間及搜尋條件

5.6.2算法設計

5.6.3實例構造

5.6.4算法分析

5.6.5Python實戰

5.7圖的m著色問題——滿m叉樹

5.7.1問題分析——解空間及搜尋條件

5.7.2算法設計

5.7.3實例構造

5.7.4算法分析

5.7.5Python實戰

5.8最小質量機器設計問題——滿m叉樹

5.8.1問題分析——解空間及搜尋條件

5.8.2算法設計

5.8.3實例構造

5.8.4算法分析

5.8.5Python實戰

第6章分支限界法——寬度優先或最小耗費(最大效益)優先搜尋

6.1分支限界法的基本思想

6.201背包問題

6.3旅行商問題

6.4布線問題

6.4.1問題分析——解空間及搜尋條件

6.4.2算法設計

6.4.3實例構造

6.4.4算法分析

6.4.5Python實戰

6.5分支限界法與回溯法的比較

第7章線性規劃問題與網路流

7.1線性規劃問題

7.1.1一般線性規劃問題的描述

7.1.2標準型線性規劃問題的描述

7.1.3標準型線性規劃問題的單純形算法

7.2最大網路流

7.2.1基本概念

7.2.2增廣路算法

7.2.3最大網路流的變換與套用

7.3最小費用最大流

7.3.1基本概念

7.3.2消圈算法

7.3.3最小費用最大流的變換與套用

第8章隨機化算法

8.1概述

8.1.1隨機化算法的類型及特點

8.1.2隨機數發生器

8.2數值隨機化算法

8.2.1計算π的值

8.2.2計算定積分

8.3蒙特卡羅算法

8.3.1主元素問題

8.3.2素數測試

8.4拉斯維加斯算法

8.4.1整數因子分解

8.4.2n皇后問題

8.5舍伍德算法

8.5.1隨機快速排序

8.5.2線性時間選擇

第9章NP完全理論

9.1易解問題和難解問題

9.2P類和NP類問題

9.2.1P類問題

9.2.2NP類問題

9.2.3P類問題和NP類問題的關係

9.3NP完全問題

9.3.1多項式變換技術

9.3.2典型的NP完全問題

9.4NP完全問題的近似算法

9.4.1頂點覆蓋問題

9.4.2裝箱問題

9.4.3旅行商問題TSP

9.4.4集合覆蓋問題

參考文獻

作者簡介

王秋芬，女，1978-，碩士研究生，副教授。研究方向為計算機軟體理論、算法、大數據，主講《作業系統》、《數據結構》、《算法設計與分析》等課程。從教以來，獲校級教學技能競賽一等獎、省級教學技能競賽二等獎；以第一作者發表論文20餘篇，出版《算法設計與分析》、《算法設計藝術》等3部著作；主持、參與省級項目6項，主持課程與教材建設項目5項；獲省部級以上獎勵5項；已獲授權國家發明專利4項。