Дискретная математика (998286), страница 6
Текст из файла (страница 6)
1.4.4. Представление множеств упорядоченными списками Если универсум очень велик (или бесконечен), а рассматриваемые подмножества универсума не очень велики, то представление с помощью битовых шкал не является эффективным с точки зрения экономии памяти. В этом случае множества обычно представляются списками элементов. Элемент списка при этом представляется записью с двумя полями: информационным и указателем на следующий элемент, Весь список представляется указателем на первый элемент. е1ещ - гесогд т': шЕо; ( информационное поле ) п: г е1еш ( указатель на следующий элемент ) ецио гесого При таком представлении трудоемкость операции Е составит О(п), а трудоемкость операций С, и, 0 составит О(пт), где п и т — мощности участвующих в операции множеств.
Если элементы в списках упорядочить, например, по возрастанию значения поля т', то трудоемкость всех операций составит О(п). Эффективная реализация операций над множествами, представленными в виде упорядоченных списков, основана на весьма общем алгоритме, известном как алгоритм типа сяияния. Глава К Множества и отношении Алгоритм типа слияния параллельно просматривает два множества, представленных упорядоченными списками, причем на каждом шаге продвижение происходит в том множестве, в котором текущий элемент меньше. 1,4.5.
Проверка включения слиянием Рассмотрим алгоритм типа слияния, который определяет, является ли множе- ство А подмножеством множества В, Алгоритм 1.3. Проверка включения слиянием Вход: проверяемые множества А н В, которые заданы указателями а н 6. Выход: 1, если А с В, в противном случае О. ра: = а; рб: = 6' ттЫ!е ра ~ ш1 бт рЬ ~ ей йо 1Г рай < рбя 11геа тетвгл О 1 элемент множества А отсутствует в множестве В ) е1ве 11 рай > рЬл' баев рб: = рб.и 1 элемент множества А, может быть, присутствует в множестве В ) е1ве ра: = ра.н 1 здесь рад = рб.т', то есть ) рб: = рб.н т элемент множества А точно присутствует в множестве В ) еай !! евй тт1й!е гетега ра = ш! ОБОСНОВАНИЕ На каждом шаге основного цикла возможна одна из трех ситуации: текущий элемент множества А меньше.
больше или равен текущему элементу множества В. В первом случае текущий элемент множества А заведомо меньше, чем текущий и все последующие элементы множества В, а потому он не содержится в множестве В, и можно завершить выполнение алгоритма. Во втором случае происходит продвижение по множеству В в надежде отыскать элемент, совпадающий с текущим элементом множества А. В третьем случае найдены совпадающие элементы, и происходит продвижение сразу в обоих множествах.
По завершении основного цикла возможны два случая; либо ра = пй, либо ра ф пй. Первый случай означает, что для всех элементов множества А удалось найти совпадающие элементы в множестве В. Второй случай означает, что множество В закончилось раньше, то есть не для всех элементов множества А удалось найти совпадающие элементы в множестве В. П 1.4.6.
Вычисление объединения слиянием Рассмотрим алгоритм типа слияния, который вычисляет объединение двух мно- жеств, представленных упорядоченными списками. К4. Представление множеств в ЭВМ Алгоритм 1.4. Вычисление объединения слиянием Вход: объединяемые множества А и В, которые заданы указателями а и Ь. Выход: объединение С = А О В, заданное указателем с. ра:=а;рЬ:=Ь;с:=пй; е:=ш! иЫ!е ра фш! Й рЬ ~пй ао !1 рал < рьл гйеп а: =рал; ра: =ра.п ( добавлению подлежит элемент множества А ) е1ве !1 рал > рЬл Гйеп а': = рЬл'; рЬ: = рЬ.п ( добавлению подлежит элемент множества В ) е)ве й: = рал ( здесь рал = рЬл', н можно взять любой из элементов ) ра: = ра.п; рЬ: = рЬ.п епа й Аррас!с, е, Щ добавление элемента А в конец списка с ) епа' иЫе р: =пй !1 ра фпй гйеп р: = ра ( нужно добавить в результат оставшиеся элементы множества А ) еш! К !! РЬ ~ш1 Спев р: = рЬ ( нужно добавить в результат оставшиеся элементы множества В ) епй !1 и!п1е р фпй Йо Аррепо(с, е, рл) р:=р.п епа тт!и1е ОБОСНОВАНИЕ На каждом и!аге основного цикла возможна одна из трех ситуаций: текущий элемент множества А меньше, больше или равен текущему элементу множества В.
В первом случае в результирующий список добавляется текуший элемент множества А и происходит продвижение в этом множестве, во втором аналогичная операция производится с множеством В, а в третьем случае найдены совпадающие элементы и происходит продвижение сразу в обоих множествах. Таким образом, в результат попадают все элементы обоих множеств, причем совпадающие элементы попадают ровно один раз. По завершении основного цикла один из указателей ра и рЬ (но не оба вместе!) может быть не равен ш). В этом случае остаток соответствующего множества без проверки добавляется в результат.
П Вспомогательная процедура Аррепб(с,е,а) присоединяет элемент а к хвосту е списка с. АлгоРитм 1.5. Процедура Аррепс! — Присоединение элемента в конец списка Вхол: указатель с на первый элемент списка, указатель е на последний элемент списка, добавляемый элемент Ы.
Выход: указатель с на первый элемент списка, указатель е на последний элемент списка. д: = печ(е!еш); дл:= адп:=пй ( новый элемент списка ) Глава 1. Множества и отношения 11 с =ш1 ЬЬеп с:=ч е1зе е.и: =ч епа К ОБОСНОВАНИЕ До первого вызова функции Аррепт( имеем: с = ш1 и е = ш1. После первого вызова указатель с указывает на первый элемент списка а указатель е — на последний элемент (который после первого вызова является тем же самыМ элементом). Если указатели с и е не пусты и указывают на первый и последний элементы правильного списка, то после очередного вызова функции Аррепт1 это свойство сохраняется, поскольку из текста основной программы видно, что, кроме инициализации, все остальные манипуляции с этими указателями выполняются только с помощью функции Аррепт(.
П 1.4.7. Вычисление пересечения слиянием Рассмотрим алгоритм типа слияния, который вычисляет пересечение двух мно- жеств, представленных упорядоченными списками. Алгоритм 1.6. Вычисление пересечения слиянием Вход: пересекаемые множества А н В, заданные указателями а и Ь. Выход: пересечение С = А гт В, заданное указателем с. ра: = а; рЬ: = Ь; с: = пй; е: =пй ттЬ11е ра ~п11 ьт рЬ фпй до К рал ( рЬ.т 1Ьеп ра: = ра.п ( элемент множества А не принадлежит пересечению ) е1зе 1Г рал ) рЬл' 1Ьеп рЬ: =рь.п ( элемент множества В нс принадлежит пересечению ) е1ее ( здесь ра.т = рьл — данный элемент принадлежит пересечению ) Аррепй(с, е,рал);ра: = ра.п; рЬ: = рЬп епд 11 епд ттЬйе ОБОСНОВАНИЕ На каждом шаге основного цикла возможна одна из трех ситуаций: текущий элемент.
множества А меньше, больше или равен текущему элементу множества В. В первом случае текущий элемент множества А не принадлежит пересечению, он пропускается и происходит продвижение в этом множестве, во втором то же самое производится с множеством В. В третьем случае найдены совпадающие элементы, один экземпляр элемента добавляется в результат и происходит продвижение сразу в обоих множествах. Таким образом, з результат попадают все совпадающие элементы обоих множеств, причем ровно один раз.
П ЗЗ 1.5. Отношения 1.5. Отношения Обычное широко используемое понятие «отношения» имеет вполне точное ма. тематическое значение, которое вводится в этом разделе. 1.5.1. Упорядоченные пары Если а и Ь вЂ” объекты, то через (а, Ь) обозначим упорядоченную нару. Равенство упорядоченных пар определяется следующим образом: (а,Ь) = (с,а):=а = сйсЬ= д. Вообще говоря, (а, Ь) ф (Ь, а). ЗАМЕЧАНИЕ Упорядоченные пары можно рассматривать как множества, если определить их так: (а, Ь): =(а, (а, Ь)). Таким образом, понятие упорядоченной пары не выводит рассмотрение за пределы теории множеств, но независимое определение технически удобнее.
1.5.2. Прямое произведение множеств Пусть А и  — два множества. Прямым (декартовым) произведением двух множеств А и В называется множество упорядоченных пар, в котором первый элемент каждой пары принадлежит А, а второй принадлежит В: А х В: = ((а, Ь) ) а е Айс 5 е В) . ЗАМЕЧАНИЕ Точка на плоскости может быть задана упорядоченной парой координат, то есть двумя точками на координатных осях. Таким образом, Еа = и х й. Метод координат ввел в употребление Рене Декарт (1596 — 1650), отсюда и название «декартово произведением Степенью множества А называется его прямое произведение самого на себя. Обо- значение: А":=А х х А. » раз Соответственно, А"; = А, Аз: = А х А и вообще А": = А х А" 1.
ТЕОРЕМА )А х В) = 1А! )В!' доказательство Первый компонент упорядоченной пары можно выбрать (А) способами, второй— )В) способами. Таким образом, всего имеется )АйВ) различных упорядоченных пар, П а4 Глава К Множества и отношения СЛЕДСТВИЕ )А" ~ = ~А!". 1.5.3. Отношения Пусть А и  — два множества. (Бинарньгм) отношением В из множества А в множество В называется подмножество прямого произведения А и В: В с А х В. Для бинарных отношений обычно используется инфинсная форма записи: аВЬ: =(а, Ь) Е В С А х В.
Если А = В, то говорят, что В есть отношение на множестве А. Пример Пусть задан универсум сГ. Тогда Е (принадлежность) — отношение из множества сГ в множество 2", а С (включение) и = (равенство) — отношения на 2~. Хорошо известны отношения =, «, , >, >, ф, определенные на множестве чисел. Пусть В есть отношение на А: В С А х А, а, Ь Е А.
Введем следующие понятия: Универсальное отношение: Введем обобщенное понятие отношения: и-местное (п-арное) отношение В— это множество упорядоченных наборов (норглежвй): В С Аг х ° ° ° х А„= ((ам аз,...,а„) ~ аг Е Агй...йон Е А„). Множества А; не обязательно различны. ОТСТлПЛЕНИЕ Многоместные отношения используются, например, в теории баз данных. Само назввни «реляционная» база данных происходит от слова ге!зг!ов (отношение). Далее рассматриваются только двуместные (бинарные) отношения, при этом ело во «бинарные» опускается. 1.5.4. Композиция отношений Пусть Вг с А х С вЂ” отношение из А в С, а Вз с С х  — отношение из С в 1 Композицией двух отношений Вг и Вз называется отношение В с А х В из А В, определяемое следующим образом: В:=Вг оВз.=((а,Ь) ! а Е АйЬ Е Вйес Е С аВзсйсВзЬ).
Композиция отношений на множестве А является отношением на множестве . Обратное отношение: Дополнение отношения: ТЬждестввннов отношение: В ~:=((а,Ь) ~ (Ь,а) Е В). В: = ((а, Ь) $ (а, Ь) ф В). 1:=((а,а) ) а Е А). (Г: = ((а, Ь) ~ а е А й Ь е А). Ь5. Отношения 1.5.5. Степень отношения Пусть  — отношение на множестве А. Степенью отношения В на множестве А называется его композиция с самим собой. Обозначение: В":=Во ° ° о В, Соответственно, Во:=1, В1:=В, Вз:=Во В и вообще В":='Ни 1 о В. ТЕОРЕМА Если некоп1орал пара (а, 6) принадлежит какой-либо степени отношения В на множестве А мощности и, то эта пара принадлежит и степени В не выше и — 1: В С А ов ~А) = и =ь (У а, Ь е А 3 Ь аВ~Ь =ь 3 Ь < и аВьЬ), Доказательство Существование требуемой степени Ь отношения В обеспечивается следующим построением. тчИе Ь > п Йо со'=а; сь:=6 (а,6) е Вь =ь 3с1,..., сь 1 е А соВс1НсэВ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
