Множества и их свойства

Размещено на http://www.allbest.ru/

Содержание

1. Множества и операции над ними

2. Представление множеств и отношений в программах

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

Список использованной литературы

1. Множества и операции над ними

Множество - это совокупность объектов, называемых элементами множества. Например:

* {Эссекс, Йоркшир, Девон}; * {2, 3, 5, 7, 11}.

В этом примере элементы каждого множества заключены в фигурные скобки. Чтобы обеспечить возможность ссылок, мы будем обозначать множества прописными латинскими буквами. Например,

S = {3, 2, 11, 5, 7} - множество, содержащее целые числа. Заметим, что множество S совпадает с одним из множеств, выписанных выше, поскольку порядок, в котором записываются элементы множества, значения не имеет.

В общем случае запись аS означает, что объект а - элемент множества S. Часто говорят, что а принадлежит множеству S. Если объект а не принадлежит S, то пишут: а S.

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

Существует несколько способов конструирования нового множества из двух данных. Опишем коротко эти операции на множествах. Прежде всего, отметим, что все элементы некоторых множеств принадлежали другим большим множествам. Например, все элементы множества С = {0, 1, 4, 9, 16,…} содержатся в множестве Z = {0, ±1, ±2, ±3,…}.



Рисунок 1 - Диаграмма Венна подмножества А S

Объединением двух множеств А и В называется множество

АВ = {х: х А или х В}.

Оно состоит из тех элементов, которые принадлежат либо множеству A, либо множеству В, а возможно и обоим сразу. Диаграмма Венна объединения показана на рисунке 2.

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

А В = {х: х А и х В}.

Оно состоит из элементов, которые принадлежат как множеству А, так и множеству B. Диаграмма Венна пересечения приведена на рисунке 3.

Рисунок 2 - Диаграмма Венна



Рисунок 3 - Диаграмма Венна для объединения множеств для пересечения множеств

Дополнением множества В до множества А называется

A\В = {х: х А и x В}.

Дополнение А \ В состоит из всех элементов множества А, которые не принадлежат В (см. рисунок 4). Если мы оперируем подмножествами некоего большого множества U, мы называем U универсальным множеством для данной задачи. На наших диаграммах Венна прямоугольник как раз и символизирует это универсальное множество. Для подмножества А универсального множества U можно рассматривать дополнение А до U, т. е. U \ А. Поскольку в каждой конкретной задаче универсальное множество фиксировано, множество U \ А обычно обозначают и называют просто дополнением множества А. Таким образом, понимая, что мы работаем с подмножествами универсального множества U можно записать

= {х: не (х А)} = {х: х A}.

Диаграмма Венна дополнения изображена на рисунке 5.

Рисунок 4 - Диаграмма Венна разности А \ В



Рисунок 5 - Диаграмма Венна дополнения

Симметрической разностью двух множеств А и В называют множество А Д В = {х: (х А и х В) или (х В и х А)}.

Оно состоит из всех тех и только тех элементов универсального множества, которые либо принадлежат А и не принадлежат В, либо наоборот, принадлежат В, но не А. Грубо говоря, симметрическая разность состоит из элементов, лежащих либо в А, либо в В, но не одновременно. Диаграмма Венна, иллюстрирующая симметрическую разность, начерчена на рисунке 6.

Рисунок 6 - Диаграмма Венна симметрической разности А Д В

2. Представление множеств и отношений в программах

В этом параграфе рассматривается представление множеств в программах. Термин «представление» (еще употребляют термин «реализация») применительно к программированию означает следующее. Задать представление какого-либо объекта (в данном случае множества) - значит, описать в терминах используемой системы программирования структуру данных, используемую для хранения информации о представляемом объекте, и алгоритмы над выбранными структурами данных, которые реализуют присущие данному объекту операции. Предполагается, что в используемой системе программирования доступны такие общеупотребительные структуры данных, как массивы, структуры (или записи) и указатели. Таким образом, применительно к множествам определение представления подразумевает описание способа хранения информации о принадлежности элементов множеству и описание алгоритмов для вычисления объединения, пересечения и других введенных операций [5].

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

Множества и задачи информационного поиска

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

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

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

* Поиск (а; S) определяет, принадлежит ли элемент а множеству S;

если а S, результат операции - ответ «да»; в противном случае -

ответ «нет».

* Вставка (а, S) добавляет элемент а в множество S, то есть заменяет S на S U {а}.

* Алгоритм правильного обхода(S) печатает элементы множества S с

соблюдением порядка.

* Удаление (a, S) удаляет элемент а из множества S, то есть заменяет S на S \ {а}.

* Объединение (S1, S2, S3) объединяет множества S1 и S2, т. е. строит

множество S3 = S1 U S2.

* Минимум (S) выдает наименьший элемент множества S.

Следующая операция - операция минимум(S). Для нахождения наименьшего элемента в двоичном дереве поиска Т строится путь v0, vi, …, vp, где v0-корень дерева Т, vi - левый сын вершины vi-1 (i= 1,2,…, р), а у вершины vp левый сын отсутствует. Ключ вершины vp, и является наименьшим элементом в дереве Т. В некоторых задачах полезно иметь указатель на вершину vy, чтобы обеспечить доступ к наименьшему элементу за постоянное время.

Алгоритм выполнения операции минимум(S) использует рекурсивную процедуру левый сын(v), определяющую левого сына вершины v. Алгоритм и процедура выглядят следующим образом.

Input

двоичное дерево поиска Т для множества S

begin

if T = 0 then output «дерево пусто»;

else

вызвать процедуру левый сын(r)

(здесь r - корень дерева Т);

минимум:=1 (v), где v - возврат процедуры левый сын;

end

Output ответ «дерево пусто», если Т не содержит вершин;

минимум - наименьший элемент дерева Т в противном случае.

Procedure левый сын (v).

begin

if v имеет левого сына w then return левый сын (w)

else return v

end

Пример 1. Проследите работу алгоритма минимум на дереве поиска, изображенном на рисунке 7.

Решение. Дерево Т не пусто, следовательно, вызывается процедура левый сын (1).

Вершина 1 имеет левого сына - вершину 2, значит, вызывается процедура левый сын (2).

Вершина 2 имеет левого сына вершину 4, значит, вызывается процедура левый сын (4).

Вершина 4 не имеет левого сына, поэтому вершина 4 и будет возвратом процедуры левый сын.

Ключом вершины 4 является слово begin, следовательно, наименьшим элементом дерева Т является значение минимум= begin.

Рисунок 7 - Дерево поиска минимума S



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

* вершина v является листом; в этом случае v просто удаляется из дерева;

* у вершины v в точности один сын; в этом случае объявляем отца вершины v отцом сына вершины v, удаляя тем самым v из дерева (если v - корень, то его сына делаем новым корнем);

* у вершины v два сына; в этом случае находим в левом поддереве вершины v наибольший элемент b, рекурсивно удаляем из этого поддерева вершину, содержащую b, и присваиваем вершине v ключ b. (Заметим, что среди элементов, меньших а, элемент b будет наибольшим элементом дерева. Кроме того, вершина, содержащая b, может быть или листом, являющимся чьим-то правым сыном, или иметь только левое поддерево.)

Ясно, что до выполнения операции удаление (а, S) необходимо проверить, не является ли дерево пустым и содержится ли элемент а в множестве S. Для этого придется выполнить операцию поиск (а, S), причем, и в случае положительного ответа необходимо выдать кроме ответа «да» и номер вершины, ключ которой совпадает с a (далее ключ вершины v будем обозначать через l(v)). Кроме этого, для реализации операции удаление (a, S) требуется знать и номер вершины w, являющейся отцом вершины v. Саму же рекурсивную процедуру удаление (а, S) можно реализовать так, как показано ниже.

Procedure удаление (а, S)

begin

if v - лист then удалить v из Т

else

(2) if v имеет только левого или только

правого сына u then

(3) if v имеет отца w then

назначить и сыном w

else

сделать u корнем дерева,

присвоив ему номер v

else

найти в левом поддереве v наибольший элемент b, содержащийся в вершине у;

(6) return удаление (b, S);

(7) l(v):=b;

end

Пример 2. Проследите за работой алгоритма удаление (а, S) для двоичного дерева поиска S, изображенного на рисунке 2.7, если a - это слово «if».

Решение. Слово «if» расположено в корне с номером 1, у которого два сына (вершины 2 и 3), поэтому выполняем строку (5) алгоритма. Наибольшее слово, меньшее «if» (лексикографически), расположенное в левом поддереве корня и находящееся в вершине 2, - это end. Вызываем процедуру удаление (end, S).

Условие строки (2) алгоритма выполняется, так как вершина 2 с ключом end имеет только левого сына. Условие строки (3) не выполняется, так как удаляемая вершина является корнем. Поэтому переходим к строке (4): делаем вершину 2 корнем, сыновьями которого становятся вершины 4 (левым) и 3 (правым). Работа процедуры удаление (end, S) закончена.

Продолжаем выполнение алгоритма (выполняем строку (7)): полагаем ключ вершины 1 равным «end» (l (I):=end).

Полученное в результате дерево изображено на рисунке 8.

Заметим, что при работе рассмотренных алгоритмов необходимо находить сыновей, отца и ключ заданной вершины двоичного дерева поиска. Это можно сделать довольно просто, если дерево в памяти компьютера хранится в виде трех массивов: LEFTSON, RIGHTSON и KEY. Эти массивы устроены следующим образом:

LEFTSON (i) =	v, если v - левый сын вершины i *, если у вершины i левого сына нет
RIGHTSONM (i) =	v, если v - правый сын вершины i *, если у вершины i правого сына нет

key(i) = l(i) - ключ вершины i.

Рисунок 8 - Результат работы алгоритма удаление (а, S) для двоичного дерева поиска S

Например, бинарное поисковое дерево, изображенное на рисунке 7, может быть представлено в виде таблицы 1.

Таблица 2.1 - Представление бинарного поискового дерева в виде таблицы

I	LEFTSON	RIGHTSON	KEY
1	2	3	if
2	4	*	end
3	*	6	then
4	*	5	begin
5	*	*	else
6	*	*	while

Правила поиска сыновей и ключа заданной вершины следуют из определения массивов. Определение отца заданной вершины состоит в нахождении строки массивов LEFTSON или RIGHTSON, в которой находится номер заданной вершины. Например, отцом вершины 4 является вершина 2, так как число 4 находится во второй строке массива LEFTSON.

Объединение множеств

Обратимся теперь к объединению множеств, то есть к операции объединение (S1, S2, S3).

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

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

Процедура объединения непересекающихся множеств применяется, например, при построении минимального остовного дерева в данном нагруженном графе.

Рассмотрим алгоритм объединения непересекающихся множеств на основе списков. Будем считать, что элементы объединяемых множеств пронумерованы натуральными числами 1,2,…. n. Кроме того, предположим, что имена множеств - также натуральные числа. Это не ограничивает общности, поскольку имена множеств можно просто пронумеровать натуральными числами.

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

Сформируем два массива R и next размерности n, в которых R(i) - имя множества, содержащего элемент i, a next(i) указывает номер следующего элемента массива R, принадлежащего тому же множеству, что и элемент i. Если i - последний элемент какого-то множества, то положим next(i) = 0. Для указателей на первые элементы каждого множества будем использовать массив list, число элементов которого равно числу рассматриваемых в задаче множеств, и элемент которого list(j) содержит номер первого элемента множества с именем j в массиве R.

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

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

Пример 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.

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

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) для

Пример 4



Таблица 5 - Протокол выполнения алгоритма 1.2 для п = 3

i	Р		В
		0	0	0
1	1	0	0	1
2	2	0	1	1
3	1	0	1	0
4	3	1	1	0
5	1	1	1	1
6	2	1	0	1
7	1	1	0	0

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

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

elem = record

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

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

При таком представлении трудоемкость операции составит O(n), а трудоемкость операций составит О(nm), где n и m - мощности участвующих в операции множеств.

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



1

1 1

1 2 1

13 3 1

14 6 4 1

Рисунок 9 - Иллюстрация к алгоритму слияния

В этом равнобедренном треугольнике каждое число (кроме единиц на боковых сторонах) является суммой двух чисел, стоящих над ним. Число сочетаний С (m, n) находится в (m + 1) - м ряду на (n + 1) - м месте.

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

Элементы множества {1,…, m} упорядочены. Поэтому каждое n_элементное подмножество также можно рассматривать как упорядоченную последовательность. На множестве таких последовательностей естественным образом определяется лексикографический порядок. Следующий простой алгоритм генерирует все n_элементные подмножества m_элементного множества в лексикографическом порядке.



Список использованной литературы

1. Р. Хаггарти Дискретная математика для программистов Москва: Техносфера, 2003.

2. Гончарова Г.А., Мочалин А.А. Элементы дискретной математики: Учебное пособие. - М.: ФОРУМ: ИНФРА_М, 2004.

3. Романовский И.В. Дискретный анализ. Учебное пособие для студентов, специализирующихся по прикладной математике и информатике. Издание 2_е, исправленное, - СПб.: Невский диалект, 2000 г.

4. Д. Кнут Искусство программирования для ЭВМ, т. 2, М.: Мир, 2000.

5. Новиков Ф.А. Дискретная математика для программистов. - СПб.: Питер, 2001.

6. Ламуатье Ж._П. Упражнения по программированию на Фортране IV, М.-Мир, 1978.

7. Светозарова Г.И. и др. Практикум по программированию на языке Бейсик: Учеб. пособие для вузов. - М.: Наука. Гл. ред. физ.-мат. лит., 1988.

8. Зеленяк О.П. Практикум по программированию на Turbo Pascal. Задачи, алгоритмы и решения - К.: Издательство «ДиаСофт», 2001.

9. Абрамов С.А., Гнездилова Г.Г. и др., Задачи по программированию, М., Наука. Гл. ред. физ.-мат. лит., 1988.

10. Абрамов С.А., Зима Е.В. Начала информатики. - М., Наука. Гл. ред. физ.-мат. лит., 1989.

11. Юркин А.Г. Задачник по программированию. - СПб.: Питер, 2002.

Размещено на Allbest.ru

...