- •Дискретная математика
- •Введение
- •Лабораторная работа №1
- •1. Теоретический раздел
- •2. Примеры решения задач с использованием множеств
- •3. Контрольные вопросы
- •4. Задания для самостоятельного решения
- •Лабораторная работа №2
- •1. Теоретический раздел
- •2. Примеры решения задач
- •3. Контрольные вопросы
- •4. Задания для самостоятельного решения
- •Лабораторная работа №3
- •1. Теоретический раздел
- •2. Примеры решения задач
- •3. Контрольные вопросы
- •4. Задания для самостоятельного решения
- •Лабораторная работа №4
- •1. Теоретический раздел
- •2. Описание алгоритма фронта волны
- •3. Контрольные вопросы
- •4. Задания для самостоятельного решения
- •Лабораторная работа №5
- •1. Теоретический раздел
- •2. Описание алгоритма построения минимального остовного дерева
- •3. Контрольные вопросы
- •4. Задания для самостоятельного решения
- •Лабораторная работа №6
- •1. Теоретический раздел
- •2. Описание алгоритмов нахождения кратчайшего пути
- •2.1. Алгоритм Дейкстры нахождения минимального пути
- •2.2. Алгоритм нахождения минимального пути Форда-Беллмана
- •3. Контрольные вопросы
- •4. Задания для самостоятельного решения
- •Лабораторная работа №7
- •1. Теоретический раздел
- •2. Описание алгоритма нахождения полного потока
- •3. Контрольные вопросы
- •4. Задания для самостоятельного решения
- •Лабораторная работа №8
- •1. Теоретический раздел
- •2. Описание алгоритма нахождения максимального потока
- •3. Контрольные вопросы
- •4. Задания для самостоятельного решения
- •Литература
- •Дискретная математика
ПРИДНЕСТРОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
им. Т. Г. ШЕВЧЕНКО
Рыбницкий филиал
Кафедра физики, математики и информатики
Дискретная математика
Лабораторный практикум
Рыбница, 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