yandex rtb 1
ГоловнаЗворотній зв'язок
yande share

Алгоритмы структуры данных

ТЕМА 4

Основные операторы множеств

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

4.1. Введения в множества

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

Когда множества используются в качестве инструмента при разработке алгоритмов и структур данных, то атомами обычно являются целые числа, символы, строки символов и т.п., и все элементы одного множества, как правило, имеют одинаковый тип данных. Мы часто будем предполагать, что атомы линейно упорядочены с помощью отношения, обычно обозначаемого символом "<" и читаемого как "меньше чем" или "предшествует". Линейно упорядоченное множество S удовлетворяет следующим двум условиям.

1.    Для любых элементов а и b из множества S может быть справедливым только одно из следующих утверждений: а < b, а = b или b < а.

2.   Для любых элементов а, b и с из множества S таких, что а < b и b < с, следует а < с (свойство транзитивности).

Множества целых и действительных чисел, символов и символьных строк обладают естественным линейным порядком, для проверки которого можно использовать оператор отношения < языка Pascal. Понятие линейного порядка можно определить для объектов, состоящих из множеств упорядоченных объектов. Формулировку такого определения мы оставляем читателю в качестве упражнения. (Прежде чем приступать к общей формулировке, рассмотрите пример двух множеств целых чисел, одно из которых состоит из чисел 1 и 4, а второе — из чисел 2 и 3, и сформулируйте условия, в соответствии с которыми первое множество будет больше или меньше второго.)

Система обозначений для множеств

Множество обычно изображается в виде последовательности его элементов, заключенной в фигурные скобки, например {1, 4} обозначает множество, состоящее из двух элементов, — чисел 1 и 4. Порядок, в котором записаны элементы множества, не существен, поэтому мы можем писать {4, 1} так же, как и {1, 4}, при записи одного и того же множества. Отметим (и будем это иметь в виду в дальнейшем), что множество не является списком (хотя бы по признаку произвольного порядка записи элементов), но для представления множеств мы будем использовать списки. Повторим также еще раз, что мы предполагаем отсутствие повторяющихся элементов в множестве, поэтому набор элементов {1,4,1} не будем воспринимать как множество.

 Иногда мы будем представлять множества с помощью шаблонов, т.е. выражений вида {х | :утверждение относительно х”, где "утверждение относительно х" является формальным утверждением, точно описывающим условия, при выполнении которых объект х может быть элементом множества. Например, шаблон | х — положительное целое число и х ≤1000} представляет множество {1, 2, ...,1000}, а запись | для произвольного целого у, х = у2} определяет множество точных квадратов целых чисел. Отметим, что множество точных квадратов бесконечно и его нельзя представить перечислением всех его элементов.

Фундаментальным понятием теории множеств является понятие отношения принадлежности к множеству, обозначаемое символом . Таким образом, запись х  А обозначает, что х принадлежит множеству А, т.е. является элементом этого множества; элемент х может быть атомом или другим множеством, но А не может быть атомом. Запись х  А означает, что не принадлежит множеству А", т.е. х не является элементом множества А. Существует специальное множество, обозначаемое символом 0, которое называется пустым множеством и которое не имеет элементов. Отметим, что 0 является именно множеством, а не атомом, хотя и не содержит никаких элементов. Утверждение х  Ø является ложным для любого элемента х, в то же время запись х  у (если х и у атомы) просто не имеет смысла: здесь синтаксическая ошибка, а не ложное утверждение.

Говорят, что множество А содержится в множестве В (или включается в множество В), пишется А С В или В  А, если любой элемент множества А является также элементом множества В. В случае A  В также говорят, что множество А является подмножеством множества В. Например, {1, 2}  {1, 2, 3}, но множество {1, 2, 3} не может быть подмножеством множества {1, 2}, поскольку множество {1, 2, 3} содержит элемент 3, которого не имеет множество {1, 2}. Каждое множество включается в самого себя, пустое множество содержится в любом множестве. Два множества равны, если каждое из них содержится в другом, т.е. они имеют одни и те же элементы. Если А ≠ В и А  В, то множество А называют собственным, истинным или строгим подмножеством множества В.

Основными операциями, выполняемыми над множествами, являются операции объединения, пересечения и разности. Объединением множеств А и В (обозначается А и В) называется множество, состоящее из элементов, принадлежащих хотя бы одному из множеств А и В. Пересечением множеств А и В (обозначается А  В) называется множество, состоящее только из тех элементов, которые принадлежат и множеству А, и множеству В. Разностью множеств А и В (обозначается А  В) называется множество, состоящее только из тех элементов множества А, которые не принадлежат множеству В. Например, если А = {а, b, с} и В = {b, d}, то А  В = {а, b, с, d}, A  В = {b} и А\ В = {а, с}.

 

 

42