算法設計

《算法設計》是2007年清華大學出版社出版發行的圖書，作者是Jon Kleinberg / Éva Tardos。

基本介紹

• 書名：算法設計
• 作者：(美)克林伯格
• ISBN：9787302143352
• 定價：75.00 元
• 出版社：清華大學出版社
• 出版時間：2007
• 開本：16

圖書簡介

本書圍繞算法設計技術組織素材，對每種算法技術選擇了多個典型範例進行分析。本書將直觀性與嚴謹性完美地結合起來。每章從實際問題出發，經過具體、深入、細緻的分析，自然且富有啟發性地引出相應的算法設計思想，並對算法的正確性、複雜性進行恰當的分析、認證。

內容簡介

本書是近年來關於算法設計和分析的不可多得的優秀教材。本書覆蓋的面較寬，凡屬串列算法的經典論題都有涉及，並且論述深入有新意。全書共200多道豐富而精彩的習題是本書的重要組成部分，也是本書的突出特色之一。

本書特點

以各種算法設計技術（如貪心法、分治策略、動態規劃、網路流、近似算法、隨機算法等）為主線來組織素材，突出了算法設計的思想和分析的基本原則，為從事實際問題的算法設計與分析工作提供了清晰的、整體的思路和方法。

本教材內容非常豐富，不但深入系統地闡述了算法設計與分析的理論，而且給出了大量的典型範例和參考文獻。

本教材以算法為主線來處理算法與數據結構的關係。這種安排突出了算法設計的中心思想，避免了與數據結構課程在內容上的重複，更加適合於國內的教學計畫。

本教材的敘述和選材非常適合教學。內容由淺入深，由具體到抽象，從算法設計技術與分析方法自然過渡到計算複雜性理論，選配了大量難度適當的練習，並給出求解範例。

目錄

第1章　引言：某些典型的問題

1.1　第一個問題：穩定匹配

1.2　五個典型問題

帶解答的練習

練習

注釋和進一步的閱讀

第2章　算法分析基礎

2.1　計算可解性

2.2　增長的漸近階

2.3　用表和數組實現穩定匹配算法

2.4　一般運行時間的概述

2.5　更複雜的數據結構：優先佇列

帶解答的練習

練習

注釋和進一步的閱讀

第3章　圖

3.1　基本定義與套用

3.2　圖的連通性與圖的遍歷

3.3　用優先佇列與棧實現圖的遍歷

3.4　二分性測試：寬度優先搜尋的一個套用

3.5　有向圖中的連通性

3.6　有向無圈圖與拓撲排序

帶解答的練習

練習

注釋和進一步的閱讀

第4章　貪心算法

4.1　區間調度：貪心算法領先

4.2　最小延遲調度：一個交換論證

4.3　最優高速快取：一個更複雜的交換論證

4.4　一個圖的最短路徑

4.5　最小生成樹問題

4.6　實現Kruskal算法：Unoin－Find數據結構

4.7　聚類

4.8　Huffman碼與數據壓縮

4.9　最小費用有向樹：一個多階段貪心

帶解答的練習

練習

注釋和進一步的閱讀

第5章　分治策略

5.1　第一個遞推式：歸併排序算法

5.2　更多的遞推關係

5.3　計數逆序

5.4　找最接鄰近的點對

5.5　整數乘法

5.6　卷積與快速傅立葉變換

帶解答的練習

練習

注釋和進一步的閱讀

第6章　動態規劃

6.1　帶權的區間調度：一個遞歸過程

6.2　動態規劃原理：備忘錄或者子問題疊代

6.3　分段的最小二乘：多重選擇

6.4　子集和與背包：加一個變數

6.5　RNA二級結構：在區間上的動態規劃

6.6　序列比對

6.7　通過分治策略線上性空間的序列比對

6.8　圖中的最短路徑

6.9　最短路徑和距離向量協定

6.10　圖中的負圈

帶解答的練習

練習

注釋和進一步的閱讀

第7章　網路流

第8章　Ng與計算的難解性

第9章　一個超出

第10章　擴展易解性的界限

第11章　近似算法

第12章　局部搜尋

第13章　隨機算法

後記：永不停止運行的算法

索引