AOP_Tom3 (1021738), страница 187
Текст из файла (страница 187)
Отсюда следует, что Е В«< Е С» и Е В «< Е С «. Доказательство завершается выводом, что хс-«+ хсе«> 2 + А» + А — « — В« — В-« -г С«+ С «. [Дальнейшие результаты приводятся в,1АСА! 30 (1989), 270. 279.] Верхняя оценка в (17) имеет также соответствующую нижнюю оценку: Эндрю и Фрэнсис Яо доказали, что И,(п) > и -» —,'С (1п 1ап — !вг — 9) при С > 1 и и > (8С)~м [см В/СОМ/» 11 (1982), 428-447]. 20. (а) Обозначим вершины компонентов двух типов через а, Ь < с.
Соперник поступает следующим образом при ссессзбыто*сньсх сравнениях. Случай 1, а: а': принять произвольное решение. Случай 2, х с Ь. сказать, что х > 6; все последующие сравнения у: Ь с этим конкретным Ь будут иметь результат у > 6, в противном случае сравнения выбираются соперником для (/с(п — 1), что приводит в общей сложности к > 2 + »1«(и — 1) сравнениям. Это снижение будем для краткости выражать так; 'пусть Ь = ппп: 2+К(п — 1)2 Случай 3, : пу.
с=; 2+с/ (п — Ц. (Ь) Обозначим новые типы вершин с(ы йс < е; / < д < й > с Случай 1, а; а' или с: с': произвольное решение. Случай 2, а: с: сказать, что а < с. Случай 3, х: 6с пусть 6 = шш 2+ К(и — 1). Случай 4, х: СС: пусть сС = ппп, 2+(/с(и — 1). Случай 5, х: е: пусть е = п»ах; РАЗДЕЛ 5.3.4 1. (Если ти = 2Ь вЂ” 1 почетно, то лучше, чтобы в диаграмме за оз вместо шьет, обет, юз+г, ... следовали элементы ез4.4, шз.т 4, ьзз-г, ....
Такая замена корректна, поскольку линии, которые мы переставляем, сравниваются одна с другим.) 8-элементвая сортировка Пратта (3,5]-элементвое четео-нечеткое слияние Хз Ет — 47 хг хт -7 — зг хз ег — 4 — зз У! бз — 7 — 44 уг ктг -4 — гб Уз бз — 7 — гб У4 тбз 7 уз бб — 44 2. Для приращении Ь нужно 2 — (2Ь, > и] уровней; см, приведенную выше диаграмму для и = 8. 3. С(пг, пз-1) = С(т, ти) — 1 при ти > 1. 4. Если предположитзь что Т(б) = 4, то в каждый момент должны действовать три компаратора, так как 5(б) = 12. Но тогда, удалив нижнюю линию и связанные с ней четыре компаратора, мы по.лучили бы 5(б) < 8.
а это — противоречие (Те же рассуждения показывают, что Т(7) = Т(8) = 6. Яан Парберри (1ап РагЬеггу) провел длительный компьютерный поиск и пришел к результату Т(9) = Т(10) = 7; см Мабб. 5узгепж ТЬеогу 24 (1991), 101 †1.) 3+ Ц 7(п — 1). Случай б, х т /: пусть / = пни, 2 + К(и — 1). Случай 7, х: д: пусть / и д = ппп; 3+ (/т(74 — 2). Случай 8, х: Ь: пусть Ь = птах; 3 + К 4(и — 1). Случай 9, х: Ь пусть т = или; 2 + К (и — 1). (с) Поскольку при З = 1 имеем (/4(и) = и — 1, в этом случае неравенство выполняется. При 1 < 1 < и/2 — 1 используем индукцию и (а). При З = и/2, Ст(и — Ц = (7, 7(и — 1) используем индукпию и (а).
27. (а) Высота Ь удовлетворяет соотношению 24 > 2 т 1 > 2 т Рг(1)/р = 1/р (Ь) Если г < З, мы достигнем АЗ после не менее чем и — )5б( — )Тб) = и — (5б( — т' подбрасываний монеты. Ый по старшинству элемент будет либо самым малым, либо самым большим в (,), а элелтенты из С. еще не будут сравниваться один с другим, так что нам понадобится не менее ~ф — 1 дополнительных подбрасываний монеты. Если ~5б( < д, получим (4У) = г, а если нет, то получим )ф > (5б( — )С(уб)! Ч-1 > )5б( — (д — т ) + 1; так что в обоих случаях будет сделано не менее и — д подбрасываний. Существует и-~-1 — З множеств Т, в которых содержатся З вЂ” 1 старших элементов, определяемых данным листом дерева, и для каждого такого Т вероятность достичь его равна либо О, либо 2 т/( т'), где / > и — д есть чигло подбрасываний лтонеты, соответствующее Т.
(Этот соперник был "реализован" в статье Бента (Вепс) и Джона (ЮоЬп), 5ТОС 17 (1988), 213. 216 ) (с) если 1 < г, замените з значением и+1 — й получим, что з > г, когда г максимизирует правую сторону, поскольку г будет 0(з/и ) Если возможно достичь АЗ с ~С(у) ~ > д — г при всех у б Тб, алгоритм выполнит и — 1 сравнений 1-го по старшинству элемента со всеми другими в дополнение не менее чем к (г — 1)(д — т.
+ 1) сравнениям, которые выполняются между 5 и Т1 (уб). (6) Выберем г = ) тщ) и ц = 2г — 2. (Несколько лучше положить д = г+ („lт+ -') — 2; такой выбор позволит максимизировать нижнюю опенку, выведенную в (с).) 5. Пусть /(и) = /([и/2]) + 1 + [!8[п/2Ц, если и > 2. Тогда, применив индукцию по и, получим /(и) = (1+ [!8п])[!8 и]/2. 6. Можно считать, что на каждой стадии выполняется [и/2] сравнений (лишние сравнения не помешают) Так как Т(6) = 5, достаточно доказать, что Т(5) = 5. В случае п = 5 после двух стадий мы не можем избежать частичных упорядочений >ь или ч~'„ которые нельзя рассортировать за оставшиеся две стадии.
7. Допустим, что исходными ключами будут [1, 2,..., 10). Ключевым моментом решения является то, что после первых 16 компараторов линии 2, 3, 4 и 6 не могут содержать ни 8, ни 9, ни 6 и 7 вместе. 8. Это очевидное обобщение теоремы Е. 9. М(3,3) > 5(6) — 25(3), М(4,4) > о(8) — 2.9(4), М(5, 5) > 2М(2,3) + 3, как следует из результатов упр. 8 и М(2, 3) > Я(5) — 5(2) — Я(3). Аналогично М(3, 4) = 8. Но чему равны ЛХ(3,5) и ЛХ(4,5)? 10. Используйте указание и метод доказательства теоремы Е. Затем покажите, что число нулей в четной подпогледовательности минус число нулей в нечетной подпоследовательности равно *! или О.
11. (Решение М. У. Грина.) Рассматриваемая сеть симметрична в том смысле, что всякий рвз, когда ьч сравнивается с а,, найдется соответствующее сравнение ам,;, ам, ь Любая симметричная сеть, способная сортировать последовательность (ае,..., аш Д, будет также сортировать последовательность ( — аэ~,,..., -ао) Бзтчер заметил, что эта сеть в действительности будет сортировать любой циклический сдвиг (х„ аз~-и ...,ээ~ м ао, ,а, ~) битонной последовательности. Это следует нз принципа нулей и единиц. [Данный результат не приложим к битонным сортировщикам, если их порядок отличен от степени 2. Например, сортировщик на рис. 52 не сможет сортировать последовательность (О, О, О, О, О, 1, 0).
Сформулированное Бэтчером определение битонной последовательности сложнее и менее удобно, чем то, которым мы пользуемся.] 12. Последовательность к Ч д является битонной (рассмотрите погледонательности из 0 и 1), а последовательность к Л д — нет (рассмотрите, например, (3, 1, 4, 5) Л (6, 7, 8, 2)). 13.
Идеальное тасанание заменяет ж элементом аз, где двоичное представление 1 получается из представления 1 в результате циклического сдвига вправо на адин разрнд (см. также упр. 3.4.2-13). Рассмотрим перетасовку компараторов, а не линий. Тогда первый столбец компараторов имеет дело с парами а[1] и а[1 О! 2" '], следующий столбец — с парами э[1] и э[1!9 2" ~], ..., ый столбец — с э[1] и э[! ОЭ 1], (1+ 1)-й столбец — снова с э[1] и а[1 Э 2" '] и т. д.
Здесь Э обозначает операцию "исключающее или" над двоичными представлениями. Этн соображения показывают, что рис. 57 эквивалентен рис. 56; после э стадий мы получаем рассортированные группы из 2' элементов с чередующимися направлениями упорядочения. В работе С. С. Р!алгол, Т. Бне1, Маей. Яуэгешэ Тйеогу 27 (1994), 491-508, показано, что любая сеть такой структуры имеет, по меньшей мере, П((!ойп) /!ой !ойп) уровней задержки.
14. (а) Пусть д„= к„, у;, = х„, уь = вь при 1, ф й ф ?,: тогда до' = хо. (Ь) Это очевидно до тех пор, пока множества (1„1„6,/д) имеет только три отличающихся элемента; пРедположим, что 1, = сь Тогда, если а ( й пеРвые а — 1 компаРатоРов заменЯт (!ю 7„Д)) соответственно элементами (1„7п1,) как в (а')', так и в (а )', (с) (а')' = о и а' = о, так что можно предположить, что г~ > вэ > > вь > 1. (О) Пусть !7 = а[з:2], тогда дл (ни..., в„) = (й, ч лз ) л (д (ли ., ., к„..., хз, ..,, к„) ч д (ям..., хз, ., ., к,,..., к ) ). Построив итеративную процедуру из этих равенств, получим искомый результат.
(е) /„(х) = 1 тогда и только тогда, когда не существует пути на графе С„от т к у при условии х, > хз. Если о -- сеть сортировки, то сопряженная с о сеть также является сетью сортировки и 7' (к) = О при всех х, удовлетворяющих неравенству х, > х,~.ь Примем х = ер1; это показывает, что С не имеет дуг от т к йт при некотором )тт ~ т. Если йт ~ т + 1, то х = еЮ Ч еы»1 показывает, что С имеет лугу от т или 1»т к Йг при некотором кт ф (т, кт). Если )тз 1» т + 1, продолжаем рассуждать так же до тех пор, пока не найдем путь на графе С от т к т + 1.
Обратно, если и не является сетью сортировки, положим, что х вектор с хт > х,ет и д (х) = 1. Для некоторого сопряженного о' получим 7' ° (х) = 1, так что С„может и не иметь пути от т к т+ 1. [В общем случае (ко), < (ха)т при всех к тогда и только тогда, когда Се имеет ориентированный путь от т к 2 при всех а', сопряженных с а.] 1б. [1:4ЦЗ:2Ц1,3Ц2:4Ц2:3]. 19. Процесс, очевидно, заканчивается После каждого выполнения шага Т2 выходы с номерами т„и 2, меняются местами, поэтому в результате выполнения алгоритма сформируется некоторая перестановка выходных линий.
Так как получившаяся (стандартная) сеть не изменяет вход (1,2,..., и), выходные линии должны вернуться на свои прежние места. 17. Сделайте сеть стандартной, воспользовавшись результатом упр. 16 Затем, анализируя входную последовательность (1, 2,..., и), увидим, что стандартные сети выбора должны помещать 1 наибольших элементов на 1 линий с наибольшими номерами, а 1»(тт)-сеть должна помещать бй в порядке убывания элемент на линию п+ 1 — Ь Примените принцип нулей и единиц. 18. Из доказательства теоремы А следует, что 1'т(п) > (и — 1) [13(1+ 1)] + (131].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
