Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 71
Текст из файла (страница 71)
9. [28] Как бы вы изменили алгоритм К, чтобы он заводил одни заданные серии (в зависимости от ЕС) в порядке возрастания, а другие — в порядке убывания? 10. [06] Начальная установка указателей ЫЕЕЕ на шаге К1 обычно не соответствует никакому действительному турниру, твк как внешний узел Р+ э' может не лежать в поддереве с вершиной во внутреннем узле у'. Объясните, почему алгоритм К все равно работает.
[Указание. Будет ли работать алгоритм К, если множеству (ьОЕЕЕООС(Х[О])),..., $ ОЯЕЕ(ЫС(Х[Р— Ц))) присваивается на шаге К1 проиэеольнал перестановка множества (ЫС(Х[О]),..., ЫС(Х[Р— Ц) )?] 11. [М25] Верно ли утверждение, что для случайных исходных данных вероятность того, что ЕЕТ(О) < ЛАЯ?КОТ нв шаге К4, приближенно равна -'? 12. [М46] Детально проанализируйте количество выполнений каждой части алгоритма К.
Например, как часто выполняется перестановка на шаге Кб? 13. [?2] Почему вторая серии, полученная при выборе с замещением, обычно длиннее первой? ь 14. [НМЯ6] Используйте аналогию со снегоочистителем, чтобы оцепить средшою длину двух последних серий, которые получены при выборе с замещением, примененном к длинной посэедовательиости исходных данных. 15. [00] Верно ли, что последняя сериа, полученная при выборе с замещением, никогда не содержит более Р записей? Проанализируйте свой ответ, 18. [МЕ6] Найдите "простое" необходимое и достаточное условие того, что файл )?~ )?з )сл будет полностью упорядочен за один проход Р-путевого выбора с замещением.
Ка- кова вероятность этого события как функции Р и Ф, если исходными данными служит случайная пересчвновка множества (1, 2,...,?т')? 1?. [20] Что получается в результате работы алгоритма К, когда исходные ключи пред- ставляют собой невозрастающую последовательность Ж > Кэ » . Кл? ь 18. [ЕЕ] Что произойдет, если вновь применить аагоритм К к файлу, полученному в результате работы алгоритма К? 19. [НМЕЯ] Используйте аналогию со снегоочистителем, чтобы доказать, что первая се- рия, полученная при выборе с замещением, имеет длину примерно (е — 1)Р записей. 20. [ЯМЗ() Какую примерно ллину имеет первая серия, полученная при натуральном выборе, когда Р = Р'? ь 21.
[ЯМОЮ) Определите приблизительную длину серий, полученных посредством натурального выбора при Р' < Р. 22. [КЩО) Целью этого упражнения является определение средней длины серий, получаемых при натуральном выборе при Р' > Р. Пусть к = )с+ д — действительное числа > 1, где к = [к), а 8 = к шоб 1. Рассмотрим функцию Е(к) ы Рь(е), где Рь(в) — палиномы, определяемые производящей функцией ~ Рь(У)х = е */(1 — ве ').
ьйе Таким обрыом, Ре(у) = 1, Гз(9) = е — д, Рз(9) = ез — е — ед+ -„'б~ и т. д, Предположим, что в момент времени О снегоочиститель начинает моделировать процесс натурального выбора, н допустим, что за Т единиц времени позади него упадут ровно Р снежинок. В этот момент второй снегоочиститель начинает тат же путь, занимая в момент времени 1+ Т та же положение, которое занимал первый снегоочиститель в момент й В конце концов, к моменту «Т пазади первого снегоочистителя упадут ровно Р' снежинок; второй снегоочиститель очищает остаток дороги и исчезает.
Используя эту модель для интерпретации натурального выбора, покажите, что длина серии е Р(к) Р получается при 23. [ЖИо] В предыдущем упражнении проанализирован натуральный выбор в там случае, когда записи из резервуара всегда читаются в там же порядке, в котором они занисывались: "первым включается — первым исключается"'.
Оцените длину серий, которая получилась бы, если бы содержимое резервуара, оставшееся от предыдущей серии, читалось в совершенно случайном порядке, как будто записи в резервуаре тщательно перемешивались между сериями. 24. [НМур) Цель этого упражнения — анализ последствий, вызванных случайным изменением направления упорядочения серий в выборе с замещением. а) Пусть рв(хп зз,..., хь) — та же производящая функция, что и в теореме К, но для каждой из Й серий определена, является лн она восходящей либо нисходящей. Например, мы можем считать, что все серии с нечетными номерами — ве:ходящие, а с четными — нисходящие.
Покажите, что теорема К справедлива для каждой из 2 ь производящих функций такого аида. Ь) В силу (а) можно считать Р ы 1. Можно также предположить, чта исходной является равномерно распределенная последовательность независимых случайных величин в диапазоне между 0 и 1.
Пусть а(х,у) = ез — е" *, солих<у; е' если х > у. Пусть у(х) Их — вероятность того, что определенная возрастиощая серии начинается с х. Докажите, что ()е а(х, у)у(х) Их) Ыу есть вероятность того, что следующая серия начинается с у. [зкизаиие. Рассмотрите для каждого и > О вероятность того, что х<Х| « . Х„>уприданиыххиу,) с) Рассмотрите серии, меыяющие направление упорядочении с вероятностью р; другими главами, направление каждой серии, кроме первой, совпадает с направлением предыдущей серии с вероятностью д = (1 — р) и ыротнвоположыо ему с вероятностью р.
(Таким обрезом, если р = О, то все серии имеют одинаковые направления', если р ы 1, направление серий чередуется, а при р = 1 серии случайны и независимы.) Пусть г! г! И*) =1, У«~ (д) =р/ (*,д)1 (1 — *)дх+д/ (х )А (х)д*. о о Пока!ките, что вероятность того, что п-я серия начинается с х, есть Т„(х) с(х, если (и- 1)-я серия восходящая, и у,!(1- х) дх, если (п — 1)-я серия ннсходшцая. 6) Найдите решение 1 для уравнения установившегося режима г! г! г! г(д) = р / о(х,д)з(1 — х)г(к+ 6 / о(х, д)г(х) Их, / з(х)дх = 1. о о о (Указание. Покажите, что 3'~~(х) не зависит от х.) е) Покажите, что последовательность у„(х) п, (с) весьма быстро сходится к функции /(х) п.
(6). Т) Покажите, что средняя длина восходящей серии, начинающейся с х, равна е! К) Наконец, объедините все предыдущие результаты и докажите следукецую теорему. Если напрааееиыя последовательных серий при выборе с замещением независимо измеюгются на прогывоположнью с вершгтиостью р, то срсдыяя длина серпы стремится к (6! (8+ Р))Р. (Эта теорема при р = 1 впервые была доказана Кнутом (САСМ 6 (1963), 686-688); при р = -' ее дшсазал А. Г.
Конхейм (А. С. КопЬеш) в 1970 году.) 26, (НЩО) Рассмотрите следующую процедуру. И1. Прочитать запись, поместив ее в "резервуар" емкостью в алые слово. Затем прочитать следующую запись К, и пусть К будет ее ключом. Х2. Вывестн содержимое резервуара, установить 1ДЗТКЕТ равным его ключу и очистить резервуар. ХЗ. Ели К < ьаЗТКЕТ, то вывести Е, установить !.АЗТКЕТ +- К и перейти к !лагу Хб. Х4, Если резервуар не пуст, вернуться к шагу Х2; в щютивном случае поместить Е в резервуар.
ХЗ. Прочитать новую запись К и установить К равным ее ключу. Перейти к шагу ХЗ. ! Эта процедура, в сущности, эквивалентна натуральному выбору с Р = 1 и Р' = 1 илн 2 (в зависимости от тога, в какой момент мы опустошаем резервуар — как только он заполнится или когда необходимо будет записать в заполненный резервуар новый злемент, переживающий его), но она порождает нисходящие серии и ее выполнение никогда не прекращается. Такие отклонеыия не приносят вреда„оны удобны для достижения нашей цели.
Действуя, как в упр. 24, обозначим через уь(х, д) Ыр дх вероятность тога, что х н д суть значения 11ЗТКЕТ и К соответственно сразу же после п-га выполнения шага М2. Докажите, чта существует функция д„(х) от одной переменной, тани, что | (х,д) = д.(х), если х < д, и у (х, д) = д„(х) — е "(д (х) — д (д)), если х > д. Фуыкпдя дь(х) определяется соотношениями д!(х) = 1! г г1 д„+»(х) = / с"д (и) ои+ / ое(е+ 1) / ои((е" — Цу„(и) + у„(о)) о о э г» г~ + х/ Нс / Ии ((е — 1)д„(и) + у„(а)). Покажите далее, что ожидаемая длина и-й серии равна » г* г' йх /»11» (у„(х)(г" — 1) + д„(у))(2 — -'д~) + / ох(1 — х)д„(х)е~.
о о о [Зо»»ечеиие. Решение етого уравнения в установившемся режиме оказывается очень сложным; оно была численно найдено Дж. Мак-Кепкой (,1. МсКеппа), Он показал, чта длина серии стремится к прслельной 2.01307209. Теорема К ие применима к натуральному выбору, так что случай Р = 1 нельзя распространить на другие Р,« 26. «Мдд«Рассмотрев алгоритм упр. 25 как определение натурального выбора для Р' = 1, найдите среднюю длину первой серии длк Р' = т при любом г > 0 по следующей схеме. а) Покьжите, что первая серия имеет длину и с вероятностью ( +.)["+"1~( +.+1)1. Ь) Определите "числа Стнрлинга второго порядка" [[ " «) правилами [[ Ц =4~ о, [[ Ц =(и+и» вЂ” 1) ~[[ Ц+[[ Ц) прин>0, [":"1 = ~ ~".:,"ПЛ с) Докажите, что средняя длина первой серии будет, следовательно, равна с,е — » — 1, где ь 27.
[ЯМА) (В. Добосевич (1Ч. ПоЬаяеичся).) Если при Р' < Р используется натуральный выбор, то не нужно прекращать формирование серии после заполнения вспомогательного буфера. Можно сохранять записи, которые не принадлежат текущей серии, в главной приоритетной очереди, как при выборе с замещением, до тех пор, пока в текущей серии не осташ.тся талька Р~ записей.
Тогда их можно сбросить на вьпщл и заменить содержимым вспомогательного буфера. Насколько такой подход лучше более простого подхода, проанализированного в упр. 212 28. [до«В основном тексте раздела рассматривается только сортировка записей фиксированного размера. Как приспособить выбор с замещением к записям пере»»анной длииму 29. [Уд) Рассмотрим 2» узлов полностью двоичного правопрошитого дерева„которое ниже показаяо гре4шчески в варианте, когда и = 3: (Ср.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
