Разработка и анализ алгоритма
присваивается 0 или 1 (каждое значение имеет вероятность — ).
Какое ожидаемое число условий будет выполнено таким случайным присваиванием?Обозначим Z случайную переменную, равную количеству выполненных усло- вий. Как и в разделе 13.3, разложим Z на сумму случайных переменных, каждая из которых принимает значение 0 или 1, а именно Z = 1, если условие C выполнено, или 0 в противном случае. Следовательно, Z = Z1 + Z2 + ... + Zk. Теперь значение E[Z] равно вероятности того, что условие Ci выполнено, а эта вероятность легко вы- числяется: чтобы условие C не было выполнено, каждой из его трех переменных должно быть присвоено значение, которое мешает его истинности; так как пере-
= —. Следовательно,
условие С. выполняется с вероятностью
Используя линейность ожидания, мы видим, что ожидаемое количество вы- полненных условий равно m\=⅞]+⅜] ⅝·
Еще по теме Разработка и анализ алгоритма:
- Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
- § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
- § 2.ФУНКЦИИ МЕТОДОЛОГИИ В РАЗРАБОТКЕ МЕТОДИК АНАЛИЗА СОЦИАЛЬНЫХ ФАКТОВ
- Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
- АЛГОРИТМ
- АЛГОРИТМ УДАЧИ
- Алгоритм исцеления:
- Алгоритм избавления от боли
- 2. Специфика и алгоритмы работы с источниками.
- Алгоритм обработки результатов.
- СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
- Э. ТАНЕНБАУМ, А. ВУДХАЛЛ. ОПЕРАЦИОННЫЕ СИСТЕМЫ Разработка и реализация 3-е издание, 2007
- 2.7. Разработка анкеты
- Разработка Плана
- 6. Разработка перспектив
- Разработка и принятие Основного закона