Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 35
Текст из файла (страница 35)
Чтобы подсчитать общее количество таких последовательностей, определим о-1-1-1 Х= ~' Хс„ г=1 Вычислив от обеих частей этого равенства математическое ожидание и использо- вав его линейность, получаем о-и+1 Е[Х] = Е 2 Хгн 1=1 о — Й-~.1 Е [Хси[ г=1 н-и+1 Рг (Авя) 1=1 н-и+1 1/2" 1=1 и — /с+ 1 21 Подставляя в полученное соотношение различные значения и, можно определить математическое ожидание количества последовательностей длиной /с. Если зто число окажется большйм (намного превышающим единицу), то следует ожидать большого количества последовательностей выпадения орлов длиной /с с высокой вероятностью появления. Если же это число намного меньше единицы, то встретить такую последовательность в серии испытаний маловероятно. Если Часть 2 Оснссн 1бб Й = с 1к и для некоторой положительной константы с, получим Е~Х) = 2с!к с и — с1яп+ 1 Пс 1 (с1бп — 1)/и пс-1 пс — 1 =Е(1/ ' ').
Если число с достаточно велико, математическое ожидание количества последовательностей непрерывных выпадений орла длиной с1к п очень мало, из чего можно заключить, что это событие маловероятно. С другой стороны, если с = 1/2, то мы получаем Е 1Х) = 9(1/и'1з з) = тз(пз?з), и можно ожидать, что будет немало последовательностей орлов длиной (1/2) 1к п. Поэтому вероятность того, что встретится хотя бы одна такая последовательность, достаточно велика.
Исходя лишь из этих грубых оценок, можно заключить, что ожидаемая длина самой длинной последовательности орлов равна Й(1яп). 5.4.4. Задача о найме в оперативном режиме В качестве последнего примера рассмотрим одну из разновидностей задачи о найме сотрудника. Предположим, что в целях выбора наиболее подходящего кандидата мы не хотим проводить собеседование со всеми претендентами. Мы не хотим также повторять процедуру оформления на работу нового сотрудника и увольнения старого в поисках наиболее подходящей кандидатуры. Вместо этого мы попытаемся подыскать такого кандидата, который максимально приблизится к наивысшей степени соответствия должности.
При этом необходимо соблюдать одно условие: после каждого интервью нужно либо сразу предложить должность претенденту, либо отвергнуть его. Как достичь компромисса между количеством проведенных интервью и квалификацией взятого на работу кандидата? Можно смоделировать эту задачу таким образом. После встречи с очередным кандидатом каждому из них можно дать оценку. Обозначим оценку 1-го кандидата как зсоге(1) и предположим, что всем претендентам выставлены разные оценки. После встречи с з кандидатами будет известно, какой из этих з претендентов на должность получил максимальную оценку, однако остается неизвестным, найдется ли среди оставшихся и — з' кандидатов человек с более высокой квалификацией. Будем придерживаться следующей стратегии: выберем положительное целое число Й < и, проведем интервью с lс претендентами, отказав всем им в должности, а затем возьмем на работу первого из последующих претендентов, оценка которого будет превышать оценки всех предыдущих кандидатов.
Если же самый квалифицированный специалист окажется среди первых й претендентов, то придется взять на работу и-го кандидата. Формальная реализация этой схемы представлена в приведенной ниже процедуре Ом-1 пчп-Млх1мцм(/с, п), которая возвращает номер нанимаемого кандидата.
Глана 5. Вероятностный анализ и рандоыизираеаииые овеориооиы 1б7 Он-Ь1гсн-МАх1м11м()с, и) 1 Ьев1всоте = -со 2 Гоге = 11о )с 3 11 всотеЯ > Ьез1всоте 4 Ьез1всоте = всоте(1) 5 Гаг 1 = lс + 1 Го и 6 И'всотеЯ > Ьев1зсоте 7 ГЕПвтн 1 8 ге1пгп п Мы хотим определить для каждого положительного )с вероятность того, что будет нанят наиболее квалифицированный претендент. Затем выберем наилучшее из всех значений lс и реализуем описанную стратегию с зтим значением. Пока что полагаем )с фиксированным. Обозначим наивысшую оценку кандидатов с номерами от 1 до 7' как М(~) = шах1<,< (всоте(1)).
Пусть  — событие, определяемое как выбор самого квалифицированного кандидата, а Вс — событие, при котором самым квалифицированным нанатым на работу кандидатом оказался с-й. Поскольку все события Вв являются взаимоисключающими, выполняется соотношение Рг (В) = 2 '," 1 Рг (Вс). Заметим, что поскольку согласно нашей стратеги ни один из первых Ь претендентов на работу не принимается, Рг(В1) = 0 для 1 = 1, 2,..., Iс. Таким образом, получаем Рг(В) = ~~ Рг(В1) онн-'н1 (5.12) Теперь вычислим величину Рг (В,).
Чтобы на работу был принят 1-й кандидат, необходимо выполнение двух условий. Во-первых, в 1-й позиции должен оказаться самый квалифицированный кандидат (обозначим зто событие как Вс), а вовторых, в ходе выполнения алгоритма не должен быть выбран ни один из претендентов, пребывающий на позициях с Ь + 1-й по 1 — 1-ю, что произойдет только тогда, когда при всех 7, таких, что Ь+ 1 < 7' < 1 — 1, в строке б будет выполняться условие весте(1) < Ьев1всоте. (Поскольку оценки не повторяются, возможность равенства всоте(7) = Ьев$всоте можно проигнорировать.) Другими словами, все оценки от весте()с+1) до весте(1 — 1) должны быть меньше М(/с); если же какая-то из них окажется больше М(/с), то будет возвращен индекс первой из оценок, превышающих все предыдущие.
Обозначим как О, событие, заключающееся в том, что на работу не взят ни один из претендентов, проходивших собеседование под номерами от )с + 1 до 1 — 1. К счастью, события В, и О, независимы. Событие О; зависит только от порядка нумерации кандидатов, которые находятся на позициях от 1 доз — 1, а событие В; зависит только от того, превышает ли оценка кандидата 1 оценки всех прочих кандидатов. Порядок оценок в позициях от 1 до 1 — 1 не влияет на то, превышает ли оценка 1'-го претендента все предыдущие оценки, а квалификация 1-го кандидата не влияет на расположение кандидатов с порядковыми номерами от 1 до 1 — 1.
Таким образом, можно применить уравнение (В.15), с/авось Е Основы /бв чтобы получить Рг(Вг) = Рг(В; О О;) = Рг(В,) Рг(О,) Ясно, что вероятность Рг (Вс) равна 1/и, поскольку кандидат с наивысшей квалификацией может находиться в любой из и позиций с равной вероятностью. Чтобы произошло событие О„наиболее квалифицированный кандидат среди претендентов с номерами от 1 до 1 — 1 должен находиться на одной из первых /с позиций. Он с равной вероятностью может оказаться на любой из этих г — 1 позиций, так что Рг (О,) = й/(1 — 1) и, соответственно, Рг(Вс) = /г/(и(1 — 1)).
Воспользовавшись уравнением (5. 12), получим Рг(В) = Е Рг(Вв) с=в~-1 и / п(( — 1) й 1 =-Е— п с' — 1 с=ни-1 /с 1 п с=в Ограничим приведенную выше сумму сверху и снизу, заменив суммирование ин- тегрированием. Согласно неравенствам (А.12) получаем и 1 'с 1 и-1 1 с=н Вычисление этих определенных интегралов дает границы й й — (1п п — 1и й) ( Рг (В) < — (1п(п — 1) — 1п(/с — 1) ), что приводит к достаточно точной оценке величины Рг(о').
Поскольку нам нужно максимально повысить вероятность успешного исхода, постараемся выбрать значение й, при котором нижняя граница Рг(В) имеет максимум.(Выбор нижней границы продиктован еще и тем, что найти ее максимум легче, чем максимум верхней границы.) Дифференцируя выражение (й/и)(1п и — 1п й) по й, получаем 1 — (1п и — 1п й — 1) Приравняв производную к нулю, найдем, что нижняя граница интересующей нас вероятности достигает максимального значения, когда 1п й = 1и п — 1 = 1п(п/е) илн, что то же самое, когда й = и/е. Таким образом, реализовав описанную выше !б9 Глаеа 5. Веролтноетный анелю и рандотилироеанные алгоритмы стратегию при й = п/е, мы наймем самого достойного кандидата с вероятностью, не меньшей 1/е. Упражнении 5.4.1 Сколько человек должно собраться в комнате, чтобы вероятность того, что день рождения у кого-нибудь из них совпадет с вашим, была не меньшей 1/2? Сколько человек необходимо, чтобы вероятность того, что хотя бы двое из них родились 7 ноября, превысила величину 1/2? 5.4.2 Предположим, что мы наполняем Ь корзин шарами до тех пор, пока в какой-то из корзин не окажется два шара.
Все опускания шаров выполняются независимо, и шар с равной вероятностью может оказаться в любой корзине. Чему равно математическое ожидание количества опущенных в корзины шаров? 5.4.3 * В ходе анализа парадокса дней рождения было принято предположение о взаимной независимости всех дней рождения. Является ли это предположение существенным, или достаточно попарной независимости? Обоснуйте свой ответ. 5.4.4 * Сколько человек нужно пригласить на вечеринку, чтобы вероятность того, что трое из них родились в один и тот же день, достигла заметной величины? 545 * Какова вероятность того, что строка длиной Ь, составленная из символов и-элементного множества, является размещением й элементов этого множества? Как этот вопрос связан с парадоксом дней рождения? 5.4.6 * Предположим, что и шаров распределяются по п корзинам.
Каждый шар опускается независимо от других и с равной вероятностью может оказаться в любой из корзин. Чему равно математическое ожидание количества пустых корзин? Чему равно математическое ожидание количества корзин с одним шаром? 5.4. 7 * Уточните нижнюю оценку длины последовательности выпадений орлов. Для этого покажите, что при и подбрасываниях симметричной монеты вероятность того, что такая последовательность будет не длиннее 1к и — 2 1к 1я и, меньше 1/п.
Часть!. Основы 770 Задачи 5,1. Вероятностный подсчет С помощью Ь-битового счетчика моькно вести подсчет до 2" — 1 элементов. Предложенный Р. Моррисом (К. Могпз) вероятностный подсчет (ргоЬаЬВ!зг!с соцпг!пя) позволяет проводить нумерацию намного большего количества элементов ценой потери точности. Пусть значение переменной-счетчика 1 = 0,1,...,2ь — 1 означает номер элемента гц возрастающей последовательности неотрицательных чисел. Будем считать, что начальное значение счетчика равно нулю, т.е. по = О. Операция !исккмя1чт увеличивает значение счетчика! случайным образом. Если! = 2ь — 1, то в результате этого действия выдается сообщение о переполнении.
В противном случае значение счетчика с вероятностью 1/(пььг — тн) возрастает на единицу и остается неизменным с вероятностью 1 — 1/(п,~г — и,). Если для всех 1 > 0 выбрать и; = ь', то мы получим обычный счетчик. Более интересная ситуация возникает, если выбрать, скажем, и; = 2* ' для 1 > 0 или кч = Г, (1-е число Фибоначчи; см, раздел 3.2).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
