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

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

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

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

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

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

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

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

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

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

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

Знання

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

Уміння

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рейтинг студента заочної форми навчання складається з балів, що він отримує за: 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 до 5 балів, – конспект лекції, оформлений за ДСТУ, ЕСТД - 1 бал.

Штрафні бали

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

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

Міжсесійна атестація Не передбачається.

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

RD = 1*r_пр1+1*r_пр2+2*r_{компр1-2}+13*r_мкр=2+3+28+133 + (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. Переведення рейтингових балів до оцінок за університетською шкалою

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