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

Анотація навчальної дисципліни

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

Основні результати навчання
ПРН1. Застосовувати знання основних форм і законів абстрактно-логічного мислення, основ методології наукового пізнання, форм і методів вилучення, аналізу, обробки та синтезу інформації в предметній області комп'ютерних наук.
ПРН2. Використовувати сучасний математичний апарат неперервного та дискретного аналізу, лінійної алгебри, аналітичної геометрії, в професійній діяльності для розв’язання задач теоретичного та прикладного характеру в процесі проектування та реалізації об’єктів інформатизації.
ПРН5. Проектувати, розробляти та аналізувати алгоритми розв’язання обчислювальних та логічних задач, оцінювати ефективність та складність алгоритмів на основі застосування формальних моделей алгоритмів та обчислюваних функцій.

Тематика та види навчальних занять
1 тиждень.
Лекція 1. «Визначення дискретної математики. Оцифрування, квантування, дискретизація – парадигма сучасної обчислювальної техніки. Приклад оцифрування звука. Втрати інформації при оцифруванні. Міст між описом роботи пристрою та його реалізацією логічними функціями, втіленими на рівні фізики. Формальна логіка як розділ математики». 
Практичне заняття 1. «Логічні функції. Формальний запис логічних розмірковувань. Логічні операції та їх відносний пріоритет. Спрощення запису формул. Основні тотожності булевої алгебри».

2 тиждень. 
Лекція 2. «Завдання булевих функцій. Табличний спосіб. Аналітичний спосіб. Булеві функції однієї та двох змінних. Взаємоперетворення булевих функцій. Визначення вироджених та невироджених функцій. Залежності між булевими функціями та  визначення всіх функцій від двох змінних через операції «І», «АБО» та «НІ».
Практичне заняття 2. «Алгебра Жегалкіна, визначення, формули прямого переходу від алгебри Жегалкіна до Булевої та, навпаки, від Булевої алгебри до алгебри Жегалкіна. Визначення канонічного поліному в контексті Алгебри Жегалкіна. Класифікація булевих функцій згідно із теоремою Поста. Визначення функціональної повноти щодо суперпозиції функцій».

3 тиждень. 
Лекція 3. «Синтез повного двійкового суматора як приклад переходу від формального опису до реалізації фізичного пристрою за допомогою булевих функцій. Мінімальні форми та канонічна задача синтезу булевих функцій. Визначення довершеної диз’юнктивної нормальної форми (ДДНФ) та диз’юнктивної нормальної форми (ДНФ) як базових термінів алгоритму мінімізації».
Практичне заняття 3. «Визначення операцій поглинання та склеювання. Визначення тупикових форм як результату мінімізації. Визначення ціни за Квайном як критерію мінімальної функції. Мінімізація за допомогою карт Карно». 
Видача завдання на РГР.

4 тиждень. 
Лекція 4. «Автоматична мінімізація булевих функцій як альтернатива методу Карно. Базові алгоритми. Визначення комплексу кубів. Метод Квайна-Мак-Класки».
Практичне заняття 4. «Мінімізація функцій методом Квайна-Мак-Класки». 
Виконання  першої частини РГР.

5 тиждень. 
Лекція 5. «Мінімізація функцій від трьох та чотирьох змінних методом кубів. Порівняння різних методів мінімізації, обґрунтування вибору того чи іншого метода. Мінімізація частково визначених функцій». 
Практичне заняття 5. «Мінімізація функцій від трьох та чотирьох змінних методом кубів».
Виконання  першої частини РГР.

6 тиждень. 
Лекція 6. «Теорія множин. Основні визначення. Способи завдання множин, підмножини. Операції над множинами, операція додавання та її відповідність операції інверсії в Булевій алгебрі, кола Ейлєра. Властивості операцій над множинами. Множина всіх підмножин, булеан. Методи доведення тотожностей алгебри множин»
Практичне заняття 6. «Спрощення виражень множин через властивості та використання кіл Ейлера для отримання результату операцій над множинами».
Виконання  першої частини РГР.

7 тиждень. 
Лекція 7. «Теорія множин. Визначення кортежу, декартового добутку, впорядкованої пари, кардинального числа. Визначення відповідності, бінарних відносин, композиції відносин, матриця відносин та інші способи завдання бінарних відносин (табличний та у вигляді графів)». 
Практичне заняття 7. «Побудова матриці відносин». 
Захист першої частини РГР.

8 тиждень.
Лекція 8. «Елементи теорії графів. Визначення графу, верхівки графу, дуги та ребра. Базові визначення: матриця суміжностей та матриця інцидентностей як спосіб зберігати інформацію щодо графа».
Практичне заняття 8. «Побудова графів по матрицям суміжності та інцидентності».
Модульна контрольна робота 1.

9 тиждень.
Лекція 9. «Теорія графів. Визначення ваги дуги, верхівки, ребра. Визначення різновиду дуг-петель та неорієнтованого графу, зваженого та незваженого. Загальні типи графів: псевдографи, мультиграфи, прості графи, нуль-графи, повні графи, дводольні графи, однорідні графи. Визначення ступеню верхівки графа. Композиція відносин, уявлення композиції відносин на графі, способи отримання рішень щодо композиції відносин. Приклади використання алгоритму пошуку композиції відношень». 
Практичне заняття 9. «Побудова орієнтованого та неорієнтованого графа, побудова зваженого графа».
Виконання  другої частини РГР.

10 тиждень.
Лекція 10. «Алгоритм знаходження мінімального шляху на дискретному полі – алгоритм Лі. Визначення хроматичного числа графу, алгоритм розмальовки, опис, галузь застосування, приклади використання алгоритму розмальовки». 
Практичне заняття 10. «Визначення хроматичного числа за допомогою алгоритмів розмальовки графа, алгоритм Лі».
Виконання  другої частини РГР.

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

12 тиждень
Лекція 12.«Дерева і ліс в теорії графів, базові визначення. Типи дерев. Визначення остову графу. Алгоритми Краскала та Прима для побудови остовного дерева. Алгоритми пошуку мінімального шляху на графі, особливості використання, доцільність того чи іншого алгоритму. Алгоритм Флойда-Уоршелла  для пошуку мінімального шляху між будь-якими двома верхівками графу». 
Практичне заняття 12 «Побудова остовного дерева за алгоритмами Прима та Краскала. Знаходження мінімального шляху між вершинами графа за допомогою алгоритму Флойда-Уоршелла».
Виконання  другої частини РГР.

13 тиждень.
Лекція 13. «Пошук найкоротшого  та найдовшого шляхів на графі між двома конкретними верхівками: алгоритм Дейкстри, порівняння із алгоритмом Флойда по критеріях швидкості та використання пам’яті. Визначення пласких (планарних) графів. Графи Понтрягіна-Куратовського». 
Практичне заняття 13. «Знаходження мінімального шляху між вершинами графа за допомогою алгоритму Дейкстри».
Виконання  другої частини РГР.

14 тиждень.
Лекція 14. «Визначення центру та центроїду на графі. Алгоритми пошуку. Аналіз задач, в яких доцільно використовувати той чи інший алгоритм. Визначення ексцентриситету для всіх верхівок графа. Коди Прюфера, що дозволяють зберігати графи-дерева в одномірному масиві. Пакування графа-дерева, код та антикод».
Практичне заняття 14. «Побудова дерева, що однозначно описане кодами Прюфера в одномірному масиві розміром n-2 (n – кількість верхівок графа)». 
Виконання  другої частини РГР.

15 тиждень.
Лекція 15. «Комбінаторика. Правила суми та добутку. Розміщення, перестановки та сполучення з повторенням та без. Біном Ньютона. Принцип включення і виключення».
Практичне заняття 15. «Рішення задач з комбінаторики».
Захист другої частини РГР.
Модульна контрольна робота 2.

Самостійна робота здобувача відбувається впродовж семестру та складається з підготовки до аудиторних занять, контрольних заходів, індивідуальних завдань. 
Консультації: здійснюються викладачем впродовж семестру згідно розкладу.

Оцінювання результатів навчання

Оцінювання результатів навчання з дисципліни здійснюється за накопичувальною системою, яка дає можливість здобувачеві протягом семестру отримати максимально 100 балів.

Модуль 1
Практичні заняття – за активну участь по 1 балу за заняття (всього 8 балів)
Бездоганно виконана перша частина розрахунково-графічної роботи, надана у встановлені терміни викладачу – максимально 12 балів.
Модульна контрольна робота 1 – бездоганне виконання 30 балів (в кожному завданні модульної контрольної роботи наведено максимальну кількість балів за виконання кожного завдання).
Модуль 2
Практичні заняття – за активну участь по 1 балу за заняття (всього 7 балів)
Бездоганно виконана друга частина розрахунково-графічної роботи, надана у встановлені терміни викладачу – 13 балів. 
Модульна контрольна робота 2 – бездоганне виконання 30 балів (в кожному завданні модульної контрольної роботи наведено максимальну кількість балів за виконання кожного завдання).

Посилання на рекомендовані джерела
1. Конспект лекцій з дисципліни «Дискретна математика» для студентів денної форми навчання інституту комп’ютерних систем спеціальності 122 – «Комп’ютерні науки» / Укл.: Ю.В.Дрозд, М.О. Дрозд, – Одеса. ОНПУ, 2019. – 93с. 
2. Методичні вказівки та завдання для проведення практичних занять з дисципліни «Дискретна математика» для студентів денної форми навчання інституту комп’ютерних систем спеціальності 122 – «Комп’ютерні науки» / Укл.: Ю.В.Дрозд, М.О. Дрозд, – Одеса. ОНПУ, 2019. – 59с. 
3. Методичні вказівки та завдання для виконання розрахунково-графічної роботи з дисципліни «Дискретна математика» для студентів денної форми навчання інституту комп’ютерних систем спеціальності 122 – «Комп’ютерні науки» / Укл.: Ю.В.Дрозд, М.О. Дрозд, – Одеса. ОНПУ, 2019. – 14с. 
4. Балога С.І. Дискретна математика. Навчальний посібник. – Ужгород: ПП «АУТДОР-ШАРК», 2021. – 124 с. https://dspace.uzhnu.edu.ua/jspui/bitstream/lib/36740/1/Навчальний%20посібник%20Дискретна%20математика%20.pdf
5. Дискретна математика: Конспект лекцій (Частина 1) [Електронний ресурс]: навч. посіб. для студ. спеціальності 113 «Прикладна математика», освітньої програми «Наука про дані та математичне моделювання» / О.Л.Темнікова ; КПІ ім. Ігоря Сікорського. – Електронні текстові дані (1 файл: 2,97 Мбайт). – Київ : КПІ ім. Ігоря Сікорського, 2021. – 154 https://ela.kpi.ua/bitstream/123456789/42839/1/LectureDM1Temnikova.pdf