МИНИСТЕРСТВО ОБРАЗОВАНИЯ

РОССИЙСКОЙ ФЕДЕРАЦИИ

МОСКОВСКАЯ ГОСУДАРСТВЕННАЯ АКАДЕМИЯ ПРИБОРОСТРОЕНИЯ И ИНФОРМАТИКИ

Кафедра «Персональные компьютеры и сети»

Методические указания

по выполнению лабораторных и практических работ

по курсу

ДИСКРЕТНАЯ МАТЕМАТИКА

Москва

2004

Составители: Похвощева Л. Н.,

к.т.н. Фёдоров В. Н.,

Бунина Л. В.,

к.т.н. Шептунов М. В.

УДК 519.1(075.8)+681.3.06

Методические указания по выполнению лабораторных и практических работ по курсу “Дискретная математика ” / МГАПИ; Сост.: Похвощева Л. Н., Фёдоров В. Н., Бунина Л. В., Шептунов М. В. М., 2004. 40 с.

Рассматриваются основы применения методов дискретной математики в практических задачах. Представлены типовые фрагменты программ на языках C и Pascal, необходимые при решении задач.

Методические указания предназначены для подготовки студентов различных специальностей, изучающих дискретную математику.

Для специальности 2201 эти методические указания могут использоваться в курсе “Дискретная математика” для подготовки и

выполнения лабораторных и практических работ.

Рецензент: к.т.н., профессор Рощин А. В

.ВВЕДЕНИЕ

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

В современной иерархии математических наук дискретная математика является промежуточным звеном между рядом дисциплин естественно-научного и технического профиля.

Задачами курса дискретной математики являются ознакомление и освоение основных моделей и методов формализованного представления: теоретико-множественных, логических, графических. Мощным фундаментом современной дискретной математики являются теория множеств, математическая логика и теория графов.

Дискретная математика была и остаётся одной из наиболее динамичных математических дисциплин. Она изучается почти во всех ВУЗах естественно-научного, технического и экономического профиля.

На сегодняшний день наиболее значимым направлением развития дискретной математики являются информационные технологии. Это объясняется прежде всего необходимостью создания и эксплуатации персональных ЭВМ, компьютерных сетей, систем управления, а также автоматизированных средств обработки информации.

Комплекс лабораторных и практических работ предназначен для практического закрепления материала курса «Дискретная математика». Программой предусматривается выполнение следующих лабораторных и практических работ:

1. Нахождение множеств по операциям.

2. Определение всех подмножеств универсума.

3. Численная проверка комбинаторного принципа включений и исключений.

4. Представление графов в ЭВМ.

5. Внутренняя и внешняя устойчивость множества вершин графа.

6. Операции над графами.

7. Маршруты и циклы в графе.

8. Исследование графа на нахождение эйлерова цикла.

9. Фундаментальные циклы и разрезы графа.

10. Радиус и диаметр графа.

11. Кратчайший маршрут во взвешенном графе.

В данных методических указаниях рассматриваются вопросы так называемой “конечной математики”, т. е. математики, непосредственно не связанной с понятиями бесконечности, предела и непрерывности.

Предлагаемые методические указания к лабораторному практикуму предназначены для специальности 2201 “Вычислительные машины, комплексы, системы и сети” и могут также быть полезными для ряда смежных специальностей.

Лабораторная работа N⁰1

Нахождение множеств по операциям

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

Содержание работы:

1. Разработка программы для выполнения операций над множествами.

2. Разработка и отладка программы для нахождения заданного множества.

Операции над множествами

Теоретико-множественные представления – описание исследуемой системы, процессов средствами теории множеств, т.е. как множества взаимосвязанных и/или взаимодействующих частей – элементов. Связи между элементами задаются через отношения и/или соответствия. Множества, элементы, отношения, соответствия характеризуются определенными свойствами и набором допустимых операций над ними.

Объединение:

АÈВ= {х| хÎА Ú хÎВ};

Пересечение:

АÇВ= {х| хÎА & хÎВ};

Разность:

А\В={х| хÎА & хÏВ};

Симметрическая разность:

АDВ={(АÈВ)\(АÇВ)};

Дополнение:

А={х|хÏА}.

Пример.

Дано: универсум U={1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

А={1, 3, 5, 7};

В={5, 6, 7, 8, 10};

С={1, 2, 7, 9}.

Найти: Множества

С1= А D ВÇС;

С2= АÇВÈС;

С3= АÈВDС2;

______

С4 =А\ВÈС1; C5= C3ÇC4

___

С6= А È В

Пример:

program mnojecvo;

const n=1;

var a,b,c,d,e: set of 1..200; j,x,y:byte;

begin a:=[]; b:=[3,5,8]; d:=[1,3,6]; e:=[1,3,8];

for j:=1 to 5 do

begin

readln(x);

a:=a+[x]

end;

c:=a-b-d-e;

for x:=1 to 200 do

if(x in c)

then

writeln(x);

readln;

end.

Cодержание отчета:

1. Текст программы на C₊₊ либо Visual Basic (допускается в среде

Delphi);

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

исходных данных.

Лабораторная работа №2

Определение всех подмножеств универсума

Цель работы: изучение различных алгоритмов нахождения всех

подмножеств универсума.

Содержание работы:

1. Разработка алгоритма решения задачи о нахождении всех подмножеств множества.

2. Разработка алгоритма построения бинарного кода Грея.

3. Разработка и отладка программы для заданного множества.

Подмножество А универсума U представляется кодом (машинным словом или битовой шкалой) а, в котором:

1, если u_(i) Î A,

а_(i) = 0, если u_(i) ÏA,

Множество, содержащее m элементов, имеет 2^m подмножеств. Так как существует взаимооднозначное соответствие между числами из 0 : 2^m-1 и наборами 0-1 векторов, нужно взять число 0 и его представление 0,...,0, а дальше прибавлять по единице, имитируя это на текущем наборе, до тех пор, пока не получится набор 1,…,1. Переход от набора к номеру и от номера к набору – это соответственно переход от двоичного представления числа к его значению и от значения к двоичному представлению.

Например, множество А={1, 2, 3} содержит такие подмножества:

000 {0}

001 {3}

010 {2}

011 {2,3}

1. {1}

2. {1,3}

1. {1,2}

2. {1,2,3}

Однако, при таком просмотре 0-1 наборов очередное прибавление единицы может вызвать сильное изменение набора (например, 010111 –011000). Иногда желательно, чтобы перебирались наборы, похожие друг на друга; например, в случае 0-1 наборов можно потребовать, чтобы на каждом шаге менялось значение только одной компоненты.

Существующий алгоритм бинарного кода Грея приведен в [2].

Принципиальная схема такого перебора основана на идее рекурсии. Чтобы перебрать все наборы длины m, зафиксируем нулевое значение у m-й компоненты и переберем все наборы длины m-1 для оставшихся компонент. Перебрав их, сменим значение m-й компоненты на 1 (на этом шаге, номер которого 2^m-1 меняется именно эта единственная компонента) и снова переберем наборы длины m-1, но уже в обратном порядке. В таблице приведен перебор для наборов длины 4 , где it – номер итерации, k_it – номер обновляемой компоненты.

х4	x3	x2	x1	it	kit
0	0	0	0	1	1
0	0	0	1	2	2
0	0	1	1	3	1
0	0	1	0	4	3
0	1	1	0	5	1
0	1	1	1	6	2
0	1	0	1	7	1
0	1	0	0	8	4
1	1	0	0	9	1
1	1	0	1	10	2
1	1	1	1	11	1
1	1	1	0	12	3
1	0	1	0	13	1
1	0	1	1	14	2
1	0	0	1	15	1
1	0	0	0	16	-

Этот алгоритм программируется с использованием рекуррентных процедур.

Возможен другой подход. Cледующий алгоритм предлагает такой вычислительный процесс:

1. Создать два набора x и y, каждый из m нулей и единиц. Первоначально x=y = {0,..,0}.

2. На каждой итерации прибавлять 1 к числу, для которого x является двоичным разложением.

3. Фиксировать позицию к, в которой нуль сменяется единицей.