Недетерминированный алгоритм - Большая Энциклопедия Нефти и Газа, статья, страница 1
Длина минуты зависит от того, по какую сторону от двери в туалете ты находишься. Законы Мерфи (еще...)

Недетерминированный алгоритм

Cтраница 1


Недетерминированный алгоритм ( при одном и том же входе) может действовать по-разному, в зависимости от того, какие произвольные числа будут выбраны.  [1]

Постройте недетерминированный алгоритм с емкостной сложностью О ( п), выясняющий, пусто ли множество, представленное произвольным полурасширенным регулярным выражением. Почему ваш алгоритм не срабатывает, когда вы пытаетесь узнать, представляет ли данное регулярное выражение все цепочки.  [2]

Например, недетерминированный алгоритм решения задачи коммивояжер можно было бы построить, используя в качестве стадии угадывания просто выбор произвольной последовательности городов, а в качестве стадии проверки упомянутую, полиномиальную процедуру и проверку доказательства для задачи коммивояжер. Очевидно, для любой индивидуальной задачи / найдется такая догадка S, что результатом работы стадии проверки на входе ( /, 5) будет да в том и только в том случае, если для индивидуальной задачи / существует маршрут искомой длины.  [3]

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

Определяется понятие полиномиальных недетерминированных алгоритмов; они соответствуют задачам, которые решаются путем перебора, описываемого деревом поиска полиномиальной глубины.  [5]

Неочевиден этот факт для всех задач, разрешаемых за полиномиальное время недетерминированными алгоритмами. Верно ли, что нет маршрута, проходящего через все города и имеющего длину, не превосходящую В. Для выяснения, имеет ли поставленный вопрос ответ да, неизвестен способ, который был бы короче, чем проверка всех ( или почти всех) возможных маршрутов.  [6]

Очевидно, никакое физическое устройство не способно на неограниченное недетерминированное поведение; недетерминированные алгоритмы - это абстракция, которая позволяет нам игнорировать некоторые проблемы программирования поиска с возвращением. Сравнивая алгоритм 9.1 с алгоритмом 4.1, мы видим сильное различие: алгоритм 9.1 не содержит возвращения, если достигается тупик, потому что функция выбор заставляет исследовать все пути.  [7]

По существу в доказательстве дается процедура построения, которая для любого полиномиального недетерминированного алгоритма, выходом которого будет просто истинно или ложно, и для любой входной последовательности строит одно булево выражение в конъюнктивной нормальной форме, которое является выполнимым, если и только если для этой входной последовательности алгоритм вычисляет ответ истинно. Далее, в доказательстве показывается, что построение этого булевого выражения из формального описания недетерминированного алгоритма и его входной последовательности можно выполнить за полиномиальное время. Опираясь на этот результат, можно показать, что существует последовательность таких булевых выражений, соответствующая разрядам выходной последовательности для любого алгоритма из оЛГ 3 и любой входной последовательности.  [8]

Неформально класс NP можно определить с помощью понятия, которое мы будем называть недетерминированный алгоритм.  [9]

Класс NP, определяемый неформально, это класс всех задач распознавания II, которые при разумном кодировании могут быть решены недетерминированными алгоритмами за полиномиальное время.  [10]

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

Чтобы понять, какие следствия будут вытекать из того, что Р содержит задачу коммивояжера или одну из многих других загадочных задач, необходимо ввести класс № У задач, которые можно решить за полиномиальное время с помощью недетерминированного алгоритма. Не формально мы определяем состояние алгоритма как комбинацию адреса выполняемой в текущий момент команды и значений всех переменных. Другими словами, детерминированный алгоритм в каждый момент времени может делать только что-то одно. В недетерминированном алгоритме для любого данного состояния может быть больше одного допустимого следующего состояния; другими словами, недетерминированный алгоритм в каждый момент времени может делать больше одной вещи. Недетерминированные алгоритмы не являются в каком-либо смысле вероятностными или случайными алгоритмами; они являются алгоритмами, которые могут находиться одновременно во многих состояниях.  [12]

Поясним значение термина решает в этом определении. Основное назначение полиномиального недетерминированного алгоритма состоит в объяснении понятия проверяемости за полиномиальное время, а не в том, чтобы служить реалистическим методом решения задач распознавания свойств.  [13]

В основном здесь различаются детерминированные алгоритмы САР и недетерминированные алгоритмы САП. Самоорганизующиеся системы работают по самоорганизующемуся алгоритму, изменяющемуся по ходу процесса управления.  [14]

Задача принадлежит классу NP, если она разрешима за полиномиальное время недетерминированным алгоритмом.  [15]



Страницы:      1    2