Год выпуска: 2011 Автор: Anatoly Plotnikov Издательство: LAP Lambert Academic Publishing Страниц: 152 ISBN: 9783844393460
Описание
Problems of the class NP — it's almost all problems solved on the computer. Therefore, this is extremely important and actually to research the properties of such problems and to construct their mathematical models, which allows in a number of cases to improve the solution algorithms or propose new ones. In studying the problems of the class NP we focused on the NP-complete problems, the researching their properties and constructing models. We construct a mathematical model of constructive combinatorial problems, clarify the concept of a class of problems solved by a non-deterministic Turing machine and define the concept of the problem without foresight, investigate the set-theoretic properties of extreme combinatorial problems. We offer the polynomial-time algorithm for the maxumum independent set problem based on a hypotheses. Also, we find a criterion for Hamiltonicity of a graph and consider some covering problems. This book should be especially useful to professionals in...
