English
УкраїнськаДискретна математика : практикум (Збірник задач з дискретної математики)
Навчальний посібник містить матеріал для вивчення основних теоретичних засад, функціональних можливостей та практичного застосування дискретної математики, основи математичної логіки і теорії множин, елементи комбінаторного аналізу, основи теорії відношень, основи теорії графів та дерев, основи теорії кодування, булеві функції, мови, граматики та автомати, основи теорії алгоритмів, основи теорії кодування. Посібник призначений для здобуття студентами практичних навичок застосування класичних алгоритмів дискретної математики та сучасних алгоритмів штучного інтелекту, що використовуються при побудові комп’ютерних програм. Теоретичний та практичний матеріал викладено у доступній формі. Викладення матеріалу супроводжується значною кількістю прикладів, що полегшує його сприйняття та засвоєння. Навчальний посібник призначається для студентів, що навчаються за спеціальностями 122 «Комп’ютерні науки», 124 «Системний аналіз», 126 «Інформаційні системи та технології» та споріднених спеціальностей, які пов’язані з інформатикою та інформаційними технологіями. В результаті освоєння матеріалу студент буде вміти застосовувати відомі методи та алгоритми дискретної математики для дослідження предметної області та побудови математичного опису прикладних проблем. Посібник може бути використаний аспірантами як підґрунтя для наукових досліджень та викладачами як дидактичний матеріал, а також для самостійного вивчення. Книга призначена для спеціалістів із проектування, розроблення та впровадження інтелектуальних систем опрацювання інформаційних ресурсів, науковців у галузі глобальних інформаційних системи, систем штучного інтелекту, Інтернет-технологій, фахівців з електронної комерції, Інтернет-маркетингу та Інтернет-реклами, менеджерів комплексних Web-проектів, а також для здобувачів 3-ого (освітньо-наукового) рівня вищої освіти в галузі знань 12 «Інформаційні технології».
Вступ ........................................................................................................................................ 8
Розділ 1. Множини та операції над ними .......................................................................... 15
1.1. Множина. Кортеж. Декартів добуток .......................................................................... 15
1.2. Операції над множинами .............................................................................................. 18
1.3. Взаємно однозначна відповідність .............................................................................. 21
1.4. Комп’ютерне подання множин .................................................................................... 21
1.5. Еквівалентність та потужність множин ...................................................................... 30
1.6. Тестові завдання для самоконтролю ........................................................................... 35
1.7. Ключ до тестових завдань ............................................................................................ 37
1.8. Індивідуальні завдання для виконання лабораторної роботи ................................... 37
1.9. Комп’ютерний проект ................................................................................................... 39
1.10. Додаткові завдання для самостійної роботи ............................................................ 39
1.11. Контрольні запитання ................................................................................................. 42
Розділ 2. Логіка висловлювань та логіка першого ступеня ............................................. 43
2.1. Логіка висловлювань та логіка першого ступеня ...................................................... 43
2.2. Закони логіки висловлень ............................................................................................. 48
2.3. Загальнозначущість та заперечуваність у логіці висловлень ................................... 49
2.4. Нормальні форми логіки висловлювань ..................................................................... 50
2.5. Логіка першого ступеня ................................................................................................ 52
2.6. Закони логіки предикатів ............................................................................................. 58
2.7. Випереджена нормальна форма логіки предикатів ................................................... 60
2.8. Логічне виведення у логіці висловлювань ................................................................. 61
2.9. Правила виведення в логіці висловлювань................................................................. 63
2.10. Метод резолюцій ......................................................................................................... 65
2.11. Алгоритми методу резолюцій доведення теорем у штучному інтелекті .............. 68
2.11.1. Правила виведення у численні предикатів ............................................................ 69
2.11.2. Підстановка та уніфікація. Найзагальніший уніфікатор ...................................... 71
2.11.3. Алгоритм уніфікації ................................................................................................. 73
2.11.4. Сколемівська нормальна форма.............................................................................. 75
2.11.5. Метод резолюцій у численні предикатів ............................................................... 77
2.11.6. Хорнівські диз’юнкти та метод SLD-резолюцій ................................................... 85
2.11.7. Алгоритм SLD-резолюції ........................................................................................ 87
2.11.8. Принцип логічного програмування ........................................................................ 88
2.11.9. Інтерпретатор логічної програми ........................................................................... 90
2.12. Тестові завдання для самоконтролю ......................................................................... 94
2.13. Ключ до тестових завдань .......................................................................................... 95
2.14. Індивідуальні завдання для виконання лабораторної роботи ................................. 96
2.15. Комп’ютерний проект ............................................................................................... 103
2.16. Додаткові завдання для виконання лабораторної роботи ..................................... 103
2.17. Контрольні запитання ............................................................................................... 129
Розділ 3. Відношення ......................................................................................................... 131
3.1. Відношення та їх властивості .................................................................................... 131
3.2. Відношення еквівалентності ...................................................................................... 135
3
3.3. Відношення часткового порядку ............................................................................... 136
3.4. Відношення толерантності ......................................................................................... 137
3.5. Топологічне сортування ............................................................................................. 140
3.6. Операції над відношеннями ....................................................................................... 142
3.7. Замикання відношень .................................................................................................. 143
3.8. Алгоритм Уоршалла для побудови транзитивного замикання .............................. 144
3.9. База даних і відношення ............................................................................................. 146
3.10. Бінарні відношення та їх особливості ..................................................................... 149
3.11. Основні властивості та типи бінарних відношень ................................................. 155
3.12. Агрегація відношень. Поняття фактор-відношення .............................................. 164
3.13. Елементи теорії впорядкованих множин ................................................................ 167
3.14. Подання переваг ОПР за допомогою бінарних відношень ................................... 171
3.15. Неметризовані бінарні відношення ......................................................................... 178
3.16. Метризовані бінарні відношення ............................................................................. 183
3.17. Тестові завдання для самоконтролю ....................................................................... 186
3.18. Ключ до тестових завдань ........................................................................................ 188
3.19. Індивідуальні завдання для виконання лабораторної роботи ............................... 188
3.20. Комп’ютерний проект ............................................................................................... 192
3.21. Додаткові завдання для виконання лабораторної роботи ..................................... 197
3.22. Контрольні запитання ............................................................................................... 202
Розділ 4. Булеві функції ..................................................................................................... 205
4.1. Означення булевої функції ......................................................................................... 205
4.2. Диз’юнктивна нормальна форма (ДНФ) ................................................................... 209
4.3. Кон’юнктивна нормальна форма (КНФ) .................................................................. 209
4.4. Методи побудови скороченої ДНФ ........................................................................... 211
4.5. Алгоритми Куайна та Девіса-Патнема доведення теорем у штучному інтелекті 213
4.6. Логічні методи подання функцій та механізмів вибору .......................................... 216
4.7. Логічна форма функцій вибору ................................................................................. 220
4.8. Класи функцій вибору та взаємозв’язки між ними .................................................. 224
4.9. Механізм вибору ......................................................................................................... 228
4.10. Тестові завдання для самоконтролю ....................................................................... 241
4.11. Ключ до тестових завдань ........................................................................................ 242
4.12. Індивідуальні завдання для виконання лабораторної роботи ............................... 242
4.13. Комп’ютерний проект ............................................................................................... 244
4.14. Додаткові завдання для самостійної роботи .......................................................... 244
4.15. Контрольні запитання ............................................................................................... 246
Розділ 5. Елементи комбінаторного аналізу .................................................................... 248
5.1. Основні правила комбінаторного аналізу. Поняття вибірки. Розміщення та
сполучення. ......................................................................................................................... 248
5.2. Обчислення кількості розміщень, перестановок і сполучень ................................. 257
5.3. Комбінаторика без повторень .................................................................................... 258
5.3.1. Перестановки ............................................................................................................ 258
5.3.2. Розміщення................................................................................................................ 261
5.3.3. Сполучення ............................................................................................................... 264
5.3.4. Перестановки з нерухомими точками .................................................................... 271
4
5.4. Комбінаторика з повторенням ................................................................................... 277
5.4.1. Перестановки ............................................................................................................ 277
5.4.2. Розміщення................................................................................................................ 280
5.4.3. Сполучення ............................................................................................................... 286
5.4.4. Задача про цілочисельні розв’язки ......................................................................... 293
5.5. Приклади розв’язування комбінаторних задач ........................................................ 294
5.6. Рекурсія для комбінаторики ....................................................................................... 298
5.7. Розбиття множини на підмножини ............................................................................ 306
5.7.1. Впорядковане розбиття множини на задане число підмножин заданих
потужностей ........................................................................................................................ 306
5.7.2. Невпорядковане розбиття множини на задане число підмножин заданих
потужностей ........................................................................................................................ 311
5.7.3. Невпорядковане розбиття множини на задане число непорожніх підмножин
довільних потужностей ...................................................................................................... 317
5.7.4. Довільні невпорядковані розбиття множини на непорожні підмножини .......... 319
5.8. Поліноміальна формула .............................................................................................. 320
5.9. Біном Ньютона ............................................................................................................ 320
5.10. Інверсії ........................................................................................................................ 323
5.11. Зворотні перестановки .............................................................................................. 324
5.12. Рекурентні рівняння. Розв’язування рекурентних рівнянь ................................... 326
5.13. Тестові завдання для самоконтролю ....................................................................... 327
5.14. Ключ до тестових завдань ........................................................................................ 328
5.15. Індивідуальні завдання для виконання лабораторної роботи ............................... 328
5.16. Комп’ютерний проект ............................................................................................... 335
5.17. Додаткові завдання для самостійної роботи .......................................................... 346
5.18. Контрольні запитання ............................................................................................... 368
Розділ 6. Теорія графів ....................................................................................................... 369
6.1. Основні означення та властивості ............................................................................. 369
6.2. Способи подання графів ............................................................................................. 372
6.3. Шляхи та цикли ........................................................................................................... 378
6.4. Алгоритми обходу графів ........................................................................................... 380
6.4.1. Алгоритм пошуку вглиб у графі ............................................................................. 380
6.4.2. Алгоритм проходження графу вшир ...................................................................... 383
6.5. Розфарбовування графа .............................................................................................. 385
6.6. Алгоритм Дейкстри ..................................................................................................... 385
6.7. Цікаві задачі на графах ............................................................................................... 389
6.7.1. Топологічне сортування .......................................................................................... 389
6.7.2. Пошук мостів ............................................................................................................ 390
6.7.3. Задача про максимальний потік .............................................................................. 390
6.7.4. Мінімальні кістякові дерева .................................................................................... 392
6.7.5. Задача Пріма-Крускала ............................................................................................ 392
6.7.6. Алгоритм Пріма ........................................................................................................ 394
6.7.7. Алгоритм Крyскала .................................................................................................. 396
6.7.8. Алгоритм Флойда-Уоршелла .................................................................................. 398
6.7.9. Оптимальне розміщення .......................................................................................... 403
6.7.10. Задача про комівояжера ......................................................................................... 404
5
6.7.11. Алгоритм Літтла ..................................................................................................... 406
6.7.12. Задача про паросполучення ................................................................................... 409
6.7.13. Оптимальність для підзадач .................................................................................. 411
6.8. Тестові завдання для самоконтролю ......................................................................... 412
6.9. Ключ до тестових завдань .......................................................................................... 413
6.10. Індивідуальні завдання для виконання лабораторної роботи ............................... 413
6.11. Комп’ютерний проект ............................................................................................... 418
6.12. Додаткові завдання для самостійної роботи .......................................................... 421
6.13. Контрольні запитання ............................................................................................... 424
Розділ 7. Дерева .................................................................................................................. 426
7.1. Основні означення та властивості ............................................................................. 426
7.2. Подання дерев .............................................................................................................. 428
7.2.1. Подання дерев на зв’язній пам’яті.......................................................................... 428
7.2.2. Подання дерев на суміжній пам’яті ........................................................................ 429
7.3. Алгоритми обходу дерев ............................................................................................ 432
7.4. Рекурсія для обходу дерев .......................................................................................... 436
7.5. Подання дерев у програмуванні ................................................................................ 437
7.6. Програмна реалізація алгоритмів обходу дерева вглиб та вшир ........................... 439
7.7. Бінарне (двійкове) дерево ........................................................................................... 439
7.8. Реалізація двійкових дерев у мові програмування .................................................. 441
7.8.1. Опис вершини ........................................................................................................... 441
7.8.2. Дерева мінімальної висоти ...................................................................................... 442
7.8.3. Формування бінарного дерева ................................................................................ 443
7.8.4. Алгоритм обходу бінарного дерева ........................................................................ 444
7.8.5. Пошук за допомогою дерева ................................................................................... 444
7.8.6. Побудова дерева пошуку ......................................................................................... 446
7.8.7. Пошук по дереву ...................................................................................................... 446
7.9. Розбір арифметичного виразу .................................................................................... 448
7.9.1. Дерево для арифметичного виразу ......................................................................... 448
7.9.2. Форми запису арифметичного виразу .................................................................... 448
7.9.3. Алгоритм побудови дерева ..................................................................................... 449
7.9.4. Обчислення виразу по дереву ................................................................................. 450
7.9.5. Розбір виразу з дужками .......................................................................................... 451
7.9.6. Багатозначні числа і змінні ..................................................................................... 452
7.9.7. Спрощення виразу за допомогою дерева ............................................................... 453
7.9.8. Операція виключення з бінарного дерева .............................................................. 454
7.9.9. Подання бінарного дерева в прямокутній пам’яті ................................................ 455
7.9.10. Застосування бінарних дерев ................................................................................ 455
7.9.11. Збалансоване дерево .............................................................................................. 456
7.10. Каркаси ....................................................................................................................... 457
7.11. Бектрекінг ................................................................................................................... 459
7.12. Індукція дерев рішень ............................................................................................... 467
7.13. Тестові завдання для самоконтролю ....................................................................... 471
7.14. Ключ до тестових завдань ........................................................................................ 473
7.15. Індивідуальні завдання для виконання лабораторної роботи ............................... 473
7.16. Комп’ютерний проект ............................................................................................... 474
6
7.17. Додаткові завдання для самостійної роботи .......................................................... 476
7.18. Контрольні запитання ............................................................................................... 479
Розділ 8. Мови, граматики, автомати ............................................................................... 480
8.1. Граматики з фразовою структурою ........................................................................... 480
8.2. Типи граматик з фразовою структурою .................................................................... 482
8.3. Дерева виведення ........................................................................................................ 483
8.4. Форми Бекуса-Наура ................................................................................................... 484
8.5. Скінченний автомат з виходом .................................................................................. 485
8.6. Скінченний автомат без виходу ................................................................................. 485
8.7. Мови ............................................................................................................................. 486
8.8. Математична модель мовосприйняття ...................................................................... 487
8.8.1. Визначення способів подання мови на синтаксичному рівні .............................. 488
8.8.2. Механізм виводу фраз формальної граматики ...................................................... 492
8.9. Тестові завдання для самоконтролю ......................................................................... 496
8.10. Ключ до тестових завдань ........................................................................................ 497
8.11. Індивідуальні завдання для виконання лабораторної роботи ............................... 498
8.12. Комп’ютерний проект ............................................................................................... 503
8.13. Додаткові завдання для самостійної роботи .......................................................... 503
8.14. Контрольні запитання ............................................................................................... 512
Розділ 9. Основи теорії алгоритмів................................................................................... 513
9.1. Основні вимоги до алгоритмів ................................................................................... 514
9.2. Машина Тюрінга ......................................................................................................... 516
9.3. Обчислення числових функцій на машинах Тюрінга.............................................. 521
9.4. Теза Тюрінга. Приклади алгоритмічно нерозв’язних проблем. ............................. 522
9.5. Формальні алгоритмічні системи .............................................................................. 523
9.6. Теорія складності обчислень ...................................................................................... 527
9.7. Тестові завдання для самоконтролю ......................................................................... 529
9.8. Ключ до тестових завдань .......................................................................................... 530
9.9. Індивідуальні завдання для виконання лабораторної роботи ................................. 530
9.10. Комп’ютерний проект ............................................................................................... 533
9.11. Додаткові завдання для самостійної роботи .......................................................... 535
9.12. Контрольні запитання ............................................................................................... 538
Список літератури .............................................................................................................. 540
Додатки ................................................................................................................................ 552
Додаток А. Лістинги програм ........................................................................................... 552
Лістинг A.1. Множини ....................................................................................................... 552
Лістинг A.2. Відображення ............................................................................................... 554
Лістинг A.3. Граф ............................................................................................................... 556
Лістинг A.4. Дерева ............................................................................................................ 559
Лістинг A.5. Алгоритм Пріма ........................................................................................... 561
Лістинг A.6. Алгоритм Крускала ...................................................................................... 563
Лістинг A.7. Алгоритм Дейкстри ..................................................................................... 565
Лістинг A.8. Алгоритм Флойда ......................................................................................... 567
Додаток Б. Додаткові індивідуальні та тестові завдання ............................................... 570
Дискретна математика – це розділ математики, в якому вивчають
дискретні математичні об’єкти та структури, зокрема, скінченні графи,
скінченні групи, скінченні автомати, машини Тюрінга тощо. З давніх часів
відомі комбінаторно-логічні задачі, розв’язання яких пов’язані з перебором
комбінацій дискретних об’єктів та логічним аналізом варіантів, що при цьому
виникають. Дискретні системи з найдавніших часів застосовуються в
комп’ютерній практиці. Розвиваючись паралельно з іншими розділами
математики, елементи дискретної математики виявилися їх складовою
частиною. Прикладами дискретних математичних об’єктів є натуральний ряд
чисел, скінченна множина елементів будь-якої природи; функція
(відображення) з скінченної множини у скінченну множину, слово
(послідовність символів) і формальна мова в скінченному алфавіті, скінченний
граф та інші.
Дискретна математика є розділом математики, що зародилася в давні
часи. Її відмінністю є дискретність, тобто антипод неперервності. Дискретна
математика включає традиційні розділи: математичну логіку, алгебру, теорію
чисел, теорію множин, теорію графів, автоматів та граматик. У більш як
двотисячорічній історії дискретної математики сучасний період є одним із
найінтенсивніших періодів її розвитку: дуже швидко розширюється сфера
застосування, інтенсивно зростають обсяги нової інформації та кількість нових
результатів. Якщо ще порівняно недавно ця наука була сферою інтересів лише
вузького кола фахівців, то тепер вона перетворюється на наукову дисципліну,
дуже важливу і потрібну для багатьох.
Основу сучасних швидкісних та якісних технологій опрацювання
інформації становлять комп’ютери – від персональних до серверів. Подання
інформації до комп’ютерів дискретне і її опрацювання складається з
послідовностей елементарних перетворень тих чи інших інформаційних
одиниць (слів, літер, цифр тощо). Отже, фундаментальною ідеєю щодо
відображення реального світу у комп’ютері є ідея дискретизації об’єктів. Для
ефективної роботи на комп’ютері необхідно навчитися будувати моделі
реальних об’єктів та процесів їх перетворення. Досить часто такими моделями
можуть бути конструкції дискретної математики, такі як алгебра, формула,
автомат, граф, алгоритм тощо.
В 60-х роках 20 ст. впровадження обчислювальної техніки до сфери
управління, проектування та опрацювання інформації призвело до створення
автоматизованих систем управління (АСУ) та проектування (САПР). Поступово
склалася ціла практична та теоретична галузь науки і техніки – розроблення та
запровадження АСУ різних типів, САПР, автоматизованих інформаційних
систем, зокрема інформаційно-пошукових, інформаційно-довідкових та інших.
Поступово до 80–х років нова галузь була поставлена на солідну наукову
основу, оформилась організаційно. Далі дискретна математика стала основою
багатьох алгоритмів та методів штучного інтелекту, а зараз активно
використовується для розроблення сучасних систем штучного інтелекту (СШІ)
8
та інших інформаційних технологіях (ІТ).
Створення автоматизованих систем опрацювання інформації та
управління базувалося на трьох принципах:
1) кібернетичному (Норберта Вінера): “сутність принципу управління в
тому, що рух і дія великих мас або передача великих кількостей енергії
спрямовуються і контролюються за допомогою невеликих кількостей енергії,
що несуть інформацію”.
2) модельному: в системі управління певним об’єктом створюється
аналог об’єкту управління, який називається моделлю. Керуючий вплив
відпрацьовується на моделі і реалізується потім на об’єкті управління.
3) алгоритмічному: вибір керуючого впливу, реалізація якого приносить
найкращі в певному сенсі наслідки функціонування об’єкту управління,
формулюється у вигляді проблеми. Вирішення проблеми подається у вигляді
алгоритму – такої схеми виконання операцій на моделі, результатом реалізації
якої є керуючий вплив, що приносить бажані наслідки. Реалізація алгоритму
виконується комп’ютером, що виконує програму (процедуру), яка є записом
алгоритму на мові програмування.
Автоматизовані системи управління та системи опрацювання інформації,
таким чином, є комп’ютеризованими системами, функціонування яких
здійснюється у вигляді процесу реалізації системи алгоритмів, послідовність
виконання яких залежить від стану об’єкту управління.
Дискретна математика забезпечує системотехніка засобами й методами
реалізації кожного з етапів кібернетичного підходу. Також дискретна
математика забезпечує штучний інтелект та інформаційні технології засобами й
методами дискретного опрацювання інформації в часі. Головне завдання
дисципліни – сформувати математичний фундамент освіти студента як
майбутнього програміста та аналітика, а також прищепити вміння
цілеспрямовано добудовувати його знаннями, одержаними на інших курсах.
Інформація про різні природні явища та технологічні процеси
сприймається людиною у вигляді тих або інших полів, які математично
подаються за допомогою функцій вигляду y = f(x,t), де y – значення поля в цій
точці, x – точка, в якій воно вимірюється, t – час. При вимірюванні поля у
фіксованій точці x=a функція f(x,t) вироджується у функцію часу y(t) = f(a,t).
Здебільшого всі скалярні величини, що входять у співвідношення y =
f(x,t) (тобто t, y і координати точки x), можуть набувати неперервного ряду
значень дійсних чисел. Під неперервністю розуміють те, що величини, які
розглядаються, можуть змінюватися будь-якими дрібними кроками. Подану
таким способом інформацію прийнято називати неперервною або аналоговою.
Якщо стосовно тієї самої інформації про поле y = f(x,t) зафіксувати деякі
значення кроків усіх скалярних величин, які її характеризують, то дістанемо
дискретне подання інформації (дискретну інформацію). Оскільки точність
вимірювань завжди обмежена, навіть маючи справу з неперервною
інформацією, людина сприймає, а комп’ютер зберігає її у дискретному вигляді.
Проте будь-яка неперервна інформація може бути апроксимована (знайдені її
9
наближені значення) дискретною інформацією з будь-якою точністю, тому
можна говорити про універсальність дискретної форми подання інформації.
Крім того, результати вимірювань будь-яких скалярних величин
подаються, зрештою, в числовому вигляді, а оскільки при заданій точності
вимірювань ці числа є кінцевими наборами цифр (із комою або без неї),
дискретну форму подання інформації часто ототожнюють із цифровою.
Дискретна математика складається з ряду спеціальних розділів, серед
яких найважливіші: комбінаторний аналіз, теорія графів, теорія дискретних
функцій, теорія автоматів та алгоритмів, теорія складності, теорія формальних
мов, теорія кодування, дискретна геометрія та інші. Використання дискретної
математики складають основи сучасних комп’ютерних наук та інформатики.
Комбінаторика – це важливий розділ дискретної математики, який
пов’язаний з методами підрахунку кількості об’єктів певної природи.
Комбінаторні задачі мають особливу прикмету. Такою прикметою є спільність
у формулюванні самих задач, які майже завжди починаються зі слів “Скількома
способами …?“. Цікава сама по собі, комбінаторика важлива і для багатьох
інших розділів математики: алгебри, теорії ймовірностей та математичної
статистики, теорії інформації, економіки, лінгвістики та інші. Особливого
значення вона починає набувати у зв’язку з бурхливим розвитком
комп’ютерних наук. Комбінаторика як теорія скінченних множин (у широкому
значені оперує натуральними числами і тому може здатися, що вона є більш
«елементарною», ніж інші розділи математики. Але така оцінка була б
завчасною. З досвіду відомо – тим, хто вперше пробує розв’язувати задачі з
комбінаторики, важко звикнути до сенсу її термінів. На жаль, підручників з
дискретної математики, особливо з великою кількістю задач з комбінаторики
українською мовою для студентів технічних вузів практично немає.
Мета навчального посібника “Збірник задач з дискретної математики” –
заповнити певною мірою вказану прогалину. Автори, не прагнучи охопити весь
матеріал, намагались у доступній формі ознайомити читача з основними
поняттями та методами комбінаторики, виробити в нього навички
комбінаторного мислення. У посібнику розглядаються в основному
найпростіші й водночас найбільш важливі для практики комбінаторні задачі
(так звані урнові моделі). Щоби познайомитись з предметом ґрунтовніше,
можна звернутися до спеціальної літератури, перелік якої пропонується в кінці
навчального посібника. Розділи посібника переважно не повторюють жодного
підручника з дискретної математики - матеріал викладено за власною
методичною основою із дотриманням належного рівня математичної строгості,
що дозволяє студентам самостійно засвоїти теоретичний матеріал і легко
розв’язувати задачі прикладного характеру. Теоретичний матеріал
проілюстровано значною кількістю розв’язаних типових задач, при виборі яких
автори керувались не стільки їхньою практичною актуальністю, скільки
ілюстративністю для засвоєння відповідних положень. Розглянуто широке коло
важливих дискретних задач, яких немає у класичних підручниках з вищої
математики. Це значно розширює клас інженерних задач, для розв’язання яких
10
може бути корисним цей навчальний посібник.
Для кожного підрозділу посібника підібрано задачі різного рівня
складності як для аудиторної, так і для самостійної роботи студентів. В
інтересах читача більшість задач супроводжується не тільки відповідями, а й
вказівками для їхнього розв’язання. Посібник може бути корисним не лише для
студентів, а й аспірантів, а також викладачів деяких спеціальних дисциплін та
співробітників наукових установ.
Збірник задач з дискретної математики містить матеріал для вивчення
основних теоретичних засад, функціональних можливостей та практичного
застосування дискретної математики, основи математичної логіки і теорії
множин, елементи комбінаторного аналізу, основи теорії відношень, основи
теорії графів та дерев, основи теорії кодування, булеві функції, мови, граматики
та автомати, основи теорії алгоритмів, основи теорії кодування. Посібник
призначений для здобуття студентами практичних навичок застосування
класичних алгоритмів дискретної математики та сучасних алгоритмів штучного
інтелекту, що використовуються при побудові комп’ютерних програм.
Теоретичний та практичний матеріал викладено у доступній формі. Викладення
матеріалу супроводжується значною кількістю прикладів, що полегшує його
сприйняття та засвоєння. Збірник задач з дискретної математики призначається
для студентів, що навчаються за спеціальностями 122 “Комп’ютерні науки”,
124 “Системний аналіз”, 126 “Інформаційні системи та технології” та
споріднених спеціальностей, які пов’язані з інформатикою та інформаційними
технологіями. В результаті освоєння матеріалу студент буде вміти
застосовувати відомі методи та алгоритми дискретної математики для
дослідження предметної області та побудови математичного опису прикладних
проблем. Збірник задач з дискретної математики може бути використаний
аспірантами як підґрунтя для наукових досліджень та викладачами як
дидактичний матеріал, а також для самостійного вивчення. Книга призначена
для спеціалістів із проектування, розроблення та впровадження
інтелектуальних систем опрацювання інформаційних ресурсів, науковців у
галузі глобальних інформаційних системи, систем штучного інтелекту,
Інтернет-технологій, фахівців з електронної комерції, Інтернет-маркетингу та
Інтернет-реклами, менеджерів комплексних Web-проектів, а також для
здобувачів 3-ого (освітньо-наукового) рівня вищої освіти в галузі знань 12
«Інформаційні технології». Кожний розділ закінчується переліком питань для
самоконтролю та переліком практичних завдань.
Розділ 1 присвячений вивченню множин, операцій над множинами,
комп’ютерного подання множин. В цьому розділі розглядається
фундаментальне поняття множини. Наводяться операції над множинами, різні
типи множин та їх властивості, детально описується окремий тип множин –
відношення, функціональні відображення та їх властивості. Матеріал розділу
використовується для моделювання структури та функціонування багатьох
об’єктів управління, формується математичний апарат інших дисциплін
спеціальності («Реляційна алгебра», «Схемотехніка», «Основи баз даних та
11
знань» та інших).
Розділ 2 знайомить з питаннями законів логіки висловлювань, побудови
нормальних форм логіки висловлювань, законів логіки першого ступеня,
побудови випередженої нормальної форми та застосування правил виведення в
логіці висловлювань.
Логіка – є могутнім засобом для вирішення задач людиною. Математична
логіка – спроба формально описати ці засоби та застосовувати їх до будь-яких
областей із реального світу. Двійкова логіка є одним із центральних питань у
комп’ютерних науках через те, що інформація у сучасних комп’ютерів
представлена саме у двійковому вигляді. Цей розділ присвячено опису різних
типів логічних функцій, що приймають значення 0 або 1, наводиться поняття
формули та різних нормальних форм із засобами зведення будь-якої логічної
формули до них. Особливо важливим елементом розділу є теорема повноти. В
ньому також наводяться системи числень висловлювань та предикатів, які
дозволяють формально вірно (тобто із збереженням логічного слідування)
отримувати нові результати із вже існуючих даних. Для використання у
комп’ютерах математичної логіки у розділі також описуються основи
автоматичного доведення теорем.
Розділ 3 присвячений відношенням та їх властивостям, відношенням
еквівалентності та часткового порядку, операціям над відношеннями,
замиканням відношень.
У розділі 4 наведено поняття булевої функції, алгебри булевих функцій,
спеціальні форми подання булевих функцій, а також мінімізація булевих
функцій. Цей розділ є “логічним” продовженням попередніх.
У розділі 5 розглянуто основні правила комбінаторного аналізу,
обчислення кількості розміщень та сполучень, застосування бінома Ньютона,
розв’язування рекурентних рівнянь. Комбінаторика є дуже важливим розділом
як дискретної математики, так математичних наук взагалі. Методи, які
вивчаються в цьому розділі, закладають підґрунтя до багатьох важливих
напрямків комп’ютерних наук: важкорозв’язувані задачі, оцінка складності
задач та алгоритмів. Логічним продовженням цього розділу постає великий за
обсягом та значенням курс «Теорія ймовірностей та математична статистика».
Поняття графа та їх властивості описані у розділі 6. Зокрема тут
розглядаються способи подання графів, алгоритми обходу графів,
розфарбовування графів та задачі пошуку найкоротших шляхів у графі
(алгоритм Дейкстри). Теорія графів надає дуже зручний математичний апарат
для опису програмних та багатьох інших моделей. Величезна кількість задач,
які постають в рамках комп’ютерних наук, можуть бути вдало представлені, а
потім і вирішені засобами теорії графів. Особливо важливим є наявність
графічної інтерпретації поняття графа, що надає ще більшої зручності, а відтак,
і привабливості цій теорії. В розділі розглядаються різні типи графів та їх
властивості, алгоритми пошуку в графах. Окремими випадками графів є дерева
та мережі. Важливими поняттями є цикли (ейлерові та гамільтонові),
розфарбування графів, планарність.
12
Дерева та їх застосування подані у розділі 7. В даному розділі розглянуто
обхід дерев, основні форми запису виразів (префіксна, інфіксна та постфіксна),
дерева прийняття рішень, а також алгоритм бектрекінг та алгоритм Крускала.
Розділ 8 присвячений формальним мовам, граматикам та автоматам. У
цьому розділі наведено типи граматик за ієрархією Хомські, дерева виведення,
скінченні автомати з виходом та без виходу, способи подання мов.
Важливим фактором при роботі з комп’ютером є наявність мов
спілкування або програмування. Матеріал цього розділу якраз відповідає за
створення подібних конструкцій – штучних мов. Розглядається поняття
граматики та їхня класифікація за Хомським, породження мов граматиками,
контекстно-вільні граматики та їх властивості, алгоритми для роботи із різними
типами граматик. При створенні будь якого апаратного засобу найпершою
вимогою є моделювання й проектування його. Автомати – це потужний
математичний апарат, якраз направлений на вирішення таких задач. У розділі
наводяться поняття скінченого автомату й проаналізовані їх властивості.
Питання аналізу й синтезу автоматів і експерименти по розпізнанню станів
розглянуті на прикладі скінчених автоматів. Показано зв’язок автоматів із
граматиками, коли для кожної мови можна поставити граматику, що породжує
її, й автомат, що її розпізнає.
У розділі 9 означено основні поняття теорії алгоритмів та розглянуто
застосування машини Тюрінга.
Наприкінці треба зазначити, що матеріали цього курсу є дуже
важливими, можна певно говорити – базовими, для подальшого навчання в
галузі знань 12 “Інформаційні технології” за спеціальностями
122 “Комп’ютерні науки”, 124 “Системний аналіз”, 126 “Інформаційні системи
та технології” та споріднених спеціальностей, які пов’язані з інформатикою та
інформаційними технологіями.
Автори цього навчального посібника висловлюють щиру подяку своєму
наставнику та викладачу, професору Нікольському Юрію Володимировичу за
те, що він не лише привив нам любов до цієї дисципліни, але своєю
наполегливою працю надихнув продовжити його роботу в цьому напряму.
Також автори висловлюють щиру подяку фахівцям в галузі знань
12 “Інформаційні технології” за плідну співпрацю, вагомі поради та слушні
зауваження при формуванні структури книги та її наповнення. Зокрема,
дякуємо за підтримку:
Бісікалу О.В. – доктору технічних наук, професору, декану факультету
комп’ютерних систем та автоматики Вінницького національного
технічного університету;
Бобалу І.Ю. – кандидату технічних наук, доценту кафедри «Інформаційні
системи та мережі» Національного університету «Львівська
політехніка»;
Винокуровій О.А. – доктору технічних наук, професору, головному
науковому співробітнику Проблемної науково-дослідної лабораторії
АСУ Харківського національного університету радіоелектроніки;
13
Гожому О.П. – доктору технічних наук, професору кафедри комп’ютерної
інженерії Чорноморського національного університету імені Петра
Могили;
Катренку А.В. – кандидату економічних наук, доценту кафедри
«Інформаційні системи та мережі» Національного університету
«Львівська політехніка»;
Литвиненку В.І. – доктору технічних наук, професору, завідувачу кафедри
інформатики і комп’ютерних наук Херсонського національного
технічного університету;
Пасічнику В.В. – доктору технічних наук, професору кафедри
«Інформаційні системи та мережі» Національного університету
«Львівська політехніка»;
Пелешку Д.Д. – доктору технічних наук, професору, проректору з науково-
педагогічної роботи «IT Step University»;
Пукачу П.Я. – доктору технічних наук, професору, завідувачу кафедри
«Обчислювальна математика та програмування» Національного
університету «Львівська політехніка»;
Цмоцю І.Г. – доктору технічних наук, професору, завідувачу кафедри
автоматизованих систем управління Національного університету
«Львівська політехніка»;
Шароновій Н.В. – доктору технічних наук, професору, завідувачу кафедри
інтелектуальних комп’ютерних систем Національного технічного
університету «Харківський політехнічний інститут»;
Шаховській Н.Б. – доктору технічних наук, професору, завідувачу кафедри
систем штучного інтелекту Національного університету «Львівська
політехніка»;
Щербині Ю.М. – кандидату фізико-математичних наук, доценту кафедри
дискретного аналізу та штучних інтелектуальних систем Львівського
національного університету імені Івана Франка.