The book "Algorithms: development and application. Classic Computer Science »
Hi, Habrozhiteli! We have a new product:
For the first time, one of the most authoritative books on the development and use of algorithms is published in Russian. Algorithms are the basis of programming that determines how software will use data structures.
You will get acquainted with the basic aspects of building algorithms, basic concepts and definitions, data structures, then go to the basic methods of constructing algorithms, undecidability and methods for solving unsolvable problems, and, finally, learn the randomization when designing algorithms. The most complex topics are explained with clear and simple examples, so the book can be used for self-study by students, as well as by research scientists or computer technology professionals who want to get an idea of the application of certain algorithms design techniques.
')
Algorithmic analysis consists of two fundamental components: the allocation of a mathematically pure kernel of the problem and the identification of methods for designing a suitable algorithm based on the structure of the problem. And the better an analyst owns the full arsenal of possible design methods, the sooner he begins to recognize the “pure” formulations that underlie the intricate real-world tasks.
Algorithmic problems form the core of computer science, but they rarely appear in the form of neatly packed, mathematically exact questions. More often, they are burdened with many troublesome details tied to a specific case; some of these details are important, others are redundant. As a result, algorithmic analysis consists of two fundamental components: identifying a mathematically pure kernel of the problem and identifying methods for designing a suitable algorithm based on the structure of the problem. These two components are interrelated: the better the analyst has a full arsenal of possible design methods, the faster he begins to recognize the “pure” formulations that underlie the intricate real-world tasks. Thus, when used with maximum efficiency, algorithmic ideas do not simply provide solutions to clearly defined tasks — they form the language for clearly expressing the questions underlying them.
The purpose of this book is to convey to the reader this approach to algorithms in the form of a design process that begins with tasks that occur across the entire range of computational applications, uses a good understanding of algorithm design methods, and the end result is the development of effective solutions to such problems. We will study the role of algorithmic ideas in computer science in general and will try to connect these ideas with a range of precisely formulated problems, for the solution of which algorithms are designed and analyzed. In other words, what reasons make us look for the solution of these problems and how do we choose concrete ways of formulating them? How do we know which design principles are relevant in a given situation?
Based on the above, we tried to show how to identify “pure” formulations of algorithmic problems in complex computational areas and how to design effective algorithms based on these formulations for solving the obtained problems. In order to understand the complex algorithm, it is often easiest to reconstruct a sequence of ideas (including unsuccessful approaches and deadlocks) that led from the original simplified methods to a solution worked out over time. This is how the presentation style was formed, which does not lead the reader to formulate the problem directly to the algorithm and, in our opinion, better reflects how we and our colleagues approach the solution of such problems.
The book is intended for students who have undergone a two-semester introductory course on computational technologies (standard course "CS1 / CS2"), during which they wrote programs for implementing basic algorithms, and working with data structures such as trees and graphs, as well as with basic data structures (arrays, lists, queues, and stacks). Since the transition between this course and the first course in algorithms has not yet become standard, the book opens with a presentation to those familiar to students of some educational institutions in CS1 / CS2, but in other institutions are included in the first-year curriculum in algorithms. Accordingly, this part can be considered either as a review or as a new material; including it, we hope that the book can be used in a wider range of training courses and with greater flexibility regarding the basic knowledge required for the reader.
In accordance with the described approach, we develop basic methods for designing algorithms, studying problems from many areas of computer science and related fields. In particular, fairly detailed descriptions of possible applications from systems and networks (caching, switching, interdomain routing on the Internet), artificial intelligence (planning, games, Hopfield networks), pattern recognition (image segmentation), information extraction (point detection transition, clustering), operations research (air traffic planning) and computational biology (sequence alignment, secondary structure of RNA).
The concept of computational undecidability and NP-completeness in particular plays a significant role in the book. This corresponds to our approach to the overall design process of the algorithm. Sometimes an interesting problem arising in the practical field has an effective solution, and sometimes it turns out to be provably NP-complete; For a full-fledged approach to solving a new algorithmic problem, you should be able to explore both options with equal certainty. Since so many natural tasks in computer science are NP-complete, the development of mechanisms for working with unsolvable problems has become a key factor in the study of algorithms, and this topic is widely presented in the book. The conclusion that the problem is NP-complete should be taken not as the end of the study, but as an invitation to search for approximation algorithms, methods of heuristic local search or solvable special cases. Each of these three approaches is widely considered in the book.
In order to simplify work with such tasks, each chapter includes the section “Exercises with solutions”, in which we take one or several tasks and describe in detail the process of finding a solution. For this reason, the discussion of each exercise with a solution is much longer than the simple recording of a complete, correct solution (in other words, much longer than it was necessary for a complete solution if the task was given to the student for an independent solution). As in the rest of the book, the discussions in these sections should give the reader an idea of the larger processes used to solve problems of this type and ultimately lead to an exact solution.
It is worth mentioning two more circumstances related to the use of these tasks for independent work in training courses. First, the tasks are ordered in an approximately increasing order of difficulty, but this is only an approximate guideline, and we are not advised to pay too much attention to it; Since the bulk of the tasks were designed for students to work independently, large subsets of tasks in each chapter are rather closely related in terms of complexity. Secondly, apart from the initial chapters, we will have to work on solving these problems, both in order to link the description of the problem with the algorithmic methods described in the chapter, and for the direct design of the algorithm. In our training course, we assigned about three such tasks for a week.
In addition to the tasks and exercises with solutions, this book uses a number of other educational aspects, as well as additions that simplify its use for educational purposes.
As mentioned earlier, many sections in the book are devoted to formulating an algorithmic problem (including its history and motivation to find a solution), designing and analyzing an algorithm for solving it. In accordance with this style, such sections have a single structure, including a sequence of subsections: “Task” with a description of the task and its exact wording; “Algorithm design” using suitable methods for algorithm development; and "Analysis of the algorithm" with the proof of the properties of the algorithm and analysis of its effectiveness. In cases where extensions of the problem are considered or additional analysis of the algorithm is given, additional subsections are included. The purpose of this structure is to introduce a relatively general style of presentation, which proceeds from the initial discussion of the problem arising in the computational domain, to a detailed analysis of methods for solving it.
Chapter 1 begins with a presentation of some typical algorithmic problems. We begin with the problem of stable matchings, because it allows us to define the basic aspects of algorithm development more specifically and elegantly than any abstract reasoning: the search for stable matchings is conditioned by a natural, albeit complex, practical area, on the basis of which we can abstract an interesting formulation of the problem and an unexpectedly efficient algorithm for solving it. In the remainder of chapter 1, five “typical tasks” are considered, which predetermine the topics from the remainder of the course. These five tasks are interrelated in the sense that all of them can be considered as variations and / or special cases of the task of searching for an independent set; but one problem can be solved with the help of a “greedy” algorithm, another - by dynamic programming, the third - by finding the flow in the network, the fourth (the actual set of the independent set) is NP-complete, and the fifth - PSPACE-complete. The fact that closely related tasks can vary considerably in complexity plays an important role in the book, and these five tasks serve as reference points, to which we repeatedly return as we present the material.
Chapters 2 and 3 help to link the material to the CS1 / CS2 course, discussed above. Chapter 2 introduces the key mathematical definitions and concepts used in the analysis of algorithms, as well as the motivation for their application. The chapter begins with an informal review of what is meant by the computational solvability of a problem, as well as the concept of polynomial time as a formal criterion of efficiency. Then questions of the growth rate of functions and asymptotic analysis are considered more formally, information is given on the functions that are often encountered in the analysis of algorithms, as well as on their standard applications. Chapter 3 discusses the basic definitions and algorithmic primitives needed to work with graphs and which are central to many of the book’s tasks. By the end of the CS1 / CS2 training course, students implement many basic graph theory algorithms, but it is useful to present this material in the wider context of algorithm design. In particular, we consider basic graph definitions, graph traversal methods (width traversal and depth traversal), and basic concepts of directed graphs, including strong connectivity and topological ordering.
Chapters 2 and 3 also present many of the basic data structures used to implement the algorithms in the book; more complex data structures are described in subsequent chapters. Our approach to data structures is to represent them when they are needed to implement the algorithms described in the book. Thus, although many data structures will already be familiar to students in the CS1 / CS2 course, we will consider them in the wider context of designing and analyzing algorithms.
Chapters 4–7 discuss four basic methods for designing algorithms: greedy algorithms, the principle of “divide and power-wui”, dynamic programming, and finding the flow in the network. With greedy algorithms, it is important to understand when they are working and when not; Our consideration of this topic is based on the classification method of the algorithms used to prove the correctness of the work of the greedy algorithms. The chapter concludes with an overview of the main applications of greedy algorithms for finding the shortest paths, directional and non-directional spanning trees, grouping and compression. The discussion of the “divide and conquer” method begins with a review of recurrence relations strategies as limits for execution time; then we will show how knowledge of these recurrent relations can control the design of algorithms that exceed straightforward solutions of many basic problems, including comparing estimates, finding the closest pairs of points on a plane, and the fast Fourier transform. Familiarity with dynamic programming begins with an intuitive recursion on which it is based, with the subsequent development of more and more expressive formulas through applications in which they naturally occur. Finally, we consider the algorithms for the problems of finding a stream in the network; Most of this chapter will be devoted to a variety of practical applications of these streams. To the extent that online streams are covered in algorithmic training courses, students often do not sufficiently well represent the wide range of tasks to which they can be applied; we will try to pay tribute to their flexibility and present the use of streams for load distribution, scheduling, image segmentation, and a number of other tasks.
Chapters 8 and 9 are devoted to the concept of computational undecidability. They focus on NP-completeness; Basic NP-complete tasks are categorized to help students identify possible cuts when new tasks are discovered. We will come to fairly complex proofs of NP-completeness, with recommendations on how to approach the construction of complex abbreviations. Also, types of computational complexity beyond NP-completeness, especially in the PSPACE-completeness area, will be considered. This useful concept emphasizes that insolvability does not end in NP-completeness; PSPACE completeness also lays the foundation for central concepts from the field of artificial intelligence (planning and playing games), which without it would not have been reflected in the algorithmic domain under consideration.
Chapters 10 through 12 deal with three basic methods for working with computationally intractable problems: identifying structured special cases, approximation algorithms, and local search heuristics. The chapter on solvable special cases shows that instances of NP-complete problems encountered in practice may not be so difficult in the worst cases, because they often contain a structure that can be used to design an efficient algorithm. We will show that NP-complete problems are often successfully solved if we confine ourselves to the input data having a tree structure. The topic ends with a detailed discussion of the decomposition of graphs into a tree. Although this topic is more suitable for graduation courses, it has significant practical value for which it is difficult to find more accessible material. In the chapter devoted to approximation algorithms, the process of designing efficient algorithms and the problem of analyzing the optimal solution for constructing good estimates are considered. As for the methods of designing approximation algorithms, we focus on greedy algorithms, linear programming and the third method, which will be called “pricing”, using the ideas of the first two. Finally, we consider the local search heuristics, including the Metropolis algorithm and the model quenching method. This topic is often not considered in the middle level algorithmic courses, because very little is known about provable guarantees of such algorithms; however, given their wide practical distribution, we believe that it will be useful for students to know about them. Descriptions of cases for which there are demonstrable warranties are also included.
Chapter 13 discusses the use of randomization in the design of algorithms. Several good books have been written on this topic. Here we will try to provide a more compact introduction to some of the methods of applying randomization methods, based on information that is usually included in training courses in discrete mathematics of the middle level.
John Kleinberg (Jon Kleinberg) - Professor of Computer Systems Theory at Cornell University. He received his doctorate from the Massachusetts Institute of Technology in 1996.
Kleinberg's studies are devoted to algorithms, primarily related to the structure of networks and information, and their practical applications in the field of computer technology, optimization, data analysis and computational biology. His work on network analysis has helped lay the foundation for the current generation of Internet search engines.
Eva Tardos is a professor of computer systems theory at Cornell University. Received a doctorate degree at Ötvös University in Budapest (Hungary) in 1984. Member of the American Academy of Arts and Sciences and the Computer Engineering Association of the USA.
The scientific interests of Tardos are related to the design and analysis of algorithms for solving problems from graph and network theory. Her works in the field of network flow algorithms and approximating algorithms for solving network problems are best known. Her recent work has been devoted to algorithmic game theory.
More information about the book can be found on the publisher's website.
Table of contents
Excerpt
For Habrozhiteley a 25% discount on the coupon - Algorithms
For the first time, one of the most authoritative books on the development and use of algorithms is published in Russian. Algorithms are the basis of programming that determines how software will use data structures.You will get acquainted with the basic aspects of building algorithms, basic concepts and definitions, data structures, then go to the basic methods of constructing algorithms, undecidability and methods for solving unsolvable problems, and, finally, learn the randomization when designing algorithms. The most complex topics are explained with clear and simple examples, so the book can be used for self-study by students, as well as by research scientists or computer technology professionals who want to get an idea of the application of certain algorithms design techniques.
')
Algorithmic analysis consists of two fundamental components: the allocation of a mathematically pure kernel of the problem and the identification of methods for designing a suitable algorithm based on the structure of the problem. And the better an analyst owns the full arsenal of possible design methods, the sooner he begins to recognize the “pure” formulations that underlie the intricate real-world tasks.
Algorithmic problems form the core of computer science, but they rarely appear in the form of neatly packed, mathematically exact questions. More often, they are burdened with many troublesome details tied to a specific case; some of these details are important, others are redundant. As a result, algorithmic analysis consists of two fundamental components: identifying a mathematically pure kernel of the problem and identifying methods for designing a suitable algorithm based on the structure of the problem. These two components are interrelated: the better the analyst has a full arsenal of possible design methods, the faster he begins to recognize the “pure” formulations that underlie the intricate real-world tasks. Thus, when used with maximum efficiency, algorithmic ideas do not simply provide solutions to clearly defined tasks — they form the language for clearly expressing the questions underlying them.
The purpose of this book is to convey to the reader this approach to algorithms in the form of a design process that begins with tasks that occur across the entire range of computational applications, uses a good understanding of algorithm design methods, and the end result is the development of effective solutions to such problems. We will study the role of algorithmic ideas in computer science in general and will try to connect these ideas with a range of precisely formulated problems, for the solution of which algorithms are designed and analyzed. In other words, what reasons make us look for the solution of these problems and how do we choose concrete ways of formulating them? How do we know which design principles are relevant in a given situation?
Based on the above, we tried to show how to identify “pure” formulations of algorithmic problems in complex computational areas and how to design effective algorithms based on these formulations for solving the obtained problems. In order to understand the complex algorithm, it is often easiest to reconstruct a sequence of ideas (including unsuccessful approaches and deadlocks) that led from the original simplified methods to a solution worked out over time. This is how the presentation style was formed, which does not lead the reader to formulate the problem directly to the algorithm and, in our opinion, better reflects how we and our colleagues approach the solution of such problems.
General information
The book is intended for students who have undergone a two-semester introductory course on computational technologies (standard course "CS1 / CS2"), during which they wrote programs for implementing basic algorithms, and working with data structures such as trees and graphs, as well as with basic data structures (arrays, lists, queues, and stacks). Since the transition between this course and the first course in algorithms has not yet become standard, the book opens with a presentation to those familiar to students of some educational institutions in CS1 / CS2, but in other institutions are included in the first-year curriculum in algorithms. Accordingly, this part can be considered either as a review or as a new material; including it, we hope that the book can be used in a wider range of training courses and with greater flexibility regarding the basic knowledge required for the reader.
In accordance with the described approach, we develop basic methods for designing algorithms, studying problems from many areas of computer science and related fields. In particular, fairly detailed descriptions of possible applications from systems and networks (caching, switching, interdomain routing on the Internet), artificial intelligence (planning, games, Hopfield networks), pattern recognition (image segmentation), information extraction (point detection transition, clustering), operations research (air traffic planning) and computational biology (sequence alignment, secondary structure of RNA).
The concept of computational undecidability and NP-completeness in particular plays a significant role in the book. This corresponds to our approach to the overall design process of the algorithm. Sometimes an interesting problem arising in the practical field has an effective solution, and sometimes it turns out to be provably NP-complete; For a full-fledged approach to solving a new algorithmic problem, you should be able to explore both options with equal certainty. Since so many natural tasks in computer science are NP-complete, the development of mechanisms for working with unsolvable problems has become a key factor in the study of algorithms, and this topic is widely presented in the book. The conclusion that the problem is NP-complete should be taken not as the end of the study, but as an invitation to search for approximation algorithms, methods of heuristic local search or solvable special cases. Each of these three approaches is widely considered in the book.
In order to simplify work with such tasks, each chapter includes the section “Exercises with solutions”, in which we take one or several tasks and describe in detail the process of finding a solution. For this reason, the discussion of each exercise with a solution is much longer than the simple recording of a complete, correct solution (in other words, much longer than it was necessary for a complete solution if the task was given to the student for an independent solution). As in the rest of the book, the discussions in these sections should give the reader an idea of the larger processes used to solve problems of this type and ultimately lead to an exact solution.
It is worth mentioning two more circumstances related to the use of these tasks for independent work in training courses. First, the tasks are ordered in an approximately increasing order of difficulty, but this is only an approximate guideline, and we are not advised to pay too much attention to it; Since the bulk of the tasks were designed for students to work independently, large subsets of tasks in each chapter are rather closely related in terms of complexity. Secondly, apart from the initial chapters, we will have to work on solving these problems, both in order to link the description of the problem with the algorithmic methods described in the chapter, and for the direct design of the algorithm. In our training course, we assigned about three such tasks for a week.
Learning aspects and additions
In addition to the tasks and exercises with solutions, this book uses a number of other educational aspects, as well as additions that simplify its use for educational purposes.
As mentioned earlier, many sections in the book are devoted to formulating an algorithmic problem (including its history and motivation to find a solution), designing and analyzing an algorithm for solving it. In accordance with this style, such sections have a single structure, including a sequence of subsections: “Task” with a description of the task and its exact wording; “Algorithm design” using suitable methods for algorithm development; and "Analysis of the algorithm" with the proof of the properties of the algorithm and analysis of its effectiveness. In cases where extensions of the problem are considered or additional analysis of the algorithm is given, additional subsections are included. The purpose of this structure is to introduce a relatively general style of presentation, which proceeds from the initial discussion of the problem arising in the computational domain, to a detailed analysis of methods for solving it.
Summary
Chapter 1 begins with a presentation of some typical algorithmic problems. We begin with the problem of stable matchings, because it allows us to define the basic aspects of algorithm development more specifically and elegantly than any abstract reasoning: the search for stable matchings is conditioned by a natural, albeit complex, practical area, on the basis of which we can abstract an interesting formulation of the problem and an unexpectedly efficient algorithm for solving it. In the remainder of chapter 1, five “typical tasks” are considered, which predetermine the topics from the remainder of the course. These five tasks are interrelated in the sense that all of them can be considered as variations and / or special cases of the task of searching for an independent set; but one problem can be solved with the help of a “greedy” algorithm, another - by dynamic programming, the third - by finding the flow in the network, the fourth (the actual set of the independent set) is NP-complete, and the fifth - PSPACE-complete. The fact that closely related tasks can vary considerably in complexity plays an important role in the book, and these five tasks serve as reference points, to which we repeatedly return as we present the material.
Chapters 2 and 3 help to link the material to the CS1 / CS2 course, discussed above. Chapter 2 introduces the key mathematical definitions and concepts used in the analysis of algorithms, as well as the motivation for their application. The chapter begins with an informal review of what is meant by the computational solvability of a problem, as well as the concept of polynomial time as a formal criterion of efficiency. Then questions of the growth rate of functions and asymptotic analysis are considered more formally, information is given on the functions that are often encountered in the analysis of algorithms, as well as on their standard applications. Chapter 3 discusses the basic definitions and algorithmic primitives needed to work with graphs and which are central to many of the book’s tasks. By the end of the CS1 / CS2 training course, students implement many basic graph theory algorithms, but it is useful to present this material in the wider context of algorithm design. In particular, we consider basic graph definitions, graph traversal methods (width traversal and depth traversal), and basic concepts of directed graphs, including strong connectivity and topological ordering.
Chapters 2 and 3 also present many of the basic data structures used to implement the algorithms in the book; more complex data structures are described in subsequent chapters. Our approach to data structures is to represent them when they are needed to implement the algorithms described in the book. Thus, although many data structures will already be familiar to students in the CS1 / CS2 course, we will consider them in the wider context of designing and analyzing algorithms.
Chapters 4–7 discuss four basic methods for designing algorithms: greedy algorithms, the principle of “divide and power-wui”, dynamic programming, and finding the flow in the network. With greedy algorithms, it is important to understand when they are working and when not; Our consideration of this topic is based on the classification method of the algorithms used to prove the correctness of the work of the greedy algorithms. The chapter concludes with an overview of the main applications of greedy algorithms for finding the shortest paths, directional and non-directional spanning trees, grouping and compression. The discussion of the “divide and conquer” method begins with a review of recurrence relations strategies as limits for execution time; then we will show how knowledge of these recurrent relations can control the design of algorithms that exceed straightforward solutions of many basic problems, including comparing estimates, finding the closest pairs of points on a plane, and the fast Fourier transform. Familiarity with dynamic programming begins with an intuitive recursion on which it is based, with the subsequent development of more and more expressive formulas through applications in which they naturally occur. Finally, we consider the algorithms for the problems of finding a stream in the network; Most of this chapter will be devoted to a variety of practical applications of these streams. To the extent that online streams are covered in algorithmic training courses, students often do not sufficiently well represent the wide range of tasks to which they can be applied; we will try to pay tribute to their flexibility and present the use of streams for load distribution, scheduling, image segmentation, and a number of other tasks.
Chapters 8 and 9 are devoted to the concept of computational undecidability. They focus on NP-completeness; Basic NP-complete tasks are categorized to help students identify possible cuts when new tasks are discovered. We will come to fairly complex proofs of NP-completeness, with recommendations on how to approach the construction of complex abbreviations. Also, types of computational complexity beyond NP-completeness, especially in the PSPACE-completeness area, will be considered. This useful concept emphasizes that insolvability does not end in NP-completeness; PSPACE completeness also lays the foundation for central concepts from the field of artificial intelligence (planning and playing games), which without it would not have been reflected in the algorithmic domain under consideration.
Chapters 10 through 12 deal with three basic methods for working with computationally intractable problems: identifying structured special cases, approximation algorithms, and local search heuristics. The chapter on solvable special cases shows that instances of NP-complete problems encountered in practice may not be so difficult in the worst cases, because they often contain a structure that can be used to design an efficient algorithm. We will show that NP-complete problems are often successfully solved if we confine ourselves to the input data having a tree structure. The topic ends with a detailed discussion of the decomposition of graphs into a tree. Although this topic is more suitable for graduation courses, it has significant practical value for which it is difficult to find more accessible material. In the chapter devoted to approximation algorithms, the process of designing efficient algorithms and the problem of analyzing the optimal solution for constructing good estimates are considered. As for the methods of designing approximation algorithms, we focus on greedy algorithms, linear programming and the third method, which will be called “pricing”, using the ideas of the first two. Finally, we consider the local search heuristics, including the Metropolis algorithm and the model quenching method. This topic is often not considered in the middle level algorithmic courses, because very little is known about provable guarantees of such algorithms; however, given their wide practical distribution, we believe that it will be useful for students to know about them. Descriptions of cases for which there are demonstrable warranties are also included.
Chapter 13 discusses the use of randomization in the design of algorithms. Several good books have been written on this topic. Here we will try to provide a more compact introduction to some of the methods of applying randomization methods, based on information that is usually included in training courses in discrete mathematics of the middle level.
About the authors
John Kleinberg (Jon Kleinberg) - Professor of Computer Systems Theory at Cornell University. He received his doctorate from the Massachusetts Institute of Technology in 1996.
Kleinberg's studies are devoted to algorithms, primarily related to the structure of networks and information, and their practical applications in the field of computer technology, optimization, data analysis and computational biology. His work on network analysis has helped lay the foundation for the current generation of Internet search engines.
Eva Tardos is a professor of computer systems theory at Cornell University. Received a doctorate degree at Ötvös University in Budapest (Hungary) in 1984. Member of the American Academy of Arts and Sciences and the Computer Engineering Association of the USA.
The scientific interests of Tardos are related to the design and analysis of algorithms for solving problems from graph and network theory. Her works in the field of network flow algorithms and approximating algorithms for solving network problems are best known. Her recent work has been devoted to algorithmic game theory.
More information about the book can be found on the publisher's website.
Table of contents
Excerpt
For Habrozhiteley a 25% discount on the coupon - Algorithms
Source: https://habr.com/ru/post/278821/
All Articles