Основы дискретной математики

Кроме того, сформируем массив size, каждый элемент которого size(j) содержит количество элементов множества с именем j.

Будем различать внутренние имена множеств, содержащиеся в массиве к, и внешние имена, получаемые множествами в результате выполнения операции объединение. Соответствие между внутренними и внешними именами множеств можно установить с помощью массивов Ехт-NAME и INT-NAME. Эл

емент массива EXT-NAME(j) содержит внешнее имя множества, внутреннее имя которого есть j, а INT-NAME(k) – внутреннее имя множества, внешнее имя которого есть к.

Пример 2.3 Используя только что определенные массивы, опишите множества {1,3,5,7}, {2,4.8}, {6} с внешними именами 1, 2, 3 и внутренними именами 2, 3, 1 соответственно.

Решение. Прежде всего, отметим, что общее количество элементов всех множеств равно восьми. Поэтому размерность массивов R и next будет n = 8. Кроме того, напомним, что номера элементов массивов list, SIZE, Ехт-NAME и значения элементов массива R – это внутренние имена множеств, а массива INT-NAME внешние.

Алгоритм выполнения операции объединение (S1, S2, S3) состоит в добавлении к списку элементов большего из множеств S1 и S2 элементов меньшего множества и присвоение полученному множеству внешнего имени S3. При этом вычисляется также размер построенного множества S3.

Объединение (i, j, к)

Input

i, j – внешние имена объединяемых множеств

(пусть размер i меньше размера j);

массивы R, NEXT, LIST, SIZE, ЕХТ-NAME, INT-NAME;

begin

A:=INT-NAME(i);

B:=INT-NAME(j);

element:=LIST(A);

while element <> 0 do

begin

R(element):=B;

last:=element;

element:=NEXT(element)

end

NEXT(last):=LIST(B);

LIST(B):=LIST(A);

SIZE(B):=SIZE(B) + SIZE(A);

INT-NAME(K):=B;

EXT-NAME(B):=k

End

Объединение множеств i, j с внешним именем k.

В процессе работы алгоритм совершает следующие действия:

1) определяет внутренние имена множеств i и j;

2) определяет начало списка элементов меньшего множества;

3) просматривает список элементов меньшего множества и изменяет соответствующие элементы массива R на внутреннее имя большего множества;

4) объединяет множества путем подстановки меньшего множества перед большим;

5) присваивает новому множеству внешнее имя k.

Заметим, что время выполнения операции объединения двух множеств с помощью рассмотренного алгоритма пропорционально мощности меньшего множества.

2.1.3 Алгоритмы генерации множеств

Реализация операций над подмножествами заданного универсума U

Пусть универсум U – конечный, и число элементов в нем не превосходит разрядности ЭВМ: мощность |U| < n. Элементы универсума нумеруются: U = {u1,…, un}. Подмножество А универсума U представляется кодом (машинным словом или битовой шкалой) С, в котором:

где С(i) – это i‑й разряд кода С.

Код пересечения множеств А и В есть поразрядное логическое произведение кода множества А и кода множества В. Код объединения множеств А и В есть поразрядная логическая сумма кода множества А и кода множества В. Код дополнения множества А есть инверсия кода множества А. В большинстве ЭВМ для этих операций есть соответствующие машинные команды. Таким образом, операции над небольшими множествами выполняются весьма эффективно.

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

Генерация всех подмножеств универсума

Во многих переборных алгоритмах требуется последовательно рассмотреть все подмножества заданного множества. В большинстве компьютеров целые числа представляются кодами в двоичной системе счисления, причем число 2k – 1 представляется кодом, содержащим k единиц. Таким образом, число 0 является представлением пустого множества 0, число 1 является представлением подмножества, состоящего из первого элемента, и т. д. Следующий тривиальный алгоритм перечисляет все подмножества n‑элементного множества (представлен в паскале-подобном коде, описание в [23]).

Алгоритм 1.1: Алгоритм генерации всех подмножеств n‑элементного множества

Вход: n 0 – мощность множества

Выход: последовательность кодов подмножеств i

for i from 0 to 2n – 1 do

yield i

end for

Обоснование: Алгоритм выдает 2n различных целых чисел, следовательно, 2n различных кодов.

С увеличением числа n увеличивается количество двоичных разрядов, необходимых для его представления. Самое большое (из генерируемых) число 2n‑1 требует для своего представления ровно n разрядов. Таким образом, все подмножества генерируются, причем ровно по одному разу.

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

Алгоритм построения бинарного кода Грея

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

Алгоритм 1.2: Алгоритм построения бинарного кода Грея Вход: n 0 – мощность множества

Выход: последовательность кодов подмножеств В

В: array [l n] of 0 1 {битовая шкала для представления подмножеств}

for i from 1 to n do

B[i]: = 0 {инициализация} end for

yield В {пустое множество}

for i from I to 2n – 1 do

p: = Q(i) {определение элемента, подлежащего добавлению или удалению}

B[р]: = 1 – В[р] {добавление или удаление элемента}

yield В {очередное подмножество} end for

proc Q(i) {количество 2 в разложении i на множители + 1} q: = l; j: = i while j четно do

j:=j/2; q: = q + l end while return q end proc

Обоснование

Для n = 1 искомая последовательность кодов суть 0,1. Пусть есть искомая последовательность кодов В1,…, для n = к. Тогда последовательность кодов B10,…, 0, 1, …. B11 будет искомой последовательностью для n = к + 1. Действительно, в последовательности B10,…, 0, 1,…, В11 имеется 2k+1 кодов, они все различны и соседние различаются ровно в одном разряде по строению. Именно такое построение и осуществляет данный алгоритм. На нулевом шаге алгоритм выдает правильное подмножество В (пустое). Пусть за первые 2k – 1 шагов алгоритм выдал последовательность значений В. При этом В [k + 1] = В [k + 2] = • • • = В[n] = 0. На 2 k‑ом шаге разряд В [k + 1] изменяет свое значение с 0 на 1. После этого будет повторена последовательность изменений значений В [1. k] в обратном порядке, поскольку Q (2k + m) = Q (2k – m) для

 Скачать реферат