Разработка и анализ алгоритма

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

присваивается 0 или 1 (каждое значение имеет вероятность — ).

Какое ожидаемое число условий будет выполнено таким случайным присваиванием?

Обозначим Z случайную переменную, равную количеству выполненных усло- вий. Как и в разделе 13.3, разложим Z на сумму случайных переменных, каждая из которых принимает значение 0 или 1, а именно Z = 1, если условие C выполнено, или 0 в противном случае. Следовательно, Z = Z1 + Z2 + ... + Zk. Теперь значение E[Z] равно вероятности того, что условие Ci выполнено, а эта вероятность легко вы- числяется: чтобы условие C не было выполнено, каждой из его трех переменных должно быть присвоено значение, которое мешает его истинности; так как пере-

= —. Следовательно,

условие С. выполняется с вероятностью

Используя линейность ожидания, мы видим, что ожидаемое количество вы- полненных условий равно m\=⅞]+⅜] ⅝·

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

Еще по теме Разработка и анализ алгоритма:

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