算法分析導論

定　價：￥38.00

作　者：	（美）塞奇威克，（法）弗拉吉萊特著，馮舜璽譯；馮舜璽譯
出版社：	機械工業(yè)出版社
叢編項：	計算機科學叢書
標　簽：	算法

購買這本書可以去

ISBN：	9787111164418	出版時間：	2006-04-01	包裝：	膠版紙
開本：	小16開	頁數(shù)：	314	字數(shù)：

內(nèi)容簡介

　　本書是計算機科學叢書之一，本書全面介紹了算法的數(shù)學分析中使用的基本方法，所涉及的內(nèi)容來自經(jīng)典的數(shù)學課題（包括離散數(shù)學、初等實分析、組合數(shù)學），以及經(jīng)典的計算機科學課題（包括算法和數(shù)據(jù)結(jié)構(gòu)）。雖然書中論述了“最壞情形”和“復雜性”分析所需的基本數(shù)學工具，但是重點還是討論“平均情形”或“概率”分析。論題涉及遞歸、生成函數(shù)、漸近性、樹、串、映射等內(nèi)容．以及對排序、樹查找、串查找和散列諸算法的分析。本書闡述了用于算法數(shù)學分析的主要方法，所涉及的材料來自經(jīng)典數(shù)學課題，包括離散數(shù)學、初等實分析、組合數(shù)學，以及來自經(jīng)典的計算機科學課題，包括算法和數(shù)據(jù)結(jié)構(gòu)。本書內(nèi)容集中覆蓋基礎(chǔ)、重要和有趣的算法，前面?zhèn)戎財?shù)學，后面集中討論算法分析的應(yīng)用，重點是算法分析的數(shù)學方法。每章包含大量習題以及參考文獻，使讀者可以更深入地理解書中的內(nèi)容。本書適合作為高等院校數(shù)學、計算機科學以及相關(guān)專業(yè)的本科生和研究生的教材，也可供相關(guān)技術(shù)人員參考。

作者簡介

　　RobertSedgewick斯坦福大學博士（導師為DorlaidE.Knuth），普林斯頓大學計算機科學系教授，AdobeSystems公司董事，曾是XeroxPARC的研究人員，還曾就職于美國國防部防御分析研究所以及INRIA。

圖書目錄

出版者的話
專家指導委員會
譯者序
序
前言
記號解釋
第1章算法分析概述
1.1 為什么要對算法進行分析
I.2 計算復雜性
1.3 算法分析的過程
1.4 平均情形分析
1.5 例：快速排序的分析
1.6 漸近逼近
1.7 分布
1.8 概率算法
參考文獻
第2章遞歸關(guān)系
2.1 基本性質(zhì)
2.2 一階遞歸
2.3 非線性一階遞歸
2.4 高階遞歸
2.5 求解遞歸的方法
2.6 二分分治遞歸和二進制數(shù)
2.7 一般的分治遞歸
參考文獻
第3章生成函數(shù)
3.1 常規(guī)生成函數(shù)
3.2 指數(shù)生成函數(shù)
3.3 利用生成函數(shù)求解遞歸
3.4 生成函數(shù)的展開
3.5 利用生成函數(shù)進行變換
3.6 關(guān)于生成函數(shù)的函數(shù)方程
3.7 利用OGF求解三數(shù)中值Quicksort遞歸
3.8 利用生成函數(shù)的計數(shù)
3.9 符號方法
3.10 拉格朗日反演
3.11 概率生成函數(shù)
3.12 二元生成函數(shù)
3.13 特殊函數(shù)
參考文獻
第4章漸近逼近
4.1 有關(guān)漸近逼近的記號
4.2 漸近展開式
4.3 漸近展開式的操作
4.4 有限和的漸近逼近
4.5 歐拉一麥克勞林求和
4.6 二元漸近性
4.7 拉普拉斯方法
4.8 算法分析中的“正態(tài)”例
4.9 算法分析中的“泊松”例
4.10 生成函數(shù)的漸近性
參考文獻
第5章樹
5.1 二叉樹
5.2 樹和森林
5.3 樹的性質(zhì)
5.4 樹的算法
5.5 二叉查找樹
5.6 Catalan樹中的平均路徑長
5.7 二叉查找樹中的路徑長
5.8 隨機樹的可加參數(shù)
5.9 高
5.10 樹性質(zhì)平均情形結(jié)果的小結(jié)
5.11 樹和二叉樹的表示
5.12 無序樹
5.13 標號樹
5.14 其他類型的樹
參考文獻
第6章排列
6.1 排列的基本性質(zhì)
6.2 排列的算法
6.3 排列的表示法
6.4 計數(shù)問題
6.5 利用CGF分析排列的性質(zhì)
6.6 逆序與插入排序
6.7 左向右最小值與選擇排序
6.8 圈與原位排列
6.9 極值參數(shù)
參考文獻
第7章串與trie樹
7.1 串查找
7.2 位串的組合性質(zhì)
7.3 規(guī)則表達式
7.4 有限狀態(tài)自動機與Knuth.MorrisPratt算法
7.5 上下文無關(guān)語法
7.6 trie樹
7.7 trie算法
7.8 trie樹的組合性質(zhì)
7.9 更大的字母表
參考文獻
第8章字與映射
8.1 使用分離鏈接的散列
8.2 字的基本性質(zhì)
8.3 生日悖論與贈券收藏家問題
8.4 占有約束與極值參數(shù)
8.5 占有分布
8.6 開放定址散列法
8.7 映射
8.8 整數(shù)因子分解與映射
參考文獻
索引