с алгоритмом поиска 6-раскраски этот алгоритм даёт возможность найти максимальное независимое множество (и тем самым решить задачу о нарушении симметрии) за время 0(lg*ra) с помощью детерминированного алгоритма.

30.5.4. Упражнения

30.5-1 Докажите, что в примере с выбором одного из двух процессоров с помощью бросания монетки математическое ожидание требуемого времени конечно.

30.5-2 Пусть дана 6-раскраска списка из га элементов. Найдите EREW-алгоритм, который за время 0(1) строит 3-раскраску того же списка, используя га процессоров.

30.5-3 Пусть дерево с га узлами задано следующим образом: каждый узел, кроме корня, имеет указатель на родителя. Найдите CREW-алгоритм, который строит 0(1)-раскраску этого дерева за время 0(lg* га).

30.5-4*. Придумайте эффективный алгоритм поиска 0(1)-раскраски графа степени 3 и оцените время его работы.

30.5-5*. Назовём к-разделённым подмножеством списка (fc-ruling set) множество его объектов, которое не содержит соседних объектов и не имеет дырок длины больше к (то есть его дополнение не содержит более к подряд идущих объектов). Например, любое максимальное независимое множество будет 2-разделённым. Как найти О (lg га)-разделённое подмножество в га-элементном списке за время 0(1), используя га процессоров? Тот же вопрос для О (lg lg га)-множества.

30.5-6* Придумайте алгоритм поиска 6-раскраски га-элементного списка за время 0(lg(lg*ra)), предполагая, что каждый процессор может хранить заранее вычисленную таблицу размера О (lgra). (Указание. От скольких значений зависит конечный цвет объекта в построенной нами 6-раскраске?)

30.6. Задачи

30-1 Обработка префиксов на отрезках

При обработке префиксов на отрезках (segmented prefix computation), как и при обычной обработке префиксов, фиксирована бинарная ассоциативная операция <g> на множестве S. По данной последовательности х = (ж1,Ж2,... ,хп), Х{ £ S и последовательности границ (segment sequence) b = (bi, £>2, -. - , bn), где bi £ {0,1}, b\ = 1, требуется вычислить последовательность (yi, у2, , уп), yi £ S, которая строится так: каждая единица в последовательности b означает начало нового отрезка, и на каждом отрезке неза-

Задачи

661

Рис. 30.12 30.12. Обработка префиксов на отрезках (операция - сложение). Показаны входные последовательности х и Ъ и выходная последовательность у. В этом примере имеется 5 отрезков.

висимо производится обработка префиксов (см. рис. 30.12). а. Определим на множестве пар {0,1} X S новую операцию с>:

Докажите, что эта операция ассоциативна.

Ь). Найдите EREW-алгоритм для обработки префиксов на отрезках за время О (lgra).

с). Найдите EREW-алгоритм, сортирующий список из га к-разрядных чисел за время О (A; lgra).

30-2 Поиск максимума из га чисел с помощью га процессоров

Здесь описан CRCW-алгоритм нахождения максимума из га чисел, использующий р = га процессоров.

a.Докажите, что если тп р/2, то нахождение максимума из тп чисел можно за время 0(1) свести к нахождению максимума из не более чем тп2/р чисел, используя CRCW-машину с р процессорами.

b.Пусть вначале имеется тп = [р/2\ чисел. Сколько их останется после к применений конструкции пункта (а)?

c.Постройте CRCW-алгоритм поиска максимума из га чисел со временем работы O(lglgra), использующий р = га процессоров.

30-3 Связные компоненты

В этой задаче строится алгоритм для поиска связных компонент неориентированного графа G = (V,E). Алгоритм предназначен для CRCW-машины (в которой может записаться любое из одновременно записываемых значений) с + процессорами. Для каждой вершины v мы храним указатель p[v]. Вначале p[v] = v для всех вершин v. В конце p[v] = р[и] в том и только в том случае, когда и и v лежат в одной связной компоненте. Во время работы алгоритма указатели образуют несколько деревьев ссылок (pointer trees). Дерево ссылок называется звездой (star), если р[и] = p[v] для любых двух его вершин и и v.

Предполагается, что каждое ребро в графе продублировано, то есть вместе с парой (и, v) множество Е содержит пару (v,u). Алгоритм использует две основных операции: Ноок и Jump, а также процедуру Star, которая делает siar[u] равным true, если вершина v принадлежит звезде.

если а = О если а = 1

5Star(G)

6for (для) каждого ребра (и, v) £ E[G]

7do if star[u] и p[u] ф p[v]

8then<- p[v]

Jump(G)

1for (для) каждой вершины v £ V[G]

2do p[v] <-

Алгоритм работает следующим образом: вначале выполняется Ноок, а затем чередуются Hook, Jump, Hook, Jump и так далее, пока при выполнении процедуры Jump не окажется, что ни один указатель не меняется. Заметьте, что вначале дважды выполняется процедура Ноок.

a.Напишите процедуру Star(G).

b.Докажите, что указатели р образуют в любой момент несколько деревьев, причём корни находятся в тех вершинах, которые указывают на себя. Докажите, что если р[и] = p[v], то и и v лежат в одной связной компоненте.

c.Докажите, что алгоритм работает правильно, то есть останавливается и в момент остановки р[и] = p[v] тогда и только тогда, когда и и v принадлежат одной связной компоненте.

Оценим время работы алгоритма. Рассмотрим какую-нибудь связную компоненту С, содержащую не меньше двух вершин. Пусть в некоторый момент работы алгоритма компонента С состоит из нескольких деревьев {Ti}. Определим потенциал компоненты С как

Ф(С) = height(Ti)

где height(Т) - высота дерева Т. Наша цель - показать, что каждая пара операций Hook-Jump уменьшает Ф(С) в некоторое фиксированное число раз (или ещё сильнее).

d.Докажите, что после первого вызова процедуры Ноок нет деревьев высоты 0 и что Ф(С) \V\.

e.Докажите, что последующие вызовы процедуры Ноок не увеличивают Ф(С).

f.Докажите, что после любого вызова процедуры Ноок, кроме первого, среди деревьев ссылок нет звёзд (за исключением связных компонент, все вершины которых уже объединены в одну звезду).

g.Докажите, что если деревья ссылок для данной связной компоненты С ещё не превратились в одну звезду, то после вызова процедуры Jump потенциал Ф(С) уменьшается по крайней мере в полтора раза. Каков наихудший случай (когда потенциал уменьшается меньше всего)?

h.Выведите из предыдущего, что время работы алгоритма составляет 0(lg \V\).

30-4 Транспонирование изображения