Алгоритмы - построение и анализ (1021735), страница 27
Текст из файла (страница 27)
Поэтому, чтобы разработать рандомизированный алгоритм для этой задачи, необходимо повысить степень юнтроля над порядком поступления претендентов на должность. Внесем в модель небольшие изменения. Допустим, бюро по трудоустройству подобрало и кандидатов. Работодатель договаривается, чтобы ему заранее прислали список кандидатов, и каждый день самостоятельно случайным образом выбирает, с кем из претендентов проводить собеседование. Несмотря на то, что работодатель по-прежнему ничего не знает о претендентах на должность, задача существенно изменилась. Теперь не нужно гадать, будет ли очередность кандидатов случайной; вместо этого мы взяли этот процесс под свой контроль и сами сделали случайным порядок проведения собеседований.
В общем случае алгоритм называется рандомизированным (гапбош!лед), если его поведение определяется не только набором входных величин, но и значениями, которые выдает генератор случаннмх чисел. Будем предполагать, что в нашем распоряжении имеется генератор дискретных случайных чисел КАнпом. При вызове процедура КА!чООм(а,б) возвращает целое число, принадлежащее интервалу от а до 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), выражающим свойство линейности математического ожидания, математическое ожидание суммы случайных величин можно выразить как сумму математических ожиданий каждой величины. Благодаря линейности математичесюго ожидания использование индикаторной случайной величины становится мощным аналитическим методом, который применим даже в том случае, когда между случайными величинами имеется зависимость.
Теперь мы можем легко вычислить математическое ожидание количества выпадений орла: Таким образом, индикаторные случайные величины значительно упростили вычисления по сравнению с методом, использующимся в уравнении (В.Зб). Вы еще не раз встретитесь с этими величинами в данной книге. Анализ задачи о найме сотрудника с помощью индикаторных случайных величин Вернемся к задаче о найме сотрудника, в которой нужно вычислить математическое ожидание события, соответствующего найму нового менеджера.
Чтобы провести вероятностный анализ, предположим, что кандидаты приходят на собеседование в случайном порядке (этот вопрос уже обсуждался в предыдущем разделе; в разделе 5.3 будет показано, каким образом можно обойтись без этого предположения). Пусть Х вЂ” случайная величина, значение которой равно количеству наймов нового офис-менеджера. Далее можно воспользоваться определением Глава 5. Вероятностный анализ и рандомизированные алгоритмы 147 математического ожидания (уравнение В.19) и получить соотношение и Е[Х] = ,'~ хРг(Х = х), но эти вычисления окажутся слишком громоздкими. Вместо этого воспользуемся индикаторными случайными величинами, благодаря чему вычисления значительно упростятся.
Чтобы воспользоваться индикаторными случайными величинами, вместо вычисления величины Е [Х] путем определения одного значения, связанного с числом наймов нового менеджера, определим п величин, связанных с наймом конкретных кандидатов. В частности, пусть Х; — индикаторная случайная величина, связанная с событием найма г-го кандидата. Таким образом, ['1 Х; = 1(1-й кандидат нанят) = ~[0 если г-й кандидат нанят, (5.2) если 1-й кандидат отклонен, и Х = Х1+Хз+ ° ° +Х„. (5.3) Из леммы 5.1 следует, что Е [Х,] = Рг (1-й кандидат нанят), и теперь нам надо вычислить вероятность выполнения строк 5 и б процедуры Н1кю Азязтлхт.
Работодатель нанимает кандидата под номером г' (строка 5), только если он окажется лучше всех предыдущих (от 1-го до г — 1-го). Поскольку мы предположили, что кандидаты приходят на собеседование в случайном порядке, это означает, что первые г кандидатов также прибыли в случайном порядке. Любой из первых 1 кандидатов с равной вероятностью может оказаться лучшим. Поэтому вероятность того, что квалификация претендента с номером г выше квалификации претендентов с номерами от 1 до г — 1, и что он будет взят на работу, равна 1/1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
