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