Рандомизированный алгоритм
Cтраница 1
Рандомизированный алгоритм часто используется на компьютерах, в которых предусмотрена возможность вывода графического изображения на экран в режиме 1 пиксел за раз. Для детерминированного алгоритма требуется большой объем памяти. Стоит отметить, что для вывода на печать необходим принтер, способный работать с большими изображениями. [1]
 |
Ковер Серпинского. рандомизированный алгоритм ( построено 10000 точек. [2] |
В рандомизированном алгоритме, который часто называют игрой Хаос ( см. упр. [3]
Описанный авторами рандомизированный алгоритм, обеспечивая в пределе сходимость к оптимальной стратегии, по-видимому, может быть использован в задачах управляемого случайного поиска. [4]
Ниже приводится рандомизированный алгоритм ( РСИФ), в котором все вычисления и вывод на экран производятся в мировых координатах. [5]
В качестве конкретной иллюстрации преимуществ бросания монеты я приведу простой рандомизированный алгоритм сопоставления с образцом, изобретенный Рабином и мною в 1980 г. Задача сопоставления с образцом - одна из основных в обработке текстов. Грубый метод решения этой задачи состоит в непосредственном сравнении образца с каждым я-раз-рядным блоком внутри текста. В худшем случае время выполнения этого метода пропорционально произведению длины образца на длину текста. [6]
Показать, что игра Хаос есть не что иное, как рандомизированный алгоритм для получения ковра Серпинского, описанный в этом параграфе. [7]
Для приближенного решения задачи минимизации функционала / ( R) был разработан эвристический рандомизированный алгоритм. Общая схема метода следующая. [8]
Найти а4финные преобразования TI, TZ, 7з системы итерированных функций, аттрактор которой изображен на рис. 4.3. Смоделировать СИФ на компьютере с помощью детерминированного или рандомизированного алгоритма. [9]
Алгоритмы, в процессе выполнения которых бросается монета, время от времени предлагались с тех пор, как появились первые компьютеры, но систематическое изучение таких рандомизированных алгоритмов началось только примерно с 1976 г. Интерес к этой теме привлекли два удивительно эффективных рандомизированных алгоритма проверки того, является ли число п простым; один из этих алгоритмов предложили Соловей и Фолкер Штрассен, а другой - Рабин. [10]
В нижнем левом углу содержатся сегменты, которые интересовали Карпа в самое последнее время и в которых имеются ] открытые вопросы. Рандомизированный алгоритм, например, располагается напротив Вероятностного анализа, потому что-это две альтернативы анализа детерминированных алгоритмов, в худшем случае. Рандомизированные алгоритмы могут быть способны решать задачи за полиномиальное время, тогда как детерминированные не могут, и это могло бы означать расширение понятия хороших алгоритмов. Возможно, через построение программных конструкций не фон-неймановских машин можно построить более эффективные на практике алгоритмы посредством параллелизма. [11]
В нижнем левом углу содержатся сегменты, которые интересовали Карпа в самое последнее время и в которых имеются ] открытые вопросы. Рандомизированный алгоритм, например, располагается напротив Вероятностного анализа, потому что-это две альтернативы анализа детерминированных алгоритмов, в худшем случае. Рандомизированные алгоритмы могут быть способны решать задачи за полиномиальное время, тогда как детерминированные не могут, и это могло бы означать расширение понятия хороших алгоритмов. Возможно, через построение программных конструкций не фон-неймановских машин можно построить более эффективные на практике алгоритмы посредством параллелизма. [12]
Замечательным свойством алгоритмов, основанных на теории систем итерированных функций, является то, что их результат ( аттрактор) совершенно не зависит от выбора начального множества EQ или начальной точки XQ. В случае детерминированного алгоритма это означает, что в качестве EQ можно взять любое компактное множество на плоскости: предельное множество по-прежнему будет совпадать с ковром Серпинского. В случае рандомизированного алгоритма, вне зависимости от выбора начальной точки TO, после нескольких итераций точки начинают заполнять ковер Серпинского. [13]
В первом способе случайность вводится в поведение самого алгоритма, а во втором предполагается, что случайность присутствует в выборе частных случаев. Подход, основанный на рандомизированных алгоритмах, конечно, более привлекателен из этих двух, так как он обходится без предположений о среде, в которой алгоритм будет использоваться. Однако пока не показана эффективность рандомизированных алгоритмов в борьбе с комбинаторными взрывами, характерными для NP-полных задач, и, видимо, оба этих подхода будут иметь свои применения. [14]
Например, если мы случайным образом взболтаем массив до сортировки, тогда допущение о том, что элементы массива находятся в случайном порядке, будет выполнено. Для таких алгоритмов, называемых рандомизированными алгоритмами, анализ средней производительности приводит к ожидаемому времени выполнения в строгом вероятностном смысле. Более того, часто можно доказать, что вероятность того, что такой алгоритм будет медленным, пренебрежимо мала. [15]
Страницы: 1 2