Theory of algorithms and computations. Educational guide
Please sign in so that we can notify you about a reply
The first part introduces the theory of algorithms (often also referred to as the theory of computable functions or simply computability theory). Various approaches to its construction are outlined, based on the use of the theory of recursive functions, Turing machines, Post and Minsky machines, infinite abacus, Markov algorithms, and the exotic language Fractran proposed by Conway. Classic examples of algorithmically unsolvable problems are presented. The second part covers the basics of the theory of NP-complete problems. The NP-completeness of a number of classic combinatorial problems of exhaustive nature is proven, such as the satisfiability problem of logical formulas, the traveling salesman problem, the knapsack problem, the coin change problem, the minimum covering and maximum clique problems, and others. Exact and approximate algorithms for solving these problems are discussed. At the end of each part, a list of tasks complementing its content is provided. Some of them include solution hints. The book is based on a semester-long course taught by the author at the Faculty of Mathematics and Computer Science of the Baku branch of Moscow State University named after M.V. Lomonosov.
Author:
Author:Gashkov Sergey Borisovich
Cover:
Cover:hardcover
Category:
- Category:Education & Teaching
- Category:Science & Math
Dimensions:
Dimensions:24.3x17.5x1.4 cm
Series:
Series:Computers and Software
ISBN:
ISBN:978-5-507-46897-3
No reviews found