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