本書是國際算法大師烏迪·曼博（Udi Manber）博士撰寫的一本享有盛譽的著作。全書共分12章：第1章到第4章為介紹性內(nèi)容，涉及數(shù)學(xué)歸納法、算法分析、數(shù)據(jù)結(jié)構(gòu)等內(nèi)容；第5章提出了與歸納證明進行類比的算法設(shè)計思想；第6章到第9章分別給出了4個領(lǐng)域的算法，如序列和集合的算法、圖算法、幾何算法、代數(shù)和數(shù)值算法；第10章涉及歸約，也是第11章的序幕，而后者涉及NP完全問題；第12章則介紹了并行算法；最后是部分習(xí)題的答案及參考文獻。本書的特色有二，旨在提高讀者的問題求解能力，使讀者能夠理解算法設(shè)計的過程和思想：一是強調(diào)算法設(shè)計的創(chuàng)造性過程，注重算法設(shè)計背后的創(chuàng)造性思想，而不拘泥于某個具體算法的詳細討論；二是將算法設(shè)計類比于定理歸納證明，揭示了算法設(shè)計的基本思想和本質(zhì)。
本書的組織結(jié)構(gòu)清晰且易于理解，強調(diào)了創(chuàng)造性，具有濃郁特色，時至今日仍有其巨大的價值，并且適合作為計算機及相關(guān)專業(yè)算法和高級算法課程的教材。 作者簡介
Udi Manber
美國著名的計算機科學(xué)家，國際公認(rèn)的算法大師，在線信息搜索引擎的先驅(qū)。1982年于華盛頓大學(xué)獲得計算機科學(xué)博士學(xué)位，曾是美國亞利桑那大學(xué)計算機專業(yè)教授。離開學(xué)校后在雅虎公司擔(dān)任執(zhí)行官，閆前是亞馬遜（Amazon.com）的副總裁和首席算法師（CAO），也是亞馬遜旗下搜索網(wǎng)站A9.corn的首席執(zhí)行官。他提出的UDI測試已經(jīng)成為衡量搜索引擎質(zhì)量的評估標(biāo)準(zhǔn)。
目錄：
第1章 引論
第2章 數(shù)學(xué)歸納法
2.1 引言
2.2 三個簡單的例子
2.3 平面內(nèi)區(qū)域的計數(shù)
2.4 簡單的著色問題
2.5 復(fù)雜一些的加法題
2.6 一個簡單的不等式
2.7 歐拉公式
2.8 圖論中的一個問題
2.9 格雷碼
2.10 在圖上尋找無重邊的路
2.11 數(shù)學(xué)平均數(shù)和幾何平均數(shù)定理
2.12 循環(huán)不變量：將十進制數(shù)轉(zhuǎn)換為二進制數(shù)
2.13 常見的錯誤
2.14 小結(jié)
第3章 算法分析
3.1 引言
3.2 符號O
3.3 時間與空間復(fù)雜度
3.4 習(xí)之和
3.5 遞推關(guān)系
3.5.1 巧妙地猜測
3.5.2 分治關(guān)系
3.5.3 涉及全部歷史的遞推關(guān)系
3.6 一些有用的證明論據(jù)
3.7 小結(jié)
第4章 數(shù)據(jù)結(jié)構(gòu)簡介
4.1 引言
4.2 基本數(shù)據(jù)結(jié)構(gòu)
4.2.1 元素
4.2.2 數(shù)組
4.2.3 記錄
4.2.4 鏈表
4.3 樹
4.3.1 樹的表示
4.3.2 堆
4.3.3 二叉搜索樹
4.3.4 AVL樹
4.4 散列
4.5 合并碴找問題
4.6 圖
4.7 小結(jié)
第5章 基于歸納的算法設(shè)計
5.1 引言
5.2 多項式求值
5.3 最大導(dǎo)出子圖
5.4 尋找一對一映射
5.5 社會名流問題
5.6 分治算法：輪廓問題
5.7 在二叉樹中計算平衡因子
5.8 尋找最大連續(xù)子序列
5.9 增強歸納假設(shè)
5.10 動態(tài)規(guī)劃：背包問題
5.11 常見的錯誤
5.12 小結(jié)
第6章 序列和集合的算法
6.1 引言
6.2 二叉搜索的幾種形式
6.2.1 純二叉搜索
6.2.2 循環(huán)序列的二叉搜索
6.2.3 二叉搜索特殊下標(biāo)
6.2.4 二叉搜索長度未知的序列
6.2.5 重疊子序列問題
6.2.6 解方程
6.3 內(nèi)插搜索
6.4 排序
6.4.1 桶排序和基數(shù)排序
6.4.2 插入排序和選擇排序
6.4.3 歸并排序
6.4.4 快速排序
6.4.5 堆排序
……
第7章 圖算法
第8章 幾何算法
第9章 代數(shù)和數(shù)值算法
第10章 歸約
第11章 NP完全問題
第12章 并行算法
部分習(xí)題答案
參考文獻
|
