Теория множеств

Объединением (или суммой) множеств А и В называется множество, состоящее из тех и только тех элементов, которые принадлежат хотя бы одному из множеств А или В: A  B = {x | x  A или x  B}.
Пересечением (или произведением) множеств А и В называется множество, состоящее из тех и только тех элементов, которые принадлежат каждому из множеств А и В: A  B = {x | x  A и x  B}.
Если A  B = , то множества А и В называются непересекающимися.
Разностью множеств А и В называется множество A \ B , состоящее из тех и только тех элементов, которые принадлежат А, но не принадлежат В: A \ B = {x | x  A и x  B}.
Симметрической разностью множеств А и В называется множество A Δ B = (A  B) \ (A  B) = {x | (x  A и x  B) или (x  B и x  A)}.
Дополнением множества А называется множество всех элементов универсального множества, не входящих в A: A = U \ A = {x | x  A}.
Операции объединения и пересечения допускают обобщение для большего количества множеств (в том числе и бесконечного). В общем случае для объединения k множеств используется обозначение , или для бесконечного числа множеств: = {x |  i  I | x  A_i}. Аналогично, для пересечения k множеств используется обозначение , или , если количество множеств бесконечно: = {x |  i  I |x  A_i }.
Н а рисунке 1.1 (справа) приведены т.н. диаграммы Эйлера-Венна, графически иллюстрирующие вышеописанные операции над множествами. Введенные операции показаны на диаграммах Венна темным цветом. Такие геометрические представления множеств часто используются при решении задач или доказательстве каких-либо утверждений.

4. 
   Рассмотрим два множества чисел: А = {1, 2, 3, 4}; B = {1, 3, 5, 7}. Тогда операции над этими множествами будут иметь вид:
   объединение A  B = {1, 2, 3, 4, 5, 7};
   пересечение A  B = {1, 3}; разность A \ B = {2, 4} и B \ A = {5, 7}; симметрическая разность A Δ B = {2, 4, 5, 7}. Для рассмотрения дополнения A необходимо знать универсальное множество, все элементы которого за исключением элементов A и будут являться дополнением.
   

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

Задать представление какого-либо объекта в программе – означает описать в терминах используемой системы программирования структуру данных, используемую для хранения информации о представляемом объекте, и алгоритмы над выбранными структурами данных, которые реализуют присущие данному объекту операции.
Один и тот же объект может быть представлен различными способами, причем в разных ситуациях могут оказаться наиболее эффективными разные способы. Выбор представления зависит от целого ряда факторов: особенности представляемого объекта, состава и относительной частоты использования операций в конкретной задаче, и т.д. Хороший программист должен знать разные способы представления объекта и в каждой конкретной ситуации уметь выбрать из них наиболее подходящий.
Для конечного универсума, мощность которого не превосходит разрядности машинного слова, подмножества универсума могут представляться битовой шкалой (аналог характеристической функции – 0 или 1 для каждого элемента). Битовая шкала имеет размерность универсума, и для каждого подмножества число единиц в соответствующей ему битовой шкале определяется мощностью этого подмножества. Если элемент входит в подмножество, то ему соответствует 1, иначе 0. Тогда операции над подмножествами осуществляются посредством поразрядных логических операций.
Во многих переборных алгоритмах требуется последовательно рассмотреть все подмножества заданного множества. В случае использования битовой шкалы существуют специальные алгоритмы, которые будут рассмотрены позже.
Если универсум велик, а подмножества имеют сравнительно небольшую мощность, то использование характеристических функций невыгодно, т.к. в них будет много нулей. Для представления таких множеств обычно используют списки элементов. Элемент множества тогда может быть представлен записью с двумя полями: информационным и указателем на следующий элемент. Трудоемкость операций включения, пересечения и объединения определяется как O(mn), где m и n – мощности множеств; операции  – как O(n).
При использовании списков, упорядоченных по информационному полю, трудоемкость всех операций является линейной (О(n)). В таком случае эффективная организация всех операций над множествами основана на общем алгоритме, известном как алгоритм типа слияния.
Алгоритм типа слияния параллельно просматривает два множества, представленных упорядоченными списками, причем на каждом шаге продвижение вперед (увеличение номера рассматриваемого элемента) происходит в том множестве, в котором текущий элемент меньше. В качестве простейшей организации множеств можно использовать упорядоченный массив элементов.
1. Проверка включения AB
Вход: Два упорядоченных множества A и B (массивы).
Выход: да или нет (1 или 0, true или false).
i:=1; j:=1; // указатели на начало множеств
пока i|A|+1 и j|B|+1 цикл
если A[i] < B[j] то вернуть 0 и выход // элемент A отсутствует в B
иначе если A[i] > B[j] то j:=j+1 // переход к след. элементу B
иначе // элементы совпали – перейти к следующим
i:=i+1; j:=j+1;
конец если
конец цикла
если i=|A|+1 то вернуть 1 иначе вернуть 0.
Алгоритмы, вычисляющие объединение множеств, пересечение и дополнение устроены совершенно аналогичным образом. Общее действие – продвижение вперед (увеличение индекса) в том массиве, элемент которого меньше, и сразу в обоих, если элементы равны.
Для определения объединения в результирующее множество заносятся каждый из меньших элементов и один, если они равны. Если конец одного из множеств достигнут раньше, все оставшиеся элементы другого дописываются в конец итогового множества.
Для определения пересечения в результирующее множество заносится тот элемент, который совпал у обоих множеств. Если конец одного из множеств достигнут раньше, работа алгоритма заканчивается.

4. 
   Разбиения и покрытия
   

Пусть Ě ={E_i} для i I – некоторое семейство непустых подмножеств множества M, E_i  M. Тогда семейство Ě называется покрытием множества M, если каждый элемент множества M принадлежит хотя бы одному из E_i: