Главная Промышленная автоматика.

Более формально можно сказать так: если на множестве S определено отношение эквивалентности, то в соответствии с этим отношением множество S можно разбить на непересекаюшиеся подмножества Si, S2,..., которые называются классами эквивалентности, и объединение этих классов совпадает с S. Таким образом, а = Ъ для всех а и & из подмножества S,-, но а не эквивалентно Ь, если они принадлежат разным подмножествам. Например, отношение сравнения по модулю п - это отношение эквивалентности на множестве целых чисел. Чтобы показать это, достаточно заметить, что а - а = О (рефлексивность), если а - Ъ = dn, то b - а = (-d)n (симметричность), если а - Ь = dn тл Ь - с = еп, ю & - с = (d + е)п (транзитивность). В случае сравнения по модулю и сушествует га классов эквивалентности, каждое из которых является множеством целых чисел. Первое множество состоит из целых чисел, которые при делении на и дают остаток О, второе множество состоит из целых чисел, которые при делении нагадают остаток 1, и т.д., га-е множество состоит из целых чисел, которые дают остаток п - 1.

Задачу эквивалентности можно сформулировать следуюшим образом. Есть множество S и последовательность утверждений вида "о эквивалентно Ь". Надо по представленной последовательности таких утверждений определить, какому классу эквивалентности принадлежит предъявленный элемент. Например, есть множество S - {1, 2, 7} и последовательность утверждений

1=2 5 = 6 3 = 4 1=4

Необходимо построить классы эквивалентности: множества S. Сначала полагаем, что все элементы этого множества представляют отдельные классы, затем, применяя заданную последовательность утвервдений, объединяем "индивидуальные" классы. Вот последовательность этих объединений:

1=2 (1. 2} {3} {4} {5} {6} {7}

5=6 {1,2} {3} {4} {5.6} {7}

3-4 {1,2} {3.4} {5,6} {7}

14 {1,2.3.4} {5,6} {7}

Мокно "решать" задачу эквивалентности начиная с любого утверждения заданной последовательности утверждений. При "обработке" утверждения а = Ь сначала с помошью оператора FIND находятся классы эквивалентности для элементов а и ft, затем к этим классам применяется оператор MERGE.

Задача эквивалентности часто встречается во многих областях компьютерных наук. Например, она возникает при обработке компилятором Fortran "эквивалентных объявлений", таких как

EQUTVALENCE (А(1),В(1,2),С(3)). (A(2),D,E), (F.G)

Другой пример представлен в главе 7, где решение задачи эквивалентности помогает найти остовное дерево минимальной стоимости. П

Простая реализация АТД MFSET

Начнем с простейшего АТД, реализующего операторы MERGE и FIND. Этот АТД, назовем его MFSET (Множество с операторами MERGE и FIND), можно определить как множество, состояшее из подмножеств-колпонектов. со следую-шими операторами.

1. MERGE(A. В) объединяет компоненты Атд. В, результат присваивается или А, или В.

2. FIND(x) - функция, возврашаюшая имя компонента, которому принадлежит х.

3. INITIAL(A, х) создает компонент с именем у1, содержащим только элемент х.

Говорят, что а сравнимо с Ь по модулю п, если а и Ь имеют один и тот же остаток от деления на п, или, другими словами, если а - Ь кратно га.



Для корректной реализации АТД MFSET надо разделить исходные типы данных или объявить, что MFSET состоит из данных двух разных типов - типа имен множеств и типа элементов этих множеств. Во многих приложениях можно использовать целые числа для имен множеств. Если общее количество элементов всех компонент равно л, то можно использовать целые числа из интервала от 1 до и для идентификации элементов множеств. Если принять это предположение, то в таком случае существенно, что номерами элементов можно индексировать ячейки массива. Тип имен компонентов не так важен, поскольку это тип ячеек массива, а не индексов. Но если мы хотим, чтобы тип элементов множеств был отличным от числового, то необходимо применить отобралсение, например посредством хеш-функции, ставящее в соответствие элементам множеств уникальные целые числа из заданного интервала. В последнем случае надо знать только общее число элементов всех компонентов.

После всего сказанного не должно вызывать возражений следующее объявление типов:

const

л = { количество всех элементов };

type

MFSET = array[1..л] of Integer;

или объявление более общего типа

array [интервал элементов] of (тип имен множеств)

Предположим, что мы объявили тип MFSET как массив components (компоненты), предполагая, что eomponents[x] соаержш имя множества, которому принадлежит элемент х. При этих предположениях операторы АТД MFSET реализуются легко, что видно из листинга 5.13 с кодом процедуры MERGE. Процедура INITIAL(A, х) просто присваивает components[x] значение А, а функция FIND(x) возвращает значение components[x].

Листинг 5.13. Процедура MERGE

procedure MERGE ( А, В: integer; var С: mfset ) ; var

x: 1..n; begin

for x:= 1 to л do

if CfxJ = В then Clx]:= Л end; { MERGE j

Время выполнения операторов при такой реализации MFSET легко проанализировать. Время выполнения процедуры MERGE имеет порядок 0(л), а для INITIAL и FIND время выполнения фиксированно, т.е. не зависит от п.

Быстрая реализация АТД MFSET

Применение алгоритма из листинга 5.13 для последовательного выполнения и - 1 раз оператора MERGE займет время порядка 0(п). Один из способов ускорения выполнения оператора MERGE заключается в связывании всех элементов компонента в отдельные списки компонентов. Тогда при слиянии компонента В в компонент А вместо просмотра всех элементов необходимо будет просмотреть только список элементов компонента В. Такое расположение элементов сократит среднее время слияния компонентов. Но нельзя исключить случая, когда каждое i-e слияние выполня-

1 Для слияния п элементов в одно множество потребуется в самом худшем случае не более п - 1 выполнений оператора MERGE.



ется в виде оператора MERGE(A, В), где компонент А состоит из одного элемента, а 5 - из г элементов, и результат слияния получает имя компонента А. Выполнение такого оператора требует 0(1) шагов, а последовательность и - 1 таких операторов

потребует времени порядка i = п(п - 1)/2 .

Чтобы избежать описанной ситуации, можно отслеживать размер каждого компонента и всегда сливать меньшее множество в большее. Тогда каждый раз элемент из меньшего множества переходит в множество, которое, по крайней мере, в два раза больше его исходного множества. Поэтому, если первоначально было и компонентов и каждый из них содержал по одному элементу, то любой элемент может перейти в любой компонент не более чем за 1 + logra шагов. Таким образом, в новой версии оператора MERGE время его выполнения пропорционально количеству элементов в компоненте, чье имя изменяется, а обшее число таких изменений не больше п(1 + logn), поэтому время всех слияний имеет порядок 0(п logn).

Теперь рассмотрим структуру данных, необходимую для такой реализации. Во-первых, необходимо отображение имен множеств в записи, состоящие из

• поля count (счет), содержащего число элементов в множестве, и

• поля firstelement (первый элемент), содержащего индекс Ячейки массива с первым элементом этого множества.

Во-вторьпс, необходим еше один массив записей, индексированный элементами. Здесь записи имеют поля:

• setname (имя множества), содержашее имя множества;

• nextelemerit (следующий элемент), значение которого указывает на следующий элемент в списке данного множества.

Будем использовать О в качестве маркера конца списка, т.е. значения NIL. В языках программирования, подходящих для таких структур, можно было бы использовать указатели на последний массив, но язык Pascal не разрешает указателей внутрь массивов.

В специальном случае, когда имена множеств и элементы являются целыми числами из интервала от 1 до п, можно использовать массив для реализации отображения, описанного выше. В таком случае возможно следующее объявление:

type

nametype = I. .п; elementtype = l..n; MFSET = record

setheaders: array[l..n] of record { заголовки списков множеств } count: О . . л; firstelement: 0..п;

end;

names: array[1..л] of record { массив имен множеств } setлame: nametype; nextelement: 0..n

end;

Отметим здесь полезность и важность присваивания результата слияния наименьшему множеству, хотя в более простых реализациях результат слияния обычно присваивается первому аргументу оператора MERGE.

Здесь "намекается" на то, что если последовательность применений оператора MERGE представить в виде дерева, то это дерево по своей структуре будет приближаться к полному дереву. Отсюда вытекает утверждение следующего предложения о "1 + logn шагах". - Прим.ред.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 [52] 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0021