算法概論

內容概要

　　本書系統(tǒng)全面地介紹了算法的基本知識。這些知識和技巧既是高等院校“算法與數(shù)據(jù)結構”課程的主要內容，也是計算機科學蓬勃發(fā)展的理論基礎?！　”緯w了絕大多數(shù)算法設計中的常用技術。在表達每一種技術時，闡述它的應用背景，強調每個算法運轉背后的簡潔數(shù)學思想，注意運用與其他技術類比的方法來說明它的特征，并提供了大量相應實際問題的例子。本書同時也注重了對每一種算法的復雜性分析。全書共10章，從基本的數(shù)字算法人手，先后介紹了分治、圖的遍歷、貪心算法、動態(tài)規(guī)劃、線性規(guī)劃等技術，對NP完全問題進行廠基本而清晰的闡述，對隨機算法、近似算法和量子算法這些近年來發(fā)展迅猛的領域也花費了一定的筆墨。書中每章后面都附有大量的習題，有利于讀者對書中內容的理解和應用。

作者簡介

　　Sanjoy Dasgupta于2002年在加州大學伯克利分校獲得計算機科學專業(yè)的博土學位。他是AT&T實驗室的高級技術人員。他的工作重點是研究數(shù)據(jù)挖掘的算法，對業(yè)務數(shù)據(jù)的語音識別和分析的應用。他在多維數(shù)據(jù)的統(tǒng)計分析的開發(fā)算法領域獲得很重要的研究成果。

書籍目錄

第0章 序言0.1 書籍和算法0.2 從Fibonacci數(shù)列開始0.3 大O符號習題第1章 數(shù)字的算法1.1 基本算術1.1.1 加法1.1.2 乘法和除法1.2 模運算1.2.1 模的加法和乘法1.2.2 模的指數(shù)運算1.2.3 Euclid的最大公因數(shù)算法1.2.4 Euclid算法的一種擴展1.2.5 模的除法1.3 素性測試1.4 密碼學1.4.1 密鑰機制：一次一密亂碼本和AES1.4.2 RSA1.5 通用散列表1.5.1 散列表1.5.2 散列函數(shù)族習題第2章 分治算法2.1 乘法2.2 遞推式2.3 合并排序2.4 尋找中項2.5 矩陣乘法2.6 快速Fourier變換2.6.1 多項式的另一種表示法2.6.2 計算步驟的分治實現(xiàn)2.6.3 插值2.6.4 快速Fourier變換的細節(jié)習題第3章 圖的分解3.1 為什么是圖3.2 無向圖的深度優(yōu)先搜索3.2.1 迷宮探索3.2.2 深度優(yōu)先搜索3.2.3 無向圖的連通性3.2.4 前序和后序3.3 有向圖的深度優(yōu)先搜索3.3.1 邊的類型3.3.2 有向無環(huán)圖3.4 強連通部件3.4.1 定義有向圖的連通性3.4.2 一個有效的算法習題第4章 圖中的路徑4.1 距離4.2 廣度優(yōu)先搜索4.3 邊的長度4.4 Dijkstra算法4.4.1 廣度優(yōu)先搜索的一個改進4.4.2 另一種解釋4.4.3 運行時間4.5 優(yōu)先隊列的實現(xiàn)4.5.1 數(shù)組4.5.2 二分堆4.5.3 d堆4.6 含有負邊的圖的最短路徑4.6.1 負邊4.6.2 負環(huán)4.7 有向無環(huán)圖中的最短路徑習題第5章 貪心算法5.1 最小生成樹5.1.1 一個貪心方法5.1.2 分割性質5.1.3 Kruskal算法5.1.4 一種用于分離集的數(shù)據(jù)結構5.1.5 Prim算法5.2 Huffman編碼5.3 Horn公式5.4 集合覆蓋習題第6章 動態(tài)規(guī)劃6.1 重新審視有向無環(huán)圖的最短路徑問題6.2 最長遞增子序列6.3 編輯距離6.4 背包問題6.5 矩陣鏈式相乘6.6 最短路徑問題6.7 樹中的獨立集習題第7章 線性規(guī)劃與歸約7.1 線性規(guī)劃簡介7.1.1 示例：利潤最大化7.1.2 示例：生產(chǎn)計劃7.1.3 示例：最優(yōu)帶寬分配7.1.4 線性規(guī)劃的變體7.2 網(wǎng)絡流7.2.1 石油運輸7.2.2 最大流7.2.3 對算法的深入觀察7.2.4 最優(yōu)性的保證7.2.5 算法的效率7.3 二部圖的匹配7.4 對偶7.5 零和博弈(游戲)7.6 單純形算法7.6.1 n維空間中的頂點和鄰居7.6.2 算法7.6.3 補遺7.6.4 單純形法的運行時間7.7 后記：電路值1習題第8章 NP-完全問題8.1 搜索問題8.2 NP-完全問題8.3 所有的歸約習題第9章 NP-完全問題的處理9.1 智能窮舉搜索9.1.1 回溯9.1.2 分支定界9.2 近似算法9.2.1 頂點覆蓋9.2.2 聚類9.2.3 TSP9.2.4 背包問題9.2.5 逼近的層次9.3 局部搜索中的啟發(fā)方法9.3.1 重新審視旅行商問題9.3.2 圖劃分9.3.3 處理局部最優(yōu)習題第10章 量子算法10.1 量子位元、疊加狀態(tài)和度量10.2 算法設計10.3 量子傅立葉變換10.4 周期性10.5 量子電路10.5.1 基本量子門10.5.2 量子電路的兩種基本類型10.5.3 量子傅立葉變換電路10.6 將因子分解問題轉化為周期求解問題10.7 因子分解的量子算法習題歷史背景及深入閱讀的資

章節(jié)摘錄

　　序言　　如果你環(huán)視左右，就會發(fā)現(xiàn)電腦與網(wǎng)絡在生活中無處不在，它們織就了一張復雜的網(wǎng)，人類的各種活動都蘊含其中：教育、商業(yè)、娛樂、研究、制造、醫(yī)療管理、人際交往，甚至包括戰(zhàn)爭。如今有兩項技術可以用日新月異這個詞來形容，其中之一就是硬件速度的飛速提升，這得益于微電子業(yè)和芯片制造業(yè)驚人的發(fā)展速度。

編輯推薦

　　作為一本介紹算法技術和思想的書籍，本書不僅是面各信息學科大學生的優(yōu)秀教材（或參考書），更是將任何具有初等數(shù)學基礎的人引入算法應用與研究殿堂的一塊引路石。本書循序漸進、深入淺出地展示了算法研究與應用領域中，從模型分析、算法構造到復雜性分析和算法優(yōu)化的方方面面。涉及內容從古老的算術算法、排序算法、簡單算法、線性規(guī)劃、動態(tài)規(guī)劃、隨機算法以及NP復雜理論，甚至是尚未完全顯現(xiàn)全貌的量子計算，覆蓋了經(jīng)典、現(xiàn)代和未來算法發(fā)展的眾多代表性成果?！　”緯x材新穎，內容豐富，適用于作為計算機學科以及相關學科算法課程的教材和參考書，同時也可作從事算法研究的入門書籍。　　本書主要內容　　分治算法，圖的分解與圖中的路徑，貪心算法，線性規(guī)劃歸約，NP—完全問題，量子算法。　　實踐指南清晰，內容深入廣泛，實例學以致用。

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    算法概論 PDF格式下載

---