دانلود کتاب مقدمه‌ای بر تحلیل الگوریتم‌ها، جلد چهارم

This book is a short introduction to algorithms, which are the methods whereby we assign intellectual work to machines. Given a computational problem, an algorithm is a procedure to solve it; this procedure is usually implemented in a programming language, such as Python, to be run on a computer. We present two intertwined concepts related to algorithms: design technique, such as Greedy or Dynamic Programming; and analysis, such as performance or correctness. Both are essential: we solve a problem by designing an algorithm, but we justify our solution by analyzing the algorithm. The intended audience for this book consists of both undergraduate and graduate students in Computer Science and Mathematics, but since the presentation is self-contained, i.e., all background is given, this book can serve as an introduction to algorithms for anyone. We begin this book with a chapter of preliminaries, where we introduce the framework of pre/post-conditions and loop invariants. We illustrate the framework by proving the correctness of some classical algorithms, such as Euclid’s procedure for computing the greatest common divisor of two numbers. We conclude the preliminaries with three ranking algorithms: Stable Marriage, PageRank and Pairwise Comparisons. As ranking comes naturally to the human mind, and ranking procedures are practical, this is a fitting way to start a foray into algorithms. We present three standard algorithm design techniques in eponymous chapters: greedy algorithms, dynamic programming and the divide and conquer paradigm. We are concerned with correctness of algorithms, rather than, say, efficiency or the underlying data structures. For example, in the chapter on the greedy paradigm we explore in depth the idea of a promising partial solution, a powerful technique for proving the correctness of greedy algorithms. We include online algorithms and competitive analysis, as well as randomized algorithms with a section on cryptography. The chapter on parallel algorithms is based on Linear Algebra. While Calculus has become the standard for assessing mathematical maturity at the university undergraduate level, Linear Algebra is perhaps even more useful as a tool for engineering and computation. We bring an advanced approach to Linear Algebra through algorithms that deploy parallelism in order to compute the standard constructions, e.g., the determinant or characteristic polynomial of a matrix. The fourth edition of the book added a chapter on Machine Learning, Chapter 8. Machine Learning is now pervasive, and since the advent of the cloud, anyone has access to the compute (and storage) resources needed to train models. It inverts the classical paradigm of rule-based algorithms to algorithms trained on large amounts of data. The book finishes with two foundational chapters. The first one is an exposition of the basics of the theory of computation. We approach this field through manipulations of strings; thus, we present Finite Automata and Turing Machines as implementations of rules for transforming strings. The second foundational chapter covers the mathematical basics for this book; the reader unfamiliar with discrete mathematics is encouraged to start with this chapter (Chapter 10) and do all the problems therein. Algorithms solve problems, and many of the problems in this book fall under the category of optimization problems, whether cost minimization, such as Kruskal’s algorithm for computing minimum cost spanning trees—Section 2.1, or profit maximization, such as selecting the most profitable subset of activities—Section 4.4. The book is sprinkled with exercises (problems), many theoretical, but a significant number require an implementation of an algorithm in Python; consider the following introductions to Python: [Dierbach (2013)] or [Downey (2015)]1. The Python programming language is relatively easy, especially for short snippets of code. The solutions to most problems are included in the “Answers to selected problems” at the end of each chapter. The solutions to most of the programming exercises will be available for download from GitHub.2 This book draws on many sources. First of all, [Cormen et al. (2009)] is a fantastic reference for anyone who is learning algorithms. I have also used as reference the elegantly written [Kleinberg and Tardos (2006)]. A classic in the field is [Knuth (1997)], and I base my presentation of online algorithms on the material in [Borodin and El-Yaniv (1998)]. I have learned greedy algorithms, dynamic programming and logic from Stephen A. Cook at the University of Toronto. Section 10.3, a digest of relations, is based on lectures given by Ryszard Janicki in 2008 at McMaster University. Section 10.4 is based on logic lectures by Stephen A. Cook taught at the University of Toronto in the 1990s. I am grateful to Ryan McIntyre who proofread the 3rd edition manuscript, and updated the Python solutions, during the summer of 2017, and to Rishikesh Patil who proof-read the 4th edition during the summer of 2024. I am grateful to the many students who improved the manuscript by reading it carefully and pointing out typos, omissions, errors and gaps, including Skyler Atchison, Greg Herman, and Christopher Kuske. As stated at the beginning of this Preface, we aim to present a concise, mathematically rigorous, introduction to the beautiful field of Algorithms. I agree strongly with [Su (2010)] that the purpose of education is to cultivate the yawp: “I sound my barbaric yawp over the root(top)s of the world!” words of John Keating, quoting a Walt Whitman poem ([Whitman (1892)]), in the movie Dead Poets Society. This yawp is the deep yearning inside each of us for an aesthetic experience ([Scruton (2011)]). Hopefully, this book will supply a yawp or two.