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

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

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

Рисунок 2.6 – Диаграмма Венна симметрической разности А Δ В

2.1.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

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

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

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

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

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

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

Рисунок 2.7 – Дерево поиска минимума S

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

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

из дерева;

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

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

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