Introduction to Algorithm Analysis
The task of this book is simple: to analyze the "ideas" underlying the programs and show how to prove their correctness. How to mathematically prove that a given algorithm does what it is supposed to do? And why is it so important? The correctness of classical algorithms is proved: integer division, Euclid's algorithm, ranking, etc. In addition to traditional algorithms such as greedy algorithms, dynamic programming algorithms and divide-and-conquer algorithms, the book also explores randomized and online algorithms. The former have become ubiquitous due to the advent of cryptography, and the latter are necessary in many areas, from operating systems to the stock market. The book is littered with tasks. Most of the tasks are theoretical, but many require the implementation of an algorithm; the Python 3 programming language is used for such tasks. Despite its brevity, the publication is mathematically rigorous. A preliminary acquaintance with discrete mathematics is desirable. The publication is intended for university students, specialists in the field of computer science and mathematics, as well as a wide range of programmers and developers.
No reviews found
