Материал: Методические указания к выполнению лабораторных работ по дисциплине «Дискретная математика» для студентов направления подготовки бакалавров. Собенина О.В., Пак А.А

что множество В закончилось раньше, то есть не для всех элементов множества А удалось найти совпадающие элементы в множестве В.

Вычисление объединения слиянием

Рассмотрим алгоритм типа слияния, который вычисляет объединение двух множеств, представленных упорядоченными списками.

Алгоритм. Вычисление объединения слиянием.

Вход: объединяемые множества А и В, которые заданы указателями а и b.

Выход: объединение С=А В, заданным указателем с. pa:=a; pb:=b; c:=nil; e:=nil;

while pa nil & pb nil do if pa.i<pb.i then

d:=pa.i; pa:=pa.n {добавлению подлежит элемент множества

А}

else if pa.i>pb.i then

d:=pb.i; pb:=pb.n {добавлению подлежит элемент множества B}

else

d:=pa.i {здесь pa.i=pb.i, и можно взять любой из элемен-

тов}

pa:=pa.n; pb:=pb.n; end if

Append(c,e,d) {добавление элемента d в конец списка с} end while

p:=nil

if pa nil then

p:=pa {нужно добавить в результат оставшиеся элементы множества А}

end if

if pb nil then

p:=pb {нужно добавить в результат оставшиеся элементы множества B}

9

end if

while p nil do

Append(c,e,d,i)

p:=p.n end while

Обоснование. На каждом шаге основного цикла возможна одна из трёх ситуаций: текущий элемент множества А меньше, больше или равен текущему элементу множества В. В первом случае в результирующий список добавляется текущий элемент множества А и происходит продвижение в этом множестве, во втором аналогичная операция производится с множеством В, а в третьем случае найдены совпадающие элементы и происходит продвижение сразу в обоих множествах. Таким образом, в результат попадают все элементы обоих множеств, причем совпадающие элементы попадают ровно один раз. По завершении основного цикла один из указателей pa и pb (но не оба вместе!) может быть не равен nil. В этом случае остаток соответствующего множества без проверки добавляется в результат.

Вычисление пересечения слиянием

Рассмотрим алгоритм типа слияния, который вычисляет пересечение двух множеств, представленных упорядоченными списками.

Алгоритм. Вычисление пересечения слиянием.

Вход: пересекаемые множества А и В, которые заданы указателями а и b.

Выход: пересечение С=А В, заданным указателем с.

pa:=a; pb:=b; c:=nil; e:=nil; while pa nil & pb nil do if pa.i<pb.i then

pa:=pa.n {элементы множества А не принадлежат пересечению}

10

else if pa.i>pb.i then

pb:=pb.n {элементы множества B не принадлежат пересечению}

else

{здесь pa.i=pb.i – данный элемент принадлежит пересечению}

Append(c,e,pa.i); pa:=pa.n; pb:=pb.n; end if

end while

Обоснование. На каждом шаге основного цикла возможна одна из трёх ситуаций: текущий элемент множества А меньше, больше или равен текущему элементу множества В. В первом случае текущий элемент множества А не принадлежит пересечению, он пропускается и происходит продвижение в этом множестве, во втором то же самое производится с множеством В. В третьем случае найдены совпадающие элементы, один экземпляр элемента добавляется в результат и происходит продвижение сразу в обоих множествах. Таким образом, в результат попадают все совпадающие элементы обоих множеств, причем ровно один раз.

Вопросы для самопроверки

1.Что такое множество?

2.Какие спецификации множеств знаете?

3.Какими способами можно задать множество?

4.Что такое семейство множества?

5.Как определяется операция симметрической разности двух множеств ?

6.Какими свойствами обладают операции над множества?

7.Что такое декартово произведение множеств?

8.Какие операции над множествами знаете?

9.Как определяются операции над множествами.

10.Дать определение универсального множества.

11.Дать определение собственного подмножества.

12.Дать определение конечного множества.

11

ПРАКТИЧЕСКАЯ ЧАСТЬ Задания

Написать программу, реализующую следующую процедуру:

1.Даны два множества, заданные перечислением своих элементов. Получить симметрическую разность этих элементов.

2.Даны два множества, заданные перечислением своих элементов. Определить декартовое произведение этих множеств.

3.Получить семейство множества, заданного, перечислением своих элементов.

4.Выяснить является ли данное множество подмножеством множества.

5.Выяснить является ли множество собственным подмножеством.

6. Для произвольных множеств А, В и С определить

(A\ B) (A\ C), (A B) C .

A B C , (A B) \ C.

9.Вычисление пересечения множеств слиянием.

10.Вычисление объединения множеств слиянием.

11.Проверка включения слиянием.

12.Генерация всех подмножеств универсума.

Порядок выполнения работы

1.Получить задание у преподавателя.

2.Разработать алгоритм решения задачи.

3.Реализовать полученный алгоритм.

4.Проанализировать результаты работы алгоритма.

5.Оформить отчет по лабораторной работе.

12

Содержание отчета

1.Номер и тема лабораторной работы.

2.Цель выполнения работы.

3.Схема алгоритма.

4.Исходные данные и результаты вычислений.

5.Анализ полученных результатов и вывод по работе.

ЛАБОРАТОРНАЯ РАБОТА № 2

ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМИЧЕСКИХ ПРОЦЕДУР ТЕОРИИ ОТНОШЕНИЙ

Цель работы: изучение основных понятий и определений теории отношений, свойств отношений, операций над ними и специальных типов бинарных отношений. Получение практических навыков программной реализации алгоритмических процедур теории отношений.

Программное средство: среда разработки приложений MS Visual Studio, языки программирования С#, C++.

Теоретические сведения

В множестве X n-местным или n-арным отношением назы-

ется носителем отношения. Будем говорить, что упорядоченные элементы x1,x2 ,....,xn находятся в отношении R, если x1,x2 ,....,xn R. Одноместное отношение называется унарньм,

или свойством, и соответствует подмножеству множества X. Особую роль в приложениях играют бинарные отношения R Х Х. Каждому бинарному отношению можно поставить в соответствие матрицу бинарного отношения, которую также обозначают через R= rij n n (n ) и элементы которой rij оп-

13