Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 63
Текст из файла (страница 63)
Вместо модуля сравнения-обмена будем писать (в';у). Сеть с и входами и г модулими компараторов обозначим через (Й:71] (Ьз:1з) . (1,:1,), где каждое из 1 и у меньше или равно и; для краткости будем называть ее и-сешьм. Сеть называется спшндартной, если 1 < у„для 1 < 9 < г, Так, например, на рис. 44 приведена стандартная 4-сеть, обозначенная последовательностью компараторов (1:2)(З:4)(1: ЗП2:4)(2: 3). Наши соглашения в тексте о графическом представлении диаграмм сетей позволяют рисовать только стандартные сети; все комоараторы (1:у) изображшотся прямой линией от 1 к у, где 1 < 71 '1тобы нарисовать нестандартную сеть, можно использовать стрелку от 1 к 1, указывающую, что большее число направляется к острию стрелки.
Наприыер, на рис. 56 изображена нестандартная сеть для 16 элементов с компараторами (1.2Ц4Щ5:6Ц8:7) и т. д. В упр, 11 доказывается, что это сеть сортировки. (х[1.'2])е = хе, когда 1 ЭЛ Л Ф 11 Будем говорить, что а является сешьы сортировки, если (хо); < (хо)с ы для всех х и для 1 < 1 < п. Символ ее> обозначает вектор, в позиции 1 которого находится 1, а в остальных позициях — 0; таким образом, (е01)э = ЛО. Символ 11» обозначает множество всех 2" и-мерных векторов из О и 1, а Р— множество всех и! векторов, являющихся перестановками (1,2,..., и). Мы будем использовать обозначения х Л у и х Ч у для векторов (х~ Л ум.,., х» Л у„) и (к~ Ч уц, .., х Ч у„) и будем писать х < у, если х, < у; при всех 6 Таким образом, х < у тогда и только тогда, когда х Ч у = у, либо тогда и только тогда, когда х Л у = х.
Еглн х н у лежат в 11, то будем говорить, что х пахрмеаега у, если х = (у Ч е01) и'. у при некотором 1. Наконец, для всех х в 11» пусть н(х) будет числом единиц в х, а ь(х) — числом нулей; таким образом, н(х)+ ь(х) н п. 1. [20] Нарисуйте диаграмму сети четно-нечетного слияния для гл = 3 н и = 5. 2.
[22] Покажите, что алгоритму сортировки В. Пратга (см. упр. 5.2.1 — 30) соответствует сеть сортировки а элементов, имеющая приблизительно (1об«п)(1об«п) уровней задержки. Нарисуйте такую сеть для и = 12. 3. [М20] (К. Э. Бэтчер (К. Е. Ва«сЬег).) Найдите простое соотношение между С(гп, гл — 1) н С(щ,гл).
° 4. [М23] Докажите, что Т(б) = 5. 5. [М1 Р] Докажите, что вырюкение (13) действительно определяет время задержки для сети сортировки, описанной соотношениями (10). 6. [28] Пусть Т(п) — минимальное число стадий, требуемых для сортировки н различных чисел посредством одновременно«а анпелненал непересехаыагихся сравнений (без соблюдения сетевого ограничения); каждое такое множество сравнений может быть представлено узлом, содержащим множество пар (Н: уц 1«:у«,... „1,:у, ), где все 1,, Лц 1«, 2«,, 1„1, различны; от этого узла отходит вниз 2" ветвей, соответствующих случаям (Кн <Кл ~~2 <Кэ» ''' % <йэ ) (Кц > Кл, К,«< Кхн ..., К,„< К,„) и т. д. Докажите, что Т(5) = Т(6) = 5, У.
[25] Покажите, что если три последних компаратора сети для и = 10 на рис. 49 заменить "слабой" последовательностью [5:6Ц4: 5][б; 7], то сеть по-прежнему будет выполнять сортировку. 6. [М20] Докажите, что Л1(»па+ел«,н~+п«) > М(гпцп~) + М(гв«„п«)+ ш1в(гпнп«) при тпцшыпцп«> О. 9. [М25] (Р У Флойд (К. Ж. Р!оуб) ) Докажите, что Л«(3, 3) = 6, М(4 4) = 9, ЛХ(5, 5) ы 13. 10. [М22] Докажите, что бнтонный сортировщнк Бэтчера, определенный в разделе, который предшествует (15), действительно работает.
[Указание. Достаточно доказать, что будут сортироваться все последовательности, состоящие из й единиц, зв которымн следуют 1 нулей, за которыми следуют и - х — 1 единиц.) 11. [М28] Докаяснте, что бнтонный сортировщнк Бзтчера порядка 2' будет сортировать не только последовательности («а, «ц..., ««~,), для которых «а > . > «е < . < ««~ но н все последовательности, для которых «е « «е » ««н [Как следствие этого сеть на рнс. 56 будет сортировать 16 элементов, твк как каждая стадия состоит из битонных сортировщиков нли обращенных бятонных сортировщиков, применяемых к последовательностям, которые были рассортированы в противоположных направлениях,) 12. [МЗ0) Докажите или опровергните следующее утверждение: если х и д — битонные последовательности равной длины, то последовательности з Ч у и к Л д также битонные.
ь 13, [З4] (Х. С. Стоун (Н. Б. Ясоне).) Покажите, что сеть сортировки для 2' элементов можно построить по схеме, представленной на рис. 37, для случая 1 = 4. Каждый из 1э шагов этой схемы состоит иэ "идеального тасования" первых 2' ' элементов с последними 2' ', за которым следуют операции, выполняемые одновременно над 2' ' парами соседних элементов. Каждая из этих операций обозначена либо через "О" (иет операции), либо через "+" (стандартный модуль компаратора), либо через "-" (обращенный модуль компаратора).
Сортировка протеюет в г стадий по 1 шагов каждая; на последней стадии все операции суть "+". В течение ссадин е при е < 1 мы выполняем 1 — в шагов, где все операции суть "О"( а затем выполняем е шагов, где на каждом. 7-м шаге поочередно выполняются 2е операций "+" и затем 2г ' операций "—" при 4 = 1,2,...,э. [Попутно отметим, что эта схема сортировки может быть реализована весьма простым устройством, реаэизующнм один шаг "тасовання и операций" и возвращающим выход на вход. Первые три шага на рис. 57 молсно, конечно, исключить.
Онн оставлены лишь для того, чтобы сделать схему понятнее. Стоун замечает, что тот эсе принцип "тесовання/операции" встречается в других алгоритмах, таких как быстрое преобразование Фурье (см. формулу 4,6.4-(46)).] ь 14. [МЗ7] (В. Е. Алексеев.) Пусть а = [гсу)) . [С:у,) представляет собой и-сеть; при 1 < е < г определим а' = Я:У[]... [г',,: у,',Цз,;1„]...
[С;,у,], где зь н уе получены из м и Уь путем замены г, элементом У, и замены,~„элементом 1, во всех случаях, когда они встречаются. Например, если а = [1:2ЦЗ:4Ц1:3][2:4Ц2:3), то а' = [1:4][З:2Ц1:ЗЦ2:4)[2:3). а) Докажите, что Р и = Р„(о'). Ь) Докажите, что (о') = (а')'. с) Сонрллсенной с и является любая сеть вида (... ((агч)")...)'ь, Докажите„что а имеет ие более 2" ' сопряженных сетей. г() пусть д„(к) = [я б Р а] и пусть У (к) = (зч ч лз, ) л . л (з,„ч хгь). Докажите, что д (х) = Ч'(7 (к) [о является сопряженной с а). е) Пусть С есть ориентированный граф с вершинамн [1,...,н) н дугамн 1, -+ у„при 1 < е < г. Докажите, что а является сетью сортировки тогда и только тогда, когда 0,„~ имеет направленный путь от 1 к 1+1 при 1 < 1 < я и для всех о', сопряженных с а.
[Это условие весьма примечательно, поскольку С не зависит от порядка компараторов в а.) 13. [Зд] Найдите нестандартную сеть сортировки четырех элементов, содержащую только пять модулей компараторов. 16. [МЗЗ] Докажите, что следующий алгоритм преобразует любую сеть сортировки [М:уг] ... [С:уг) в стандартную сеть сортировки той же длины. Т1. Пусть д — наименылий индекс, такой, что ге > у',. Если таких индексов нет, то остановиться.
Т2. Заменить все вхожДениЯ ге элементамн уе н нсе вгожценик 1» элементами ьг во всех компараторах [С:Я для д < е < г. Вернуться к шагу Т1. $ Так, «4; 1ЦЗ:2)[1:ЗЦ2:4Ц1:2ЦЗ;4] преобразуется сначала в [1:4ЦЗ:2Ц4:ЗЦ2;1Ц4:2)[3:1], затем в [1:4Ц2 ЗЦ4:2ЦЗ:1Ц4 ЗЦ2;1], затем в [1:4Ц2:ЗЦ2 4ЦЗ:1Ц2 ЗЦ4:1] и т д., пока не получится стацлартная сеть [1: 4Ц2: 3) [2: 4Ц1: ЗЦ1: 2ЦЗ: 4]. 17. [МЗЗ] Пусть Ры — мнгакество всех [",) последовательностей (кг,...,я„) из нулей и единиц, имеющих ровно г единиц.
Докажите, что (7г(и) равно минкмальному числу компв.- раторов, которые необходимы в сети, сортирующей все элементы Ры, что гг(п) равно мн- нимальиомУ числУ компаРатоРов, необходимых длЯ соРтнРовки Р,„О Ри,ш, н что Йгг(и) равно минимальному числу компараторов, необходимых для сортировки [)осью, Р» 1» =поп((рп)» [рб Р„), «» =-щах((рп)»]рб Р ) пря 1 < й < и для нижней и верхней границ диапазона значений, которые могут появляться на линии выхода )с. Пусть 1» и «» — аналогично определенные величины для сети и' = о[1:2].
Докажите, что 1; = 1; Л 1, 1. < 1, + 1, «; > «; + « — (и + 1), «] = «; Ч « . [Указа««е. Для далнь»х векторов х и у из В„, таких, что (хо)~ = (уп)„ж О. ь(х) = 1, и ('(у) 1з, найдите вектор х нз В, такой, что (хп ). = О, ь(х) < 1, + 11.] 28. [М30] Пусть 1» и «» определены, как в упр. 24. Докажите, что множество ((рп)» ] р щ Р ) содержит все целые числа между 1» и «» включительно. 28. [М24] (Р, У. Флойд,) Пусть а есть п-сеть.
Докажите, что мнохсество В„о = (хп ] х 1п В ) люжет быть определено из множества Рсп = (рп ] р (в Р„) и, обратно, Р„а может быть определено из В„а. ь 2Т. [М20] Пусть х и у — векторы и пусть ха и уп — рассортированные векторы, Докажите, что.(хп), < (уп). тогда и только тогда, когда для любой совокупности 1 элементов из у можно найти совокупность ( элементов из х, такую, что любой элемент, взятый из х, меньше некоторого элемента, взятого из у, или равен ему. Используйте этот принцип для доказательства того,что если рассортировать строки любой матрицы, а затем рассортировать столбцы, го строки останутся упорядоченными.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
