算法分析导论（英文版）

图书标准信息

• 作者 [美]塞奇威克（Sedgewick R.） 著
• 出版社 机械工业出版社
• 出版时间 2006-04
• 版次 1
• ISBN 9787111186069
• 定价 59.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 492页
• 丛书 经典原版书库

【内容简介】

本书为全英文。它全面介绍了算法的数学分析中使用的基本方法，所涉及的内容来自经典的数学素材（包括离散数学、初等实分析、组合数学），以及经典的计算机科学素材（包括算法和数据结构）。虽然书中论述了“最坏情形”和“复杂性问题”分析所需的基本数学工具，但是重点还是讨论“平均情形”或“概率”分析。论题涉及递归、生成函数、渐近性、树、串、映射等内容，以及对排序、树查找、串查找和散列诸算法的分析。
本书全面介绍了算法的数学分析中使用的基本方法，所涉及的内容来自经典的数学素材（包括离散数学、初等实分析、组合数学），以及经典的计算机科学素材（包括算法和数据结构）。虽然书中论述了“最坏情形”和“复杂性问题”分析所需的基本数学工具，但是重点还是讨论“平均情形”或“概率”分析。论题涉及递归、生成函数、渐近性、树、串、映射等内容，以及对排序、树查找、串查找和散列诸算法的分析。
尽管人们极为关注算法的数学分析，但是广泛使用的方法和模型方面的基本信息尚不能为该领域的工作和研究所直接使用。作者在本书中处理这种需求，把该领域出现的挑战以及为跟上新的研究以迎接这些挑战所必需的背景资料完美地结合在一起。

【作者简介】

Robert Sedgewick斯坦福大学博士(导师为Donald E.Knuth)，普林斯顿大学计算机科学系教授，Adobe Systems公司董事，曾是Xerox PARC的研究人员，还曾就职于美国国防部防御分析研究所以及INRIA。

【目录】

CHAPTERONE：ANALYSISOFALGORITHMS
1.1WhyAnalyzeanAlgorithm?
1.2ComputationalComplexity
1.3AnalysisofAlgorithms
1.4Average-CaseAnalysis
1.5Example:AnalysisofQuieksort
1.6AsymptoticApproximations
1.7Distributions
1.8ProbabilisticAlgorithms
CHAPTERTWO:RECURRENCERELATIONS
2.1BasicProperties
2.2First-OrderRecurrences
2.3NonlinearFirst-OrderRecurrences
2.4Higher-OrderRecurrences
2.5MethodsforSolvingRecurrences
2.6BinaryDivide-and-ConquerRecurrencesandBinary
Numbers
2.7GeneralDivide-and-ConquerRecurrences
CHAPTERTHREE:GENERATINGFUNCTIONS
3.1OrdinaryGeneratingFunctions
3.2ExponentialGeneratingFunctions
3.3GeneratingFunctionSolutionofRecurrences
3.4ExpandingGeneratingFunctions
3.5TransformationswithGeneratingFunctions
3.6FunctionalEquationsonGeneratingFunctions
3.7SolvingtheQuicksortMedian-of-ThreeRecurrencewithOGFS
3.8CountingwithGeneratingFunctions
3.9TheSymbolicMethod
3.10LagrangeInversion
3.11ProbabilityGeneratingFunctions
3.12BivariateGeneratingFunctions
3.13SpecialFunctions
CHAPTERFOUR:ASYMPTOTICAPPROXIMATIONS
4.1NotationforAsymptoticApproximations
4.2AsymptoticExpansions
4.3ManipulatingAsymptoticExpansions
4.4AsymptoticApproximationsofFiniteSums
4.5Euler-MaclaurinSummation
4.6BivariateAsymptotics
4.7LaplaceMethod
4.8“Normal”ExamplesfromtheAnalysisofAlgorithms
4.9“Poisson”ExamplesfromtheAnalysisofAlgorithms
4.10GeneratingFunctionAsymptotics
CHAPTERFIVE:TREES
5.1BinaryTrees
5.2TreesandForests
5.3PropertiesofTrees
5.4TreeAlgorithms
5.5BinarySearchTrees
5.6AveragePathLengthinCatalanTrees
5.7PathLengthinBinarySearchTrees
5.8AdditiveParametersofRandomTrees
5.9Height
5.10SummaryofAverage-CaseResultsonPropertiesofTrees
5.11RepresentationsofTreesandBinaryTrees
5.12UnorderedTrees
5.13LabelledTrees
5.14OtherTypesofTrees
CHAPTERSIX:PERMUTATIONS
6.1BasicPropertiesofPermutations
6.2AlgorithmsonPermutations
6.3RepresentationsofPermutations
6.4EnumerationProblems
6.5AnalyzingPropertiesofPermutationswithCGFs
6.6InversionsandInsertionSorts
6.7Left-to-RightMinimaandSelectionSort
6.8CyclesandInSituPermutation
6.9ExtremalParameters
CHAPTERSEVEN：STRINGSANDTRIES
7.1StringSearching
7.2CombinatorialPropertiesofBitstrings
7.3RegularExpressions
7.4Finite-StateAutomataandtheKnuth-Morris-Pratt
Algorithm
7.5Context-FreeGrammars
7.6Tries
7.7TrieAlgorithms
7.8CombinatorialPropertiesofTries
7.9LargerAlphabets
CHAPTEREIGHT:WORDSANDMAPS
8.1HashingwithSeparateChaining
8.2BasicPropertiesofWords
8.3BirthdayParadoxandCouponCollectorProblem
8.4OccupancyRestrictionsandExtremalParameters
8.5OccupancyDistributions
8.6OpenAddressingHashing
8.7Maps
8.8IntegerFacterizationandMaps
ListofTheorems
Index