算法分析導(dǎo)論

內(nèi)容概要

本書全面介紹了算法的數(shù)學(xué)分析所需要使用的主要技術(shù)，包括經(jīng)典的數(shù)學(xué)內(nèi)容（如離散數(shù)學(xué)、初等實分析、組合學(xué)等）以及經(jīng)典的計算機科學(xué)內(nèi)容（如算法和數(shù)據(jù)結(jié)構(gòu)等）。書中重點強調(diào)了平均情形下的算法分析，同時也包含對最壞情形下的算法分析。    盡管人們極為關(guān)注算法的數(shù)學(xué)分析，但是廣泛使用的方法和模型方面的基本信息尚不能為該領(lǐng)域的工作和研究所直接使用。作者在本書中處理這種需求，把該領(lǐng)域出現(xiàn)的挑戰(zhàn)以及為跟上新的研究以迎接這些挑戰(zhàn)所必需的背景資料完美地結(jié)合在一起。

作者簡介

Robert Sedgewick斯坦福大學(xué)博士(導(dǎo)師為Donald E.Knuth)，普林斯頓大學(xué)計算機科學(xué)系教授，Adobe Systems公司董事，曾是Xerox PARC的研究人員，還曾就職于美國國防部防御分析研究所以及INRIA。

書籍目錄

TABLE OF CONTENTSCHAPTER ONE: ANALYSIS OF ALGORITHMS 1.1 Why Analyze an Algorithm? 1.2 Computational Complexity 1.3 Analysis of Algorithms 1.4 Average-Case Analysis 1.5 Example: Analysis of Quieksort 1.6 Asymptotic Approximations 1.7 Distributions 1.8 Probabilistic AlgorithmsCHAPTER TWO: RECURRENCE RELATIONS 2.1 Basic Properties 2.2 First-Order Recurrences 2.3 Nonlinear First-Order Recurrences 2.4 Higher-Order Recurrences 2.5 Methods for Solving Recurrences 2.6 Binary Divide-and-Conquer Recurrences and Binary Numbers 2.7 General Divide-and-Conquer RecurrencesCHAPTER THREE: GENERATING FUNCTIONS 3.1 Ordinary Generating Functions 3.2 Exponential Generating Functions 3.3 Generating Function Solution of Recurrences 3.4 Expanding Generating Functions 3.5 Transformations with Generating Functions 3.6 Functional Equations on Generating Functions 3.7 Solving the Quicksort Median-of-Three Recurrence with OGFs 3.8 Counting with Generating Functions 3.9 The Symbolic Method 3.10 Lagrange Inversion 3.11 Probability Generating Functions 3.12 Bivariate Generating Functions 3.13 Special FunctionsCHAPTER FOUR: ASYMPTOTIC APPROXIMATIONS 4.1 Notation for Asymptotic Approximations 4.2 Asymptotic Expansions 4.3 Manipulating Asymptotic Expansions 4.4 Asymptotic Approximations of Finite Sums 4.5 Euler-Maclaurin Summation 4.6 Bivariate Asymptotics 4.7 Laplace Method 4.8 "Normal" Examples from the Analysis of Algorithms 4.9 "Poisson" Examples from the Analysis of Algorithms 4.10 Generating Function AsymptoticsCHAPTER FIVE: TREES 5.1 Binary Trees 5.2 Trees and Forests 5.3 Properties of Trees 5.4 Tree Algorithms 5.5 Binary Search Trees 5.6 Average Path Length in Catalan Trees 5.7 Path Length in Binary Search Trees 5.8 Additive Parameters of Random Trees 5.9 Height 5.10 Summary of Average-Case Results on Properties of Trees 5.11 Representations of Trees and Binary Trees 5.12 Unordered Trees 5.13 Labelled Trees 5.14 Other Types of TreesCHAPTER SIX: PERMUTATIONS 6.2 Algorithms on Permutations 6.3 Representations of Permutations 6.4 Enumeration Problems 6.5 Analyzing Properties of Permutations with CGFs 6.6 Inversions and Insertion Sorts 6.7 Left-to-Right Minima and Selection Sort 6.8 Cycles and In Situ Permutation 6.9 Extremal ParametersCHAPTER SEVEN: STRINGS AND TRIES 7.1 String Searching 7.2 Combinatorial Properties of Bitstrings 7.3 Regular Expressions 7.4 Finite-State Automata and the Knuth-Morris-Pratt Algorithm 7.5 Context-Free Grammars 7.6 Tries 7.7 ride Algorithms 7.8 Combinatorial Properties of Tries 7.9 Larger AlphabetsCHAPTER EIGHT: WORDS AND MAPS 8.1 Hashing with Separate Chaining 8.2 Basic Properties of Words 8.3 Birthday Paradox and Coupon Collector Problem 8.4 Occupancy Restrictions and Extremal Parameters 8.5 Occupancy Distributions 8.6 Open Addressing Hashing 8.7 Maps 8.8 Integer Factorization and MapsList of TheoremsIndex

媒體關(guān)注與評論

書評分析算法的人享有雙重的幸福。首先，他們能夠體驗到優(yōu)雅數(shù)學(xué)模式純粹的美，這處模式存在于優(yōu)美的計算過程之中。其次，當他們的理論使得其他工作能夠做得更快、更經(jīng)濟時，他們得到的是實際的褒獎。因此，我們盼望已久的這部著作極受歡迎。該書作者不僅是該領(lǐng)域世界范圍內(nèi)的領(lǐng)袖，而且還是闡述的大師。                                ——Donald E. Knuth

編輯推薦

　　本書為全英文。它全面介紹了算法的數(shù)學(xué)分析中使用的基本方法，所涉及的內(nèi)容來自經(jīng)典的數(shù)學(xué)素材(包括離散數(shù)學(xué)、初等實分析、組合數(shù)學(xué))，以及經(jīng)典的計算機科學(xué)素材(包括算法和數(shù)據(jù)結(jié)構(gòu))。雖然書中論述了“最壞情形”和“復(fù)雜性問題”分析所需的基本數(shù)學(xué)工具，但是重點還是討論“平均情形”或“概率”分析。論題涉及遞歸、生成函數(shù)、漸近性、樹、串、映射等內(nèi)容，以及對排序、樹查找、串查找和散列諸算法的分析。

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    算法分析導(dǎo)論 PDF格式下載

---