Рандомизированный алгоритм

Cтраница 2

Формульная схема алгоритма, которую удалось получить в рекуррентном виде, была запрограммирована на ЦВМ М-20 и использована для моделирования алгоритма методом Монте-Карло. Результаты моделирования иллюстрируют доказанную выше сходимость рандомизированного алгоритма. [16]

Эмпирическое исследование алгоритмов быстрой сортировки. [17]

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

В первом способе случайность вводится в поведение самого алгоритма, а во втором предполагается, что случайность присутствует в выборе частных случаев. Подход, основанный на рандомизированных алгоритмах, конечно, более привлекателен из этих двух, так как он обходится без предположений о среде, в которой алгоритм будет использоваться. Однако пока не показана эффективность рандомизированных алгоритмов в борьбе с комбинаторными взрывами, характерными для NP-полных задач, и, видимо, оба этих подхода будут иметь свои применения. [19]

В 1968 г., - возможно, под влиянием общественных волнений, охвативших страну - я решил перебраться в Калифорнийский университет в Беркли, который был центром студенческого движения. Возможность работать с такими выдающимися учеными, как Алан Хофман, Раймонд Миллер, Арнольд Розенберг и Шмуэль Виноград, была просто бесценной. Мой новый круг коллег включал Майкла Харрисона, известного специалиста по теории языков, который и соблазнил меня перебраться в Беркли; Юджина Лоулера, эксперта по комбинаторной оптимизации; Мануэля Блюма, основателя теории сложности, который потом выполнил выдающуюся работу на границе теории чисел и криптографии, и Стивена Кука, чья работа но теории сложности повлияет на меня так сильно через несколько лет. В Отделении математики работали Джулия Робинсон, чья работа над 10 - й проблемой Гильберта вскоре принесет плоды; Роберт Соловей, знаменитый логик, открывший важный рандомизированный алгоритм распознавания простоты числа, и Стив Смейл, чья потрясающая работа по вероятностному анализу алгоритмов линейного программирования оказала на меня влияние через несколько лет. [20]

Есть очень красивые теоретические разработки о том, сколько теряешь, когда вынужден полагаться на передачу сообщений в разреженной сети процессоров вместо прямой попарной связи между процессорами. В реалистичной распределенной системе процессоры должны не только считать, но и сотрудничать подобно почте, где сообщения летают между местами обработки. Есть очень хорошие теоретические работы о различных типах протоколов, где, как в так называемой задаче о византийских генералах, - еще одно из этих громких названий, - коллектив процессоров должен прийти к соглашению посредством передачи сообщений, даже когда часть процессоров неисправна и действует враждебно, пытаясь все запутать. Уже стало ясным, что здесь очень хорошо работает рандомизация. Протоколы, нужные для этих задач сотрудничества и связи в распределенной системе, можно упростить, если использовать бросание монеты. Что в такого рода задачах применимы рандомизированные алгоритмы - это важное открытие. Так что есть много связей между теорией и протоколами для реальных распределенных систем. [21]

Страницы: 1 2