AOP_Tom3 (1021738), страница 16
Текст из файла (страница 16)
Докажите также, что две такие канонические формы равны для всех хм,х тогда и только тогда, когда опи идентичны (с точностью до порядка). 31. [М24] (Р. Дедекинд (К. Пег1еЫпб), 1897.) Пусть б„— число различных канонических форм от хы, х в смысле упр. 30. Так, бз = 1, бг = 4 и бз = 18. Чему равно бзу 32. [М28[ (31 У. Грин (31. %'. Сгееп).) Пусть Сз = (00,.01,11); определим Сою как множество всех цепочек уффы, таких, что О, ф, зт, ы имеют длину 2' ' и дф, фод Угу и ф г принадлежат Со Пусть о — сеть, состоящая из четырех первых уровней 18-элементного сортировщика, изображенного на рис 49.
Покажите, что 11зео = См и докажите, что это множество имеет в точности бз + 2 элементов (см. упр. 31). ь ЗЗ. [М22[ Не все б„функций от (хм.,., х„) из упр. 31 могут встретиться в сетях компараторов. Докажите, что функция (хз Л хг) Ч(хг Лхз) Ч(хз Лхз) це может быть результатам работы никакой сети компараторов от (хм..., х ). 34.
[23[ Является ли следующая сеть сетью сортировки? Зб. [20] Докажите, что в любой стаядартной сети сортировки должен, по крайней мере, один раз встретиться каждый из сосмдних компараторов [1: з+1[ при 1 < з < и. ь 30. [22[ Сеть, представленная на рис. 47. содержит только кратчайшие сравнения [зЬз-ь1[. Ьудем называть такие сети при.мипзпвпмми. а) Докажите, что примитивная сеть сортировки для и элементов должна иметь не менее (') компараторов. [Указаное.
Рассмотрите инверсии перестановкн.) Ь) (Р У Флойд, 1964.) Пусть о -- примитивная сеть для п элементов, а х — вектор, такай, что (ха); > (ха)г при некоторых з < у. Докажите, что (уа), > (уп)м где у —— вектор (и, и — 1,, 1) . с) В качестве следствия (Ь) докажите, что примитивная сеть является сетью сортировки тогда и только тогда, когда она сортирует единственный вектор (и, и — 1,..., 1).
37. [М22] грешно-исчеглнал сорглпроека с транспозициями для п чисел, и > 3, — это п-уровневая сеть с -'п(п — Ц компараторами, напоминающая кирпичную кладку (рис. 58). (Если п четно, имеется два варианта.) Такую сортировку особенно легко реализовать аппаратно, поскольку выполняются попеременно только два вида действий. Докажите, что такая сеть действительно будет работающей сетью сортировки.
[Указание. См. упр. Зб.] Рнс. 58. Четио-нечетная сортировка с транспозициями ь 38. [40] Пусть Х = ("]. Найдите взаимно однозначное соответствие между диаграммами Юнга вида (и-1, п-2,..., 1) и примитивными сетями сортировки [Ц ~ь+Ц... [!к:зл+Ц [Следовательно, по теореме 5.1.4Н существует точно 1 -~З -зб -з (2п З)~ таких сетей сортировки.] Указание. В упр. Зб, (с) показано, что примитивные сети без избыточных компараторов соответствуют пути от 12... и до и... 21 на многограннике, подобном изображенному на рис. 1 в разделе 5.1.1. 39. [25] Пусть известно, что примитивная сеть компараторов состоит из и линий и правильно сортирует единственный вход 191 0... 1 О, (См. упр, Зб; полагается, что и четное.) Покажите, что в такой сети "средняя треть", состоящая из всех компараторов, подключенных только к линиям от [п/3] до [2п/3] включительно, будет сортировать любые входы, 40.
[НМ44] Пусть компараторы [Ц.П+Ц[!з:!з+Ц... [1, П,+Ц выбираются случайно, причем каждое значение !ь Е [1, 2,..., п — Ц равновероятно. Процесс прекрашаетсв, когда в составе сети в качестве подсети появляется конфигурация сортировки по методу пузырька, подобная изображенной на рис. 47. Докажите, что г < 4п~ + 0(пз1' !о8 и), а вероятность остальных случаев — О(п 'еее). 41. [М47] Пусть компараторы [! ~ .
1~][1з: уз]... [з, . 1„] выбираются случайным образом, причем каждый иеозбмшочнмй выбор 1 < зь < уь < и имеет равную вероятность. Процесс остановится, когда получится сеть сортировки. Оцените ожидаемое значение г; будет ли оно 0(пг ы) при всех е > О? ь 42. [25] (Д. Ван Ворис (П. Ъал аоот)пз).) Докажите, что Й(п) > Й(п — 1) + [18п]. 43.
]48] Найдите (гл, п)-сеть слияния с числом компараторов, меньшим С(тв, и), или докажите, что такой сети не существует. 44. [50] Найдите точное значение Б(п) для какого-либо п > 8. 45. [М20] Докажите, что любая (1, и)-сеть сортировки без разветвлений должна иметь по крайней мере [!8(п -!- 1)] уровней задержки.
и 48. [80] (М. Айгнер (йй А!Впег).) Покажите, что при использовании любого алгоритма, который способен параллельно выполнить несвязанные сравнения минимальное число стадий, необходимых для слияния ш элементов, будет не меньше [!8(т + и)]; следовательно, битонная сеть сортировки имеет оптимальную задержку. 47. [47] Является ли функция Т(п) в упр.
б строго меньшей, чем Т(п) при некотором пу ь 48. [86[ Можно дать другую интерпретацию сетей сортироикп, считая, что на каждой линни находится не одно число, а мультимножество из ш чисел; при такой интерпретации операция [1:у[ заменяет х, н х, соответственно значениями х; 1~ х, и х, ч х, — наименьшими гл и наибольшими ш из 2пг чисел х, З1 х„. (Например, на приведенной ниже схеме иллюстрируется такая интерпретации при т = 2; каждый компаратор сливает свои вколэя и отделяет нижнюю половину от верхней.) — (3, 5) (1, 3) — (1, 3) (1,2) — (1,2) — (1,2)— — (1, а) ~ (5, З) — (5,8) (5, З) — (2,9) — (2,9) (2,2) (2, З) (5,7) -в- (2,З)— (2,3) (5,7)— Если а и Ь суть мультимножества, содержащие по гп чисел, то будем говорить, что а « Ь тогда и только тогда, когда а й Ь = а (или, что эквииалентно, а в' 6 = Ь; наибольший элемент а меньше или равен наименьшему элементу Ь).
Таким образом, а 1~ Ь << а З( Ь. Пусть а есть п-сеть, а х =- (хп.,. х ) — вектор, в котором каждая компонента х,-- мультимпожество из т элементов. Докажите, что егли (ха), не « (ха)з в описанной интерпретации, то в Р„найдется вектор у, такой, что (уп), = 1 и (уа) = О. [Следовательно, сеть сортировки п элементов превращается в сеть сортировки шп элементов, если заменить сравнения пьпутевыми слияниями. На рис, 59 изображен 8-элементный сортнровщик, построенный из 4-элементного с использованием этого вывода.[ )зис. 59.
8-элементный гортировщик, построенный из 4-элементного сортировщика с ис- пользованием слияния. 49. [Мйу[ Покажите, что в обозначениях упр. 48 (х)гзр)пах = х[~(уйх) и (хМР)мт = хМ(ргтгх); однако (х й'р) )(х не всегда равно (х Я х) (((р й х) и (х д р) у (х)З х) у (р((х) не всегда Равно средним т элементам х Э1 р Ь х. Найдите правильную формулу для этик средних элементов, использовав в вей х, у, х, а также операпии й и (Г. 50.
[НМ45[ Исследуйте свойства операций Я и т', определенных в упр. 48. Можно ли охарактеризовать все тождества в этой алгебре каким-либо изящным способом или вывести все их из конечного набора тождеств? В этом отношении такие тождества, как хдх))х = х)(х и х)з(хч(хг((хту))) = хд(хвр), которые имеют место только для гп < 2, представляют относительно небольшой интерес, рассматривайте лишь тождества, справедливые при всех ш.
ь 51. [М85[ (Р. Л. Грэхем (Н. Ь. СгаЬаш).) Компаратор [Иу[ называется избыточным в сети гз~ [1:у[пю если либо (ха~); < (хо~), для всех векторов х, либо (хо~); > (хоп)1 для всех векторов х. Докажите, что если а является сетью с г неизбыточными компараторами, то найдется по крайней мере г различных упорядоченных пар (1,2) различных индексов, таких, что (хп), < (хп) для всех векторов х. (Следовательно, сеть без избыточных компараторов содержит не более (") модулей.) Рис. 00. Семейство сетей, возможность которых выполнять сортировку очень сложно проверить.
Показан варяант при тп = 3 и и = 5 (см. упр. 52). з 52. (Уй] (М. О. Рабин (М. О. КаЬ!и), 1080.) Докажите, что в общем случае исключи- тельно трудно дать заключение, является ли данная последовательность компараторов сетью сортировки, анализируя сеть, аналогичную представленной на рис. 60. Принято перенумеровывать входы хо до хтт, где 14!' = 2тпп + т + 2п; положительные целые числа являются параметрами.
Первые компараторы — ]у ! т'+ 2пй] при 1 < 2 < 2п и 1 < й < тл. Тогда имеем ]21' — 1: 22]]0!27] при 1 < у < и параллельно со специальной подсетью, которая использует только индексы > 2п Далее сравниваем ]О;2ттт+2п+2] при 1 < у < тл. И наконец, существует законченная сеть сортировки для (хт,, хл), за которой следует (О 1]]1!2] .. ]]47 — 1-11Х-1], где Ф = тип+ и Ч- 1, а) Опишите есе входы (хо, хт,, хээ ), которые ие сортируются такой сетью, в терминах поведения специальной подсети. Ь) Задан множество выражений наподобие (ут ц рг Н уэ) Л (уг эуйз Ч у4) Л... ! объясните, как построить специальную подсеть по типу сети, показанной на рис. 50, которая сортировала бы все входы тогда и только тогда, когда выражение не удовлетворяется.
53. (50] (Периодическая сетпь сортпироеки.) Две показанные ниже сети следует считать иллюстрацией рекурсивного построения буровневой сети при и = 2' в случае С =- 4. Е!ли пронумеровать линии входов от О до 2' — 1, .то Ьй уровень в случае (а) имеет компараторы ]1!у], гдез!под 2'~' ' < 2' ' ну =1!л(2"' ' — 1), всего существует 12' ' компараторов, как и в сети битонного слияния В случае (Ь) компараторы первого уровня суть ]27; 22 + 1] при 0 < 2 < 2' ' и Ьуровневые компараторы прн 2 < 1 < 1 суть ]22+ 1: 27 + 21 ы '] при 0 < у < 2' ' — 2' '; всего имеется (1-1)2' '+1 компараторов, как в сети четно-нечетного слияния.
Докажите, что если входные числа 21-упорядочены, как в теореме 5.2.1Н при некотором й > 1, то обе сети приведут к выходу, который будет 2» '-упорядочен. Таким образом, мы сможем сортировать 2' чисел, пропуская их через любую из сетей с раз. ]Когда с велико, такие сети сортировки выполняют примерно вдвое больше сравнений, чем ъггоритм 5.2 2М; но общая временная звдержка та же, что и на рис. 57, а реализация выполняется проще, поскольку та же самая сеть используется многократно.] 10 11 12 ээ 14 !6 !б 17 16 19 29 2! 22 23 24 ы гв гт гв 29 ЗО 61 32 зз Зв 66 66 67 Зв эв 4О 4! 42 вэ 19 !1 ж !з 14 16 16 !т !в !9 2О 21 22 23 24 26 гв 27 29 гв 69 з! 32 зз 64 Эв зб зт 36 69 49 41 42 43 (а) 54. (42[ Проанализируйте свойства сетей сортировки, построенных не из 2-элементных сортировщиков, а из гп-сортирующих модулей. (Например, Дж.
1Папиро (С. ЯЬар1го) построил сеть для сортировки 1б элементов, использовав четырнадцать 4-элементных сортировщиков. Наилучшее ли это решение? Докажите, что гпг элементов можно рассортировать с помощью не более 1б уровней пг-элементных сортировщиков, если т достаточно велико.) 55. (23) Перестаноеочной сетью называется последовательность модулей [ад:Л[... [г,: у,[, где каждый модуль (г:у( может устанавливаться извне в одно из двух состояний: либо он передает свои входы без изменений, либо меняет местами х, и х, (независимо от значений х, и х ). Последовательность модулей должна быть такой, чтобы на выходе можно было получить дюбую перестановку входов при соответствующей установке модулей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
