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

Дисципліна «Дискретна математика» призначена для підвищення рівня математичної підготовки здобувачів, що спеціалізуються в області інформаційних технологій проєктування. Найбільш значущою галуззю застосування методів дискретної математики є комп’ютерні технології. Це пояснюється необхідністю створення та використання ЕОМ, засобів передачі та обробки інформації автоматизованих систем та комп’ютерним проєктуванням.
Головною особливістю дискретної математики є відсутність граничного переходу та неперервність, що суттєвим чином відрізняє її від класичної математики. Тому дискретна математика сьогодні є важливим ланцюгом математичної освіти. В зв’язку з цим головним завданням курсу є оволодіння здобувачами мовою, термінами, методами та мисленням, що є характерним для дискретної математики.
Мета вивчення дисципліни: набуття фундаментальних теоретичних знань і практичних навичок з питань постановки та розв’язування задач, що мають дискретний або скінчений характер.
Основні завдання дисципліни: оволодіти мовою, термінами, методами та мисленням, що є характерним для дискретної математики.
Практичне значення та використання отриманих знань полягає у ознайомленні з мовою, термінами, методами та мисленням, що є характерним для дискретної математики. Отриманні навичок використання ЕОМ, засобів передачі та обробки інформації автоматизованих систем.
Значення для особистісного та професійного розвитку: вивчення дискретної математики сприяє розвитку логічного та аналітичного мислення, уміння формалізувати й моделювати складні системи, приймати обґрунтовані рішення на основі математичних аргументів, а також підвищує точність, уважність і послідовність у професійній діяльності.
Тематика та види навчальних занять
Для денної форми здобуття освіти
Лекційні заняття
Лекція 1. Множини та операції над ними.
Лекція 2. Алгебра множин.
Лекція 3. Теорія відношень.
Лекція 4. Теорія функцій.
Лекція 5. Властивості функцій.
Лекція 6. Комбінаторика.
Лекція 7. Елементи математичної логіки. Алгебра висловів.
Лекція 8. Основи булевої алгебри.
Лекція 9. Булеві функції.
Лекція 10. Нормальні форми булевих функцій.
Лекція 11. Мінімізація булевих виразів.
Лекція 12. Ненаправлені графи.
Лекція 13. Шляхи та цикли графа.
Лекція 14. Шлях Ейлера та цикл Гамільтона.
Лекція 15. Ізоморфізм графів.
Лабораторні роботи
Лабораторна робота №1. Операції над множинами. Алгебра множин.
Мета заняття: сформувати вміння виконувати основні операції над множинами (об’єднання, перетин, різниця, доповнення), використовувати закони алгебри множин для спрощення виразів і розв’язання прикладних задач.
Лабораторна робота №2. Властивості бінарних відношень.
Мета заняття: засвоїти поняття бінарного відношення, навчитися визначати його властивості (рефлексивність, симетричність, транзитивність, антисиметричність) та здійснювати їх графічне подання.
Лабораторна робота №3. Класи еквівалентності. Порядок множини.
Мета заняття: навчитися виділяти класи еквівалентності, будувати фактор-множини та встановлювати відношення порядку на множині, визначати частково впорядковані множини.
Лабораторна робота №4. Способи задавання функцій.
Мета заняття: оволодіти різними способами задання функцій (аналітичним, табличним, графічним, словесним), навчитися описувати відображення між множинами та досліджувати їхні властивості.
Лабораторна робота №5. Аналіз властивостей функцій.
Мета заняття: закріпити вміння визначати область визначення та область значень функції, досліджувати ін’єктивність, сюр’єктивність, бієктивність і знаходити обернену функцію.
Лабораторна робота №6. Задачі комбінаторики.
Мета заняття: сформувати навички застосування правил комбінаторики (правило добутку, суми, розміщення, перестановки, сполучення) для обчислення кількості варіантів у задачах на підрахунок.
Лабораторна робота №7. Аналіз висловів за таблицями істинності.
Мета заняття: навчитися формалізувати висловлювання, будувати таблиці істинності для логічних формул, визначати логічну еквівалентність і виконувати перевірку правильності висловів.
Лабораторна робота №8. Аналіз висловів за таблицями істинності.
Мета заняття: сформувати вміння доводити логічні вислови за допомогою правил висновку, оволодіти основами логіки предикатів і навичками роботи з кванторами.
Лабораторна робота №9. Аксіоми висловів та булеві функції.
Мета заняття: засвоїти аксіоматику висловлювальної логіки, навчитися задавати та перетворювати булеві функції, використовувати логічні схеми для реалізації виразів.
Лабораторна робота №10. Запис ЗДНФ та ЗКНФ. Перемикачі.
Мета заняття: навчитися перетворювати булеві функції до заданої диз’юнктивної та кон’юнктивної нормальної форми (ЗДНФ, ЗКНФ), а також будувати схеми перемикачів за цими формами.
Лабораторна робота №11. Мінімізація булевих функцій.
Мета заняття: засвоїти методи мінімізації булевих функцій (алгебраїчні та графічні методи, карти Карно), оптимізувати логічні вирази для побудови ефективних цифрових схем.
Лабораторна робота №12. Задавання та зображення графів.
Мета заняття: навчитися представляти ненаправлені графи різними способами (списками суміжності, матрицями суміжності й інцидентності), а також будувати їх графічне подання.
Лабораторна робота №13. Визначення шляхів та маршрутів графів.
Мета заняття: сформувати вміння знаходити шляхи, маршрути та цикли в графах, визначати їх довжину та досліджувати зв’язність вершин.
Лабораторна робота №14. Визначення найкоротшого шляху графу.
Мета заняття: навчитися застосовувати алгоритми пошуку найкоротших шляхів у графах (алгоритм Дейкстри, Беллмана–Форда, Флойда–Варшалла) для розв’язання прикладних задач.
Лабораторна робота №15. Визначення ізоморфних графів.
Мета заняття: засвоїти поняття ізоморфізму графів, навчитися порівнювати графи за структурними властивостями, визначати ізоморфні графи та їх інваріанти.
Для заочної форми здобуття освіти
Лекційні заняття
Лекція 1. Множини та операції над ними. Теорія відношень. Властивості функцій. Комбінаторика. Основи булевої алгебри. Булеві функції.
Лекція 2. Нормальні форми булевих функцій. Мінімізація булевих виразів. Ненаправлені графи. Шляхи та цикли графа. Шлях Ейлера та цикл Гамільтона.

Лабораторні роботи
Лабораторна робота №1. Операції над множинами. Алгебра множин. Класи еквівалентності. Порядок множини. Аналіз властивостей функцій. Аналіз висловів за таблицями істинності.
Мета роботи: сформувати вміння виконувати основні операції над множинами, навчитися виділяти класи еквівалентності, закріпити вміння визначати область визначення та область значень функції, навчитися формалізувати висловлювання, будувати таблиці істинності для логічних формул.
Лабораторна робота №2. Аксіоми висловів та булеві функції. Мінімізація булевих функцій. Задавання та зображення графів.
Мета роботи: засвоїти аксіоматику висловлювальної логіки, засвоїти методи мінімізації булевих функцій (алгебраїчні та графічні методи, карти Карно), навчитися представляти ненаправлені графи різними способами (списками суміжності, матрицями суміжності й інцидентності).
Консультації здійснюються впродовж семестру згідно встановленого розкладу.
Індивідуальна робота
Для денної форми здобуття освіти
Розрахунково-графічна робота
Метою розрахунково-графічної роботи з дисципліни «Дискретна математика» є закріплення основних теоретичних знань і практичних навичок у ході самостійної роботи, що включає задачі аналізу і синтезу формул і схем, і виконується паралельно з роботою на лекційних і лабораторних заняттях.
Для заочної форми здобуття освіти
Розрахунково-графічна робота
Метою розрахунково-графічної роботи з дисципліни «Дискретна математика» є закріплення основних теоретичних знань і практичних навичок у ході самостійної роботи, що включає задачі аналізу і синтезу формул і схем, і виконується паралельно з роботою на лекційних і лабораторних заняттях.
Контрольна робота
Завдання для виконання контрольної роботи здобувач отримує на установчій лекції.
Робота містить 2 теоретичних питання та 5 практичних завдань.
Обсяг відповіді на кожне теоретичне питання: не менше, ніж 1 сторінка машинописного тексту. Текст відповіді повинен бути виконаний самостійно, а не скопійованим з навчального посібника.
Лабораторна робота №1. Операції над множинами. Алгебра множин. Властивості бінарних відношень. Класи еквівалентності. Порядок множини.
Лабораторна робота №2. Способи задавання функцій. Аналіз властивостей функцій. Задачі комбінаторики.
Лабораторна робота №3. Аналіз висловів за таблицями істинності. Доказ висловів. Логіка предикатів. Аксіоми висловів та булеві функції.
Лабораторна робота №4. Запис ЗДНФ та ЗКНФ. Перемикачі. Мінімізація булевих функцій. Задавання та зображення графів.
Лабораторна робота №5. Визначення шляхів та маршрутів графів. Визначення найкоротшого шляху графу. Визначення ізоморфних графів.
Термін надання виконаної контрольної роботи на перевірку – не пізніше, ніж за місяць до початку сесії.
Форми контрольних заходів та оцінювання результатів навчання
Для денної форми здобуття освіти
Поточний контроль полягає у виконанні
1) 15-и індивідуальних поточних завдань. Індивідуальні поточні завдання полягають в виконанні типових завдань відповідно до мети та завдань лабораторних занять. Бездоганне виконання індивідуальних поточних завдань №1 – №8 оцінюється по 5 балів за кожне, №9 – №11 оцінюється по 3 бали за кожне, №12 – №15 оцінюється по 4 бали за кожне.
2) розрахунково-графічної роботи. Бездоганне виконання оцінюється у 10 балів. Захист роботи – 5 балів.
3) двох модульних контрольних робіт. Модульні контрольні роботи складаються з практичної частини та проводяться у формі виконання наданих викладачем завдань. Бездоганне виконання кожної модульної контрольної роботи становить 10 балів.
Підсумковий контроль – екзамен. Максимальна оцінка, яку може отримати студент – 100 балів.
Для заочної форми здобуття освіти
Виконання та захист лабораторних робіт оцінюється у 30 балів.
Захист розрахунково-графічної роботи. Бездоганне виконання розрахунково-графічної роботи оцінюється у 10 балів. При її захисті студент може отримати до 5 балів.
Захист контрольної роботи. Бездоганне виконання контрольної роботи оцінюється у 40 балів. При її захисті студент може отримати до 15 балів.
Підсумковий контроль – екзамен. Максимальна оцінка, яку може отримати студент – 100 балів.