Новиков Ф.А. Дискретная математика для программистов (860615), страница 8
Текст из файла (страница 8)
Рассмотрим для примера первое равенство:A U А — А. Возьмем произвольный элемент х, принадлежащий левой части равенства, х е Al)A. По определению операции объединения И имеем х е А V х Е А.В любом случае х е А. Взяв произвольный элемент из множества в левой частиравенства, обнаружим, что он принадлежит множеству в правой части. Отсюдапо определению включения множеств получаем, что A U А с А. Пусть теперьх Е А. Тогда, очевидно, верно х Е А V х Е А. Отсюда по определению операцииобъединения имеем х Е A U А. Таким образом, А с A U А.
Следовательно, поопределению равенства множеств, A U А = А. Это рассуждение можно записатькороче:х е А и А <=>• х е A v х е Ах е А.Аналогичные рассуждения нетрудно провести и для остальных равенств.1Огастес Mopj-ап ( 1 8 0 6 - 1 8 7 1 ) .38Глава 1. Множества и отношения1.3.
Представление множеств в программахТермин «представление» применительно к программированию означает следующее. Представить в программе какой-либо объект (в данном случае множество) —это значит описать в терминах системы программирования структуру данных, используемую для хранения информации о представляемом объекте, и алгоритмынад выбранными структурами данных, которые реализуют присущие данномуобъекту операции. Таким образом, применительно к множествам определениепредставления подразумевает описание способа хранения информации о принадлежности элементов множеству и описание алгоритмов для вычисления объединения, пересечения и других введённых операций. Следует подчеркнуть, что,как правило, один и тот же объект может быть представлен многими разнымиспособами, причём нельзя указать способ, который является наилучшим для всехвозможных случаев.
В одних случаях выгодно использовать одно представление,а в других — другое. Выбор представления зависит от целого ряда факторов:особенностей представляемого объекта, состава и относительной частоты использования операций в конкретной задаче и т. д. Умение выбрать наилучшеедля данного случая представление является основой искусства практическогопрограммирования. Хороший программист отличается тем, что он знает многоразных способов представления и умело выбирает наиболее подходящий.1.3.1. Битовые шкалыПусть задан конечный универсум U и число элементов в нем не превосходитразрядности компьютера, \U\ ^ п.
Элементы универсума нумеруются:U = {ui,...,ип).Подмножество А универсума U представляется кодом (машинным словом илибитовой шкалой) С : array [l..n] of 0..1, в котором:_мГ1,С\г\ = <10,если щ е А,„если щ f А.ЗАМЕЧАНИЕУказанное представление можно описать короче, задав инвариант (условие, которомуудовлетворяют нее элементы): Vг € 1..п (С[г] = щ е А). В дальнейшем предпочтениеотдаётся более короткой форме записи описания представлений.Код пересечения множеств Аи В есть поразрядное логическое произведение кода множества А и кода множества В.
Код объединения множеств А и В естьпоразрядная логическая сумма кода множества А и кода множества В. Код дополнения множества А есть инверсия кода множества А. В большинстве компьютеров для этих операций есть соответствующие машинные команды. Таким образом, операции над небольшими множествами выполняются весьма эффективно.В некоторых языках программирования, например в Паскале, это представлениемножеств непосредственно включено в состав типов данных языка.1.3. Представление множеств в программах39ЗАМЕЧАНИЕЕсли мощность универсума превосходит размер машинного слова, но не очень велика,то для представления множеств используются массивы битовых шкал.
В этом случаеоперации над множествами реализуются с помощью циклов по элементам массива.Эту же идею можно использовать для представления мультимножеств. Если X == [х" 1 ,...,— мультимножество над над множеством X = {х\,... ,хп}, томассив А : array [l..n] of integer, где Уг е 1 ..п (А[г\ — а*), является представлением мультимножества X.ЗАМЕЧАНИЕПредставление индикатора совпадает с представлением его состава. Полезно сравнить этонаблюдение с первым замечанием в подразделе 1.2.1.1.3.2. Генерация всех подмножеств универсумаВо многих переборных алгоритмах требуется последовательно рассмотреть всеподмножества заданного множества { a i , . .
. ,Ofc}. В большинстве компьютеровцелые числа представляются кодами в двоичной системе счисления, причём число 2к - 1 представляется кодом, содержащим к единиц, а все числа, меньшие2к — 1, представляются кодами, имеющими не более к ненулевых разрядов. Таким образом, код числа 0 является представлением пустого множества 0, кодчисла 1 является представлением подмножества, состоящего из первого элемента, и т. д., код числа 2к — 1 является представлением всего множества { a i , . . . ,Это наблюдение позволяет сформулировать следующий тривиальный алгоритм,который перечисляет все подмножества п-элемептиого множества.Алгоритм 1.1 Генерация всех подмножеств n-элемептиого множестваВход: п ^ 0 — мощность множества.Выход: последовательность кодов подмножеств i.for г from 0 to 2 n - 1 doyield i {код очередного подмножества}end forАлгоритм выдает 2П различных целых чисел, следовательно, 2Празличных кодов от 00...О до 11...1.
Таким образом, все подмножества генерируются, причём ровно по одному разу.•ОБОСНОВАНИЕНедостаток этого алгоритма состоит в том, что порядок генерации подмножествникак не связан с их составом. Например, вслед за подмножеством с кодом 0111(состоящим из трёх элементов) будет перечислено подмножество с кодом 1000(состоящее из одного элемента).40Глава 1. Множества и отношенияОТСТУПЛЕНИЕВо многих переборных задачах требуется рассмотреть все подмножества некоторого множества и найти среди них то, которое удовлетворяет заданному условию. При этом проверка условия часто может быть весьма трудоёмкой и зависеть от состава элементовочередного рассматриваемого подмножества. В частности, если очередное рассматриваемое подмножество незначительно отличается по составу элементов от предыдущего, тоиногда можно воспользоваться результатами оценки элементов, которые рассматривались па предыдущем шаге перебора.
В таком случае, если перебирать подмножества вподходящем порядке, можно значительно ускорить работу переборного алгоритма.1.3.3. Алгоритм построения бинарного кода ГреяАлгоритм 1.2 генерирует последовательность всех подмножеств п-элементногомножества, причём каждое следующее подмножество получается из предыдущегоудалением или добавлением в точности одного элемента.Алгоритм 1.2 Построение бинарного кода ГреяВход: п ^ О — мощность множества.Выход: последовательность кодов подмножеств В.В : array [l..n] of 0..1 { битовая шкала для представления подмножеств }for г from 1 to п doВ [г]: = 0 { инициализация }end foryield В { пустое множество }for г from 1 to 2Tl - 1 dop: = Q(i) { определение номера элемента, подлежащего добавлению илиудалению }В\р]: = 1 - В\р] { добавление или удаление элемента }yield В { очередное подмножество }end forФункция Q, с помощью которой определяется номер разряда, подлежащего изменению, возвращает количество нулей на конце двоичной записи числа г, увеличенное па 1.Алгоритм 1.3 Функция Q определения номера изменяемого разрядаВход: г — номер подмножества.Выход: номер изменяемого разряда.q: = l;j: = iwhile j чётно doj:=j/2;q:=q+ lend whilereturn q1.3.
Представление множеств в программах41Д Л Я п = 1 искомая последовательность кодов есть 0 , 1 . Пусть известна искомая последовательность кодов B i , . . . , В2к для п = к. Тогда последовательность кодов BiO,..., В2к0, B2kl,...,В\1 будет искомой последовательностьюдля п = к + 1. Действительно, в последовательности Вi0,..., В2к 0, В2к 1 , . . . , ВХ1имеется 2к+1 кодов, они все различны и соседние различаются ровно в одномразряде по построению. Именно такое построение и осуществляет данный алгоритм.
На нулевом шаге алгоритм выдаёт правильное подмножество В (пустое).Пусть за первые 2к - 1 шагов алгоритм выдал последовательность значений В.При этом В[к + 1] = В[к + 2] = • • • = В[п\ = 0. На 2к-м шаге разряд В [к + 1] изменяет своё значение с 0 на 1. После этого будет повторена последовательностьизменений значений В[\..к] в обратном порядке, поскольку Q(2k+m) = Q(2k-m)для 0 ^ т ^ 2к — 1 (упражнение 1.3).•ОБОСНОВАНИЕПримерг1234567Протокол выполнения алгоритма 1.2 для п = 3.V121312100001111В00111100011001101.3.4.
Представление множеств упорядоченнымиспискамиЕсли универсум очень велик (или бесконечен), а рассматриваемые подмножествауниверсума не очень велики, то представление с помощью битовых шкал .не является эффективным с точки зрения экономии памяти. В этом случае множестваобычно представляются списками элементов. Элемент списка при этом представляется записью с двумя полями: информационным и указателем на следующийэлемент. Весь список задаётся указателем на первый элемент,elem = recordi: info; { информационное поле; тип info считается определённым}п: Т elem { указатель на следующий элемент }end recordПри таком представлении трудоёмкость операции е составит 0(п), а трудоёмкость операций С, П, U составит 0(пт), где пит— мощности участвующихв операции множеств.42Глава 1. Множества и отношенияЗАМЕЧАНИЕИспользуемый здесь и далее символ О в выражениях вида Дп) = 0(д(п)) читается«О большое» и означает, что функция / асимптотически ограничена по сравнению с д(ещё говорят, что / «имеет тот же порядок», что и д):f(n) = 0(g(n))= f 3 n o , c > 0 (Vn > по (Дп) ^сд(п))).Если элементы в списках упорядочить, например, по возрастанию значения поля г, то трудоёмкость всех операций составит 0(п).
Эффективная реализацияопераций над множествами, представленными в виде упорядоченных списков,основана па весьма общем алгоритме, известном как алгоритм слияния. Алгоритмслияния параллельно просматривает два множества, представленных упорядоченными списками, причём на каждом шаге продвижение происходит в томмножестве, в котором текущий элемент меньше.1.3.5. Проверка включения слияниемРассмотрим алгоритм слияния, который определяет, является ли множество Аподмножеством множества В.Алгоритм 1.4 Проверка включения слияниемВход: проверяемые множества А и В, которые заданы указателями а и Ь.Выход: true, если А с В, в противном случае false.pa: = a\pb: = b { инициализация }while pa ф nil к рЬф nil doif pa л < pb.i thenreturn false { элемент множества А отсутствует в множестве В }else if pa л > pb.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
