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