Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 28
Текст из файла (страница 28)
Назовем операцию присвоения порядкового номера 1-му претенденту тапИ (1) и примем соглашение, что более высокий ранг соответствует специалисту с более высокой квалификацией. Упорядоченное множество (гавИ (1), гопй (2),..., гапИ (и)) является перестановюй множества (1, 2,..., и). Утверждение, что кандидаты приходят на собеседование в случайном порядке, эквивалентно утверждению, что вероятность любого порядка рангов одинакова и равна количеству перестановок чисел от 1 до и, т.е. и!. Другими словами, ранги образуют случайную равловероятлую лере- Глава 5. Вероятностный анализ и рандомизироаанные алгоритмы 143 столовку, т.е.
каждая из и! возможных перестановок появляется с одинаювой вероятностью. Вероятностный анализ задачи о найме сотрудника приведен в разделе 5.2. Раидомизироваииые алгоритмы Чтобы провести вероятностный анализ, нужно иметь некоторые сведения о распределении входных данных.
Во многих случаях мы знаем о них очень мало. Даже если об этом распределении что-то известно, может случиться так, что знания, которыми мы располагаем, нельзя численно смоделировать. Несмотря на это вероятность и случайность часто можно использовать в качестве инструмента при разработке и анализе алгоритмов, путем придания случайного характера части алгоритма. В задаче о найме сотрудника все выглядит так, как будто кандидатов присылают на собеседование в случайном порядке, но на самом деле у нас нет никакой возможности узнать, так ли это на самом деле. Поэтому, чтобы разработать рандомизированный алгоритм для этой задачи, необходимо повысить степень юнтроля над порядком поступления претендентов на должность. Внесем в модель небольшие изменения.
Допустим, бюро по трудоустройству подобрало и кандидатов. Работодатель договаривается, чтобы ему заранее прислали список кандидатов, и каждый день самостоятельно случайным образом выбирает, с кем из претендентов проводить собеседование. Несмотря на то, что работодатель по-прежнему ничего не знает о претендентах на должность, задача существенно изменилась. Теперь не нужно гадать, будет ли очередность кандидатов случайной; вместо этого мы взяли этот процесс под свой контроль и сами сделали случайным порядок проведения собеседований. В общем случае алгоритм называется рандомизированным (гапбош!лед), если его поведение определяется не только набором входных величин, но и значениями, которые выдает генератор случаннмх чисел. Будем предполагать, что в нашем распоряжении имеется генератор дискретных случайных чисел КА!чпом.
При вызове процедура КА!чООм(а,б) возвращает целое число, принадлежащее интервалу от а до 6 и равномерно распределенное в этом интервале. Например, КА!чпом(0, 1) с вероятностью 1/2 выдает 0 и с той же вероятностью — 1. В результате вызова Капом(3, 7) числа 3, 4, 5, б и 7 возвращаются с вероятностью 1/5. Вероятность возврата процедурой Клипом любого целого числа не зависит от того, какие числа были возвращены в предыдущем вызове этой процедуры. Процедуру Клм)ом можно представить в виде рулетки с (5 — а + 1) делениями. На практике большинство сред программирования предоставляют в распоряжение программиста генератор лсевдослучайных чисел, т.е. детерминированный алгоритм, который возвращающий числа, которые ведут себя при статистическом анализе как случайные.
Часть !. Основы Упражнения 5.1-1. Покажите, что из предположения о том, что в строке 4 алгоритма Н!кн АЗЗ!Зтхнт ВСЕГда МОЖНО ОПрЕдЕЛИтЬ, КаКОй КаНдИдат ЛУЧШЕ, СЛЕдуЕт, ЧтО мы знаем общий порядок рангов кандидатов. * 5.1-2. Опишите реализацию процедуры Кльлэом(а, Ь), которая может использовать только один вызов — процедуры Клм!эом(0, 1). Чему равно математическое ожидание времени работы вашей реализации и как оно зависит от а и 6? * 5.1-3. Предположим, что нам надо выводить 0 и 1 с вероятностью 50%. В нашем распоряжении имеется процедура В!Азв!з Клмпом, которая с вероятностью р выдает О, и с вероятностью 1 — р — число 1; значение р нам неизвестно. Сформулируйте алгоритм, использующий в качестве подпрограммы процедуру В!Азнп Клмпом и возвращающий равномерно распределенные числа 0 и 1, т.е. вероятность вывода каждого из них равна 50%.
Чему равно математическое ожидание времени работы такой процедуры и как оно зависит от р? 5.2 Индикаторная случайная величина При анализе многих алгоритмов, в том числе того, с помощью которого решается задача о найме сотрудника, будет использоваться индикаторная случайная величина. Она предоставляет удобный метод перехода от вероятности к математическому ожиданию. Предположим, что в нашем распоряжении имеется пространство выборки о и событие А.
Тогда индикаторная случайная величина (шгйса!ог гаврош чаг!аЫе) 1(А), связанная с событием А, определяется так: /1 если событие А произошло, 1 0 если событие А не произошло. (5.1) 1 если выпал орел, Хн =1(Н) = 0 если выпала решка. В качестве примера определим математическое ожидание того, что при подбрасывании монеты выпадет орел. Пространство событий в этом случае имеет простой вид Я = (Н, Т'1, где вероятности выпадения орла (это событие обозначено как Н ()зев)) и решки (Т (!а!!)) равны: Рг1Н) = Рг(Т) = 1/2. Далее, можно определить индикаторную случайную величину Хн, связанную с выпадением орла, т.е. событием Н. Эта величина подсчитывает количество выпадений орла.
Если выпадает орел, она равна 1, а если решка — О. Запишем это с помощью формальных обозначений: Глава 5. Вероятностный анализ и рандомизированные алгоритмы 145 Математическое ожидание того, что выпадет орел, равняется математическому ожиданию индикаторной величины Хн. Е [Хн] = Е [1 (НЦ = = 1. Рг (Н) + О Рг (Т) = = 1 (1/г) + О (1/2) = = 1/2.
Таким образом, математическое ожидание того, что выпадет орел, равно 1/2. Как показано в приведенной ниже лемме, математическое ожидание индикаторной случайной величины, связанной с событием А, равно вероятности этого события. Лемма 5.1. Пусть имеется пространство событий Я и событие А, принадлежащее этому пространству, и пусть Хл = 1(А). Тогда Е [Хл] = Рг (А). Доказательство. Согласно определению (5.1) индикаторной случайной величи- ны и определению математического ожидания, имеем: Е[Хл] = Е[?(А)] = = 1 Рг(А)+О Рг(А) = = Рг(А). где А обозначает Я вЂ” А, т.е. дополнение события А.
Хотя индикаторные случайные величины могут показаться неудобными в применении, например, при вычислении математического ожидания выпадений орла при бросании монеты, однако они оказываются полезны при анализе ситуаций, в которых делаются повторные испытания. Например, индикаторная случайная величина позволяет простым путем получить результат в уравнении (В.36). В этом уравнении количество выпадений орла при п бросаниях монеты вычисляется путем отдельного рассмотрения вероятности того события, что орел выпадет О, 1, 2 и т.д.
раз. В уравнении (В.37) предлагается более простой метод, в котором, по сути, неявно используется индикаторные случайные величины. Чтобы было понятнее, обозначим через Х; индикаторную случайную величину, связанную с событием, когда при 1-м выбрасывании выпадает орел: Х, = =? (При г-м броске выпал орел). Пусть Х вЂ” случайная величина, равная общему количеству выпадений орла при и бросаниях монеты. Тогда Часть!. Основы Нам надо вычислить математичесюе ожидание выпадения орла. Для этого применим операцию математического ожидания к обеим частям приведенного выше уравнения: Е[Х[=Е 2 Х; Левая часть полученного уравнения представляет собой математическое ожидание суммы и случайных величин. Математическое ожидание каждой из этих случайных величин легко вычисляется при помощи леммы 5.1.
Пользуясь уравнением (В.20), выражающим свойство линейности математического ожидания, математическое ожидание суммы случайных величин можно выразить как сумму математических ожиданий каждой величины. Благодаря линейности математичесюго ожидания использование индикаторной случайной величины становится мощным аналитическим методом, который применим даже в том случае, когда между случайными величинами имеется зависимость.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
