Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 33
Текст из файла (страница 33)
После встречи с з кандидатами будет известно, какой из этих у претендентов на должность получил максимальную оценку, однако остается неизвестным, найдется ли среди оставшихся п — ~' кандидатов человек с более высокой квалификацией. Будем придерживаться следующей стратегии: выберем положительное целое число й < и, проведем интервью с й претендентами, отказав им в должности, а затем возьмем на работу первого из последующих и — й претендентов, оценка которого будет превышать оценки всех предыдуших кандидатов. Если же самый квалифицированный специалист окажется среди первых й претендентов, то придется взять на работу и-го кандидата.
Формальная реализация этой схемы представлена в приведенной ниже процедуре Он 1.пче МАх!мпм(/с, и), которая возврашает номер нанимаемого кандидата: Ом Епчц МАх~мим()с,п) 1 Ьев1зсоте — — со 2 Гог г' — 1 1о Ь 3 йо Ы асоте(г) > Ьез1зсоге 4 гйеп Ьез1асоге — всоте(1) 5 1ог г' — Й + 1 $о п Часть й Основы 6 оо!Гвсоге(г) ) Ьез1асоге 7 Изеп гегнгп г 8 ге1цгп и Определим для каждого положительного й вероятность того, что будет нанят наиболее квалифицированный претендент.
Затем выберем наилучшее из всех значений 7с и реализуем описанную стратегию с этим значением. Пока что полагаем lс фиксированным. Обозначим как М (7) = тахз<;~~ (асоге (г)) наивысшую оценку кандидатов с номерами от 1 до ~. Пусть Я вЂ” событие, определяемое как выбор самого квалифицированного кандидата. а В; — событие, при котором самым квалифицированным нанятым на работу кандидатом оказался г-й. Поскольку все события В, являются взаимоисключающими, выполняется соотношение Рг(о') = 2 ",. Рг(оз). Поскольку, согласно нашей стратеги, ни один из первых й претендентов на работу не принимается, Рг (В;) = 0 для г = 1, 2,..., /с.
Таким образом, получаем соотношение: (5.13) Теперь вычислим величину Рг (В,). Чтобы был принят на работу г-й кандидат, необходимо выполнение двух условий. Во-первых, на г-й позиции должен оказаться самый квалифицированный кандидат (обозначим это событие как В,), а во-вторых, в ходе выполнения алгоритма не должен быть выбран ни один из претендентов, пребывающий на позициях с 1+1-й по г — 1-ю.
Второе событие произойдет только тогда, когда при всех 7', таких что й+ 1 < 7' < г -1, в строке б будет выполняться условие зсоге (7') < ЬеаМсоге. (Поскольку оценки не повторяются, возможность равенства асоте (7) = Ьезгзсоге можно проигнорировать.) Другими словами, все оценки от аосте (й + 1) до зсоге (г — 1) должны быть меньше М (й); если же одна из них окажется больше М (й), то будет возвращен индекс первой из оценок, превышающей все предыдущие. Обозначим через 0; событие, что не взят на работу ни один из претендентов, проходивших собеседование под номерами от к+ 1 до г — 1.
К счастью, события В; и О, независимы. Событие О, зависит только от порядка нумерации кандидатов, которые находятся на позициях от 1 до г — 1, а событие В; зависит только от того, превышает ли оценка кандидата г оценки всех прочих кандидатов. Порядок оценок в позициях от 1 до г — 1 не влияет на то, превышает ли оценка г-го претендента все предыдущие оценки, а квалификация г-го кандидата не влияет на расположение кандидатов с порядковыми номерами от 1 до 1 — 1.
Применив уравнение (В.15)„получим: Рг(В,) = Рг(В, О О,) = Рг(В,) Рг(0;). Ясно, что вероятность Рг(В ) равна 1/и, поскольку каждый из п кандидатов может получить наивысшую оценку с равной вероятностью. Чтобы произошло Глава 5. Вероятностный анализ н рандомнэнрованные алгоритмы 167 событие О;, наиболее квалифицированный кандидат среди претендентов с номерами от 1 до а — 1 должен находиться на одной из первых й позиций. Он с равной вероятностью может оказаться на любой из этих 1 — 1 позиций, поэтому Рг(01) = Ус/(1' — 1) и, соответственно, Рг(51) = й/(п(1 — 1)). Воспользовавшись уравнением (5.13), получим: аа и и и-1 Р.(Я) = ') Р.(Яг) = ~ а=И-1 а=1+1 а=я+1 а=я Ограничим приведенную выше сумму сверху и снизу, заменив суммирование интегрированием. Согласно неравенствам (А.12), получаем: и и-1 )а~а~а Ь ааь Ь1 Вычисление этих определенных интегралов дает нам величины верхней и нижней границ: й к — (1пп — 1пй) < Рг(5) < — (1п(п — 1) — 1п(1с — 1)), и и что приводит к достаточно точной оценке величины Рг (Я).
Поскольку нам нужно максимально повысить вероятность успешного исхода, постараемся выбрать значение й, при котором нижняя граница Рг (о) имеет максимум. (Выбор нижней границы продиктован еще и тем, что найти ее максимум легче, чем максимум верхней границы.) Дифференцируя (и/И) (1и г1 — 1и й) по 1с, получаем: 1 — (1пп — 1пй — 1).
и Приравнивая производную к нулю, найдем, что нижняя граница интересующей нас вероятности достигает максимального значения, югда 1п Й = 1пп — 1 или, что то же самое, когда 1с = га/е. Таким образом, реализовав описанную выше стратегию при Й = га/е, мы наймем самого достойного кандидата с вероятностью, не меньшей 1/е. Упражнения 5.4-1. Сколько человек должно собраться в комнате, чтобы вероятность того, что день рождения у кого-нибудь из них совпадет с вашим, была не меньшей 1/2? Сюлько человек необходимо, чтобы вероятность того, что хотя бы двое из них родились 20 февраля, превысила величину 1/2? Часть 1.
Основы 168 5.4-2. Предположим, что Ь урн наполняются шарами. Каждое опускание шара происходит независимо от других, и шар с равной вероятностью может оказаться в любой урне. Чему равно математическое ожидание количества шаров, которое необходимо опустить для того, чтобы хотя бы в одной урне оказалось два шара? * 5.4-3. При анализе парадокса дней рождения было принято предположение о взаимной независимости всех дней рождения.
Является ли это предположение существенным, или достаточно попарной независимости? Обоснуйте ваш ответ. * 5.4-4. Сколько человек нужно пригласить на вечеринку, чтобы вероятность того, что трое из них родились в один и тот же день, достигла заметной величины? * 5.4-5. Какова вероятность того, что строка длиной 1с, составленная из символов п-элементного множества, является размещением Й элементов этого множества? Как этот вопрос связан с парадоксом дней рождения? * 5.4-6. Предположим, что п шаров распределяется по п урнам.
Каждый шар опускается независимо от других и с равной вероятностью может оказаться в любой из урн. Чему равно математическое ожидание количества пустых урн? Чему равно математическое ожидание количества урн с одним шаром? * 5.4-7. Уточните нижнюю оценку длины последовательности выпадений орлов. Для этого покажите, что при п подбрасываниях симметричной монеты вероятность того, что такая последовательность будет не длиннее 1бп — 21818п, меньше 1/п.
Задачи 5-1. Вероятностный подсчет С помощью Ь-битового счетчика можно вести подсчет до 2ь — 1 элементов. Предложенный Моррисом (К. Могг1з) вероятностный подсчет 1ргоЬаЬ1йзйс соипйпй) позволяет проводить нумерацию намного большего количества элементов ценой потери точности. Пусть значение переменной-счетчика г = О, 1,..., 2" — 1 означает номер элемента и; возрастающей последовательности неотрицательных чисел. Предположим, что начальное значение счетчика равно нулю, т.е. по — — О. Операция 1мсквмнчт увеличивает значение счетчика 1 случайным образом.
Если г = 2ь — 1, то в результате этого действия выдается сообщение о переполнении. В противном случае значение счетчика с вероятностью Глава 5. Вероятностный анализ и рандомизированные алгоритмы 169 1/(и,+~ — и;) возрастает на единицу и остается неизменным с вероятностью 1 — 1/(и;+1 — и;). Если для всех г > 0 выбрать и, = г, то мы получим обычный счетчик.
Более интересная ситуация возникает, если выбрать, скажем, гн = 2' или ин = .Р; (г-е число Фибоначчи; см. раздел 3.2). В задаче предполагается, что число изь 1 достаточно большое, чтобы вероятностью переполнения можно было пренебречь. а) Покажите, что математическое ожидание значение счетчика после применения к нему и операций 1нсквмечт равно и. б) Дисперсионный анализ значения счетчика зависит от выбора последовательности иь Рассмотрим простой случай, когда и, = 1001 для всех 1 > О. Оцените дисперсию значения счетчика после выполнения операции 1нскимкнт и раз.
5-2. Поиск в неотсортированном массиве В этой задаче исследуются три алгоритма поиска значения х в неотсортированном и-элементном массиве А. Рассмотрим следующую рандомизированную стратегию. Выбираем элемент массива А с произвольным индексом г' и проверяем справедливость равенства А [1] = х. Если оно выполняется, то алгоритм завершается. В противном случае продолжаем поиск, случайным образом выбирая новые элементы массива А. Перебор индексов продолжается до тех пор, пока не будет найден такой индекс т', что А [т] = х, или пока не будут проверены все элементы массива. Заметим, что выбор каждый раз производится среди всех индексов массива, поэтому круг поиска не сужается и один и тот же элемент может проверяться неоднократно.
а) Напишите псевдокод процедуры Капом БеАксн, реализующей описанную стратегию. Позаботьтесь, чтобы алгоритм прекращал работу после того, как будут проверены все индексы массива. б) Предположим, что имеется всего один индекс г, такой что А [1] = = х. Чему равно математическое ожидание количества индексов в массиве А, которые будут проверены до того, как будет найден элемент х и процедура КАноом Бклксн завершит работу? в) Обобщите решение сформулированной в части б задачи, при условии, что имеется й > 1 индексов г, таких что А [г] = х. Чему равно математическое ожидание количества индексов в массиве А, которые будут проверены до того, как будет найден элемент х и процедура КАноом БкАксн завершит работу? Ответ должен зависеть от величин и и Й. Часть 1. Основы г) Предположим, что условие А Я = х не выполняется ни для какого элемента массива А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
