AOP_Tom3 (1021738), страница 11
Текст из файла (страница 11)
[20] (Р. У. Флойд.) Покажите, что можно выбрать й наибольших и ! наименьших элементов множества из и элементов, использовав не более [1и] -й-1+2 „+, „«,„[187]+ э" ы ~«„[181[ сравнений 18. [М20[ Если бы в доказательстве теоремы Е использовались группы размером 5, а не 7, то какая бы получилась теорема? 19. [М42] Расширьте табл. 2 для и = 8. 20. [М47] Каково значение асимптотического выражения для !гг(и) — и при и -! оа? 21. [22] (П. В. Раманан (Р. У. В.а<папан) и Л. Хьяфил (Е. Нуаб!).) Докажите, чта Иг,(2ь+ 2"+' г) < 2" +2"+' '+(! — 1)(й — 1), если й > 1 > 2; покажите также, что имеется равенства для бесконечно больших й н 1, используя результаты упр. 4.
[Указание. Постройте два дерева турниров с выбыванием и разумно скомбинируйте полученные результаты.] 22. [24] (Дэвид П Киркпатрик (Оач(б 6. К1гйрасг1<й).) Покажите, что в случае 4. 2" < и — 1 < 5 2" верхняя оценка (11) для Уэ(и) может быть следующим образом уменьшена на 1. (1) Образуйте четыре "дерева с выбыванием" размером 2".
(и) Найдите минимальный из четырех максимумов и удалите все 2" элементов соотч тствуюшего дерева. (ш) Используя накопленную информацию, постройте одно дерево с выбываннем размером и — 1 — 2~. (ге) Продолжайте, как при доказательстве (11). 23. [М49[ Каково асимптотическое значение У1„?э1(и) при и э оа? 24. [НМ40[ Докажите, что Ус(и) < и+ 1+ 0(ъгй!аби) при ! < [иг2) Указание.
Покажите, что, используя столько сравнений, можно фактически найти и [! — ч'Г!пи)-й, и [Г+ ъ'Г !и и ~[-й элементы, после чего легко выявляется 1-й. э 2б. [М?5[ (В. Кунта (%'. Спасо) и Дж. И. Мунро (д. 1. Мппго).) Докажите, что У~(и) > и + à — 2, если ! < [и/2). 26. [МЗЯ[ (А.
Шепхаж (Л. БсЬопЬабе), 1974.) (а) Докажите в обозначениях упр. 14, что (А(и) > гп!п(2+ ?А(и — 1),2+ Ц ~(и — 1)) при и > 3. [Указание. Сконструируйте соперника посредством уменьшения количества элементов с и до и — 1 до тех пор, пока частичное упорядочение не будет состоять полностью из компонентов вида ° нли (Ь) Аналогично докажите, что (А(и) > шш(2+ (А(и — 1),3+ (А-~(и — 1),3+ 1?р(и — 2)) при и > б, сконструирован соперника, который имеет дело с компонентами ° .
~ ~. (с) Таким образом, получим К(и) > и+ 1+ ппп([(и — 1)/2),1) — 3 при 1 < ! < и/2. [Неравенства в (а) и (Ь) относятся также к случаю, когда 1' или (4' заменяет 1?, обеспечивая таким образом оптимальность определенных элементов в табл. 1.[ ь 27. [МЛ4[ Рпндомнэирэеаннмй соперник — это соперник, алгоритм поведения которого позволяет прн принятии решения использовать подбрасывание монеты. а) Пусть А — рандомизированный соперник и пусть Рг(1) — вероятность того, чта А достигнет листа ! данного дерева сравнений.
Покажите, что, если Рг(1) < р для всех 1, высота дерева сравнений > !3(1/р). Ь) Проанализируйте поведение следующего соперника для выбора г-га по старшинству из и элементов, причем целочисленные параметры о и г будут выбраны позже. А1. Выбирается случайное множество Т, состоящее из 1 элементов; все (~) вариантов считаются равновероятными. (Будем считать, что обеспечивается условие, при котором ! — 1 наибольших элементов принадлежат Т.) Пусть 5 = (1,..., и) ! Т— другие элементы и установлена 5э е- 5, Та е- Т, 5а и Тэ будут представлять элементы, которые люгут стать Г-ми по старшинству. А2. До'тех пор, пока [Та[ > г, все сравнения к:у выполняются следующим образом.
Если х 6 5 и у б Т, считается, что к < у. Егзи х б 5 и у б 5, подбрасывается монета и удаляется меньший элемент из 5э, если он принадлежит 5э. Если к б Т и у б Т, подбрасывается монета н удаляется больший элемент нз То, егчи он принадлежит То.
АЗ. Как талька получим [Тэ[ = г, элементы разделятся на три класса, Р, Я,В, следующим образом. Если [5э[ < а, считается, чта Р = 5, Я = Тэ, й = Т '! Тэ. В противном случае для каждого у б Те считается, что С(у) - это элемент из 5, который уже прошел сравнение с у и выбирается уэ, такой, что [С(уа)[ минимально. Пусть Р = (5 ! 5э) 0 С(уа), Я = (5о '! С(уо)) 0 (Уе), В = Т ! (Уо) Все последующие сравнения к: у выполняются так, что элементы нз Р считаются меньше элементов из Я, а элементы из !д меньше элементов из Я; если же х и у принадлежат одному и тому же классу, падбрасывэется монета.
Докажите что, если 1 < г < г и [С(уе)[ < о — г в начале шага А3, каждый лист достигается с вероятностью < (и + 1 — Г)/(2" "(",)). Указание. Покажите, что будет сделано не менее и — а подбрасываний монеты. с) Продолжая (Ь), покажите, что И(п) > тт(п — 1+ (г — 1)(д+ 1 — г), и — д+ 1Ь((")/(п+ 1 1))) для всех целочисленных значений д и г 4) Выведите (14), выбрав соответственно д н г.
э5.3.4. Сети сортировки В настоящем разделе мы будем изучать класс методов сортировки, удовлетворяющих некоторому ограничению. Интерес к таким методам объясняется н основном приложениями и солидной теоретической основой. Это новое ограничение требует, чтобы похшедовательность сравнений не зависела от предыстории в том смысле, что если мы сравниваем К; и К,, то поглелующне сравнения для глучая К, ( К. в точности те же, что и для случая К, > К, однако 1 и у меняются ролями. На рис. 43, (а) изображено дерево сравнений, в котором это условие однородности выполнено.
Заметим, что на каждом уровне производится одинаковое число сравнений, поэтому после гп сравнений имеется 2' результатов. Так как и) не является степенью 2, некоторые сравнения будут излишними в том смысле, что одно из их поддеревьев никогда пе встречаетгл на практике. Иными гловами, на некоторых ветвях дерева приходится выполнять больше сравнений, чем необходимо, чтобы сортировка была правильной на всех соответствующих ветвях. Поскольку каждый путь на таком дереве сверху донизу определяет все дерево, эту схему сортировки проще изображать в виде сети, как на рис.
43, (Ь). Прямоугольник в подобной сети представляет "модуль компаратора", имеющий два входа (изображены линиями. входящими н модуль сверху) и два выхода (изображены линиями, выходящими вниз): левый выход — меньший из двух входов, а правый выход -- больший из пих. Элемент К,' в нижней части сети есть наименьший из (КПКз, Кз, Кз), Кз — второй в порядке возрастания и т. д.
Нетрудно доказать, что любая сеть сортировки соответствует дереву сравнений, обладающему свойством независимости от предыстории (в указанном вылив смысле), и что любое такое дерево соответствует сети модулей компараторов. Между прочим, технически модуль компаратора ловольно легко изготовить. Предположим, например, что по линиям связи в модуль поступают двоичные числа по одному разряду в единипу времени, начиная со старшего.
Каждый мочуль компаратора имеет три состояния и функционирует следующим образом. Момент г Момент (1+ 1) Состояние Входы Состояние Выходы 0 00 0 00 0 01 1 01 0 10 2 01 0 11 0 11 1 У. у 1 Х у 2 Х у 2 у к Первоначально все модули находятся в состоянии 0 и выдают О О. Модуль переходит в состояние 1 илн 2, как только его входы становятся различными..Чигла, которые в момент времени 1 начали поступать сверху в сеть, соответствующую рис. 43, (Ь), Д й > й Ы 5 й о В о о С~ Я 3 а о Й с й 4 ж > Ф о Р о Ф 1 — 1 — 1 — К' 1 К1 — 4 1 — 1 3 —  — 2 — К,' 2 -4 — 3 — К,' Кз — 1 — ~ — 4 — 4 4 Кз — 3 — 3-~ — 2 2 Рис. 44. Еще один способ представ- ления сортировки последовательности (4,1,3,2)посредством сети,изображен- ной иа рис.
43. 4 — 4 — К' 4 3 — 3 Кз — 2 — 2 начнут в момент 1+3 выводиться снизу в рассортированном порядке, если включить соответствующий элемент задержки на линиях К,' и К'. Нри разработке теории сетей сортировки удобно изображать их несколько иным способом. На рис. 44 числа поступают слева, а модули компараторов представлены в виде вертикальных соединений между двумя прямыми; каждый компаратор вызывает, если необходимо, перестановку своих входов таким образом, что после прохождения компарагора большее число оказываетгя на низ!спей.линии.
В правой части диаграммы все числа упорядочены сверху вниз. Ранее, изучая методы оптимальной сортировки! мы уделяли основное внимание минимизации числа сравнений, почти (или совсем) не учитывая перемещение данных либо сложность структуры принятия решений, которые связаны с таким методом сортировки. В этом отношении сети сортировки имеют некоторое преимущество, так как данные могут храниться в и ячейках, а структура принятия решений "прямолинейна"; нет необходимости запоминать результаты предыдущих сравнений — план неизменен и фиксирован заранее. Еще одним важным преимуществом сетей сортировки является то, что часть операций можно совмещать, т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
