算法設計（簡體書）

本書是近年來關于算法設計和分析的不可多得的優秀教材。本書圍繞算法設計技術組織素材，對每種算法技術選擇了多個典型范例進行分析。本書將直觀性與嚴謹性完美地結合起來。每章從實際問題出發，經過具體、深入、細致的分析，自然且富有啟發性地引出相應的算法設計思想，并對算法的正確性、復雜性進行恰當的分析、認證。本書覆蓋的面較寬，凡屬串行算法的經典論題都有涉及，并且論述深入有新意。全書共200多道豐富而精彩的習題是本書的重要組成部分，也是本書的突出特色之一。 本書特點： 以各種算法設計技術（如貪心法、分治策略、動態規劃、網絡流、近似算法、隨機算法等）為主線來組織素材，突出了算法設計的思想和分析的基本原則，為從事實際問題的算法設計與分析工作提供了清晰的、整體的思路和方法。 本教材內容非常豐富，不但深入系統地闡述了算法設計與分析的理論，而且給出了大量的典型范例和參考文獻。 本教材以算法為主線來處理算法與數據結構的關系。這種安排突出了算法設計的中心思想，避免了與數據結構課程在內容上的重復，更加適合于國內的教學計劃。 本教材的敘述和選材非常適合教學。內容由淺入深，由具體到抽象，從算法設計技術與分析方法自然過渡到計算復雜性理論，選配了大量難度適當的練習，并給出求解范例。

Jon Kleinberg，是康奈爾大學計算機科學教授。1996年獲麻省理工學院博士學位，榮獲美國國家科學基金會（NSF）事業（Career）獎，海軍研究局（ONR）青年調查研究員（Young Investigator）獎，IBM杰出創新（Outstanding Innovation）獎，國家科學院主動研究（Initiaves in Research）獎，Packard基金會和Sloan基金會的研究基金，以及康奈爾大學工程學院與計算機科學系的教學獎。 Kleinberg的研究集中在算法，特別是與網絡結構與信息、信息科學的應用、優化、數據挖掘以及計算機生物學有關的算法，他在網絡分析中使用集線器和授權的工作對形成最新一代因特網搜索引擎的基礎起了很大的作用。

第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章　隨機算法
后記：永不停止運行的算法
索引