基本信息
- 原书名：An Introduction to the Analysis of Algorithms
- 原出版社： Addison Wesley/Pearson
内容简介
书籍
计算机书籍
本书全面介绍了算法的数学分析中使用的基本方法，所涉及的内容来自经典的数学素材(包括离散数学、初等实分析、组合数学)，以及经典的计算机科学素材(包括算法和数据结构)。虽然书中论述了“最坏情形”和“复杂性问题”分析所需的基本数学工具，但是重点还是讨论“平均情形”或“概率”分析。论题涉及递归、生成函数、渐近性、树、串、映射等内容，以及对排序、树查找、串查找和散列诸算法的分析。.
尽管人们极为关注算法的数学分析，但是广泛使用的方法和模型方面的基本信息尚不能为该领域的工作和研究所直接使用。作者在本书中处理这种需求，把该领域出现的挑战以及为跟上新的研究以迎接这些挑战所必需的背景资料完美地结合在一起。...
计算机书籍
本书全面介绍了算法的数学分析中使用的基本方法，所涉及的内容来自经典的数学素材(包括离散数学、初等实分析、组合数学)，以及经典的计算机科学素材(包括算法和数据结构)。虽然书中论述了“最坏情形”和“复杂性问题”分析所需的基本数学工具，但是重点还是讨论“平均情形”或“概率”分析。论题涉及递归、生成函数、渐近性、树、串、映射等内容，以及对排序、树查找、串查找和散列诸算法的分析。.
尽管人们极为关注算法的数学分析，但是广泛使用的方法和模型方面的基本信息尚不能为该领域的工作和研究所直接使用。作者在本书中处理这种需求，把该领域出现的挑战以及为跟上新的研究以迎接这些挑战所必需的背景资料完美地结合在一起。...
作译者
Robert Sedgewick 斯坦福大学博士(导师为Donald E. Knuth)，普林斯顿大学计算机科学系教授，Adobe Systems公司董事，曾是Xerox PARC的研究人员，还曾就职于美国国防部防御分析研究所以及INRIA。.
Philippe Flajolet INRIA的高级研究主任，在Ecole Polytechnique和普林斯顿大学任教，并在斯坦福大学、智利大学和弗吉尼亚技术大学拥有访问席位。他还是法国科学院的通信会员。...
Philippe Flajolet INRIA的高级研究主任，在Ecole Polytechnique和普林斯顿大学任教，并在斯坦福大学、智利大学和弗吉尼亚技术大学拥有访问席位。他还是法国科学院的通信会员。...
目录
CHAPTER 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 Ouicksort
1.6 AsymptoticApproximations
1.7 Distributions
1.8 Probabilistic Algorithms
CHAPTER 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 Recurrences
CHAPTER THREE:GENERATING FUNCTIONS
3.1 Ordinary Generating Functions
3.2 Exponential Generating Functions
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 Ouicksort
1.6 AsymptoticApproximations
1.7 Distributions
1.8 Probabilistic Algorithms
CHAPTER 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 Recurrences
CHAPTER THREE:GENERATING FUNCTIONS
3.1 Ordinary Generating Functions
3.2 Exponential Generating Functions
前言
THIS book is intended to be a thorough overview of the primary techniques used in the mathematical analysis of algorithms. The material covered draws from classical mathematical topics, including discrete mathematics, elementary real analysis, and combinatorics, as well as from classical computer science topics, including algorithms and data structures. The focus is on "average-case" or "probabilistic" analysis, though the basic mathematical tools required for "worst-case" or "complexity" analysis are covered as well. .
We assume that the reader has some familiarity with basic concepts in both computer science and real analysis. In a nutshell, the reader should be able to both write programs and prove theorems; otherwise, the book is intended to be self-contained. Ample references to preparatory material in the literature are also provided. A planned companion volume will cover more advanced techniques. Together, the books are intended to cover the main techniques and to provide access to the growing research literature on the analysis of algorithms.
The book is meant to be used as a textbook in a junioror senior-level course on "Mathematical Analysis of Algorithms." It might also be useful in a course in discrete mathematics for computer scientists, since it covers basic techniques in discrete mathematics as well as combinatorics and basic properties of important discrete structures within a familiar context for computer science students. It is traditional to have somewhat broader coverage in such courses, but many instructors may find the approach here a useful way to engage students in a substantial portion ,of the material. The book also can be used to introduce students in mathematics and applied mathematics to principles from computer science related to algorithms and data structures.
Supplemented by papers from the literature, the book can serve as the basis for an introductory graduate course on the analysis of algorithms, or as a reference or basis for self-study by researchers in mathematics or computer science who want access to the literature in this field. It also might be of use to students and researchers in combinatorics and discrete mathematics, as a source of applications and techniques.
Despite the large literature on the mathematical analysis of algorithms, basic information on methods and models in widespread use has not been directly accessible to students and researchers in the field. This book aims to address this situation, bringing together a body of material intended to provide the reader with both an appreciation for the challenges of the field and the requisite background for learning the advanced tools being developed to meet these challenges.
Preparation. Mathematical maturity equivalent to one or two years' study at the college level is assumed. Basic courses in combinatorics and discrete mathematics may provide useful background (and may overlap with some material in the book), as would courses in real analysis, numerical methods, or elementary number theory. We draw on all of these areas, but summarize the necessary material here, with reference to standard texts for people who want more information.
Programming experience equivalent to one or two semesters' study at the college level, including elementary data structures, is assumed. We do: not dwell on programming and implementation issues, but algorithms and data structures are the central object of our studies. Again, our treatment is complete in the sense that we summarize basic information, with reference to standard texts and primary sources.
Access to a computer system for mathematical manipulation, such as MAPLE or Mathematica, is highly recommended. These systems can relieve one from tedious calculations when checking material in the text or solving exercises.
Related books. Related texts include The Art of Computer Programming by Knuth; Handbook of Algorithms and Data Structure by Gonnet and Baeza-Yates; Algorithms by Sedgewick; Concrete Mathematics by (3raham, Knuth and Patashnik; and Introduction to Algorithms by Cormen, Leiserson, and Rivest. This book could be considered supplementary to each of these, as examined below, in turn.
In spirit, this book is closest to the pioneering books by Knuth. Our focus is on mathematical techniques of analysis, though, whereas Knuth's books are broad and encyclopedic in scope, with properties of algorithms playing a primary role and methods of analysis a secondary role. This book can serve as basic preparation for the advanced results covered and referred to in Knuth's books.
We also cover approaches and results in the analysis of algorithms that have been developed since publication of Knuth's books. Gonnet and Baeza-Yates's Handbook is a thorough survey of such results, including a comprehensive bibliography; it primarily presents results with reference to derivations in the literature. Again, our book provides the basic preparation for access to this literature.
We also strive to keep the focus on covering algorithms of fundamental importance and interest, such as those described in Sedgewick's Algorithms, whereas Graham, Knuth, and Patashnik's Concrete Mathematics focuses almost entirely on mathematical techniques. This book is intended to be a link between the basic mathematical techniques discussed in Graham, Knuth, and Patashnik and the basic algorithms covered in Sedgewick. ..
Cormen, Leiserson, and Rivest's-Introduction to Algorithms is representative of a number of books that provide access to the research literature on "design and analysis" of algorithms, which is normally based on rough worst-case estimates of performance. When more precise results are desired (presumably for the most important methods), more sophisticated models and mathematical tools are required. Cormen, Leiserson, and Rivest focus on design of algorithms (usually with the goal of bounding worst-case performance), with analytic results used to help guide the design. Our book, on the other hand, is supplementary to theirs and similar books in that we focus on the analysis of algorithms, especially on techniques that can be used to develop detailed results that could be used to predict performance. In this process, we also consider relationships to various classical mathematical tools. Chapter 1 is devoted entirely to developing this context.
This book also lays the groundwork for a companion volume, Analytic Combinatorics, a general treatment that places the material here in a broader perspective and develops advanced methods and models that can serve as the basis for new research, not only in average-case analysis of algorithms but also in combinatorics. A higher level of mathematical maturity is assumed for that volume, perhaps at the senior or beginning graduate student level. Of course, careful study of this book is adequate preparation. It certainly has been our goal to make it sufficiently interesting that some readers will be inspired to tackle more advanced material!
How to use this book. Readers of this book are likely to have rather diverse backgrounds in discrete mathematics and computer science. With this in mind, it is useful to be aware the basic structure of book: eight chapters in all, an introductory chapter followed by three chapters emphasizing mathematical methods, then four chapters emphasizing applications in the analysis of algorithms:
INTRODUCTION
I. ANALYSIS OF ALGORITHMS
DISCRETE MATHEMATICAL METHODS
2. RECURRENCES
3. GENEP. ATINO FUNCTIONS
We assume that the reader has some familiarity with basic concepts in both computer science and real analysis. In a nutshell, the reader should be able to both write programs and prove theorems; otherwise, the book is intended to be self-contained. Ample references to preparatory material in the literature are also provided. A planned companion volume will cover more advanced techniques. Together, the books are intended to cover the main techniques and to provide access to the growing research literature on the analysis of algorithms.
The book is meant to be used as a textbook in a junioror senior-level course on "Mathematical Analysis of Algorithms." It might also be useful in a course in discrete mathematics for computer scientists, since it covers basic techniques in discrete mathematics as well as combinatorics and basic properties of important discrete structures within a familiar context for computer science students. It is traditional to have somewhat broader coverage in such courses, but many instructors may find the approach here a useful way to engage students in a substantial portion ,of the material. The book also can be used to introduce students in mathematics and applied mathematics to principles from computer science related to algorithms and data structures.
Supplemented by papers from the literature, the book can serve as the basis for an introductory graduate course on the analysis of algorithms, or as a reference or basis for self-study by researchers in mathematics or computer science who want access to the literature in this field. It also might be of use to students and researchers in combinatorics and discrete mathematics, as a source of applications and techniques.
Despite the large literature on the mathematical analysis of algorithms, basic information on methods and models in widespread use has not been directly accessible to students and researchers in the field. This book aims to address this situation, bringing together a body of material intended to provide the reader with both an appreciation for the challenges of the field and the requisite background for learning the advanced tools being developed to meet these challenges.
Preparation. Mathematical maturity equivalent to one or two years' study at the college level is assumed. Basic courses in combinatorics and discrete mathematics may provide useful background (and may overlap with some material in the book), as would courses in real analysis, numerical methods, or elementary number theory. We draw on all of these areas, but summarize the necessary material here, with reference to standard texts for people who want more information.
Programming experience equivalent to one or two semesters' study at the college level, including elementary data structures, is assumed. We do: not dwell on programming and implementation issues, but algorithms and data structures are the central object of our studies. Again, our treatment is complete in the sense that we summarize basic information, with reference to standard texts and primary sources.
Access to a computer system for mathematical manipulation, such as MAPLE or Mathematica, is highly recommended. These systems can relieve one from tedious calculations when checking material in the text or solving exercises.
Related books. Related texts include The Art of Computer Programming by Knuth; Handbook of Algorithms and Data Structure by Gonnet and Baeza-Yates; Algorithms by Sedgewick; Concrete Mathematics by (3raham, Knuth and Patashnik; and Introduction to Algorithms by Cormen, Leiserson, and Rivest. This book could be considered supplementary to each of these, as examined below, in turn.
In spirit, this book is closest to the pioneering books by Knuth. Our focus is on mathematical techniques of analysis, though, whereas Knuth's books are broad and encyclopedic in scope, with properties of algorithms playing a primary role and methods of analysis a secondary role. This book can serve as basic preparation for the advanced results covered and referred to in Knuth's books.
We also cover approaches and results in the analysis of algorithms that have been developed since publication of Knuth's books. Gonnet and Baeza-Yates's Handbook is a thorough survey of such results, including a comprehensive bibliography; it primarily presents results with reference to derivations in the literature. Again, our book provides the basic preparation for access to this literature.
We also strive to keep the focus on covering algorithms of fundamental importance and interest, such as those described in Sedgewick's Algorithms, whereas Graham, Knuth, and Patashnik's Concrete Mathematics focuses almost entirely on mathematical techniques. This book is intended to be a link between the basic mathematical techniques discussed in Graham, Knuth, and Patashnik and the basic algorithms covered in Sedgewick. ..
Cormen, Leiserson, and Rivest's-Introduction to Algorithms is representative of a number of books that provide access to the research literature on "design and analysis" of algorithms, which is normally based on rough worst-case estimates of performance. When more precise results are desired (presumably for the most important methods), more sophisticated models and mathematical tools are required. Cormen, Leiserson, and Rivest focus on design of algorithms (usually with the goal of bounding worst-case performance), with analytic results used to help guide the design. Our book, on the other hand, is supplementary to theirs and similar books in that we focus on the analysis of algorithms, especially on techniques that can be used to develop detailed results that could be used to predict performance. In this process, we also consider relationships to various classical mathematical tools. Chapter 1 is devoted entirely to developing this context.
This book also lays the groundwork for a companion volume, Analytic Combinatorics, a general treatment that places the material here in a broader perspective and develops advanced methods and models that can serve as the basis for new research, not only in average-case analysis of algorithms but also in combinatorics. A higher level of mathematical maturity is assumed for that volume, perhaps at the senior or beginning graduate student level. Of course, careful study of this book is adequate preparation. It certainly has been our goal to make it sufficiently interesting that some readers will be inspired to tackle more advanced material!
How to use this book. Readers of this book are likely to have rather diverse backgrounds in discrete mathematics and computer science. With this in mind, it is useful to be aware the basic structure of book: eight chapters in all, an introductory chapter followed by three chapters emphasizing mathematical methods, then four chapters emphasizing applications in the analysis of algorithms:
INTRODUCTION
I. ANALYSIS OF ALGORITHMS
DISCRETE MATHEMATICAL METHODS
2. RECURRENCES
3. GENEP. ATINO FUNCTIONS
