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

Идея «случайности» процесса не нова; само понятие возникло давно в истории человеческой мысли. Оно отражено в азартных играх и страховом деле — и то и другое происходит из древних времен. Но хотя столь же интуитивно понятные дисциплины, такие как геометрия или логика, изучаются математическими мето- дами уже несколько тысяч лет, область математического изучения вероятности на удивление молода; первые попытки ее серьезной формализации были предпри- няты в XVII веке.
Конечно, компьютерная наука существует на много меньшем историческом отрезке, и случайности в ней уделяется внимание с первых дней.

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

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

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

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

Следовательно, задачи, которые не решаются эффективными детерминированными алгоритмами, могут не устоять перед рандомизированными алгоритмами.

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

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

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Глава 13 Рандомизированные алгоритмы:

  1. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  2. АЛГОРИТМ
  3. АЛГОРИТМ УДАЧИ
  4. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  5. Алгоритм исцеления:
  6. Алгоритм избавления от боли
  7. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  8. Алгоритм обработки результатов.
  9. 2. Специфика и алгоритмы работы с источниками.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  11. 2. ИСТОЧНИКИ ИНФОРМАЦИИ. СПЕЦИФИКА И АЛГОРИТМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ. ДОСТУП К ИСТОЧНИКАМ ИНФОРМАЦИИ. ПРАВОВЫЕ И ЭТИЧЕСКИЕ НОРМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ.
  12. Глава 8. Глава государства в зарубежных странах
  13. Глава рода
  14. Глава рода
  15. Глава 1
  16. Глава 2
  17. Глава 3