AOP_Tom3 (1021738), страница 185
Текст из файла (страница 185)
(1, О) = 0 Нетрудна праверитгч что этому соотношению удовлетворяет решение ()8(п -ь 1)). 4. Нет (см. С. СЬпв!еп, РОСЫ 19 (1978), 259-266). 6. При ! .= л + 1 можно воспользоваться стратегией А'(л, л+1), за исключением случая л < 2. При з' > л + 2 можно применить стратегию А(1, 1-~-2). 7. Чтобы вставить й + т элементов в пошледавательнасть и других элементов, вставьте независимо !л элементов и т элементов. (Если й н т велики, та можно применить более совершенную процедуру; см.
упр. 19.) 8. На следующих диаграллмах л: ! означает сравнение А,. В,", через Ма обозначена слияние л элементов с з элементами за М(л',2) шагов, а через А — сортировка конфигурации ~ или~',за три шага лв Мы Мы Млз+1 А М»г рячво »ум+1 »Г~»+2 11. Воспользуемся указанием: положим и = дь Можем считать, что 1 > 6 Без потери общности можно первым сравнением сделать АыВ . Если 1 > д~ ц то исход А» < Вэ потребует еще > Г шагов. Если» < д, и то исход А» < В, не вызовет трудностей, и поэтому необходимо исследовать лишь случай Аэ > Вэ. Балыле всего информации мы получаем при 1' = д» ы Если 1 = И+ 1, то можно было бы слить А» с д~ — д~-~ = 2» элементами, превышающими Вп»ы и слить А» с остальными д, » элементами, но для этого понадобилось бы еще )г+ ()» + 1) = Г шагов. С другой стороны, если и = д» вЂ” 1, то можно было бы слить Аэ с 2 — 1 элементами, а затем А~ — с и элементами еще за » †! (lс — 1) + (й + 1) шагов.
Следовательно, ЛХ(2, 9~ †) < а Случай 1 = 2lг значительно сложнее; обратите внимание на та, что д» вЂ” д~ ~ > 2» Предположим, что если А» > Вп» ы то мы будем сравнивать А,;В,. Если 1 > 2" ', та исход А~ < Ву потребует еще Ь+(Ь вЂ” 1) сравнений (слишком много).
Если г < 2» ', то можно, как и раныпе, доказать, что выбор 1' = 2 ' даст больше всего информации. Б случае А» > В»»-~ можно было бы сравнить также А» с В,»-»„э»-», затем с В»» ~»з»-»»э»-»; поскольку 2 '+2 +2 з > д»-», остается лишь слить (А~, Аэ) с и — (2» '+2» +2» ) элементами. Разумеется, вовсе не обязательно сразу же выполнять какие-либо сравнения с Ац можно вместо этого сравнить Аэ: Вв»» „.. Если 2 < 2» з, то рассматриваем случай Аг < В»» ы если же 1 > 2 э, то рассматриваем Аэ > В„»~ .. Этот последний случай требует еще не менее (я — 2) + (й+ 1) шагов. Продолжая рассуждение, обнаруживаем, что единсшееннмй потенциально плодотворный путь — это Аэ > Вэ...
Аз < В +~ »» э, А» > Вэ»-ы А» > В,» ~+э»-», А» > В»» ~+»»-»»з»-з, ио тогда остается еще ровно д»» элементов. Обратно, если и = д> — 1, то этот путь приводит к желаемому результату. [Асса 1пГогшас(са 1 (1971), 145 †1.! 12. Первое сравнение должно быть либо опХ», где 1 < Ь < г, либо (симметрично) Д: Х», где 1 < й < ~, Б первом случае при исходе а < Х» остается выполнить еще В„(Й вЂ” 1,1) сравнений; исхода > Х» приводит к задаче сортировки а < Д, У~ < < У„», г» < У;-»э м В > У„» м где 1г = Х„ 13. Сль Сошригегя ш Хишбег 2 йеогу (14ен Уог(»: Асабеш(с Ргееэ, 1971), 263 — 269.
14. ЯСОМР 9 (1980), 298 — 320. Полное решение для случая М(4,и) получено спустя непродолжительное время в работе Л. БсЬп!Се„Мбпйаб, Тйеаг. Сошр. Яс!. 14 (1981), 19-37, где также предлагается решение лля случая М(5, и). 15. Удваивать т до тех пор, пока результат не превзойдет и.
Для этого придется выполнить (!8(и/т)) -!-1 операций удваивания. 10. При всех (т, и), за исключением (т, и) = (2, 8), (3, б), (3, 8), (3, 10), (4, 8), (4, 10), (5, 9), (5. 10). При этих значениях число сравнений на единицу больше оптимального. 17. Предположим, т < ич н пусть ! = !8(и/т) — 9.
Тогда !8(~т") > !8и — 18т! > т !8и — (т!бт — т+1) = т(!+6)+т — 1 = Н(т, и)+От — (2~т) > Н(т, и)+Вги — 2 т > Н(т,и) — т, (Неравенство т! < т 2' является следствием того, что й(т-й) < (т/2) при 1 < й < т ) 19. Слейте сначала (Ам..., А,„) с (Вэ, Вм, Вг! !е, ). Тогда останется вставить нечетные элементы Вм ~ в последовательность о. элементов А, 1 < ! < (и/2), где о~+аз+ + о1„7э! < т. При выполнении этого последнего действия на каждое значение 1 придется выполнить а; операций, так что для завершения сортировки достаточно выполнить еще не более ги сравнений.
20. Применить неравенство (12). 22. В работе В. МьсЬае! Таппег, 31СОМР 7 (1978), 18 — 38, показано, что в алгоритме "фрактальных вставок' используется в среднем не более 1.06 !8 ( э") сравнений. В работе Ь. Ко!!бг, Сошрисегз я .4гййс!а! 1л!. 5 (1986), ЗЗо-344, проанализировано поведение "в среднем" алгоритма Н 23. Соперник имеет матрицу Х размера и х и, элементы которой х, вначале все равны едгшице. Когда алгоритм спрашивает, имеется ли равенство А, = В„, соперник устанавливает хц равным нулю. Он отвечает "нет" да тех пор, пака перманент матрицы Х не станет равным нулю.
В этом случае соперник отвечает "да" (ему ничего не остается делать, иначе выполнение алгоритма немедленно завершится!) и исключает из матрицы Х строку ! и столбец 1; полученная матрица (и — 1) х (и — 1) будет иметь ненулевой перманент. Соперник продолжает и дальше действовать таким образом, пока у него не останется матрица 0 х О. Если перманент близок к нулю, можно перекомпоновать строки и столбцы таким образом, что ю = 1 = 1 н все единицы будут иа главной диагонали матрицы.
Таким образом перманент обращается в нуль, егли хм з — 1; значит, мы должны получить хыхы — — О для всех й > 1. Отсюда следует, что, по крайней мере, и нулей удаляются при первом ответе "да" соперника, а и — 1 — при втором ответе и т. д. Выполнение алгоритма завершится лишь после получения и положительных ответов на неизбыточные вопросы и после того как мы зададим, по меньшей мере, и+ (и — 1) + + 1 вопросов (ЗАСМ 19 (1972), 649-659!. Аналогичные рассуждения приведут иве к заключению, что необходимо и+(и — 1)+. + (и — т+ 1) вопросов для того, чтобы выяснить, что А С В при )А) = т < и = ~В(, 24.
Грубое предварительное слияние потребует не более и~ -~- 9 — 1 слияний, а каждая последующая процедура вставки — не более 0 Эта верхняя оценка не может быть уменьшена. Таким образом, максимальное число сравнений будет тем же, что и в алгоритме Н (см. (19)). 25. В общем, сложность этой задачи такова же, как и для отдельною случая, когда каждый элемент хо — это либо О,либо 1 и х = э.
Тогда каждое сравнение эквивалентно 1 анализу бита хб и мы стремимся определить всю матрицу, просматривая только младшие разряды. Любая задача сортировки (1) соответствует матрице 0-1, если установить хб = (А;>В ~~,). (В работе 74 1йп!а(, .М. Яайэ, 1. А!8огЫЬпм 6 (1985), 86-103, этот вывод приписывается Дж.
Ширеру (Л БЬеагег). Аналогичный результат связывает сортировку и поиск при любом частичном упорядочении.) РАЗДЕЛ 5.З.З 1. Игрок 11 проиграл игроку 06, поэтому известно, что игрок 1д глабее, чем игроки 0$, 11 и 13. 2. Пусть х есть 1-й в порядке убывания элемент и пупп 5 есть множество всех элементов у, таких, что выполненных сравнений недостаточно для доказательства того, что я < у и д < х. Существуют перестановки, удовлетворяющие всем выполненным сравнениям, но в них ясе элементы Я меньше, чем х, действительно, мы можем потребовать, чтобы все элементы Я были меньше, чем х, и вложить полученное частичное упорядочение в линейное упоркдочение. Аналогично существуют допустимые перестановки, в которых все элементы Я больше, чем х.
Следовательно, мы не можем знать положение и, если Я не пусто. 3. Соперник может считать проигравшего в первом сравнении слабейшим среди всех игроков. 4. Предположим, что наибольшие !! — 1) элементов — это !ам...,а~ ~). Любой путь определения наибольших бэлементов на дереве сравнений, совместимый с этим предположением, должен включать, по меньшей мере, и — ! сравнений для определения наибольшего из оставшихся п — ! + 1 элементов. Каждый из таких путей должен иметь не менее и — ! точек выбора альтернатив, т.
е их в сумме существует не менее 2" '. Таким образом, каждый из и'— -' выборов наиболыпих (1 — 1) элементов должен появиться не менее чем в 2" ' листьих дерева. б. Действительно, !1'~(п) < Ъ;(и) + 5(~ — 1),как следует из упр. 2. 6. Пусть дПп1м...,1, ) = тл — 2+~!3!2О+2"-» -»2»")), и допустим, что у' = длля1~+!г» +1м+2т < Х. Докажем, что 7' = д, если 1~+1»+ . +1 +2т = Л'. Мы можем считать, что 1~ > В > > ! . Существует лишь несколько способов выполнения первого сравнения.
Стратегия А(у,й) при у < 1». Сравнить паиболыний элемент группы у с наибольшим элементом группы 7» Это дает соотношение П)м 1 ) < 1+ дП» .,11-1 1»+1 )з "л . !» — 1 1»чм 1 ) = д(Хм,1~ — м1»,1.»м...,1» — и!з,!»»м,1 ) > д(1п,! ), Сшрашегпл В(у, )г) при!» > О. Сравнить наибольший элемент групггы у с одним из меньших элементов группы /с. Это дает соотношение 7!1м...,! ) < ! + шах!а,)7) = 1 + !3, где а = д(1п..., 1, ), 1!»,,..., 1,„) < д(1,, ! ) — 1, 0 = 0Пм..., !» и 1» — 1, 1».„),...,1 ) > д!1м...,1 ) — 1. Сшрвше»ол С9, /с) при у < )с, 1, > О, 1» > О. Сравнить один из меньших элементов группы у с одним из меньших элементов группы 7» Соответствующим соотношением будет /(1м.-.,! ) < 1+ дПм...,!» м1» — 1.!»»и, ..,1 ) > д!1п...,1 ). Значение Ям..., 1 ) найдем, взяв минимум правой части среди всех этих стратегий; следовательно, 1'»1м..., ! ) > дПп...,1 ).
Если т > 1, то стратегия А»т — 1, ш) показывает, что Щ,...,1ш) < д(1м...,1 ), поскольку д(1м ..,,1 и!, ) = д(1м...,1»,1 ~), если 1в » . 1 . (Дохазательстео, )!БАЛХ+ 2")) = )!3[ЛХ -» 2 )) при О < а < Ь, если М есть положительное кратное 2».) Если и» = 1, используйте стратегию С(1, 1). ~В статье С. С. Киглицьпш определена оптимальная стратегия А(ш — 1, т) и вычислено 1 »1, 1,..., 1) в замкнутом виде; общая фор»»ула для 1 и это упрощенное доказательство были получены Флойдом в !970 году.) 7. При у > 1, если 7 + 1 находится в а', с, равно 1 плюс число сравнений, необходимых для выбора следующего в порядке убывания элемента оа. Аналогично в случае, если у + ! находится в а~', с~ всегда равно О, так как деревья в конце всегда выглядят одинаково. 8.
Другими словами, существует ли расширенное бинарное дерево с и внешними узлами, такое, что сумма расстояний от корня до 1 — 1 наиболее удаленных внутре»ших узлов меныне, чем соответствующая сумма для полного бинарного деревау Ответ на этот вопрос отрицательный, поскольку (как нетрудно показать) й-й в порядке убывания элемент р(о) больше илн равен (!8(п — (с)) при всех сс 9. (Для всех путей используются шесть сравнений, однако зта процедура не оптимальна для Уз(5).) речка 10. (в1едиана найдена вручную путем проб и ошибок; использовано упр. б, чтобы упростить нахождение полезных линий.) 11.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
