Структуры данных. Множества
16 декабря 2023 г.
Основная информация
Это краткий конспект части о множествах в книге Гид по Computer Science, Вильям Спрингер.
Множество — это неупорядоченная коллекция уникальных предметов.
Три основные операции каждая из которых принимает два множества в качестве аргументов и возвращает еще одно множество в качестве результата.
Union(A, B) — объединение множеств — это множество, содержащее каждый элемент, который принадлежит хотя бы одному из множеств A и B. Обычно объединение обозначается как A ∪ B.
Intersection(A, B) — пересечение множеств — это множество элементов, содержащихся как в A, так и в B, обозначается как A ∩ B.
Difference(A, B) — разность множеств — обозначается как A – B — это множество, в которое входят все элементы, содержащиеся в A, но отсутствующие в B.
Также еще существует операция Subset(A, B) - она возвращает логическое значение. Возвращает истину (true) - если А подмножество В.
Собственное подмножество - A является подмножеством B и не равно B.
Используемые обозначения:
A ⊆ B - A подмножество B,
A ⊆/ B - A не подмножество B,
A ⊂ B - A собственное подмножеством B
A ⊂/ B - A не собственное подмножество B.
Если A ⊆ B и B ⊆ A, то A = B.
Пример множества целых: {4, 7, 12, 18, 2004}
В JavaScript множество представлено объектом Set.
Виды множеств
Мультимножество — в нем допускается дублирование элементов: хранятся несколько копий одного значения либо ведется подсчет того, сколько раз значение присутствует в множестве.
Частично упорядоченное множество — в нем некоторые элементы расположены в определенном порядке. Для некоторой двоичной операции (операция, которая работает с двумя операндами) ≤ между элементами b и c может быть истиной b ≤ c, в других — c ≤ b или же между b и c может не существовать отношений.
Полностью упорядоченное множество - все элементы множества связаны операцией ≤ - для любых двух элементов f и g множества либо f ≤ g, либо g ≤ f.
Необходимо, чтобы отношение было:
- рефлексивным - каждый элемент множества меньше или равен самому себе,
- антисимметричным - если b меньше или равно c, то c не может быть меньше или равно b, если только b не равно c,
- транзитивным - если b меньше или равно c, а c меньше или равно d, то b меньше или равно d).
Например, пусть ≤ означает отношение «является потомком», причем по определению каждый человек является потомком самого себя. Тогда такое отношение является антисимметричным (если я твой потомок, то ты не можешь быть моим потомком) и транзитивным (если я твой потомок, а ты потомок дедушки, то я тоже потомок дедушки). Это частичное, а не полное упорядочение, поскольку, возможно, ни я не являюсь твоим потомком, ни ты — моим.
Куча — частично упорядоченное мультимножество.