Александр Соловьев - ДИСКРЕТНАЯ МАТЕМАТИКА БЕЗ ФОРМУЛ
На нашем сайте KnigaRead.com Вы можете абсолютно бесплатно читать книгу онлайн Александр Соловьев, "ДИСКРЕТНАЯ МАТЕМАТИКА БЕЗ ФОРМУЛ" бесплатно, без регистрации.
ПОСЛЕСЛОВИЕ
Самой первой NP–полной задачей стала задача нахождения клик графа, то есть полных подграфов данного графа с конкретным числом вершин…
Но в середине семидесятых годов были опубликованы так называемые "алгоритмы Магу", которые исключили из числа переборных не только задачи типа «восьми ферзей» (прежде стандартный полигон для эвристических алгоритмов «искусственного интеллекта»), но там и клики графа также находятся с помощью несложных манипуляций на уровне алгебры высказываний (преобразования выражения к ДНФ), что ни как не выше полиномиальной сложности.
Мало радости признаваться в собственной бестолковости и некомпетентности, но проблема трудно решаемых задач для меня существует в несколько извращенном виде.
