算法概論

內(nèi)容概要

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

作者簡(jiǎn)介

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

書(shū)籍目錄

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

章節(jié)摘錄

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

編輯推薦

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

圖書(shū)封面

圖書(shū)標(biāo)簽Tags

無(wú)

評(píng)論、評(píng)分、閱讀與下載

---

    算法概論 PDF格式下載

---