Дискретная математика (998286), страница 5
Текст из файла (страница 5)
гег 1.2.3. Разбиения и покрытия Пусть Я = (Е;), г — некоторое семейство подмножеств множества М, Е; С М Глава 1. Множества и отношения Рис. 1.1. Операции нвд множествами Семейство Я называется покрьаливм множества М, если каждый элемент М принадлежит хотя бы одному из Еб М с Ц Е; Ф~ Чк б М 31 Е 1 к Е Еь ает Семейство Я называется дизьюнктным, если элементы этого семейства попарно не пересекаются, то есть каждый элемент множества М принадлежит не более чем одному из множеств Е;: Ч т, т е 1 т ф т =ь Е, г~ Е = и. Дизъюнктное покрытие Я называется разбиением множества М, пример Пусть М: =(1, 2, 3).
Тогда ((1, 2), (2, 3), (3, 1) ) является покрытием, но не разбиением; ((1), (2), (3)) является разбиением (и покрытием), а семейство ((1), (2)) является дизъюнктным, но не является ни покрытием, ни разбиением. 1.3. Алгебра подмножеств Операции над множествами обладают целым рядом важных свойств, которые рассматриваются в этом разделе. КЗ, Алгебра подмножеств 1.3.1. Булеан Множество всех подмножеств множества М называется булеаном и обозначается 2м.
2:=(А~АсМ) ТЕОРЕМА Для конечного множества М ~2м~ = 2™ Доклздткпьство Индукция по )М~. База: если ~М( = О, то М = ю и 2е = (ю). Следовательно, р ~ цыц 1 2в Индукционный переход: пусть ЫМ )М~ < й =~ (2м) = 2™. Рассмотрим М = = (аы..., аь), (М! = й. Положим Мд.=(Хс2 )аьЕХ) иМз.=(Хс2 (аьфХ). Имеем 2~ = Мг 0 Мз и Мт П Ма = е. По индукционному предположению )Мт! = 2" ', )Мз~ = 2ь т. Следовательно, ~2м! = ~Мд) + 1Ма~ = 2ь т + 2" т = = 2 ° 2" т = 2ь = 2™. П Пересечение, объединение и разность подмножеств множества У (универсума) являются подмножествами множества У.
Множество всех подмножеств множе- ства У с операциями пересечения, объединения, разности и дополнения образует алгебру подмножеств множества У. 1.3.2. Свойства операций над множествами Пусть задан универсум У. Тогда Ы А, В, С с У выполняются следуюгдие свойства. АПА=А; Айте=А; 1. идемпотентностпгк АОА=А, 2. коммугп ативностгк АОВ=ВОА, 3. ассог(иапгивностгк А О (В 0 С) = (А 0 В) О С, 4. дистрибутивностгк АО(ВПС) = (АОВ) П(АОС), 5.
поглоигение: (АПВ)ОА=А, 6. свойства нуля; АОю = А, 7. свойства единицы: АОУ=У, 8. инволютивностгя А=А; АПВ=ВПА; Ап(Вг1 С) = (АпВ) пС; А и (В О С) = (А й В) О (А и С); (АОВ) г|А = А; Апи=е; Глава 1, Множества и отношения 9. законы де о«органа: АгтЗ = А ОЗ, 9, свойства дополнения: А0А=У, А. выражение для разности: А ~ В = А и З. АОА= И; В справедливости перечисленных свойств можно убедиться различными спо:обами.
Например, нарисовать диаграммы Эйлера для левой и правой частей равенства и убедиться, что они совпадают, или же провести формальное рассуждение для каждого равенства. Рассмотрим для примера первое равенство: А 0 А = А. Возьмем произвольный элемент х, принадлежащий левой части равенства, х Е АОА. По определению операции объединения 0 имеем х Е Апх Е А. В любом случае х 4 А, Взяв произвольный элемент из множества в левой части равенства, обнаружили, что он принадлежит множеству в правой части. Отсюда по определению включения множеств получаем, что А11А с А. Пусть теперь г Е А. Тогда, очевидно, верно х Е А У х е А. Отсюда по определению операции объединения имеем х е А О А.
Таким образом, А с А О А. Следовательно, по определению равенства множеств, А О А = А, Аналогичные рассуждения нетрудно провести и для остальных равенств. 1.4. Представление множеств в ЭВМ В этом параграфе рассматривается представление множеств в программах. Термин «представлениея (еще употребляют термин «реализацняь) применительно к программированию означает следующее. Задать представление какого-либо объекта (в данном случае множества) — значит описать в терминах используемой системы программирования структуру данных, используемую для хранения информации о представляемом объекте, и алгоритмы над выбранными структурачи данных, которые реализуют присущие данному объекту операции.
В данной книге предполагается, что в используемой системе программирования доступны такие общеупотребительные структуры данных, как массивы, структуры (или записи) и указатели. Таким образом, применительно к множествам определение представления подразумевает описание способа хранения информации о принадлежности элементов множеству н описание алгоритмов для вычисления объединения, пересечения и других введенных операций. Следует подчеркнуть, что, как правило, один и тот же объект может быть предтавлен многими разными способами, причем нельзя указать способ, который является наилучшим для всех возможных случаев. В одних случаях выгодно использовать одно представление, а в других — другое.
Выбор представления зависит от целого ряда факторов: особенностей представляемого объекта, состава и относительной частоты использования операций в конкретной задаче и т. д. Умение выбрать наиболее подходящее для данного случая представление является основой искусства практического программирования. Хороший программист отличается тем, что он знает много разных способов представления и умело выбирает наиболее подходящий.
,.4. Представление множеств э ЭВМ 1.4.1. Реализация операций над подмножествами заданного универсума У Пусть универсум У вЂ” конечный, и число элементов в нем не превосходит разэядности ЭВМ: [Ц ( п. Элементы универсума нумеруются: У = (иы...,о 1. Подмножество А универсума У представляется кодом (машинным словом или эитовой шкалой) С, в котором: 11, если и; ц А, [[О, если Бч ф А, где С[1] — это г-й разряд кода С.
Код пересечения множеств А и В есть поразрядное логическое произведение кода множества А и кода множества В. Код объединения множеств А и В есть поразрядная логическая сумма кода множества А и кода множества В. Код дополнения множества А есть инверсия кода множества А. В большинстве ЭВМ цля этих операций есть соответствующие машинные команды.
Таким образом', операции над небольшими множествами выполняются весьма эффективно. ЗАМЕЧАНИЕ Если мощность универсума превосходит размер машинного слова, но эе очень велика, то лля представления множеств используются массивы битовых шкал. В этом случае операции над множествами реализуются с помощью циклов по элементам массива. 1.4.2. Генерация всех подмножеств универсума Во многих переборных алгоритмах требуется последовательно рассмотреть все подмножества заданного множества. В большинстве компьютеров целые числа представляются кодами в двоичной системе счисления, причем число 2 — 1 ь представляется кодом, содержащим й единиц.
Таким образом, число О является представлением пустого множества е, число 1 является представлением подмножества, состоящего из первого элемента, и т. д. Следующий тривиальный алгоритм перечисляет все подмножества и-элементного множества. Алгоритм 1А. Алгоритм генерации всех подмножеств а-элементного множества Вход: и > Π— мощность множества Выход: последовательность кодов подмножеств 1 Гог 1 агою О Го 2" — 1 оо у1еЫ 1 еш$1ог ОБОСНОВАНИЕ Алгоритм выдает 2" различных целых чисел, следовательно, 2" различных кодов. С увеличением числа увеличивается количество двоичных разрядов, необходимых для его представления.
Самое большое (из генерируемых) число 2" ' требует для своего представления ровно и разрядов. Таким образом, все подмножества генерируются, причем ровно по одному разу. П Глава 1. Множества и отношения Недостаток этого алгоритма состоит в том, что порядок генерации подмножеств никак не связан с их составом. Например, вслед за подмножеством с кодом 0111 будет перечислено подмножество с кодом 1000. ОТСТУПЛЕНИЕ Во многих переборных задачах требуется рассмотреть все подмножества некоторого множества и найти среди них то, которое удовлетворяет заданному условию. При этом проверка условия часто может быть весьма трудоемкой и зависеть от состава элементов очередного рассматриваемого подмножества.
В частности, если очередное рассматриваемое подмножество незначительно отличается по набору элементов от предыдущего, то иногда можно воспользоваться результатами оценки элементов, которые рассматривались на предыдущем шаге перебора. В таком случае, если перебирать множества в определенном порядке, можно значительно ускорить работу переборного алгоритма. 1.4.3.
Алгоритм построения бинарного кода Грея Данный алгоритм генерирует последовательность всех подмножеств п-элементного множества, причем каждое следующее подмножество получается из предыдущего удалением или добавлением одного элемента, Алгоритм 1.2. Алгоритм построения бинарного кода Грея Вход: н > Π— мощность множества Выход: последовательность кодов подмножеств В В; а1тау [1..н] ог 0..1 ( битовая шкала для представлениа подмножеств ) 1ог 1 6ош 1 го н г)о В[1]: = О ( инициализация ) епб гог у!е!б В ( пустое множество ) гог 1 6ощ 1 Го 2" — 1 до р: = О(1) ( определение элемента, подлежащего добавлению или удалению ) В[р]: = 1 — В[р] ( добавление нли удаление элемента ) узел В ( очередное подмножество ) епб Гог ргос Я(Г) ( количество 2 в разложении Г на множители + 1 ) д:=1;,1:=1 жЫ1е у чегно Йо ,1: = З/2; д: = д + 1 епд чЬйе гесвгп о епб ргос ОБОСНОВАНИЕ Для и = 1 искомая последовательность кодов суть О, 1.
Пусть есть искомая последовательность кодов Вю..., Вза для и = 6. Тогда последовательность кодов ВтО,..., Вз О, Вз 1,..., Вт1 будет искомой последовательностью для и = й+ 1. Действительно, в последовательности В,О,..., Ваап, Вза1,..., В,1 имеется 2ь+г вх Представление мнокеств в ЭВМ кодов, они все различны и соседние различаются ровно в одном разряде по построению.
Именно такое построение и осуществляет данный алгоритм. На нулевом шаге алгоритм выдает правильное подмножество В (пустое). Пусть за первые 2ь — 1 шагов алгоритм выдал последовательность значений В. При этом В[)г+ 1] = В[Й+ 2] = = В[п] = О. На 2~-м шаге разряд В[в+ 1] изменяет свое значение с О на 1, После этого будет повторена последовательность изменений значений В[1..в] в'обратном порядке, поскольку Я(2а + т) = Я(2а — т) для О < т < 2" — 1. П Пример Протокол выполнения алгоритма 2 для и = 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
