Вступ 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. Відношення часткового порядку 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 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. Алгоритм Крускала 396 6.7.8. Алгоритм Флойда-Уоршелла 398 6.7.9. Оптимальне розміщення 403 6.7.10. Задача про комівояжера 404 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 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

Лістинг А.1. Множини 552

Лістинг А-2 Відображення 554

Лістинг А.З. Граф 556

Лістинг А.4. Дерева 559

Лістинг А.5. Алгоритм Пріма 561

Лістинг А.6. Алгоритм Крускала 563

Лістинг А.7. Алгоритм Дейкстри 565

Лістинг А.8. Алгоритм Флойда 567

Додаток Б. Додаткові індивідуальні та тестові завдання 570

Навчальний посібник містить матеріал для вивчення основних теоретичних засад, функціональних можливостей та практичного застосування дискретної математики, основи математичної логіки і теорії множин, елементи комбінаторного аналізу, основи теорії відношень, основи теорії графів та дерев, основи теорії кодування, булеві функції, мови, граматики та автомати, основи теорії алгоритмів, основи теорії кодування. Посібник призначений для здобуття студентами практичних навичок застосування класичних алгоритмів дискретної математики та сучасних алгоритмів штучного інтелекту, що використовуються при побудові комп’ютерних програм. Теоретичний та практичний матеріал викладено у доступній формі. Викладення