Тривиальный алгоритм

Cтраница 1

Тривиальный алгоритм требует просмотра некоторого полного семантического дерева, соответствующего конечному множеству высказываний, встречающихся в А. Этот алгоритм крайне неэффективен: если формула А содержит п различных высказываний, то нужно рассматривать 2 интерпретаций. [1]

Тривиальный алгоритм нахождения ПКМ с минимальным числом единиц для графа G заключается в следующем. [2]

Тривиальным алгоритмом нахождения ПКМС с минимальным числом запретов является алгоритм полного перебора в классе эквивалентности по отношению изоморфизма алфавита состояний автомата. Он заключается в следующем. [3]

Описанный выше тривиальный алгоритм поиска формулы наименьшей сложности относится к классу так называемых переборных алгоритмов. [4]

Не обсуждая тривиальный алгоритм, заметим лишь, что однозначные числа не проверяются, а найденные суперпростые числа записываются в массив SPN-и выводятся на жран. В конце программы, с целью сохранить результаты, суперпростые числа записываются в текстовый файл. [5]

Но помимо громоздкости, этот тривиальный алгоритм обладает еще одним существенным недостатком: из него нельзя извлечь никакого предварительного представления о сложности той сети, которая будет получена в результате его применения. [6]

Возможен следующий способ повышения эффективности тривиального алгоритма. Выделяются все допустимые конъюнкции К и к множеству Kj применяется тривиальный алгоритм. Этот простой прием существенно увеличивает эффективность тривиального алгоритма. [7]

Такая большая трудоемкость объясняется не малой эффективностью тривиального алгоритма, а трудностью решения задачи синтеза в общем виде и присуща всем алгоритмам, предназначенным для ее решения, - к этому выводу одним из первых пришел С. В. Яблонский в своей работе [48], рассматривая данную задачу для контактных схем. С тех пор эта точка зрения стала общепринятой, получив много косвенных подтверждений своей справедливости. [8]

Неполное семантическое дерево. [9]

Алгоритм Kt / айна [86] - довольно непосредственное усовершенствование тривиального алгоритма. [10]

Читатель, который старательно проработал эту главу, начиная с тривиального алгоритма подсчета числа единиц в наборе, просматривающего все разряды по очереди, и кончая заполнением пробелов в выводе верхней оценки (1.4), имеет теперь общее представление о полном спектре комбинаторных алгоритмов. В частности, каждая тема, встречающаяся в этой книге, будет некоторым напоминанием принципов разработки алгоритмов, приведенных в разд. [11]

Легко построить примеры, для которых алгоритмы Кузина и редукции ненамного эффективнее, чем тривиальный алгоритм. Точнее, установлено, что проблема выявления общезначимости ( или выполнимости) формулы исчисления высказываний NP-полна. Не вдаваясь в рассуждения, выходящие за рамки этой книги, отметим, что указанный факт означает ничтожность вероятности существования эффективного общего алгоритма для проверки выполнимости или общезначимости формул исчисления высказываний. [12]

Любая случайная последовательность, если она достаточно длинна, содержит решения всех задач. Тривиальным алгоритмом получения решения задачи из класса ( 33) были бы перебор элементов случайной последовательности и извлечение из нее тех элементов, к-рые являются решениями в указанном выше смысле. Ясно, что для интересных задач, как правило, о полном переборе не может быть н речи. Однако всегда существует множество факторов, к-рое помогает живым существам обходиться без полного перебора. Часто эти факторы паз. [13]

Любая случайная последовательность, если она достаточно длинна, содержит решения всех задач. Тривиальным алгоритмом получения решения задачи из класса ( 33) были бы перебор элементов случайной последовательности и извлечение из нее тех элементов, к-рые являются решениями в указанном выше смысле. Ясно, что для интересных задач, как правило, о полном переборе но может быть и речи. Однако всегда существует множество факторов, к-рое помогает живым существам обходиться без полного перебора. Часто эти факторы наз. [14]

Действительно, существует тривиальный алгоритм восстановления плотности, который независимо от особенностей выборки восстанавливает плотность с одними и теми же фиксированными значениями параметров. Такой алгоритм восстанавливает идеально одну-единственную плотность и плохо - другие. [15]

Страницы: 1 2