ПРИДНЕСТРОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

им. Т. Г. ШЕВЧЕНКО

Рыбницкий филиал

Кафедра физики, математики и информатики

Дискретная математика

Лабораторный практикум

Рыбница, 2011

УДК 512.075

ББК 22.143

М 33

Составители

С.И. Борсуковский, ст. преп. каф. ФМИ Рыбницкого филиала ПГУ им. Т.Г.Шевченко

Н.В. Чернега, преп. каф. ФМИ Рыбницкого филиала ПГУ им. Т.Г.Шевченко

Рецензенты:

А.Б. Глазов, зав. каф. ФМИ Рыбницкого филиала ПГУ им. Т.Г.Шевченко

Д.Ю. Паустовский, ст. преп. каф. СЭД Рыбницкого филиала ПГУ им. Т.Г.Шевченко

Дискретная математика.

Лабораторный практикум./ Сост. С.И. Борсуковский, Н.В. Чернега – Рыбница, 2011. – 83 с.

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

УДК 512.075

ББК 22.143

Рекомендовано к изданию Научно-методическим советом ПГУ им. Т.Г. Шевченко

© Составители С.И. Борсуковский, Н.В.Чернега, 2011

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ...…………………………………………...…………………………5

ЛАБОРАТОРНАЯ РАБОТА №1 5

1. Теоретический раздел 5

2. Примеры решения задач с использованием множеств 10

3. Контрольные вопросы 11

4. Задания для самостоятельного решения 12

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

1. Теоретический раздел 17

2. Примеры решения задач 19

3. Контрольные вопросы 20

4. Задания для самостоятельного решения 21

ЛАБОРАТОРНАЯ РАБОТА №3 24

1. Теоретический раздел 24

2. Примеры решения задач 27

3. Контрольные вопросы 29

4. Задания для самостоятельного решения 29

ЛАБОРАТОРНАЯ РАБОТА №4 32

1. Теоретический раздел 32

2. Описание алгоритма фронта волны 35

3. Контрольные вопросы 38

4. Задания для самостоятельного решения 38

ЛАБОРАТОРНАЯ РАБОТА №5 43

1. Теоретический раздел 43

2. Описание алгоритма построения минимального остовного дерева 46

3. Контрольные вопросы 49

4. Задания для самостоятельного решения 49

ЛАБОРАТОРНАЯ РАБОТА №6 54

1. Теоретический раздел 54

2. Описание алгоритмов нахождения кратчайшего пути 55

2.1. Алгоритм Дейкстры нахождения минимального пути 55

2.2. Алгоритм нахождения минимального пути Форда-Беллмана 59

3. Контрольные вопросы 65

4. Задания для самостоятельного решения 65

ЛАБОРАТОРНАЯ РАБОТА №7 69

1. Теоретический раздел 69

2. Описание алгоритма нахождения полного потока 71

3. Контрольные вопросы 74

4. Задания для самостоятельного решения 74

ЛАБОРАТОРНАЯ РАБОТА №8 78

1. Теоретический раздел 78

2. Описание алгоритма нахождения максимального потока 79

3. Контрольные вопросы 82

4. Задания для самостоятельного решения 82

ЛИТЕРАТУРА 86