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

Немецкий ученый, математик, создатель теории множеств
Родился в Петербурге в 1845г.
В 1867 г. окончил Берлинский университет
В 1872-1913 гг. – профессор университета в Галле
Сформулировал общее понятие мощности множества (1878)
Развил принципы сравнения мощностей множеств и
Систематически изложил принципы своего учения
Созданная Кантором теория множеств, некоторые идеи которой имелись у его предшественников, послужила причиной общего пересмотра логических основ математики и оказала влияние на всю современную ее структуру.
Георг Кантор
(XIX-XXвв.)
Историческая справка

Цели:
1) описать способы хранения информации о принадлежности элемента множеству,
2) описать алгоритмы для вычисления результатов операций над множествами
Объекты изучения: множество, элемент множества, операции над множествами

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

Некоторые способы задания множеств

Булеан – множество всех подмножеств данного множества M
Обозначение: B(M)
Пример: дано множество A={a,b,c}. Найти В(А).
B(A)={ ∅, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c} }
Мощность булеана определяется по формуле:
|B(M)|=2 |M|
Пустое множество и само множество являются несобственными подмножествами множества М
Остальные подмножества – собственные
Булеан. Мощность булеана

Операции над множествами
А
В
A
B
A
A
A
B

Представление множества машинным словом или битовой шкалой
Пусть универсальное множество конечно и число п его элементов не превосходит разрядности ЭВМ. Занумеруем элементы универсума, т. е. . Подмножество А универсума представляется кодом С, в котором
где - это i-тый разряд кода С.
Тогда, код пересечения множеств А и В есть поразрядное логическое произведение кода множества А и кода множества В. Код объединения множеств А и В есть поразрядная логическая сумма кода множества А и кода множества В. Код дополнения множеств А до универсума есть инверсия кода множества А. в большинстве ЭВМ для этих операций есть соответствующие команды. Таким образом, операции над небольшими множествами выполняются эффективно.

Если универсум очень велик или бесконечен, а рассматриваемые подмножества не очень велики, то представление с помощью битовых шкал не является эффективным с точки зрения экономии памяти. В этом случае множества представляют списками элементов, часто упорядоченными.
Эффективная реализация операций над множествами в этом случае основана на общем алгоритме, известном под названием «Алгоритм типа слияния».
Такой алгоритм параллельно просматривает два множества, представленных упорядоченными списками, причем на каждом шаге продвижение происходит в том множестве, в котором текущий элемент меньше.
Представление множества упорядоченными списками

Множества будем хранить как массив с нумерацией элементов, начинающейся с единицы.
Обозначим через i номер текущего рассматриваемого элемента в множестве A, через j – номер текущего рассматриваемого элемента множества B. Будем получать множество P, представляющее собой пересечение множеств A и B. Через k обозначим мощность множества P. Также k будет и номером последнего добавленного элемента в P
Алгоритм нахождения пересечения слиянием

Положить i = j = 1 и k = 0.
Если в A и B (одновременно) есть ещё не просмотренные элементы, выполнить:
Если A[i] = B[j], то выполнить:
Добавить A[i] в Р, то есть k := k + 1 и Р[k] := A[i]
Перейти к следующим элементам множеств A, B, то есть i := i + 1 и j := j + 1
Если A[i] < B[j], то перейти к следующему элементу множества A, то есть i := i +1
В остальных случаях (то есть когда A[i] > B[j]) перейти к следующему элементу множества B, то есть j := j + 1
Перейти к пункту 2.
Пример.
Сравниваемые пары: (1,3), (3,3), (6,4), (6,5), (6,6), (8,7)
Р 3 6
Алгоритм решения

Алгоритм нахождения объединения слиянием
Обозначим через i номер текущего рассматриваемого элемента в множестве A, через j – номер текущего рассматриваемого элемента множества B. Будем получать множество Р, представляющее собой объединение множеств A и B. Через k обозначим мощность множества Р. Также k будет и номером последнего добавленного элемента в Р.