- •Передмова
- •Лабораторна робота № 1 Множини. Генерація елементів множини та виконання операцій над множинами
- •1. Теоретичні відомості.
- •2. Завдання для самостійної роботи.
- •Варіанти завдань
- •Контрольні питання
- •Лабораторна робота № 2 Мінімізація зображення множин
- •1. Теоретичні відомості.
- •2. Завдання до самостійної роботи.
- •Контрольні питання
- •Лабораторна робота № 3 Знаходження гамільтонового циклу графа
- •1. Теоретичні відомості.
- •2. Завдання до самостійної роботи.
- •Контрольні питання
- •Лабораторна робота № 4 Побудова мінімального остовного дерева
- •Теоретичні відомості.
- •«Жадібний» алгоритм побудови мінімального остовного дерева
- •2. Завдання до самостійної роботи.
- •Контрольні питання
- •Лабораторна робота № 5 Знаходження максимального потоку транспортної мережі
- •Теоретичні відомості.
- •2. Завдання до самостійної роботи.
- •Контрольні питання
- •Лабораторна робота № 6 Визначення найкоротшого шляху в графі
- •Теоретичні відомості.
- •2. Завдання до самостійної роботи.
- •Контрольні питання
- •Лабораторна робота №7 Використання графів в мережі планування.
- •1. Теоретичні відомості.
- •Завдання до самостійної роботи.
- •Контрольні питання
- •Література
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
ЧЕРКАСЬКИЙ ДЕРЖАВНИЙ ТЕХНОЛОГІЧНИЙ УНІВЕРСИТЕТ
МЕТОДИЧНІ ВКАЗІВКИ
ДО ВИКОНАННЯ ЛАБОРАТОРНИХ РОБІТ
З ДИСЦИПЛІН
«Дискретна математика», «Основи дискретної математики», «Комп’ютерна дискретна математика»
для студентів спеціальностей технічних спеціальностей
Черкаси ЧДТУ 2010
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
ЧЕРКАСЬКИЙ ДЕРЖАВНИЙ ТЕХНОЛОГІЧНИЙ УНІВЕРСИТЕТ
МЕТОДИЧНІ ВКАЗІВКИ
ДО ВИКОНАННЯ ЛАБОРАТОРНИХ РОБІТ
З ДИСЦИПЛІНИ
«Дискретна математика», «Основи дискретної математики», «Комп’ютерна дискретна математика»
для студентів спеціальностей технічних спеціальностей
Затверджено на засіданні кафедри прикладної математики
протокол № 7 від 25.07.10
та Методичною радою ЧДТУ
протокол №___ від _______
Черкаси ЧДТУ 2010
Укладачі: Палагіна О.А., к.т.н., доцент,
Мірошкіна І.В., к.т.н., доцент,
Дербенцев Д.О., к.ф.-м.н., доцент
Рецензент: Несторенко А.М., к.п.н., доцент
Відповідальний редактор Щерба В.О.
Відповідальний за випуск Щерба А.І., к.ф.-м.н., доцент
Методичні вказівки до виконання лабораторних робіт з дисциплін «Дискретна математика», «Основи дискретної математики», «Комп’ютерна дискретна математика» для студентів спеціальностей технічних спеціальностей /Укл. Палагіна О.А., Мірошкіна І.В., Дербенцев Д.О., - Черкаси, ЧДТУ, 2010, - 49 с.
Видання містить теоретичні відомості та методичні вказівки до виконання лабораторних робіт з курсу дискретної математики.
Для студентів технічних спеціальностей.
ЗМІСТ
Передмова………………………………………………………………………... 5
1. Лабораторна робота № 1. Множини. Виконання операцій над
множинами………………………………………………………………..…… 6
-
Лабораторна робота № 2. Мінімізація зображення множин………….…… 10
3. Лабораторна робота № 3. Знаходження гамільтонового циклу графа…….. 16
4. Лабораторна робота № 4. Побудова мінімального остовного дерева…….. 20
5. Лабораторна робота № 5. Знаходження максимального потоку
транспортної мережі………………………………………………………….. 26
6. Лабораторна робота № 6. Визначення найкоротшого шляху в
графі …………………………………………………………………… ......... 37
-
Лабораторна робота №7. Використання графів в
мережі планування……………………………………………………………. 43
Література………………………………………………………………………… 49
Передмова
Розвиток сучасних об’єктів нової техніки неможливий без розробки інструментальних наукових і інженерних засобів, основою яких є різні розділи математики.
Дискретна математика відноситься до основних розділів математики і є базовою наукою багатьох прикладних наук: теорії логіки, математичних основ представлення знань, теорії алгоритмів, прикладної теорії цифрових автоматів і ін.
Запропоновані методичні вказівки містять роботи, які сприяють засвоєнню практичних навиків застосування дискретної математики в інженерній практиці, дають можливість придбання навиків перекладання формалізованої мови математики на одну з програмних інженерних мов.
Кожна лабораторна робота є логічним продовженням послідуючої роботи, що визначає їх порядок виконання в тій послідовності, яка запропонована в методичних вказівках
Лабораторні роботи виконуються в програмному пакеті, запропонований викладачем.
Лабораторна робота № 1 Множини. Генерація елементів множини та виконання операцій над множинами
Мета роботи: Засвоїти на практичних прикладах поняття множини, операції з множинами.
1. Теоретичні відомості.
Теорія множин базується на шести аксіомах:
-
Аксіома існування.
Існує зокрема одна множина, при цьому в загальному випадку ця множина може бути пустою.
-
Аксіома еквівалентності.
Якщо множини А і В складені з одних і тих самих елементів, то вони співпадають (еквівалентні): А=В.
-
Аксіома об’єднання.
Для не еквівалентних множин А і В (АВ) існує множина С, яка не еквівалентна множинам А і В (СА, СВ), елементами якої є всі елементи множин А і В та в якій не міститься ні яких інших елементів. Множина С називається об‘єднанням множин А і В: С=АВ.
-
Аксіома різниці.
Для деяких множин А і В існує множина С, елементами якої є ті і тільки ті елементи множини А, які не є елементами множини В. Множина С називається різницею множин А і В: С=А\В.
-
Аксіома існування пустої множини.
Існує така множина , якій не належить жодний елемент.
-
Аксіома степені.
Для кожної непустої множини А існує родина множин В(А), елементами якої є всі підмножини Аі множини А, Аі А.
На базі цих шести аксіом визначаються операції і поняття теорії множин. Використовуючи аксіоми об’єднання і різниці, визначимо три операції над множинами.
-
Перетин множин.
Перетином множин А і В називається множина С, яка складається з елементів, котрі належать одночасно і множині А, і множині В:
С=АВ=А\(А\В).
-
Доповнення множини.
Доповненням множини А є множина, яка доповнює її ло універсальної множини Х:
=Х\А.
-
Симетрична різниця.
Симетричною різницею множин А і В називається множина С, яка складена з об’єднання різниць множин А і В:
С=АВ=(А\В)(В\А).
Основні властивості операцій над множинами.
-
Закон комутативності.
,
.
-
Закон асоціативності.
(С)()С,
(С)()С.
-
Закон дистрибутивності.
(С)()(АС),
(С)()(АС).
-
Закони дій з універсальною Х і пустою множинами.
,
,
,
,
А=,
А=Х.
-
Закон індемпотентності.
А,
А.
-
Закон поглинання.
(АВ)А,
(АВ)А.
-
Закони де Моргана.
,
.
-
Закон подвійного доповнення.
.
-
А\В=А.