Материал: Методические указания к выполнению лабораторных работ по дисциплине «Дискретная математика» для студентов направления подготовки бакалавров. Собенина О.В., Пак А.А

Разностью множеств X и Y называется множество X/Y всех тех элементов X, которые не принадлежат Y:

X\Y={x x и x .}.

Симметричной разностью множества X и Y называется множество ( \ ) ( \ ) .

Дополнением множества X называется множество всех тех элементов x, которые не принадлежат множеству X:

=U\X

Декартовым (прямым) произведением множеств X и Y

называется множество упорядоченных пар вида

Пример. Пусть X= x1,x2 ,x3 , y1, y2 . Тогда

(xi, yi ),(x1, y2 ),(x2 , y1),(x2 , y2 ),(x3 , y1),(x3 , y2 ) .

Аналогично можно определить декартово произведение n множеств 1, 2 ,....., n

1 2 .... n (x1,x2 ,...,xn ) x1 1, x2 2 ,...,xn n .

Если 1 2 ... n , то n-я степень множества X опре-

деляется как n X X ... X.

n

Представление множеств в ЭВМ

Применительно к множествам определение представления подразумевает описание способа хранение информации о принадлежности элементов множеству и описание алгоритмов для вычисления объединения, пересечения и других введённых операций.

Как правило, один и тот же объект может быть представлен многими разными способами, причем нельзя указать способ, который является наилучшим для всех возможных случаев. В одних случаях выгодно использовать одно представление, а в других - другое. Выбор представления зависит от цело-

4

го ряда факторов: особенностей представляемого объекта, состава и относительной частоты использования операций в конкретной задаче и т.д.

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

for x M do P(x) end for

означает применение процедуры Р ко всем элементам множества М.

Оператор select m M

означает выбор произвольного элемента m из множества М. Оператор

yield x

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

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

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

1, если ui A,

С[i] =

0, если ui A,

5

где C[i] – это i-й разряд кода С.

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

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

Представление множеств упорядоченными списками

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

еlem = record

i: info; { информационное поле }

n: ^ elem {указатель на следующий элемент } end record

Эффективная реализация операций над множествами, представленными в виде упорядоченных списков, основана на алгоритме, известном как алгоритм типа слияния.

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

6

Алгоритм. Проверка включения слиянием.

Вход: проверяемые множества A и B, которые заданы указателями a и b.

Выход: 1, если A B, в противном случае 0. pa:=a; pb:=b

while pa nil & pb nil do if pa.i<pb.i then

return 0 {элемент множества А отсутствует в множестве

В}

else if pa.i>pb.i then

pb:=pb.n {элемент множества А, может быть, присутствовать в множестве В}

else

pa:=pa.n {здесь pa.i=pb.i, то есть }

pb:=pb.n {элемент множества А точно присутствует в множестве В}

end if end while

return pa=nil

Обоснование. На каждом шаге основного цикла возможна одна из трёх ситуаций: текущий элемент множества А меньше, больше или равен текущему элементу множества В. В первом случае текущий элемент множества А заведомо меньше, чем текущий и все последующие элементы множества В, а потому он не содержится в множестве В, и можно завершить выполнение алгоритма. Во втором случае происходит продвижение по множеству В в надежде отыскать элемент, совпадающий с текущим элементом множества А. В третьем случае найдены совпадающие элементы, и происходит продвижение сразу в обеих множествах. По завершении основного цикла возможны два случая: либо pa=nil, либо pa nil. Первый случай означает, что для всех элементов множества А удалось найти совпадающие элементы множества В. Второй случай означает,

8