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

Мета вивчення дисципліни: формування особистості студентів, розвиток їх інтелекту та здібностей до логічного мислення; забезпечення базової підготовки щодо вільного володіння поняттями та термінологією дискретної математики, використання методів дискретної математики для розв’язання прикладних задач, формування у студентів практичних навичок, які б дали змогу ефективно застосовувати знання та методи з дискретної математики у майбутній професійній роботі.
Практичне значення та використання отриманих знань: оволодіння сучасними методами дискретного аналізу; формування базових знань та володіння поняттями, термінологією дискретної математики; оволодіння методами розв’язання прикладних задач та проведення досліджень з використанням методів та засобів дискретної математики; створення необхідного теоретичного та практичного фундаменту для успішного оволодіння дисциплінами, які пов’язані з теоретичними дослідженнями в галузі програмування та інформаційних технологій; сприяння розвитку тих якостей особистості, що мають для майбутнього бакалавра особисте професійне значення в контексті інтеграції у європейський освітній простір.
Тематика та види навчальних занять
Для денної форми здобуття освіти
Лекційні заняття
Лекція 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) 15-ти індивідуальних поточних завдань. Індивідуальні поточні завдання виконуються письмово і полягають в розв’язуванні типових задач відповідно до мети та завдань практичних занять. Бездоганне виконання індивідуальних поточних завдань №1-2 оцінюється у 3 бала; №3-8 оцінюється у 4 бала, №9-10 оцінюється у 5 балів, №11-15 оцінюються у 4 бала,.
2) двох модульних контрольних робіт. Модульна робота складається з теоретичної частини та практичної частини. Бездоганне виконання кожної модульної контрольної роботи становить 20 балів.
Підсумковий контроль – екзамен. Екзаменаційний білет складається з теоретичної частини та практичної частини. Максимальна оцінка, яку може отримати студент – 100 балів.