AOP_Tom3 (1021738), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

содержит ли она четное или нечетное число инверсий),и основанный исключительно на сравнениях элементов а, должен выполнить не менее и 1б п сравнений, хотя он имеет всего два возможных исхода. выражение ]и,оьь~ — ис ыо,]. (Хотя этот метод использует гораздо меньше информации, чем содержится в полной матрице сравнений, подобной (24), ои, как оказывается, во многих случаях дает оптимальные результаты.) ь 20. [Мйб] Докажите, что расширенное бинарное дерево имеет минимальную длину внешнего пути тогда и только тогда, когда существует такое число 1, что все внешние узлы находятся на уровнях 1 и 1+ 1 (или, быть может, только на уровне 1). 30.

(М23] (Оитилзаяьная обменная саршираека.) Любой алгоритм обменной сортировки в соответствии с определением, данным в разделе 5.2.2, можно представить в виде дерева сравнений-облгеиае, а именно — в виде структуры бинарного дерева, внутренние узлы которого имеют вид П 1, где ! < 1, и интерпретируются следующим образом: "Есле К < К„то продвинуться по левой ветви дерева; если К, > К,, та поменять местамя записи 1 н 2 и продвинуться по правой ветви дерева" По достижении внешнего узла должны выполняться условия К1 < К « .. К .

Таким образом, дерева сравнений-обмепов отличается от дерева сравнений тем, что оно описывает не только операции сравнения, но и операции перемещения данных. Обозначим через 5. (и) минимальное число сравнений-обменов, необходимых в наихудшем случае для сортировки элементов при помощи дерева сравненнй-обменов. Докажите, что 5,(ц) < 5(п) ж и — 1.

31. (МЯб] Продолжение упр. 30. Докажите, что 5,(5) = 3. 32. (М22] Продолжение упр. 31. Исследуйте значения функции 5,(п) пря малых и > 5. ЗЗ. (Муб] (Т. Н. Хиббард (Т. Н Н!ЬЬагб).) Бещестееииоаначимм деревом поиска порядка х с разрешением 6 называется расширенное бинарное дерево, каждый узел которого содержит неотрицательное действительное значение, такое, что: (!) значение в любом внепшеч узле < 6; (й) значение в любом внутреннем узле не превышает суммы значений двух его потомков; (ш) значение в корне равно х. Длина взеешеииага иржи такого дерева апределнется хак сумма по всем внешним узлам номеров уровней этих узлов, умноженных на содержащиеся в них значения.

Докажите, что вещественнозначное дерево поиска порядка х с разрешением 1 имеет длину взвешенного пути, минимальную среди всех таких деревьев того же порядка н с тем же разрешением тсяда н только тогда, когда в (и) имеет место равенство н для всех пар значений ха и хп принадлежащих узлам-братьям, выполняются следующие условия: ((х) не существует целого числа к > О, такого, что хе < 2" < х1 или х1 < 2" < ха; (х) (хе] — ха ж (х1] — х~ < 1. (В частности, если х — целое число, то нз условия (ч) следует, что все значения в дереве .

целые, а условие (И) эквивалентно результату упр. 22 ) Докажите также, что соответствующая минимальная длина взвешенного пути раяна х(!Зх]+ (х] -2!' *' 34. (Мбб] Определите точные значения функции 5(п) для бесконечного множества аргументов п. Зб. (49] Определите точное значение функции 5(13). 36. [Мбб] (С. С. Кислицын, 1953.) Докажите или опровергните следующее утверждение: любой ориентированный ацнклическнй граф С, в котором Т(С) > 1, имеет две вершины, и н а, такие, что диграфы С~ и Сю полученные из С а результате добавления дуг и е с и и -э а, также ацикли шы и удовлетворяют условию 1 < Т(С,)(Т(Се) < 2.

(Таким образам, Т(С, )/Т(С) ягегда лежит между 1 и = при некоторых и и а.) а5.3.2. Слияние с минимальным числом сравнений Рассмотрим теперь вопрос, имеющий отношение к предыдущему разделу: каков наилучший способ слияния упорядоченного множества гл элементов с упорядоченным множеством и, элементов'! Обозначим элементы гливаемых множеств А! <Аз« А, и В! <Вз« В Как и н разделе 5.3.1, будем предполагать, что все т + л элементов различны. Элементы Аь среди элементов Вь могут располагаться (™~") способами. Таким образом, из анализа, которым мы воспользовались в задаче о сортировке„следует, что необходимо выполнить. по крайней мере, (2) сравнений.

Егли положить пт = ап и устремить и -э оо, оставив а неизменным, то по формуле Стирлинга !е ( ) = п((1 + а) !5(1+ а) — а !ба) — — !йп + 0(1). (3) Обычная процедура слияния (алгоритм 5.2.4М) выполняет в худшем случае го+ив 1 сравнений. Обозначим через М(т, и) функцию, аналогичную Я(п), а именно минимальное число сравнений, заведомо достаточное для слияния гп элементов с и элементами.

Из только что сделанного вывода следует, что г ь( ")1рм(, )«- — ~ р (4) т Формула (3) показывает, насколько далеко могут отстоять друг от друга нижняя и верхняя оценки. При а = 1 (т. е. гп = п) нижняя оценка равна 2п — -'!5п + 0(1), так что обе оценки -- величины одного порядка, но разность между ними может быть сколь утодно велика. При а = 0.5 (т.

е. гп = — 'и) нижняя оценка равна зп(!53 — 3) + О(!ойп), что составляет примерно !53 — 54 е 0.918 от верхней оценки. С убыванием о разница между верхней и нижней оценками все увеличивается, поскольку стандартный алгоритм слияния разработан, главным образом, для массивов с гп — и. При гп = и задача о слиянии имеет весьма простое решение; слишком грубой оказывается ве верхняя, а низюяля оценка в (4). Следующую теорему независимо доказали Р.

Л. Грэхем (В.. Е. Сгабаш) и Р. М. Карп (В.. М. Кагр) примерно и 1968 году. Теорема М. ЛХ(т,т) = 2т — 1 прп 1п > 1. Доказательство. Рассмотрим какой-нибудь алгоритм, который осуществляет слияние элементов А1 « А,„с В1 « Ввг При сравнении элементов А,:В выберем ветвь А, < В„если 1 < з, и ветвь А; > В;, если 1 > у. Слияние должно завершиться конфигурацией (5) В1 < Л1 < Вз < Аз « В < А поскольку она согласуется со всеми выбранными ветвями.

И каждое из 2гп — 1 сравнений В1.Ам А,:Вез Вт.Аз, ..., В;Ам должно быть выполнено явно, иначе найдется по меньшей мере две конфигурации, не противоречащие известным фактам. Если бы мы, например, не сравнили А1 с Вт, то конфигурация В1 < Вз < А1 < Аз « . В,„ < А„, была бы неотличима от (5). $ Несложная модификация этого доказательства дает аналогичную формулу М(т,т+Ц = 2т при т > О. (6) Определение нижних оценок. Теорема М показывает, что "теоретико-информационная" нижняя оценка (2) может сколь угодно далеко отстоять от истинной нижней границы; таким образом, метод доказательства теоремы М дает нам еще один способ нахожденяя нижних оценок.

Такой метод доказательства часто рассматривается как порождение соперника, советы которого принуждают алгоритм работать как можно медленнее. Когда алгоритм слияния решает сравнить элементы А,: В, соперник так определяет судьбу сравнения, что вынуждает алгоритм избрать наиболее трудный путь. Если бы мы смогли придумать подходящего соперника, то смогли бы убедиться в том, что всякий правильный алгоритм слияния должен выполнить довольно мало сравнений.

Мы будем использовать соперников с оарапичспнмми оозмоэкпостлми, воздействие которых лимитировано заранее заданными результатами некоторых сравнений. В методе слияния, находящемся под воздействием соперника с ограниченными возможностями, ограничения считаются неизвестным~, и поэтому выполняются все необходимые сравнения даже в том случае, когда их результат предопределен. Например, в доказательстве теоремы М мы ограничили все результаты сравнений условием (5), тем не менее в алгоритме слияния нельзя воспользоваться этим обстоятельством, чтобы избежать хотя бы одного сравнения. Ограничения, которые мы будем использовать в следующем ниже анализе, относятся к левому и правому концам массивов, Левые ограничения обозначаются следующими символами: , (нет ограничения слева), '1 (результаты всех сравнений не должны противоречить услови1о А1 ( В1), / (результаты всех сравнений не должны противоречить условию А| > В,).

Аналогично правые ограничения обозначаются следующими символами: . (нет ограничения справа), '1 (результаты всех сравнений не должны противоречить условию А„, < В„). / (результаты всех сравнений не должны противоречить условию А,„> Вп). Существует девять типов соперников, обозначаемых символами ЛАХр, где Л вЂ” левое ограничение, а р †. правое.

Например, соперник 1М'1 должен говорить, что А1 ( В. н А„с Вп: соперник .М. не подчиняется никаким ограничениям. При некоторых малых значениях т н п может не существовать соперников с ограниченными возможностями некоторых типов: при т = 1., очевидно, нс может быть соперника ~М/. Займемся теперь построением весьма сложного, но чрезвычайно коварного соперника для слияняй. Он не всегда порождает оптимальные результаты, но дает нижние оценки, которые охватывают множество интересных случаев. Предположим, заданы т и и, а также левые и правые ограничения Л и р.

Пусть соперника спрашивают, какой из двух элементов (А, нли В ) больше. Соперник может, вообще говоря, применить 6 стратегий приведения задачи к случаю меныпего значения п1+п. Стратпггия А(й', 1) для т < 1с < т и 1 < 1 < тй Ответить, что А, < Вз и потребовать, чтобы последующие операции осуществляли слияния (А,,..., Аь) с (Вт,..., Вт и (Аьед,, А ) с (Вт,..., В„). Тогда последующие сравнения Ар. В дадут такие РезУльтаты: Ар < В», если Р < й и т! > 1: Ар > В», если Р > й н а < 1; они будут управляться соперником (й,1 — 1,Л,.), если р < й и т! < 1, и соперником (т — й, и+1 — 1,, р), если р > 1с н а > 1.

Стратегия В(й,1) для т < 1с < т и 1 < 1 < уй Ответить, что А, < В, и потребовать, чтобы последующие операции осуществляли слияния (Ат,..., Аь) с (Вт,..., Вт) и (Аьет,...,А„,) с (Вт,..., В„) при условии Аь < Вт < Аь,.т. (Обратите внимание на то, что Вт присутствует в обоих списках, подлежащих слиянию. Условие Ая < Вт < Аьет обеспечивает такое положение, при котором слияние одной пары лтасснвов не может дать никакой информации, которая бы помогла прн слиянии другой пары.) Тогда последующие сравнения А„:В» дадут такие результаты: Ар < В», если р < й н а > 1; Ар > В», если Р > й и т! < 1; они бУдУт УпРавлЯтьсЯ сопеРником (й,1, Л, 1), если р < й и т! < 1, и соперником (т — й, и+1 — 1, /, р), если р > й и д > 1.

Характеристики

Список файлов книги