Cтраница 3
В основе вероятностных алгоритмов лежит идея о том, что иногда лучше попробовать угадать ответ, чем вычислить его. Вероятностные алгоритмы делятся на четыре класса - численные, Монте Карло, Лас Вегас и Шервуд - хотя зачастую все вероятностные алгоритмы называются методами Монте Карло. Общим свойством всех этих категорий является то, что чем дольше алгоритм работает, тем лучший результат он выдает. [31]
Вероятностный алгоритм AL для задачи Р использует датчик случайных чисел. После фиксации случайного выбора г алгоритм выполняется ( вполне детерминированно. [32]
Численные вероятностные алгоритмы всегда дают ответ, и этот ответ будет тем точнее, чем дольше они работают. Алгоритмы Монте Карло всегда дают ответ, но иногда ответ оказывается неправильным. Чем дольше выполняется алгоритм Монте Карло, тем выше вероятность того, что он даст правильный ответ. Повторный вызов алгоритма Монте Карло также приводит к улучшению результата. [33]
Соответственно этим этапам распознавания любой алгоритм распознавания может быть представлен в виде двух последовательно выполняемых алгоритмов В я С. Применительно к вероятностным алгоритмам элементами матрицы являются апостериорные вероятности отнесения каждого объекта к соответствующему классу. Алгоритм С - решающее правило - переводит полученную матрицу в матрицу ответов, составленных из символов 1 0, х ( 1 - объект относится к данному классу, 0 - объект не относится к данному классу, х - не установлено, относится объект к данному классу или не относится), имеющую ту же размерность. [34]
Классический пример задачи из ВРР представляет ПРОВЕРКА ПРОСТОТЫ числа: дано число п, требуется определить, простое ли оно. Для этой задачи существует вероятностный алгоритм, работающий за полиномиальное время; он будет сейчас описан. [35]
Значение АПШ, п оценивают опытным путем на поверочных установках по определенной программе, предусмотренной применяемой методикой. Оцениваемому значению показателя точности соответствует обычно вероятностный алгоритм ( учитывающий наличие случайной составляющей), а действительному значению - статистический алгоритм математической обработки исходных результатов контроля. [36]
В основе вероятностных алгоритмов лежит идея о том, что иногда лучше попробовать угадать ответ, чем вычислить его. Вероятностные алгоритмы делятся на четыре класса - численные, Монте Карло, Лас Вегас и Шервуд - хотя зачастую все вероятностные алгоритмы называются методами Монте Карло. Общим свойством всех этих категорий является то, что чем дольше алгоритм работает, тем лучший результат он выдает. [37]
Любопытен открытый пока вопрос: верно ли, что R P. Заманчиво ответить на него да, исходя из философских соображений, что случайное бросание монеты не может принести много пользы, когда ответ должен быть определенным - да или нет. С ним связан другой вопрос: является ли вероятностный алгоритм ( показывающий принадлежность задачи классу R) для. В конце концов, вероятностные алгоритмы можно выполнять, используя генераторы псевдослучайных, чисел, имеющиеся для большинства компьютеров, и вероятность ошибки 2 - 100 пренебрежимо мала. [38]
В этом же источнике указано, что использование вероятностного подхода возможно и при небольших выборках, однако в этом случае необходимы некоторые оценки информативности выборки. Результаты принятия решения на основе малых выборок в источнике не описаны. Практические работы по созданию диагностирующих программных систем на базе вероятностных алгоритмов широко велись в 60 - е годы XX века. [39]
Любопытен открытый пока вопрос: верно ли, что R P. Заманчиво ответить на него да, исходя из философских соображений, что случайное бросание монеты не может принести много пользы, когда ответ должен быть определенным - да или нет. С ним связан другой вопрос: является ли вероятностный алгоритм ( показывающий принадлежность задачи классу R) для. В конце концов, вероятностные алгоритмы можно выполнять, используя генераторы псевдослучайных, чисел, имеющиеся для большинства компьютеров, и вероятность ошибки 2 - 100 пренебрежимо мала. [40]
Еще одно усовершенствование метода быстрой сортировки заключается в использовании такого разделяющего элемента, который с достаточно большой вероятностью делил бы файл вблизи его середины. Наиболее безопасный выбор, минимизирующий вероятность возникновения наихудшего случая, состоит в использовании в качестве разделяющего элемента случайного элемента массива. Тогда вероятность возникновения наихудшего случая становится ничтожно малой. Этот метод представляет собой пример вероятностного алгоритма ( probabilistic algorithm) - такого алгоритма, который использует случайный характер величин для достижения высокой эффективности с большой вероятностью, независимо от степени упорядоченности входных данных. Далее в этой книге мы столкнемся с многочисленными примерами использования свойства случайности при разработке структуры алгоритмов, в частности, когда предполагается наличие той или иной тенденции во входных данных. На практике использование в рамках быстрой сортировки генератора случайных чисел с этой целью может оказаться излишним: простой произвольный выбор оказывается достаточно эффективным. [41]
Единственное нетривиальное использование квантовых свойств для вычислений, которое мы уже рассмотрели, - это решение универсальной переборной задачи алгоритмом Гровера, изложенным в разделе 8.1. К сожалению, при этом достигается лишь полиномиальное ускорение. Поэтому никаких серьезных следствий для теории сложности вычислений ( типа BQP D ВРР) алгоритм Гровера не дает. В настоящее время нет доказательства того, что квантовые вычисления превосходят по скорости классические вероятностные. Но есть косвенные свидетельства в пользу такого утверждения. Первое из них - пример задачи с оракулом ( т.е. процедурой типа черного ящика), для которой существует полиномиальный квантовый алгоритм, в то время как любой классический вероятностный алгоритм экспоненциален. В дальнейшем мы решим также задачу о скрытой подгруппе в TLk, обобщающую все результаты из этого раздела. [42]