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

Идея «случайности» процесса не нова; само понятие возникло давно в истории человеческой мысли. Оно отражено в азартных играх и страховом деле — и то   и другое происходит из древних времен.

Темы рандомизация и вероятностного анализа проникают во многие области компьютерной науки, включая разработку алгоритмов, и когда речь заходит о случайных процессах в контексте вычислений, обычно имеется в виду одна из двух точек зрения.

Первая рассматривает случайное поведение реального мира: здесь часто изучаются традиционные алгоритмы, сталкивающиеся со случайно сгенерированными входными данными. Такие методы часто называются анализом среднего случая, потому что поведение алгоритма изучается на «средних» входных данных (подвергнутых воздействию некоторого случайного процесса) вместо худшего случая.

Вторая точка зрения связана со случайным поведением самих алгоритмов: мир всегда поставляет одни и те же входные данные худшего случая, но алгоритму разрешено принимать случайные решения при обработке ввода. Таким образом, рандомизация в этом методе действует исключительно внутри алгоритма и не требует новых допущений относительно природы входных данных. Именно этой концепции рандомизированных алгоритмов посвящена данная глава.

Чем может быть полезен алгоритм, принимающий случайные решения? Во-первых, рандомизация расширяет возможности используемой модели.

Эффективные детерминированные алгоритмы, которые всегда дают правильный ответ, могут рассматриваться как особый случай эффективных рандомизированных алгоритмов, которые дают правильный ответ с очень высокой вероятностью; они также являются особым случаем рандомизированных алгоритмов, которые всегда работают правильно и при этом, как ожидается, выполняются эффективно.

Даже при получении худших входных данных алгоритм, выполняющий свою «внутреннюю» рандомизацию, может компенсировать некоторые нежелательные аспекты худшего случая. Следовательно, задачи, которые не решаются эффективными детерминированными алгоритмами, могут не устоять перед рандомизированными алгоритмами.

Но это еще не все. Мы рассмотрим рандомизированные алгоритмы для некоторых задач, для которых существуют сравнительно эффективные детерминированные алгоритмы. Даже в таких ситуациях рандомизация часто проявляет немалую мощь: например, она может быть концептуально проще или она может обеспечить функционирование алгоритма при минимальных потребностях в хранении внутреннего состояния или информации о прошлых событиях.

Преимущества рандомизации расширяются при рассмотрении крупных компьютерных систем и сетей с множеством гибких взаимодействий между процессами, другими словами, в распределенных системах.

Здесь случайное поведение части отдельных процессов может сократить объем необходимого обмена информации или синхронизации; рандомизация часто оказывается ценным инструментом для нарушения симметрии между процессами, снижающим вероятность конфликтов и появления «горячих точек».

Многие из примеров будут взяты из ситуаций такого рода: управление доступом к общему ресурсу, распределение нагрузки по нескольким процессорам, маршрутизация пакетов в сети и т. д. Даже небольшой опыт работы с рандомизированными эвристиками может сильно пригодиться при анализе больших систем.

При изучении рандомизированных алгоритмов возникает естественная проблема: они требуют значительных знаний в области теории вероятности. Конечно, всегда лучше знать больше, чем меньше, и некоторые алгоритмы действительно базируются на сложных вероятностных идеях.

Но в этой главы мы также постараемся показать, что для понимания многих известных алгоритмов из этой области о теории вероятности в действительности достаточно знать совсем немного.

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