Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 33
Текст из файла (страница 33)
Он сомневается, что этот инвариант выполняется перед первой итерацией. Согласно его доводам пустой подмассив не содержит никаких размещений из О элементов, поэтому вероятность того, что в таком подмассиве находится то илн иное размещение, должна быть равна О. Из этих рассуждений следует, что инвариант цикла перед первой итерацией не выполняется. Перепишите процедуру КАнпомиЕ-1н-Рьлсн таким образом, чтобы связанный с ней инвариант цикла перед первой итерацией применялся к непустому подмассиву, и соответствующим образом модифицируйте доказательство леммы 5.5 для своей процедуры. Глава 5.
Веролтногтныд анализ и рандамизированные алгоритмы !55 5.3.2 Профессор решил разработать алгоритм, в результате выполнения которого получались бы все случайные перестановки, кроме тождественной. Он предложил такую процедуру. РЕКМОТЕ-'зз'1ТНОУТ-1ОЕХТ1ТУ(А) 1 п = АЛепугп 2 1огз' = 1Гоп — 1 3 Обменять А[з] с А[Клхоом(1+ 1, п)] Добьется ли профессор поставленной цели с помощью этого кода? 5.3.3 Предположим, что вместо того, чтобы менять местами элемент А[з] со случайно выбранным элементом из подмассива А[1, . п], мы меняем его местами с любым случайно выбранным элементом массива А.
РекмУте-%1тн-Ап. (А) 1 п = А.(епдгЬ 2 Тогз=1гоп 3 Обменять А[з] с А[Клипом(1, п)] Получится ли в результате выполнения этого кода равномерная случайная пере- становка? Обоснуйте свой ответ. 5.3г4 Профессор предложил для генерации случайных перестановок с однородным распределением такую процедуру. РЕКМУТЕ-В з'-СзСЫС(А) 1 п = А.1епуГЛ 2 Пусть В[1 .. п] — новый массив 3 оЯве1 = ВЛХООМ(1, п) 4 1огз' = 1 гоп 5 Иев1 = 1+ офзег б ЫИезг>п 7 Иевг = оев1 — п 8 В[аевг] = А[з] 9 гегпгп В Покажите, что каждый элемент А[з] оказывается в определенной позиции массива В с вероятностью 1/п.
Затем покажите, что алгоритм профессора ошибочен в том смысле, что полученные в результате его выполнения перестановки не будут распределены равномерно. Часть 1 Основы 15б 5.3.5 * Докажите, что в результате выполнения процедуры Ренмцте-ВУ-ЯОнт1нО вероятность отсутствия одинаковых элементов в массиве Р не меньше величины 1 — 11п. 5.3.6 Объясните, как следует реализовать алгоритм РЕЕМОТЕ-Ву-Бокт11чО в случае, когда два или более приоритетов идентичны. Другими словами, алгоритм должен выдавать случайные равномерно распределенные перестановки даже в случае, если два или более приоритетов имеют одинаковые значения. 5.3. 7 Предположим, что мы хотим создать случайную выборку нз множества (1,2,3,,п), т.е. т-элементное подмножество Я, где О < т < п, такое, что каждое т-подмножество создается с одинаковой вероятностью.
Один из способов состоит в присваивании А[в] = 1 для 1 = 1,2,3,...,и и вызове КАнпомзее-1м-РеАсе(А), после чего следует просто взять первые т элементов массива. Зтот метод выполняет и вызовов процедуры КАмпом. Если п гораздо меньше т, можно создать случайную выборку с помощью меньшего количества вызовов КАМООм.
Покажите, что приведенная далее рекурсивная процедура возвращает случайное т-подмножество множества Я, состоящего из элементов (1, 2, 3,..., п), причем каждое т-подмножество равновероятно, и при этом процедура КАнном вызывается только т раз. КАМООМ-ЯАМРЕЕ(т, п) 1 1Гт==О 2 гегигп 6 3 е1зе Я = КАмном-ЯАМРее(т — 1,п — 1) 4 1 = КАХООМ(1,и) 5 !11е Я 6 Я = Яи(и) 7 е!вел = Яи(г) 8 ге1цгп Я * 5.4. Вероятностный анализ и дальнейшее применение индикаторных случайных величин В этом разделе повышенной сложности на четырех примерах иллюстрируется дальнейшее применение вероятностного анализа. В первом примере вычисляется вероятность того, что двое из Й человек родились в один и тот же день года.
Во втором примере рассматривается процесс случайного наполнения корзин шарами, в третьем — исследуется событие, при котором в процессе бросания монеты несколько раз подряд выпадает орел. В последнем примере анализируется раз- 157 Глава 5. Леролтноетный анализ и рандачюированные алгоритчы новидность задачи о найме сотрудника, в которой решение о найме принимается без проведения собеседования со всеми кандидатами. 5.4.1. Парадокс дней рождении Первым будет рассмотрен парадокс дней роаесдеикя.
Сколько людей нужно собрать в одной комнате, чтобы вероятность совпадения даты рождения у двух из них достигла 50'Ъ? Полученное в результате решения этой задачи число на удивление мало. Парадокс в том, что зто число намного меньше, чем количество дней в году. Чтобы решить задачу, присвоим всем, кто находится в комнате, номера от 1 до )е, где Ь вЂ” количество людей в комнате. Наличие високосных годов проигнорируем и предположим, что в каждом году и = 365 дней.
Пусть для 1 = 1, 2,..., Ь величина Ь; представляет собой дату, на которую приходится день рождения 1-й персоны (1 < 6, < и). Предположим также, что дни рождения равномерно распределены по всему году, так что Рг 16, = г) = 1/и для 1 = 1, 2,..., Ь н г = 1, 2,..., гг. Вероятность того, что даты рождения двух человек 1 и 5 совпадают, зависит от того, является ли случайный выбор этих дат независимым. В дальнейшем предполагается, что дни рождения независимы, поэтому вероятность того, что 1- и 5-й посетители комнаты родились в день г, можно вычислить следующим образом: Рг(6, = т и Ь7 — — г) = Рг(6, = г) Рг (65 = г) = 1/и Таким образом, вероятность того, что оба они родились в один день, равна н Рг (61 = Ь;) = ~~1 Рг (61 = т и Ь5 = т) =1 =Ь/-) в=1 =1/п.
(5.6) Интуитивно легче понять такое утверждение: если день рождения человека Ь, зафиксирован, то вероятность того, что день рождения человека Ь выпадет на эту же дату, равна 1/и. Таким образом, вероятность того, что даты рождения двух человек 1 и 5 совпадают, равна вероятности того„ что день рождения одного нз них выпадет на заданную дату. Однако обратите внимание, что это совпадение основано на предположении о независимости дней рождения.
Теперь можно проанализировать вероятность того, что хотя бы двое из Ь людей родились в один и тот же день, рассматривая дополняющее событие. Вероятность совпадения хотя бы двух дней рождения равна 1, уменьшенной на величину вероятности того, что все дни рождения различаются. Событие, при котором все 159 Глава 5. Вероятностный анализ и рандоиизироеанные алгортныы дя из продолжительности марсианского года, понадобилось бы собрать не менее 31 марсианина.
Анализ с применением индикаторных случайных величин Индикаторные случайные величины дают возможность проведения простого, хотя и приближенного, анализа парадокса дней рождения. Определим для каждой пары (1,5) находящихся в комнате lс людей индикаторную случайную величину Х;., 1 < з < 5 < и следующим образом: Х; = 1 (Дни рождения 1 и 5 совпадают) 1, если дни рождения з и 5 совпадают, 0 0 в противном случае . Согласно (5.6) вероятность того, что у двух людей дни рождения совпадают, рав- на 1/и, и, таким образом, согласно лемме 5.1 мы имеем Е [Х; ] = Рг (Дни рождения 1 и 5 совпадают) = 1/и.
Полагая Х случайной величиной, которая представляет собой количество пар людей, дни рождения которых совпадают, имеем ь ь Х=~' , 'Х;, з=1 5=з+1 Применив к обеим частям этого равенства операцию вычисления математическо- го ожидания и воспользовавшись свойством ее линейности, получаем Е [Х[ = Е ~~ ~~1 Хи5 з=1 у=о91 Е [Хйз[ з=1 5=1Л-1 =('И к(зс — 1) Поэтому, если й(л — 1) > 2п, математическое ожидание количества пар людей, родившихся в один и тот же день, не меньше 1.
Таким образом, если в комнате как минимум з/2п п+ 1 людей, то можно ожидать, что хотя бы у двух из них дни рождения совпадают. При и = 365 и й = 28 математическое ожидание количества пар, родившихся в один н тот же день, равно (28. 27)/(2. 365) 1.0356. Часть 1 Основы 160 Таким образом, если в комнате находится 28 человек, то следует ожидать, что хотя бы у двух из них день рождения совпадет. На Марсе, где год длится 669 дней, для того чтобы добиться того же эффекта, понадобилось бы собрать не менее 38 марсиан.
В ходе первого анализа, в котором использовались только вероятности, определялосзь сколько людей нужно собрать, чтобы вероятность существования пары с совпадающими днями рождения превысила 1/2. В ходе второго анализа, в котором использовались индикаторные случайные величины, определялось количество людей, при котором математическое ожидание числа пар с одним днем рождения на двоих равно 1. Несмотря на то что в этих двух ситуациях точное количество людей различается, в асимптотическом пределе оно одинаково: 0(х/и).
5.4.2. Шары и корзины Рассмотрим процесс случайного наполнения Ь корзин одинаковыми шарами, пронумерованными натуральными числами от 1 до Ь. Шары опускаются в корзины независимо один от другого, и вероятность того, что шар окажется в некоторой из корзин, одинакова для всех корзин н равна 1/Ь. Таким образом, процесс заполнения корзин шарами представляет собой последовательность испытаний по схеме Бернулли (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
