Cтраница 2
Содержательно эта проблема состоит в том, чтобы по произвольной конъюнктивной нормальной форме ( определение КНФ см. в § 8 гл. Ясно, что проблему ВЫПОЛНИМОСТЬ можно решить тривиальным алгоритмом, перебирая для заданной КНФ К, зависящей от п переменных, все 2П двоичных наборов длины п и вычисляя для каждого из них значение формулы К. [16]
Возможен следующий способ повышения эффективности тривиального алгоритма. Выделяются все допустимые конъюнкции К и к множеству Kj применяется тривиальный алгоритм. Этот простой прием существенно увеличивает эффективность тривиального алгоритма. [17]
Рассмотрены два типа схем шифрования. Во второй схеме для защиты данных используется непредсказуемо длинный ключ в сочетании с относительно тривиальным алгоритмом шифрования. Приведены результаты экспериментов, в которых с помощью программной эмуляции исследовались эти схемы. [18]
Второй класс В образуют задачи, методы и алгоритмы решения которых неизвестны. Любая случайная последовательность альтернативных вариантов, если она достаточно длинна, содержит решения всех задач. Тривиальный алгоритм получения решения задачи из класса ( В) состоял бы в переборе элементов случайной последовательности и в извлечении из нее тех элементов, которые являются решениями в указанном выше смысле. Совершенно очевидно, что для решения сложных научно-технических задач использование метода полного перебора всех альтернативных вариантов предполагаемых решений практически не осуществимо из-за их огромной размерности. [19]
Второй класс В образуют задачи, методы и алгоритмы решения которых неизвестны. Любая случайная последовательность альтернативных вариантов, если она достаточно длинна, содержит решения всех задач. Тривиальный алгоритм получения решения задачи из класса В состоял бы в переборе элементов случайной последовательности и в извлечении из нее тех элементов, которые являются решениями в указанном выше смысле. Совершенно очевидно, что для решения сложных научно-технических задач использование метода полного перебора всех альтернативных вариантов предполагаемых решений практически не осуществимо из-за их огромной размерности. [20]
Возможен следующий способ повышения эффективности тривиального алгоритма. Выделяются все допустимые конъюнкции К и к множеству Kj применяется тривиальный алгоритм. Этот простой прием существенно увеличивает эффективность тривиального алгоритма. [21]
И здесь сложность булевой функции никак не фигурирует в ее определении. Зато для задания булевой функции используются такие сильные вычислительные средства, как примитивно-рекурсивные функции. В результате трудоемкость вычисления примитивно-рекурсивных функций частично переносится на построенные булевы функции и оказывается, что они могут вычисляться лишь с трудоемкостью перебора аналогичного тому, что в тривиальном алгоритме. [22]