Основы дискретной математики (стр. 9 из 23)

2.1 Теоретическая часть

2.1.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,…}.

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

S

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

А

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

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

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

А

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

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

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

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

A\В = {х: х

А и x В}.

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

и называют просто дополнением множества А. Таким образом, понимая, что мы работаем с подмножествами универсального множества U можно записать

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

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

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

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

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

А и х В) или (х В и х А)}.

Оно состоит из всех тех и только тех элементов универсального множества, которые либо принадлежат А и не принадлежат В, либо наоборот, принадлежат В, но не А. Грубо говоря, симметрическая разность состоит из элементов, лежащих либо в А, либо в В, но не одновременно. Диаграмма Венна, иллюстрирующая симметрическую разность, начерчена на рисунке 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). Для нахождения наименьшего элемента в двоичном дереве поиска Т строится путь v₀, v_i, …, v_p, где v₀-корень дерева Т, v_i – левый сын вершины v_i-1 (i= 1,2,…, р), а у вершины v_p левый сын отсутствует. Ключ вершины v_p, и является наименьшим элементом в дереве Т. В некоторых задачах полезно иметь указатель на вершину v_y, чтобы обеспечить доступ к наименьшему элементу за постоянное время.