1.5 Представление множеств в эвм

Для конечного универсума, мощность которого не превосходит разрядности машинного слова, подмножества универсума могут представляться битовой шкалой (аналог характеристической функции – 0 или 1 для каждого элемента). Битовая шкала имеет размерность универсума, и для каждого подмножества число единиц в соответствующей ему битовой шкале определяется мощностью этого подмножества. Если элемент входит в подмножество, то ему соответствует 1, иначе 0. Тогда операции над подмножествами осуществляются посредством поразрядных логических операций

Если универсум велик, а подмножества имеют сравнительно небольшую мощность, то использование характеристических функций невыгодно, т.к. в них будет много нулей. Для представления таких множеств обычно используют списки элементов. Элемент множества тогда может быть представлен записью с двумя полями: информационным и указателем на следующий элемент. Трудоемкость операций включения, пересечения и объединения определяется как O(m× n), где m и n – мощности множеств; операции Î – как O(n).

При использовании списков, упорядоченных по информационному полю, трудоемкость всех операций является линейной (О(n)). В таком случае эффективная организация всех операций над множествами основана на общем алгоритме, известном как алгоритм типа слияния.

Алгоритм типа слияния параллельно просматривает два множества, представленных упорядоченными списками, причем на каждом шаге продвижение вперед (увеличение номера рассматриваемого элемента) происходит в том множестве, в котором текущий элемент меньше.

В качестве простейшей организации множеств можно использовать упорядоченный массив элементов.

Проверка включения AÌ B

Вход: Два упорядоченных множества A и B (массивы).

Выход: да или нет (1 или 0, true или false).

i:=1; j:=1; // указатели на начало множеств

пока i < |A|+1 и j < |B|+1 цикл

если A[i] < B[j] то вернуть 0 и выход

// элемент A отсутствует в B

  иначе

если A[i] > B[j] то j:=j+1

// переход к след. элементу B

иначе

// элементы совпали – перейти к следующим

i:=i+1; j:=j+1;

конец если

конец цикла

если i=|A|+1 то вернуть 1, иначе вернуть 0.

Алгоритмы, вычисляющие объединение множеств, пересечение и дополнение устроены совершенно аналогичным образом. Общее действие – продвижение вперед (увеличение индекса) в том массиве, элемент которого меньше, и сразу в обоих, если элементы равны.

Для определения объединения в результирующее множество заносятся каждый из меньших элементов и один, если они равны. Если конец одного из множеств достигнут раньше, все оставшиеся элементы другого дописываются в конец итогового множества.

Для определения пересечения в результирующее множество заносится тот элемент, который совпал у обоих множеств. Если конец одного из множеств достигнут раньше, работа алгоритма заканчивается.