Название: Algorithms: A Top-Down ApproachАвтор: Rodney R. Howell
Издательство: World Scientific Publishing
Год: 2023
Страниц: 611
Язык: английский
Формат: pdf (true)
Размер: 22.3 MB
This comprehensive compendium provides a rigorous framework to tackle the daunting challenges of designing correct and efficient algorithms. It gives a uniform approach to the design, analysis, optimization, and verification of algorithms. The volume also provides essential tools to understand algorithms and their associated data structures. This useful reference text describes a way of thinking that eases the task of proving algorithm correctness. Working through a proof of correctness reveals an algorithm's subtleties in a way that a typical description does not. Algorithm analysis is presented using careful definitions that make the analyses mathematically rigorous.
This book is motivated in part by the author’s belief that people do not fully understand an algorithm until they are able to prove its correctness. For this reason, all of Chapter 2 and much of Chapter 4 are devoted to techniques for proving correctness. Outside of these two chapters, however, very few correctness proofs are given, as they would needlessly clutter the presentation with tedious details. Instead, all algorithms are presented in such a way as to facilitate a correctness proof. The particular approach used is top-down. This approach fits well with mathematical techniques of induction, proving loop invariants, and applying previously-shown theorems. By having an understanding of the mechanics of proving correctness, readers are equipped to gain a thorough understanding of an algorithm presented in a top-down way.
Algorithms are presented in a pseudo language defined with enough rigor to facilitate both performance analyses and correctness proofs. The essence of an algorithm is not tied to a particular programming language; hence, we have chosen a computational model and corresponding notation that we feel are appropriate for communicating algorithms to humans.
This text contains sufficient material for both an advanced undergraduate course and an introductory graduate-level course on the design and analysis of algorithms.
Prerequisite Material:
This book is intended to be reasonably self-contained. However, a certain degree of maturity is assumed regarding the audience. Readers are expected to have enough experience in writing programs so as to be able to understand algorithms presented in a pseudo language. Experience with basic data structures, including stacks, queues, lists, and trees, will be helpful, as will experience in manipulating finite and infinite sums, solving recurrences, and performing combinatorial analyses. Though calculus and number theory are used occasionally, background in these fields of study is not assumed.
Скачать Algorithms: A Top-Down Approach