Спеціальні розділи математики. Частина 1. Дискретна математика - СИЛАБУС НАВЧАЛЬНОЇ ДИСЦИПЛІНИ

Реквізити навчальної дисципліни

Програма навчальної дисципліни

Опис навчальної дисципліни, її мета, предмет вивчання та результати навчання

Загальні компетенції: (ЗК1) - здатність до абстрактного мислення, аналізу та синтезу. (ЗК2) - здатність застосовувати знання у практичних ситуаціях. Спеціальні (фахові, предметні) компетентності:(ФК-11) - здатність до аналізу, синтезу і оптимізації інформаційних систем та технологій з використанням математичних та імітаційних моделей і методів; (ФК13) - здатність проводити обчислювальні експерименти, порівнювати результати експериментальних даних і отриманих рішень; (ФК-15) - здатність до алгоритмічного та логічного мислення. Програмні результати навчання: (ПРН1) - знати лінійну та векторну алгебру, диференціальне та інтегральне числення, теорію функцій багатьох змінних, теорію рядів, диференціальні рівняння для функції однієї та багатьох змінних, операційне числення, теорію ймовірностей та математичну статистику в обсязі, необхідному для розробки та використання інформаційних систем, технологій та інфокомунікацій, сервісів та інфраструктури організації. (ПРН2) - застосовувати знання фундаментальних і природничих наук, системного аналізу та технологій моделювання, стандартних алгоритмів та дискретного аналізу при розв’язанні задач проектування і використання інформаційних систем та технологій. (ПРН4) - проводити системний аналіз об’єктів проектування та обґрунтовувати вибір структури, алгоритмів та способів передачі інформації в інформаційних системах та технологіях.

Опис дисципліни

Силабус освітнього компонента «Спеціальні розділи математики. Частина 1. Дискретна математика» належить до нормативних дисциплін циклу загальної підготовки зі спеціальності 126 – Інформаційні системи та технології освітньої програми Інтегровані інформаційні системи. Під час навчання студенти знайомляться з основними поняттями дискретної математики. На практичних заняттях навчаються вирішувати задачі, а також використовувати мову Python для програмування задач з множинами, відношеннями, графами, булевими функціями, граматиками, автоматами та математичною логікою. Передбачено контроль якості отриманих знань у вигляді тестової та модульної контрольних робіт.

Предмет навчальної дисципліни: дискретні процеси та системи.

Міждисциплінарні зв’язки

Дисципліна «Спеціальні розділи математики. Частина 1. Дискретна математика» базується на наступних дисциплінах: вища математика (операції над матрицями) та є основою для наступних дисциплін: алгоритми та структури даних (задачі на графах, дерева, автомати, зокрема машина Тюрінга), основи програмування (булева алгебра, теорія граматик та автоматів), теорія ймовірностей (теорія множин, теорія автоматів), архітектура комп’ютера (булева алгебра, мінімізація булевих функцій), бази даних (відношення), теорія інформації та кодування (булева алгебра), теорія прийняття рішень (бінарні відношення).

Мета навчальної дисципліни

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

Програмні результати навчання, на формування та покращення яких спрямована дисципліна: (ПРН1) - Знати лінійну та векторну алгебру, диференціальне та інтегральне числення, теорію функцій багатьох змінних, теорію рядів, диференціальні рівняння для функції однієї та багатьох змінних, операційне числення, теорію ймовірностей та математичну статистику в обсязі, необхідному для розробки та використання інформаційних систем, технологій та інфокомунікацій, сервісів та інфраструктури організації. (ПРН2) - Застосовувати знання фундаментальних і природничих наук, системного аналізу та технологій моделювання, стандартних алгоритмів та дискретного аналізу при розв’язанні задач проєктування і використання інформаційних систем та технологій. (ПРН4)* - Проводити системний аналіз об’єктів проектування та обґрунтовувати вибір структури, алгоритмів та способів передачі інформації в інформаційних системах та технологіях.

Основні завдання навчальної дисципліни

Знання

•методи теорії множин та відношень; •алгоритми мінімізації булевих функцій; •алгоритми пошуку найкоротшого шляху на графах та побудови кістякового дерева; •синтез автоматів для розпізнавання формальних мов; •застосування правил виведення в логіках висловлювань та предикатів.

Уміння

•застосовувати множини, відношення, графи для представлення типових задач; •зведення складних задач до типових задач на графах, множинах, відношеннях; •описувати формальні мови за допомогою граматик та системи за допомогою автоматів.

Пререквізити та постреквізити дисципліни (місце в структурно-логічній схемі навчання за відповідною освітньою програмою)

Пререквізити

Мати базові знання з математики.

Постреквізити

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

Зміст навчальної дисципліни

Лекційні заняття

Розділ 1. Алгебра множин 1.1 Визначення множин та способи їх представлення 1.2 Операції над множинами та їх властивості 1.3 Потужність, покриття та розбиття множин Розділ 2. Відношення та функції 2.1 Основні поняття теорії відношень. Властивості відношень 2.2 Види відношень. Замикання відношень 2.3 Функціональні відображення та їх властивості. Поняття функції Розділ 3. Алгебри. Булева алгебра 3.1 Алгебраїчні системи, алгебри та моделі 3.2 Булеві функції та їх властивості 3.3 Класи булевих функцій 3.4 Задача мінімізації булевих функцій Розділ 4. Основи теорії графів 4.1. Поняття та види графів 4.2. Задача про найкоротший шлях 4.3. Поняття дерева, способи обходу дерев 4.4. Задача побудови кістякового дерева Розділ 5. Основи теорії граматик та формальних мов 5.1. Основні поняття теорії граматик 5.2. Типи граматик та дерева виведення Розділ 6. Теорія автоматів 6.1. Основні поняття теорії автоматів 6.2. Скінченні, детерміновані та недетермінованих автомати Розділ 7. Основи математичної логіки 7.1. Логіка висловлювань 7.2. Логіка предикатів 7.3. Правила логічного виведення

Практичні заняття

Метою практичних занять є вирішення задач дискретної математики за допомогою програмних засобів. 1.Підготовка до застосування інструментальних засобів програмування на мові Python. 2.Основні структури даних мови програмування Python. 3.Представлення множин за допомогою програмних засобів. Представлення та операції над множинами за допомогою бітових рядків 4.Способи задання відношень та операції над відношеннями. Перевірка властивостей відношення та замикання відношень. 5.Побудова таблиці істинності булевої функції. Побудова досконалої диз’юнктивної та кон’юнктивної форм булевої функції. 6.Закони логіки висловлювань. Застосування правил виведення в логіці висловлювань. Дослідження методу резолюцій та принципів логічного програмування. 7.Програмне представлення графу та перевірка його на ейлеровість. Пошук найкоротшого шляху в графі. Представлення арифметичного виразу у прямому та зворотному польському записі. 8.Формальні породжувальні граматики. Ієрархія Хомскі. Скінченні автомати з виходом та без виходу.

Навчальні матеріали та ресурси

Базова література

1.Нікольський Ю.В., Пасічник В.В., Щербина Ю.М. Дискретна математика. К.: Видавнича група BHV, 2007, 368 с. 2.Капітонова Ю.В., Кривий С.Л. Летичевський О.А., Луцький Г.М., Печурін М.К. Основи дискретної математики. К.: Наукова думка, 2002, 560 с. 3.Таран Т.А. Основи дискретної математики. К.: «Просвіта», 2003, 288 с. 4.Павлов В.І. Логіка у запитаннях, відповідях і аргументаціях./ Навчальний посібник. К.:Центр учбової літератури, 2008. - 408 с. 5.Бондаренко М.Ф., Білоус Н.В., Руткас А.Г. Комп’ютерна дискретна математика.- Харків: Компанія СМІТ, -2004. – 480 с.

Допоміжна література

1.Андерсон Д. Дискретна математика і комбінаторика. 2003, 968 с. 2.Спеціальні розділи математики – 1. Дискретна математика. Методичні вказівки до виконання комплексних контрольних робіт (ККР). [Електронне видання] / Уклад.: Я.Ю. Дорогий – К.: НТУУ «КПІ», 2012. – 36 с. 3.Susanna S. Epp. Discrete Mathematics with Applications. Cengage Learning, 2019, 1057p.

Навчальний контент

Методика опанування навчальної дисципліни (освітнього компонента)

Лекційні заняття

Лекційні заняття (денна форма навчання)

1.Лекція 1. Основні поняття теорії множин Поняття множини, підмножини. Способи представлення множин. Порожня та універсальні множини. Булеан. Операції над множинами. Діаграми Ейлера-Венна. Властивості операцій над множинами. Потужність множин. Покриття і розбиття множин. Декартів добуток множин і його потужність. Лічильні множини та їхні властивості. Теорема Кантора. Методи доведення тотожностей в алгебрі множин. Л. ( 1– с.37-39, 4 – с. 6-15) Завдання на СРС. Комп’ютерне подання множин. Генерування розбиттів множини.

2. Лекція 2. Основні поняття теорії відношень Поняття відношення. Місність відношення. Бінарні відношення. Поле відношення. Обернене відношення. Способи представлення бінарних відношень. Операції над бінарними відношеннями: об’єднання, перетин, доповнення, різниця, композиція. Універсальна множина відношення. Властивості бінарних відношень: рефлексивність, симетричність, транзитивність. Степінь відношення. Л. ( 1– с. 185-188) (4 – с.15-20) Завдання для СРС Використання відношень у базах даних.

3. Лекція 3. Відношення еквівалентності та порядку Відношення еквівалентності. Класи еквівалентності. Зв’язок між відношенням еквівалентності та розбиттям. Відношення порядку. Частковий порядок. Строгий порядок. Порівнянні та непорівнянні елементи. Алгоритм топологічного сортування. Л.(1– с. 195-197, 4 – с. 20-25) Завдання для СРС. Використання топологічного сортування для планування задач.

4. Лекція 4. Замикання відношень. Функціональні відображення Максимальний та мінімальний елементи. Замикання відношень. Симетричне, рефлексивне та транзитивне замикання, способи їх одержання. Діаграми Гассе. Побудова транзитивного замикання відношення. Алгоритм Уоршалла. Л.(1 – с.188-195, 197-202, 4 – с. 25-30, 5 – с. 25-37) Завдання для СРС. Розбиття частково впорядкованої множини на ланцюги. Матроїди та їх застосування.

5. Лекція 5. Функціональні відображення. Функціональні відображення. Області значень та визначення. Образ та прообраз. Сур’єктивне, ін’єктивне та бієктивне відображення. Функція. Аргументи та значення функцій. Функції-константи. Місність функції. Обернені функції. Композиція функцій. Способи подання функцій. Функціонали. Л.( 1 – с.235-252) Завдання для СРС. Алгебраїчні системи, алгебри та моделі.

6. Лекція 6. Основи булевої алгебри. Булеві змінні та функції. Набори. Місність функцій. Таблиця істинності булевих функцій. Функції нуля та однієї змінних. Булеві функції двох змінних. Властивості булевих функцій. Диз’юнктивна нормальна форма. Досконала диз’юнктивна нормальна форма. Кон’юнктивна нормальна форма. Досконала кон’юнктивна нормальна форма. Способи їх отримання. Л.( 1– с.235-252) Завдання для СРС. Поліноміальне представлення булевих функцій. Поліном Жегалкіна.

7. Лекція 7. Задача мінімізації булевих функцій Задача та мета мінімізації булевих функцій. Операції склеювання та поглинання. Скорочена, тупикова та мінімальна диз’юнктивні нормальні форми. Загальний алгоритм мінімізації булевих функцій. Метод Квайна-Мак-Класкі. Пошук мінімальної диз’юнктивної нормальної форми. Л. ( 1 – с. 252-267, 2 - с. 102-108, 128-139) Завдання для СРС. Мінімізація булевих функцій методом Блейка.

8. Лекція 8. Поняття та види графів Поняття графа. Неорієнтовані та орієнтовані графи. Мультиграфи. Інцидентність та суміжність. Види графів. Способи представлення графів. Підграфи. Операції на графах: об’єднання, перетин, видалення вершини, стягування ребра. Зв’язність графів. Компоненти зв’язності. Діаметр, центр, радіус графа. Степінь вершин. Цикломатичне число. Л. (1–с.88-100) Завдання для СРС. Автоматична генерація графів.

9. Лекція 9. Задача про найкоротший шлях. Поняття дерева Поняття шляхів та циклів в орієнтованому та неорієнтованому графах. Визначення наявності шляхів заданої довжини. Ейлерові та Гамільтонові графи. Ізоморфні графи. Планарні графи. Теорема Ейлера. Зважені графи. Задача про найкоротший шлях. Алгоритм Дейкстри. Поняття дерева. Властивості дерев. Корінь, внутрішні вершини дерев. Глибина вершини та висота дерева. Збалансованість дерева. Л. (1– с.100-126) Завдання для СРС. Задача розфарбування графів.

10. Лекція 10. Способи обходу дерев. Задача побудови кістякового дерева Кістякове дерево. Алгоритм Пріма. Алгоритм Краскала. Способи обходу дерева: прямий, внутрішній та зворотній. Відповідні форми запису виразів: префіксний, інфіксний та постфіксний. Обчислення значення виразів, поданих у різних формах. Л. (1– с.150-160, 175-177) Завдання для СРС. Дерево прийняття рішень.

11. Лекція 11. Основні поняття теорії граматик. Типи граматик Поняття символу, алфавіту, слова. Конкатенація та степінь. Поняття граматики. Виведення слів. Породжувана мова. Типи граматик та відповідні їм типи мов: без обмежень, контекстно-залежні, контекстно-вільні, регулярні. Співвідношення між граматиками різного типу. Л. (1– с.276-281) Завдання для СРС. Визначення типу граматики та побудова її ланцюжків.

12. Лекція 12. Дерева виведення. Основні поняття теорії автоматів. Синтез детермінованих та недетермінованих автоматів Дерева виведення. Нотація Бекуса-Наура. Поняття скінченного автомату. Способи представлення автомата. Автоматне відображення та його властивості. Скінченні автомати без виходу. Розпізнавання мов за допомогою автомата. Недетерміновані автомати та еквівалентні їм детерміновані. Алгебра Кліні. Подання мов за допомогою автоматів. Л. (1 – с. 283-310) Завдання для СРС. Побудова граматики мови, яку розпізнає заданий автомат. Машина Тюрінга.

13. Лекція 13. Логіка висловлювань. Логіка предикатів Поняття висловлювання. Атомарні та складні висловлювання. Логічні операції. Формули логіки висловлювань. Таблиці істинності складних висловлювань. Алгебра висловлювань. Інтерпретації, тавтології та суперечності. Виконувані формули. Закони логіки висловлювань. Речення зі змінними. Основні поняття логіки предикатів. Квантори загальності й існування. Формули логіки предикатів. Зв’язані та вільні змінні. Закони логіки предикатів. Л. ( 1– с.9-25, 5 – с. 168-181) Завдання для СРС. Випереджена нормальна форма.

14. Лекція 14. Правила логічного виведення. Префіксна нормальна форма. Алгоритм зведення до префіксної нормальної форми. Логічне виведення. Критерій логічного виведення. Принцип прямої дедукції. Правила виведення в логіці висловлювань. Метод резолюцій. Алгоритм методу резолюцій. Логічні виведення в логіці предикатів.
    Л. ( 1 – с.26-32) Завдання для СРС. Методи доведення теорем.

15. Лекція 15. Основні поняття теорії автоматів. Скінченні автомати, автомати Мілі і Мура. Автоматні відображення. Детерміновані та недетерміновані автомати. Л. (1 – с. 276-311) Завдання для СРС. Методи подання скінченних автоматів. 16.Лекція 16. Мови та автомати Алгебра Кліні. Подання мов в автоматах. Класифікація мов за Н.Хомскі. Л. (1 – с. 276-311) Завдання для СРС. Приклади регулярних, безконтексних та контексних мов.

16. Лекція 17. Елементи теорії алгоритмів. Поняття алгоритму. Типи універсальних алгоритмічних моделей. Машини Тюрінга. Алгоритмчно нерозв’язні проблеми. Л. (1 – с. 276-311) Завдання для СРС. Знайомство з теорією рекурсивних функцій. 18 Лекція 18. Елементи теорії складності алгоритмів. Алгоритми та складність обчислень. Масові задачі. Часова та просторова складність обчислень. Поліноміальні та експоненціальні алгоритми. Л. (1 – с. 276-311) Завдання для СРС. Модель RAM для оцінки складності алгоритмів.

Лекційні заняття (заочна форма навчання)

1. Лекція 1. Основні поняття теорії множин та відношень Поняття множини, підмножини. Способи представлення множин. Порожня та універсальні множини. Операції над множинами. Діаграми Ейлера-Венна. Властивості операцій над множинами. Потужність множин. Декартів добуток множин і його потужність. Поняття відношення. Бінарні відношення. Поле відношення. Обернене відношення. Способи представлення бінарних відношень. Операції над бінарними відношеннями. Універсальна множина відношення. Властивості бінарних відношень: рефлексивність, симетричність, транзитивність. Відношення еквівалентності. Відношення порядку. Частковий порядок. Строгий порядок. Порівнянні та непорівнянні елементи. Максимальний та мінімальний елементи. Замикання відношень. Симетричне, рефлексивне та транзитивне замикання, способи їх одержання. Алгебраїчні операції та їх властивості Л. ( 1– с.185-202, 4 – с. 6-30) Завдання на СРС. Комп’ютерне подання множин. Покриття і розбиття множин. Генерування розбиттів множини. Булеан. Теорема Кантора. Степінь відношення. Використання відношень у базах даних. Класи еквівалентності. Зв’язок між відношенням еквівалентності та розбиттям. Алгоритм топологічного сортування. Діаграми Гассе. Побудова транзитивного замикання відношення. Алгоритм Уоршалла.
2. Лекція 2. Основи булевої алгебри. Булеві змінні та функції. Набори. Місність функцій. Таблиця істинності булевих функцій. Функції нуля та однієї змінних. Булеві функції двох змінних. Властивості булевих функцій. Диз’юнктивна нормальна форма. Досконала диз’юнктивна нормальна форма. Кон’юнктивна нормальна форма. Досконала кон’юнктивна нормальна форма. Способи їх отримання. Задача та мета мінімізації булевих функцій. Операції склеювання та поглинання. Скорочена, тупикова та мінімальна диз’юнктивні нормальні форми. Загальний алгоритм мінімізації булевих функцій. Метод Квайна-Мак-Класкі. Пошук мінімальної диз’юнктивної нормальної форми. Л. ( 1– с. 235-267, 2 – с. 102-108, 128-139) Завдання для СРС. Функціональні відображення. Алгебраїчні системи, алгебри та моделі. Поліноміальне представлення булевих функцій. Поліном Жегалкіна. Мінімізація булевих функцій методом Блейка.
3. Лекція 3. Основи теорії графів Поняття графа. Неорієнтовані та орієнтовані графи. Види графів. Способи представлення графів. Підграфи. Операції на графах. Зв’язність графів. Компоненти зв’язності. Діаметр, центр, радіус графа. Степінь вершин. Цикломатичне число. Поняття шляхів та циклів в орієнтованому та неорієнтованому графах. Визначення наявності шляхів заданої довжини. Ейлерові та Гамільтонові графи. Ізоморфні графи. Планарні графи. Теорема Ейлера. Зважені графи. Задача про найкоротший шлях. Поняття дерева. Властивості дерев. Кістякове дерево. Способи обходу дерева: прямий, внутрішній та зворотній. Відповідні форми запису виразів: префіксний, інфіксний та постфіксний. Обчислення значення виразів, поданих у різних формах. Л.(1 – с.88-126, 150-160, 175-177) Завдання для СРС. Алгоритми Дейкстри, Пріма, Краскала. Основні поняття теорії граматик. Основні поняття теорії автоматів. Синтез детермінованих та недетермінованих автоматів. Розпізнавання мов за допомогою автомата. Логіка висловлювань. Логіка предикатів. Правила логічного виведення.

Практичні заняття

Практичні заняття (денна форма навчання)

1. Підготовка до застосування інструментальних засобів програмування на мові Python.
2. Основні структури даних мови програмування Python.
3. Представлення множин за допомогою програмних засобів. Представлення та операції над множинами за допомогою бітових рядків
4. Способи задання відношень та операції над відношеннями. Перевірка властивостей відношення та замикання відношень.
5. Побудова таблиці істинності булевої функції. Побудова досконалої диз’юнктивної та кон’юнктивної форм булевої функції.
6. Закони логіки висловлювань. Застосування правил виведення в логіці висловлювань. Дослідження методу резолюцій та принципів логічного програмування.
7. Програмне представлення графу та перевірка його на ейлеровість. Пошук найкоротшого шляху в графі. Представлення арифметичного виразу у прямому та зворотному польському записі.
8. Формальні породжувальні граматики. Ієрархія Хомскі. Скінченні автомати з виходом та без виходу.

Практичні заняття (заочна форма навчання)

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

Самостійна робота студента

Самостійна робота студента (денна форма навчання)

1. Комп’ютерне подання множин. Генерування розбиттів множини
2. Використання відношень у базах даних
3. Використання топологічного сортування для планування задач
4. Розбиття частково впорядкованої множини на ланцюги. Матроїди та їх застосування
5. Алгебраїчні системи, алгебри та моделі
6. Поліноміальне представлення булевих функцій. Поліном Жегалкіна
7. Мінімізація булевих функцій методом Блейка
8. Автоматична генерація графів
9. Задача розфарбування графів
10. Дерево прийняття рішень
11. Визначення типу граматики та побудова її ланцюжків
12. Побудова граматики мови, яку розпізнає заданий автомат. Машина Т’юрінга
13. Випереджена нормальна форма
14. Методи доведення теорем

Самостійна робота студента (заочна форма навчання)

1. Комп’ютерне подання множин. Покриття і розбиття множин. Генерування розбиттів множини. Булеан. Теорема Кантора.
2. Степінь відношення. Використання відношень у базах даних. Класи еквівалентності. Зв’язок між відношенням еквівалентності та розбиттям. Алгоритм топологічного сортування. Діаграми Гассе. Побудова транзитивного замикання відношення. Алгоритм Уоршалла.
3. Функціональні відображення.
4. Алгебраїчні системи, алгебри та моделі
5. Поліноміальне представлення булевих функцій. Поліном Жегалкіна. Мінімізація булевих функцій методом Блейка.
6. Основні поняття теорії граматик.
7. Основні поняття теорії автоматів. Синтез детермінованих та недетермінованих автоматів. Розпізнавання мов за допомогою автомата.
8. Логіка висловлювань.
9. Логіка предикатів.
10. Правила логічного виведення.

Модульна контрольна робота (заочна форма навчання)

• 1.Означення множини. Способи завдання множин. Порожня множина, універсум (універсальна множина), булеан. Потужність множини. Потужність булеана скінченої множини. Операції над множинами: означення, діаграми, приклади. Властивості операцій над множинами. Декартовий добуток. Потужність декартового добутку.
• 2. Відношення. n-арне відношенням на множині А. Область визначення відношення. Множина значень відношення. Повне відношення. Тотожне відношення. Порожнє відношення. Обернене відношення до даного відношення. Композиція відношень R та S. Способи завдання відношень. Властивості відношень (рефлексивне, антирефлексивне (іррефлексивне), симетричне, асиметричне, антисиметричне, транзитивне). -3. Функціональне відношення, область визначення, область значень. Всюди визначене відношення. Прообраз (аргумент, змінна), образ функціонального відношення. Відображення. Типи відображень (сюр’єкція, ін’єкція, бієкція). Композиція відображень. -4.Відношення еквівалентності, класи еквівалентності. Матриця та граф відношення еквівалентності. Відношення порядку строгого та нестрогого. Множина упорядкована. Множина лінійно впорядкована. Незрівнянні елементи. Множина частково впорядкована. -5.Функції алгебри логіки або булеві функції, кортеж. Булеві функції однієї змінної. Булеві функції двох змінних. Рівносильні формули. Властивості булевих функцій. Двоїста функція, самодвоїста функція. -6.Диз’юнктивні нормальні форми, елементарна кон’юнкція, ранг. Досконала диз’юнктивна нормальна форма, алгоритми побудови та її властивості. Кон’юнктивні нормальні форми, елементарна диз’юнкція, ранг. Досконала кон’юнктивна нормальна форма, алгоритми побудови та її властивості. Мінімальні диз’юнктивні та кон’юнктивні нормальні форми. -7.Алгебра Жегалкіна. Поліномом Жегалкіна та його побудова. -8.Лінійна функція. Монотонна функція. Функція, що зберігає 0 чи зберігає 1. Система функцій функціонально повна. Система функцій мінімально повний базис. -9.Основні поняття теорії графів. Граф. Порядок графу. Суміжні та інцидентні об’єкти. Граф простий, мультиграф, псевдограф. Орієнтований граф. Способи задання графів (список ребер, матриця суміжності, матриця інцидентності) для неорієнтованих та орієнтованих графів. Ізоморфізм графів. -10.Операції та властивості графів. Степінь вершин. Вершина ізольована, висяча. Граф однорідний степеня k. Повний граф. Півстепінь виходу, півстепінь заходу. Дводольний граф. Маршрути, ланцюги та цикли. Простий ланцюг. Граф ациклічний. Шлях. Контур. Метричні характеристики графів: ланцюг геодезичний, ярус, діаметр, радіус, множина центрів. -11.Зв’язність графів. Дві вершини зв’язані. Граф зв’язний. Зв’язність графу. Компонента зв’язності. Число вершинної зв’язності. Число реберної зв’язності. Точка з’єднання. -12.Обхід графів: вглиб та вшир. Їх складність. Топологічне сортування. Алгоритми пошуку найкоротших шляхів: Алгоритм Дейкстри. Обмеження алгоритму Дейкстри та його складність. -13.Ейлеровий цикл. Ейлеровий шлях. Гамільтоновий цикл, гамільтонів маршрут.

Політика та контроль

Політика навчальної дисципліни (освітнього компонента)

Система вимог, які ставляться перед студентом: •на лекції викладач користується власним презентаційним матеріалом; використовує Google Classroom для викладання матеріалу поточної лекції, додаткової інформації та інше; •питання на лекції задаються у відведений для цього час; •заохочувальні бали виставляються за: рішення задач на очному практичному занятті; участь у факультетських та інститутських олімпіадах з навчальних дисциплін, участь у конкурсах робіт, підготовка оглядів наукових праць тощо. Кількість заохочуваних балів не більше 5; •штрафні бали виставляються за некоректну поведінку; для денного навчання штрафні бали виставляються за невчасне подання практичної роботи до захисту. Кількість штрафних балів не більше 10.

Види контролю та рейтингова система оцінювання результатів навчання (РСО)

Рейтинг студента очної форми навчання з дисципліни складається з балів, що він отримує за: 1.виконання практичних робіт; 2.розв’язування та програмування задач на практичних заняттях; 3.заохочувальні та штрафні бали.

Рейтинг студента заочної форми навчання складається з балів, що він отримує за: 1.вирішення задач та програмування на практичних заняттях; 2.виконання модульної контрольної роботи; 3.заохочувальні бали.

Система рейтингових балів та критерії оцінювання

Система рейтингових балів та критерії оцінювання Денна та заочна форма навчання:

Практичні заняття:

«відмінно», повна відповідь на питання під час захисту (не менш ніж 90% потрібної інформації), практичне завдання виконано правильно – 8 балів (3 за 1-шу та 2-гу роботи); «добре», достатньо повна відповідь на питання під час захисту (не менш ніж 75% потрібної інформації), практичне завдання виконане правильно – 5 балів (2 для 1 та 2 роботи); «задовільно», неповна відповідь на питання під час захисту (не менш ніж 60% потрібної інформації), незначні помилки в виконанні практичного завдання – 2 бали (1 для 1 та 2 роботи); «незадовільно», незадовільна відповідь та/або значні помилки в розв’язанні практичного завдання – 0 балів.

Модульні контрольні роботи:

«відмінно», повна відповідь (не менш ніж 90% потрібної інформації), завдання розв’язане без помилок, дії обґрунтовано – 18-20 балів; «добре», достатньо повна відповідь (не менш ніж 75% потрібної інформації), завдання розв’язано без значних помилок – 14-18 балів; «задовільно», неповна відповідь, в деяких задачах можуть бути присутні значні помилки, але не менше 60% розв’язано правильно – 10-14 балів; «незадовільно», незадовільна відповідь (неправильний розв’язок задач), потребує обов’язкового повторного написання в кінці семестру – 0-10 балів.

Заохочувальні бали

• за виконання творчих робіт з кредитного модуля (наприклад, участь у факультетських та інститутських олімпіадах з навчальних дисциплін, участь у конкурсах робіт, підготовка оглядів наукових праць тощо); за активну роботу на очному практичному занятті 1-2 бали, але в сумі не більше 10; – за активну роботу на лекції 1-2 бали, але в сумі не більше 10; – презентації розв’язання задачі – від 1 до 5 балів, – конспект лекції, оформлений за ДСТУ, ЕСТД - 1 бал.

Штрафні бали

За некоректну поведінку на заняттях в сумі не більше -10 балів.

Календарний рубіжний контроль

Міжсесійна атестація (денна форма навчання)

За результатами навчальної роботи за перші 7 тижнів максимально можлива кількість балів – 8 балів (2 практичних завдання, 2 заохочувальних бали). На першій атестації (8-й тиждень) студент отримує «зараховано», якщо він захистив 2 практичних завдання.

За результатами 13 тижнів навчання максимально можлива кількість балів – 34 бали (5практичних завдань, 4 заохочувальні бали). На другій атестації (14-й тиждень) студент отримує «зараховано», якщо він захистив 5 практичних завдань.

Максимальна сума вагових балів контрольних заходів протягом семестру складає: RD = 2*r_{практ1-2} + 6*r_{практ3-8} +3*r_зад + (rз - rш) = 23 + 68 + 3*2 + (rз - rш)= 60 + (rз - rш), де r_{практ1-2} – бал за 1 та 2 практичне завдання (0…3); r_{практ3-8} – бал за практичні завдання з 3 по 8 (0…8); r_зад – бали за розв’язання задач (0…2); rз – заохочувальні бали (0…5); rзш – штрафні бали (0…10).

Міжсесійна атестація (заочна форма навчання)

Не передбачається.

Максимальна сума вагових балів контрольних заходів протягом семестру складає:

RD = 1*r_пр1+1*r_пр2+2*r_{компр1-2}+13*r_мкр=2+3+28+133 + (rз - rш)= 60 + (rз - rш), де r_пр1 – бал за математичний розв’язок 1-го практичного завдання (0…2); r_пр2 – бал за математичний розв’язок 2-го практичного завдання (0…3); r_{компр1-2} – бал за комп’ютерний розв’язок 1-го та 2-го практичного завдання (0…8); r_мкр – бал за виконання одного завдання з МКР (0…3); rз – заохочувальний бал (0…10); rш - штрафний бал (0…10).

Екзамен

Максимальна сума балів стартової складової дорівнює 40 балів. Необхідною умовою допуску до екзамену є виконання всіх практичних робіт, модульної контрольної роботи і стартовий рейтинг не менше 25 балів. На протезі семестру студенти готуються до письмового екзамену. Кожний білет містить два теоретичних і два практичних питання.

Система оцінювання питань

Теоретичні питання

• «відмінно», повна відповідь (не менше 90% потрібної інформації) – 9-10 балів;
• «добре», достатньо повна відповідь (не менше 75% потрібної інформації, або незначні неточності) – 7-8 балів;
• «задовільно», неповна відповідь (не менше 60% потрібної інформації та деякі помилки) – 6 балів;
• «незадовільно», незадовільна відповідь – 0-5 балів.

Практичні питання

• «відмінно», повна відповідь (не менш ніж 90% потрібної інформації), завдання розв’язане без помилок, дії обґрунтовано – 14-15 балів;
• «добре», достатньо повна відповідь (не менш ніж 75% потрібної інформації), завдання розв’язано без значних помилок – 11-13 балів;
• «задовільно», неповна відповідь, в деяких задачах можуть бути присутні значні помилки, але не менше 60% розв’язано правильно – 9-10 балів;
• «незадовільно», незадовільна відповідь (неправильний розв’язок задач) – 0-8 балів.

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

Таблиця 1. Переведення рейтингових балів до оцінок за університетською шкалою

Додаткова інформація з дисципліни (освітнього компонента)

Перелік теоретичних питань, які виносяться на екзамен, наведено в Додатку 1.

Робочу програму навчальної дисципліни (Силабус): Складено професор, д.ф.-м.н., Дорошенко Анатолій Юхимович, доцент, к.т.н., с.н.с. Савчук Олена Володимирівна Ухвалено кафедрою ІСТ ( протокол № 16 від 12.06.2024 р.). Погоджено Методичною комісією факультету (протокол № 10 від 21.06.2024 р.)

Додаток 1

Перелік теоретичних питань на екзамен 1.Поняття множини. Способи представлення множин. Навести приклади. Поняття підмножини. Порожня та універсальні множини. Булеан. Навести приклади. 2.Операції над множинами: об’єднання, перетин, доповнення, різниця, симетрична різниця. Представлення за допомогою діаграм Ейлера-Венна. Навести приклади. 3.Властивості операцій над множинами. Навести приклади. 4.Скінченні та нескінченні множини. Потужність множин. Обчислення потужностей множин. Рівнопотужні множини. Навести приклади. 5.Покриття і розбиття множин. Навести приклади. Кортежі, елементи кортежів. Декартів добуток множин і його потужність. Навести приклади. 6.Лічильні множини та їхні властивості. Навести приклади. Теорема Кантора. 7.Методи доведення тотожностей в алгебрі множин. 8.Поняття відношення. Місність відношення. Бінарні відношення. Навести приклади. Поле відношення. Обернене відношення. 9. Способи представлення бінарних відношень. Навести приклади. 10.Операції над бінарними відношеннями: об’єднання, перетин, доповнення, різниця, композиція. Навести приклади. Універсальна множина відношення. 11.Властивості бінарних відношень. Навести приклади. 12.Степінь відношення. Відношення еквівалентності. Класи еквівалентності. Навести приклади. Зв’язок між відношенням еквівалентності та розбиттям. 13.Відношення порядку. Частковий порядок. Строгий порядок. Навести приклади. Порівнянні та непорівнянні елементи. Максимальний та мінімальний елементи. Топологічне сортування. 14.Замикання відношень. Симетричне, рефлексивне та транзитивне замикання, способи їх одержання. Навести приклади. 15.Діаграми Гассе. Побудова транзитивного замикання відношення. Алгоритм Уоршалла. 16.Функціональні відображення. Області значень та визначення. Образ та прообраз. Сур’єктивне, ін’єктивне та бієктивне відображення. Навести приклади.
17.Функція. Аргументи та значення функцій. Функції-константи. Місність функції. Обернені функції. Композиція функцій. Способи подання функцій. Функціонали. Навести приклади. 18.Поняття та складові алгебраїчної системи. Алгебри та моделі. Навести приклади. Групоїди, їхні властивості. Навести приклади. 19.Напівгрупа. Абелева напівгрупа. Підстановка. Моноїд. Група. Абелева група. Навести приклади. 20.Кільце. Властивості елементів кільця. Абелеве кільце. Поняття тіла та поля. Навести приклади. Алгебри Кантора та Буля. 21.Булеві змінні та функції. Набори. Місність функцій. Таблиця істинності. Функції нуля та однієї змінних. Навести приклади. 22.Булеві функції двох змінних. Навести приклади. 23.Властивості булевих функцій. 24.Класи булевих функцій: функції, що зберігають константу, двоїсті функції, лінійні функції, монотонні функції. Властивості двоїстості, самодвоїстість. 25.Суперпозиція булевих функцій. Замкнені класи булевих функцій. Функціонально повні системи. Навести приклади. 26.Диз’юнктивна нормальна форма. Досконала диз’юнктивна нормальна форма. Способи їх отримання. Навести приклади. 27.Кон’юнктивна нормальна форма. Досконала кон’юнктивна нормальна форма. Способи їх отримання. Навести приклади. 28.Задача мінімізації булевих функцій. Мета мінімізації булевих функцій. Операції склеювання та поглинання. Скорочена, тупикова та мінімальна диз’юнктивні нормальні форми. 29.Загальний алгоритм мінімізації булевих функцій. Метод Квайна-Мак-Класкі. Пошук мінімальної диз’юнктивної нормальної форми. 30.Поняття графа. Неорієнтовані та орієнтовані графи. Мультиграфи. Інцидентність та суміжність. Види графів. Навести приклади. 31.Способи представлення графів. Навести приклади. 32.Підграфи. Операції на графах: об’єднання, перетин, видалення вершини, стягування ребра. Навести приклади. 33.Поняття шляхів та циклів в орієнтованому та неорієнтованому графах. Визначення наявності шляхів заданої довжини. Ейлерові та Гамільтонові графи. 34.Зв’язність графів. Компоненти зв’язності. Діаметр, центр, радіус графа. Степінь вершин. Цикломатичне число. 35.Ізоморфні графи. Планарні графи. Теорема Ейлера. Зважені графи. 36.Задача про найкоротший шлях. Алгоритм Дейкстри. 37.Поняття дерева. Властивості дерев. Корінь, внутрішні вершини дерев. Глибина вершини та висота дерева. Збалансованість дерева. Навести приклади. 38.Каркасне дерево. Алгоритм Пріма. Алгоритм Краскала. Навести приклади. 39.Способи обходу дерева. Відповідні форми запису виразів. Навести приклади. 40.Поняття символу, алфавіту, слова. Конкатенація та степінь. Поняття граматики. Виведення. Породжувана мова. Навести приклади. 41.Типи граматик та відповідні типи мов. Дерева виведення. Нотація Бекуса-Наура. Навести приклади. 42.Поняття скінченного автомату. Навести приклади. Способи представлення автомата. 43.Автоматне відображення. Його властивості. Скінченні автомати без виходу. Навести приклади. Розпізнавання мов. 44.Недетерміновані автомати та еквівалентні їм детерміновані. Алгебра Кліні. Подання мов за допомогою автоматів. 45.Поняття висловлювання. Навести приклади. Атомарні та складні висловлювання. Логічні операції. 46.Формули логіки висловлювань. Таблиці істинності. Навести приклади. Алгебра висловлювань. 47.Інтерпретації, тавтології та суперечності. Виконувані формули. Навести приклади. Правило логічного виводу. 48.Закони логіки висловлювань. 49.Речення зі змінними. Логіка предикатів. Поняття логіки предикатів. Навести приклади. 50. Квантори загальності й існування. Формули логіки предикатів. Зв’язані та вільні змінні. Навести приклади. 51.Закони логіки предикатів.
52.Префіксна нормальна форма. Алгоритм зведення до префіксної нормальної форми. 53.Логічне виведення. Критерій логічного виведення. Принцип прямої дедукції. 54.Правила виведення в логіці висловлювань. 55.Метод резолюцій. Алгоритм методу резолюцій. 56.Логічні виведення в логіці предикатів.