AOP_Tom3 (1021738), страница 209
Текст из файла (страница 209)
Ч, равна (и+ 1)" 31. Таких возможных связей много, но следующие три — любимые автором [см. также Роага апб К!отбив, сЕЧиаа МасЛ. 10 (1974), 10 — 22). а) В обозначениях из предыдущего ответа счетчики Ьы Ьм..., Ь„соответствуют полной последовательности парковок тогда и только тогда, когда (Ьы Ьг,...,Ь,О) представляет собой корректную погледовательность сглепеией узлов дерева в прямом порядке. (Сравните с 2.3.3-(9), иллюстрирующим обратный порядок.) Каждое такое дерево соответствует и!/Ь|!... Ь„! различным помеченным свободным деревьям на [О,..., и), поскольку можно пометить корень нулем, а для Ь = 1, 2,, и последовательно в прямом порядке выбирать метки из оставшихся неиспользованными, из дочерних узлов Ь-го узла (Ьь + + Ь )!/ЬИ (Ьа ы + + Ьь)! способами, назначая метки слева направо в порядке возрастания.
Каждая такая последовательность счетчиков соответствует и!/Ь~!... Ь ! последовательностнм пробуждении. Ь) Доминик Фоата (Поппи! Чпе Рва!а) дал следующее красивое взаимно однозначное соответствие. Пусть а~... а — удачная последовательность парковок, при которой машина Ч, располагается в позиции !. Помеченное свободное дерево на (О, 1,..., и) строится с помощью линий, проведенныхиз/в 0 прназ = 1 низу вЧ,. ~ впротивном случаедля1 < у < и. (Будем считать узлы дерева автомобилями; автомобиль у связан с автомобилем, который припарковался именно в том месте, где проигулась /-я жена.) Например, моменты пробуждений 3 1 4 1 5 9 2 6 5 приводят согласно правилу Фоата к построению свободного дерева И обратно: последовательность припаркованных автомобилей может быть получена из дерева методом топологической сортировки в предположении, что стрелки указывают от Окончательное дерево 6 Вспомогательное дерево 6 4281 3 1 0 9875 4 2 9 7 Для обращения процедуры можно перестроить всполсогательное дерево, выполняя в прямом порядке обмен меток каждого узла с наибольшей меткой в его поддереве.
Конструкции (а) и (Ь) сильно связаны, но конструкция (с) несколько отличается от них. Она имеет испересное свойство, заключающееся в том, что сумма перестановок автомобилей из их предпочтительных положений равна числу инверсий в дереве — числу пар меток а > Ь, где а является предком Ь. Эта связь между последовательностью парковок и инверсиями дерева была впервые открыта в работе С. Кгекегав, Рег1оойса Масй. Нипб.
11 (1980), 309-320. Тот факт, что инверсии деревьев имеют прямое отношение к связным графам [Ма!1овв апс) ВсогсСшь Ви11. Алпег. Масй. Бос. 74 (1968), 92-94], позволяет сделать вывод о том, что сумма ( ле~), взятая по всем последовательностям парковки, где Р(р) ж ойб (рл — а~) + + (р„— а„). равна общему количеству связных графов с и+ И ребрами на множестве помеченных вершин (О, 1,..., и). (См. формулы (2.11), (3.5) и (8.13) в статье Лапвоп, Ьиссай, КписЬ, апсС Р)ссе1, йапссош Ясгисс. бг А!8. 4 (1993), 233 — 358.) 32.
Будем считать индексы циклическими, т. е. см = са, см+л = сс и т. д. При сз Ь, + сз+л — 1 для всех 1 решений не существует, поскольку сумма по всем 1 дает 2 с, = 51+2 сл — М < 2 с.. Следовательно, каждое решение имеет М вЂ” 2 Ьл значений 1', таких, что Ьз = с,лс = О.
Если (се,..., с'д,) представляет собой другое решение, то должно выполниться условие сг+с > 0 для хотя бы одного такого 1'; но отсюда вытекает противоречие: с',лз > сз+л, с'+л > с1лл, - .. Решение может быть найдено путем определения см м слг л, ..., егли предположитль что са = 0; тогда, если се > О, достаточно переопределять см см л,..., пока дальнейшие изменения не станут ненужными.
33. Отдельные вероятности не являются независимыми, поскольку ие было принято во внимание условие Ье + Ьл + + Ьм-л = 1л'; зто отклонение позволяет сумме 2 Ь~ иметь любое данное неотрицательное значение с ненулевой вероятностью. Соотношения (46) не являются абсолютно корректными; из них следует, например, что Ол положительно при всех й, а это пРотивоРечит томУ фактУ, что сл никогда не пРевосходит Аг — 1. Гастон Ганне (Сазсоп Соппес) иДж. Мунро (3. Манго) (Х А18огсСИтэ 5 (1984), 451-470) обнаружили интересный путь вывода точного результата из аргумента, который привел к (51), введя полезную операцию, названную преобразованием Пуассона последовательности (Ам ): мы имеем е ~* 2 „А,„„(тих)"/и! = ~ л алле тогда и только тогда, когда А „= 2 лали-/т .
л л корневого нуля и выбирается наименьший "источник" на каждом шаге. Из этой последовательности можно восстановить ас... а„. с) Сначала построим вспомогательное дерево, в котором родительский узел узла И является первым элементом, большим 1с, гледующим за ним в перестановке Ос... 9„; если такого элемента нет, родительский узел становится узлолл О. Затем создадим копию вспомогательного дерева и повторно наметим ненулевые узлы нового дерева в прямом порядке при помощи следующей процедуры: если метка текущего узла во вспомогательнолл дереве была Й, замените его текущую метку меткой, которая в текущий момент является (1+ рл — ал)-й наименьшей в его поддереве. Например: 34. (а) Существует (ь) способов выбора множества /, таких, что а» имеет определенное н значение, и (М вЂ” Ц способов присвоения значения другим а.
Таким образом, л — ь Ра ь = ( й ) (И вЂ” Ц -'/И'. (Ь) Рн(х) = В(х) в (50). (с) Рассмотрим общее количество проб для поиска всех ключей, не считая получения указателя на заголовок списка на рис. 38 (при использовании такой таблицы). Список длиной й позволяет добавить к общей сумме ( '»' ) проб:, следовательно, ьы "=~Х.(, ) -/ =( /~)(~ «()+ .'(») (0) В глучае (!) для списка длиной й требуется й проб (не считая получения заголовка списка), в то время как в глучае (й) требуется й+ бье проб.
Значит, в случае (!!) получим Сь = 2,(7»+ бье)Рвь = Р»(ц» Рн(0) = »1'/И+ (1 — 1/М)л и+ с, а в глучае (!) просто С;» — — »т/М = и. В случае, (ш) применима формула МС5 — — М вЂ” Х + ХСя, поскольку М вЂ” »1! хеш-адресов будут указывать на пустые позиции в таблице, в то время как»т хеш-адресов приведут к поиску до конца некоторого списка нз точка внутри него; это дает (18). 36. (!) г.(1+эх — (к+Ц ')Рнь = 1+»У/(2М) — М(1 — (1 — 1/М) +')/(йгя Ц 1+1о — (!в е. ")/п.
(0) Добавьте 2 6»еРнь = (1 — 1/М) е ~ к результату (!). (ш) Ес»ш неудачный поиск начинается с /-го элемента списка длиной к, данный ключ имеет г зучайный порядок по отношению к другим 7» элементам, так что ожидаемая длина поиска составляет (Р 1+2+ +(а+1 — /)+(5+1 — /))/(5+ц. Суммирование по / дает МСн = М вЂ” %+и 2 т(7»~+95'+ гк) Рл,/(ба+6) = м -м+ и(е»ж(57 — Ц/м' ч- $!т/м -1+(и/(57+ Ц)(1-(1 — 1/и) +')); следовательно, Сл~ ж -'о + -'п~ + (1 — е ")/о. 36.
(!)»т/М вЂ” 7»»/Мз. (0) 2 (две+ 7»)~Рьь = 2.(дье+ 7»~)Рль = Рл(0) + Рь(Ц+ Рн(Ц Вычитание (Сл) дает ответ (М вЂ” Ц57/И + (1 — 1/И) (1 — 2"7/И (1 1/М) ) а+с (1 — 2п — е ) < 1 — е ' — е ~ = 0.4968. [Для структур данных (ш) требуется более сложный анализ, подобный приведенному в упр. 37.) 37. Пусть Ял — среднее значение (С вЂ” Це н пусть все Мн !т' выборов хеш-последовательности и ключей равновероятны. Тогда и' 57з, = -'' ,( ) (7п (й, — 1)(й, — Ц + -: + й (й — 4)(й. — Ц) -3 (~с» йм/ 2 2 = -1И), ('~)(М- цн-"й(5- -,')(й — ц 3 я К ~ ( 5 3 1 и ) (8 †) +-'ищи — ц), (~ )(м — ц" ' ь 2)ил з + 1 Ищ(~ цил е 3 2 Дисперсия при этом равна $л — ((»т' — Ц/2М) = (»5! — Ц(»0+ бм — 5)/12М вЂ”,'и+ — 'го~. В СММ5 58.5 рассмотрена интересная связь между общей дисперсией, вычисленной здесь, и двумя другими видами дисперсии: дисперсией (ло случайным хеш-таблицам) среднего числа проб (по всем наличным элементам) и средней (по случайным хеш-таблицам) дисперсией числа проб (по всем наличным элементам) Общая дисперсия всегда является суммой двух других; и в этом случае дисперсия среднего числа проб составляет (М вЂ” 1) (Н— 1)/(2М»Н) 38.
Среднее число проб составляет х,Рл»(2Н»»г-2+4»е) при неудачном поиске и (М/Н) х х 2 Рк»Л(2(1+1/Л)Н» — 3) — при успешном согласно формулам 6.2.2-(5) и 6.2.2 — (6). Эти суммы равны 2/(Аг) + 2ЛХ(1 — (1 — 1/М) т')/(Н+ 1) + (1 — 1/М) — 2 и 2(ЛХ/ЛХ)/(Аг) + 2/(Аг-1)+2ЛХ(1 — (1 — 1/М)н)/Н-3 соответстяенно, где /(Н) = 2. Рн»Н», В упр. 5 2 1-40 говорится о том, что /(Ю) = 1па+ Х+ Ег(а) + 0(М ') при Н = аМ, М -» оо. (Хеширование с деревьями было впервые предложено в работе Р.
Е. »1г1п»1!еу, Сошр. Х. 8 (1960), 84-88. Анализ в предьгдущем параграфе показывает, что такой метод не настолько лучаге обычного метода цепочек, чтобы оправдать введение лишних полей ссылок списки для этого слишком коротки. Более того, когда М мало, хеширование с деревьями не настолько лучше обычного пниска по дереву, чтобы оправдать затраты времени на хеширование.) 39.
(Этот подход к анализу алгоритма С был предложен Дж. С. Внттером (Х. 8. У1»гег).) Имеем слг г(Л) = (ЛХ-lс)сн(Л)+(к-1)сл(Л вЂ” 1) при Л > 2 и, кроме того, 2. Лен(Л) = НМ». Следовательно, лл — ~' (к) — ~~ ((М вЂ” Л)сл(Л) + (Л вЂ” 1), (Л вЂ” 1)) »>г »>г ((М+ 2) ( ) + Л) сн(й) = (М + 2)Як + НЛХ »>г В результате получаем Ял = (Н вЂ” 1)М~ ' + (Аг — 2) М (М + 2) + .. + М(М + 2) ь д (М(М+ 2) — М~~' — 2ЛХЛХ ).
Рассмотрим общее число проб в глучве неудачного поиска, просуммированное по всем М значениям функции Ь(К); каждый список длиной й вносит вклад Й+ Л»е + (») в общую сумму, следовательно, И~+~Си — — М~+~ + Ян. 40. Определим ХХн так же, как и Ял в упр. 39, но с (»), замененным на (~т'). Найдем, что»г и» г = (М + 3) ХХл + Ян + НМ~, значит, ХХн = зе(ЛХ (М вЂ” 6Н) — 9ЛХ(М+ 2)' + 8М(М+ 3) ) Дисперсия равна 2Н~г/Мк ы + Сь — (С~к)~, .что примерно составляет — — — а — -а +(-а — -)е + — с — — е зз г г г. ° г з ° г зш г 4 !ы !г 4» з г ге при Н = аМ, М вЂ” » со. При а = 1 эта величина равна приблизительно 4.50, так что стандартное отклонение ограничено величиной 2.12. 41. Пусть 1 "н — средняя длина блока занятых ячеек на "верхнем" конце таблицы.
Вероятность того, что длина блока равна Л, составляет Ал»(М вЂ” 1 — Л) ~ "/Мь, где Ал»вЂ” число хеш-последовательностей (35), таких, что алгоритм С оставляет первые Аг — Л и последние Л ячеек занятыми, и таких, что подпоследовательность 1 2... Н-Л оказывается расположенной в порядке возрастания. Вследствие этого М $Ъ = ~ » ЛАл»(ЛХ вЂ” 1 — Л)ь » 8= М ~' — т,»(М вЂ” Л)Ан»(М вЂ” 1 — Л)~ = Мл»' — (М вЂ” Аг) ~;» Ал»(М вЂ” Л)д » 8= М~~~ — (М вЂ” Н)(ЛХ+ 1) Теперь Тл = (Н/ЛХ)(1 -» 1к — Те — — Тл г), поскольку Те + + Тл-г представляет собой среднее число предыдущих операций уменьшения Я, а Н/М вЂ” вероятность его уменьшения на текущем шаге.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
