中文名: 算法設計與分析基礎 第二版
作者: ANANY LEVITIN
圖書分類: 軟件
資源格式: PDF
版本: 掃描版
出版社: 清華大學出版社
書號: 9787302164029
發行時間: 2007年11月
地區: 大陸
語言: 簡體中文
簡介:



內容簡介
國外經典教材·計算機科學與技術:該書作者基於教學經驗，開發了一套對算法進行分類的新方法。內容包括算法效率分析基礎、蠻力法、分治法、減治法、變治法、動態規劃等11章。各章節均含有習題，書後給出體系提示。
作者簡介:
作者基於豐富的教學經驗，開發了一套對算法進行分類的新方法。這套方法站在通用問題求解策略的高度，能對現有的大多數算法進行准確分類，從而使讀者能夠沿著一條清晰的、一致的、連貫的思路來探索算法設計與分析這一迷人領域。本書作為第2版，相對第1版增加了新的習題，還增加了“迭代改進”一章，使得原來的分類方法更加完善。
本書十分適合作為算法設計和分析的基礎教材，也適合任何有興趣探究算法奧秘的讀者使用，只要讀者具備數據結構和離散數學的知識。
本書為英文版。
內容截圖：

目錄:


第1章 緒論
1.1 什麼是算法
習題1.1
1.2 算法問題求解基礎
1.2.1 理解問題
1.2.2 了解計算設備的性能
1.2.3 在精確解法和近似解法之間做出選擇
1.2.4 確定適當的數據結構
1.2.5 算法的設計技術
1.2.6 算法的描述
1.2.7 算法的正確性證明
1.2.8 算法的分析
1.2.9 為算法寫代碼
習題1.2
1.3 重要的問題類型
1.3.1 排序
1.3.2 查找
1.3.3 字符串處理
1.3.4 圖問題
1.3.5 組合問題
1.3.6 幾何問題
1.3.7 數值問題
習題1.3
1.4 基本數據結構
1.4.1 線性數據結構
1.4.2 圖
1.4.3 樹
1.4.4 集合與字典
習題1.4
小結
第2章 算法效率分析基礎
2.1 分析框架
2.1.1 輸入規模的度量
2.1.2 運行時間的度量單位
2.1.3 增長次數
2.1.4 算法的最優、最差和平均效率
2.1.5 分析框架概要
習題2.1
2.2 漸進符號和基本效率類型
2.2.1 非正式的介紹
2.2.2 符號O
2.2.3 符號Ω
2.2.4 符號？
2.2.5 漸進符號的有用特性
2.2.6 利用極限比較增長次數
2.2.7 基本的效率類型
習題2.2
2.3 非遞歸算法的數學分析
習題2.3
2.4 遞歸算法的數學分析
習題2.4
2.5 例題：斐波那契數列
2.5.1 第n個斐波那契數的精確公式
2.5.2 計算斐波那契數的算法
習題2.5
2.6 算法的經驗分析
習題2.6
2.7 算法可視法
小結
第3章 蠻力法
3.1.1 選擇排序
3.1 選擇排序和冒泡排序
3.1.2 冒泡排序
習題3.1
3.2 順序查找和蠻力字符串匹配
3.2.1 順序查找
3.2.2 蠻力字符串匹配
習題3.2
3.3 最近對和凸包問題的蠻力算法
3.3.1 最近對問題
3.3.2 凸包問題
習題6.6
習題3.3
3.4 窮舉查找
3.4.1 旅行商問題
3.4.2 背包問題
3.4.3 分配問題
習題3.4
小結
第4章 分治法
4.1 合並排序
習題4.1
4.2 快速排序
習題4.2
4.3 折半查找
習題4.3
4.4 二叉樹遍歷及其相關特性
習題4.4
4.5 大整數乘法和Strassen矩陣乘法
4.5.1 大整數乘法
4.5.2 Strassen矩陣乘法
4.6.1 最近對問題
4.6 用分治法解最近對問題和凸包問題
習題4.5
4.6.2 凸包問題
習題4.6
小結
第5章 減治法
5.1 插入排序
習題5.1
5.2 深度優先查找和廣度優先查找
5.2.1 深度優先查找
5.2.2 廣度優先查找
習題5.2
5.3 拓撲排序
習題5.3
5.4 生成組合對象的算法
5.4.1 生成排列
5.4.2 生成子集
習題5.4
5.5 減常因子算法
5.5.2 俄式乘法
5.5.1 假幣問題
5.5.3 約瑟夫斯問題
習題5.5
5.6 減可變規模算法
5.6.1 計算中值和選擇問題
5.6.2 插值查找
5.6.3 二叉查找樹的查找和插入
5.6.4 拈游戲
習題5.6
小結
第6章 變治法
6.1 預排序
習題6.1
6.2 高斯消去法
6.2.1 LU分解及其他應用
6.2.2 計算矩陣的逆
6.2.3 計算矩陣的行列式
習題6.2
6.3 平衡查找樹
6.3.1 AVL樹
6.3.2 2-3樹
習題6.3
6.4 堆和堆排序
6.4.1 堆的概念
6.4.2 堆排序
習題6.4
6.5.1 霍納法則
6.5 霍納法則和二進制冪
6.5.2 二進制冪
習題6.5
6.6 問題化簡
6.6.1 求最小公倍數
6.6.2 計算圖中的路徑數量
6.6.3 優化問題的化簡
6.6.4 線性規劃
6.6.5 簡化為圖問題
小結
第7章 時空權衡
7.1 計數排序
習題7.1
7.2 字符串匹配中的輸入增強技術
7.2.1 Horspool算法
7.2.2 Boyer-Moore算法
習題7.2
7.3 散列法
7.3.1 開散列(分離鏈)
7.3.2 閉散列(開式尋址)
習題7.3
7.4 B樹
習題7.4
小結
第8章 動態規劃
8.1 計算二項式系數
習題8.1
8.2 Warshall算法和Floyd算法
8.2.1 Warshall算法
8.2.2 計算完全最短路徑的Floyd算法
習題8.2
8.3 最優二叉查找樹
習題8.3
8.4 背包問題和記憶功能
8.4.1 背包問題
8.4.2 記憶功能
習題8.4
小結
第9章 貪婪技術
9.1 Prim算法
習題9.1
9.2 Kruskal算法
習題9.2
9.3 Dijkstra算法
習題9.3
9.4 哈夫曼樹
習題9.4
小結
第10章 迭代改進
10.1 單純形法
10.1.1 線性規劃的幾何解釋
10.1.2 單純形法概述
10.1.3 單純形法其他要點
習題10.1
10.2 最大流量問題
習題10.2
10.3 二分圖的最大匹配
習題10.3
10.4 穩定婚姻問題
習題10.4
小結
第11章 算法能力的極限
11.1 如何求下界
11.1.1 平凡下界
11.1.2 信息論下界
11.1.3 敵手下界
11.1.4 問題化簡
習題11.1
11.2 決策樹
11.2.1 排序算法的決策樹
11.2.2 查找有序數組的決策樹
習題11.2
11.3 P、NP和NP完全問題
11.3.1 P和NP問題
11.3.2 NP完全問題
習題11.3
11.4 數值算法的挑戰
習題11.4
小結
第12章 超越算法能力的極限
12.1 回溯法
12.1.1 n皇後問題
12.1.2 哈密頓回路問題
12.1.3 子集和問題
12.1.4 一般性說明
習題12.1
12.2 分支界限法
12.2.1 分配問題
12.2.2 背包問題
12.2.3 旅行商問題
習題12.2
12.3 NP困難問題的近似算法
12.3.1 旅行商問題的近似算法
12.3.2 背包問題的近似算法
習題12.3
12.4 解非線性方程的算法
12.4.1 平分法
12.4.2 試位法
12.4.3 牛頓法
習題12.4
小結
跋
附錄A 算法分析的實用公式
附錄B 遞推關系簡明指南
習題提示
參考文獻