СПЕЦІАЛЬНІ РОЗДІЛИ МАТЕМАТИКИ. ЧАСТИНА 1. ДИСКРЕТНА МАТЕМАТИКА - Робоча програма навчальної дисципліни (Силабус)

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

Рівень вищої освіти Перший (бакалаврський)
Галузь знань 12 Інформаційні технології
Спеціальність 126 Інформаційні системи та технології
Освітня програма Інтегровані інформаційні систем
Статус дисципліни Нормативна
Форма навчання очна(денна)/заочна
Рік підготовки, семестр 1 курс, осінній семестр
Обсяг дисципліни 6.0 кредитів, 180 годин (денна: 36 годин – лекції, 36 годин – лабораторні, 108 годин – СРС; заочна: 6 годин – лекції, 4 години – лабораторні, 138 годин – СРС)
Семестровий контроль/ контрольні заходи Екзамен
Розклад занять http://rozklad.kpi.ua/Schedules/ScheduleGroupSelection.aspx
Мова викладання Українська
Інформація про
керівника курсу / викладачів

Лектор: проф. Дорошенко Анатолій Юхимович,

a-y-doroshenko@ukr.net,

моб. +38(068)124-80-90

Лабораторні роботи: асистент Вітюк Альона Євгеніївна, alyonavityuk@gmail.com,

моб. +38(066)482-49-91
Розміщення курсу https://campus.kpi.ua

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

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

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

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

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

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

Програмні результати навчання

Знання:

  • методи теорії множин та відношень;

  • алгоритми мінімізації булевих функцій;

  • алгоритми пошуку найкоротшого шляху на графах та побудови кістякового дерева;

  • синтез автоматів для розпізнавання формальних мов;

  • застосування правил виведення в логіках висловлювань та предикатів.

Уміння:

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

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

  • описувати формальні мови за допомогою граматик та системи за допомогою автоматів.

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

Пререквізити: мати базові знання з математики.

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

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

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

Розділ 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. Правила логічного виведення

7.4 Елементи теорії алгоритмів та їх складності

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

Метою практичних занять є вирішення задач дискретної математики за допомогою програмних засобів.

  1. Підготовка до застосування інструментальних засобів програмування на мові Python.

  2. Основні структури даних мови програмування Python.

  3. Представлення множин за допомогою програмних засобів. Представлення та операції над множинами за допомогою бітових рядків

  4. Способи задання відношень та операції над відношеннями. Перевірка властивостей відношення та замикання відношень.

  5. Побудова таблиці істинності булевої функції. Побудова досконалої диз’юнктивної та кон’юнктивної форм булевої функції.

  6. Закони логіки висловлювань. Застосування правил виведення в логіці висловлювань. Дослідження методу резолюцій та принципів логічного програмування.

  7. Програмне представлення графу та перевірка його на ейлеровість. Пошук найкоротшого шляху в графі. Представлення арифметичного виразу у прямому та зворотному польському записі.

  8. Формальні породжувальні граматики. Ієрархія Хомскі. Скінченні автомати з виходом та без виходу.

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

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

  1. Нікольський Ю.В., Пасічник В.В., Щербина Ю.М. Дискретна математика. К.: Видавнича група BHV, 2007, 368с.

  2. Плотников А.Д. Дискретная математика: учеб. пособие. М.: Новое знание, 2005, 288 с.

  3. Новиков Ф.А. Дискретная математика для программистов: СПб.: Питер, 2009, 384 с.

  4. Капітонова Ю.В., Кривий С.Л. Летичевський О.А., Луцький Г.М., Печурін М.К. Основи дискретної математики. К.: Наукова думка, 2002, 560 с.

  5. Таран Т.А. Основы дискретной математики. К.: «Просвіта», 2003, 288с.

  6. Гетманова А.Д. Логика. М.: Высш.шк.. 1986, 288 с

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

  1. Андерсон Д. Дискретная математика и комбинаторика. СПб.:Вильямс, 2003, 968с.

  2. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М.: Энергоатомиздат, 1988, 480с

  3. Спеціальні розділи математики – 1. Дискретна математика. Методичні вказівки до виконання комплексних контрольних робіт (ККР). [Електронне видання] / Уклад.: Я.Ю. Дорогий – К.: НТУУ «КПІ», 2012. – 36 с.

  4. 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

Завдання для СРС. Приклади регулярних, безконтексних та контексних мов.
17

Лекція 17. Елементи теорії алгоритмів.

Поняття алгоритму. Типи універсальних алгоритмічних моделей. Машини Тюрінга. Алгоритмчно нерозв’язні проблеми.

Л. (1 – ст. 276-311

Завдання для СРС. Знайомство з теорією рекурсивних функцій.
18

Лекція 18. Елементи теорії складності алгоритмів.

Алгоритми та складність обчислень. Масові задачі. Часова та просторова складність обчислень. Поліноміальні та експоненціальні алгоритми.

Л. (1 – ст. 276-311

Завдання для СРС. Модель RAM для оцінки складності алгоритмів.

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

№ з/п Назва теми лекції та перелік основних питань
(перелік дидактичних засобів, посилання на літературу та завдання на СРС)
1

Лекція 1. Основні поняття теорії множин та відношень

Поняття множини, підмножини. Способи представлення множин. Порожня та універсальні множини. Операції над множинами. Діаграми Ейлера-Венна. Властивості операцій над множинами. Потужність множин. Декартів добуток множин і його потужність. Поняття відношення. Бінарні відношення. Поле відношення. Обернене відношення. Способи представлення бінарних відношень. Операції над бінарними відношеннями. Універсальна множина відношення. Властивості бінарних відношень: рефлексивність, симетричність, транзитивність. Відношення еквівалентності. Відношення порядку. Частковий порядок. Строгий порядок. Порівнянні та непорівнянні елементи. Максимальний та мінімальний елементи. Замикання відношень. Симетричне, рефлексивне та транзитивне замикання, способи їх одержання. Алгебраїчні операції та їх властивості

Л. ( 1– ст.185-202, 4 – ст. 6-30, 5– ст. 25-37)

Завдання на СРС. Комп’ютерне подання множин. Покриття і розбиття множин. Генерування розбиттів множини. Булеан. Теорема Кантора. Степінь відношення. Використання відношень у базах даних. Класи еквівалентності. Зв’язок між відношенням еквівалентності та розбиттям. Алгоритм топологічного сортування. Діаграми Гассе. Побудова транзитивного замикання відношення. Алгоритм Уоршалла.
2

Лекція 2. Основи булевої алгебри.

Булеві змінні та функції. Набори. Місність функцій. Таблиця істинності булевих функцій. Функції нуля та однієї змінних. Булеві функції двох змінних. Властивості булевих функцій. Диз’юнктивна нормальна форма. Досконала диз’юнктивна нормальна форма. Кон’юнктивна нормальна форма. Досконала кон’юнктивна нормальна форма. Способи їх отримання. Задача та мета мінімізації булевих функцій. Операції склеювання та поглинання. Скорочена, тупикова та мінімальна диз’юнктивні нормальні форми. Загальний алгоритм мінімізації булевих функцій. Метод Квайна-Мак-Класкі. Пошук мінімальної диз’юнктивної нормальної форми.

Л. ( 1– ст. 235-267, 2- ст 102-108, 128-139)

Завдання для СРС. Функціональні відображення. Алгебраїчні системи, алгебри та моделі. Поліноміальне представлення булевих функцій. Поліном Жегалкіна. Мінімізація булевих функцій методом Блейка.
3

Лекція 3. Основи теорії графів

Поняття графа. Неорієнтовані та орієнтовані графи. Види графів. Способи представлення графів. Підграфи. Операції на графах. Зв’язність графів. Компоненти зв’язності. Діаметр, центр, радіус графа. Степінь вершин. Цикломатичне число. Поняття шляхів та циклів в орієнтованому та неорієнтованому графах. Визначення наявності шляхів заданої довжини. Ейлерові та Гамільтонові графи. Ізоморфні графи. Планарні графи. Теорема Ейлера. Зважені графи. Задача про найкоротший шлях. Алгоритм Дейкстри. Поняття дерева. Властивості дерев. Кістякове дерево. Алгоритм Пріма. Алгоритм Краскала. Способи обходу дерева: прямий, внутрішній та зворотній. Відповідні форми запису виразів: префіксний, інфіксний та постфіксний. Обчислення значення виразів, поданих у різних формах.

Л.(1– 88-126, 150-160, 175-177)

Завдання для СРС. Основні поняття теорії граматик. Основні поняття теорії автоматів. Синтез детермінованих та недетермінованих автоматів. Розпізнавання мов за допомогою автомата. Логіка висловлювань. Логіка предикатів. Правила логічного виведення.

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

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

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

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

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

Денна форма навчання:

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

Заочна форма навчання:

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

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

  • Означення множини. Способи завдання множин. Порожня множина, універсум (універсальна множина), булеан. Потужність множини. Потужність булеана скінченої множини. Операції над множинами: означення, діаграми, приклади. Властивості операцій над множинами. Декартовий добуток. Потужність декартового добутку.

  • Відношення. n-арне відношенням на множині А. Область визначення відношення. Множина значень відношення. Повне відношення. Тотожне відношення. Порожнє відношення. Обернене відношення до даного відношення. Композиція відношень R та S. Способи завдання відношень. Властивості відношень (рефлексивне, антирефлексивне (іррефлексивне), симетричне, асиметричне, антисиметричне, транзитивне).

  • Функціональне відношення, область визначення, область значень. Всюди визначене відношення. Прообраз (аргумент, змінна), образ функціонального відношення. Відображення. Типи відображень (сюр’єкція, ін’єкція, бієкція). Композиція відображень.

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

  • Функції алгебри логіки або булеві функції, кортеж. Булеві функції однієї змінної. Булеві функції двох змінних. Рівносильні формули. Властивості булевих функцій. Двоїста функція, самодвоїста функція.

  • Диз’юнктивні нормальні форми, елементарна кон’юнкція, ранг. Досконала диз’юнктивна нормальна форма, алгоритми побудови та її властивості. Кон’юнктивні нормальні форми, елементарна диз’юнкція, ранг. Досконала кон’юнктивна нормальна форма, алгоритми побудови та її властивості. Мінімальні диз’юнктивні та кон’юнктивні нормальні форми.

  • Алгебра Жегалкіна. Поліномом Жегалкіна та його побудова.

  • Лінійна функція. Монотонна функція. Функція, що зберігає 0 чи зберігає 1. Система функцій функціонально повна. Система функцій мінімально повний базис.

  • Основні поняття теорії графів. Граф. Порядок графу. Суміжні та інцидентні об’єкти. Граф простий, мультиграф, псевдограф. Орієнтований граф. Способи задання графів (список ребер, матриця суміжності, матриця інцидентності) для неорієнтованих та орієнтованих графів. Ізоморфізм графів.

  • Операції та властивості графів. Степінь вершин. Вершина ізольована, висяча. Граф однорідний степеня k. Повний граф. Півстепінь виходу, півстепінь заходу. Дводольний граф. Маршрути, ланцюги та цикли. Простий ланцюг. Граф ациклічний. Шлях. Контур. Метричні характеристики графів: ланцюг геодезичний, ярус, діаметр, радіус, множина центрів.

  • Зв’язність графів. Дві вершини зв’язані. Граф зв’язний. Зв’язність графу. Компонента зв’язності. Число вершинної зв’язності. Число реберної зв’язності. Точка з’єднання.

  • Обхід графів: вглиб та вшир. Їх складність. Топологічне сортування. Алгоритми пошуку найкоротших шляхів: Алгоритм Дейкстри. Обмеження алгоритму Дейкстри та його складність.

  • Ейлеровий цикл. Ейлеровий шлях. Гамільтоновий цикл, гамільтонів маршрут.

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

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

Система вимог, які ставляться перед студентом:

  • відвідування лекційних та практичних занять є обов’язковою складовою вивчення матеріалу;

  • на лекції викладач користується власним презентаційним матеріалом; використовує Google Classroom для викладання матеріалу поточної лекції, додаткової інформації та інше;

  • питання на лекції задаються у відведений для цього час;

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

  • штрафні бали виставляються за: невчасне подання лабораторної роботи до захисту. Кількість штрафних балів не більше 18.

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

Рейтинг студента з дисципліни складається з балів, що він отримує за:

  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.

Міжсесійна атестація

За результатами навчальної роботи за перші 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ш)=2*3+6*8+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…15).

Екзамен:

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

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

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

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

«відмінно», повна відповідь (не менше 90% потрібної інформації) – 9-10 балів;

«добре», достатньо повна відповідь (не менше 75% потрібної інформації, або незначні неточності) – 7-8 балів;

«задовільно», неповна відповідь (не менше 60% потрібної інформації та деякі помилки) – 6 балів;

«незадовільно», незадовільна відповідь – 0-5 балів.

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

«відмінно», повна відповідь (не менш ніж 90% потрібної інформації), завдання розв’язане без помилок, дії обґрунтовано – 14-15 балів;

«добре», достатньо повна відповідь (не менш ніж 75% потрібної інформації), завдання розв’язано без значних помилок – 11-13 балів;

«задовільно», неповна відповідь, в деяких задачах можуть бути присутні значні помилки, але не менше 60% розв’язано правильно – 9-10 балів;

«незадовільно», незадовільна відповідь (неправильний розв’язок задач) – 0-8 балів.

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

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

Кількість балів Оцінка
100-95 Відмінно
94-85 Дуже добре
84-75 Добре
74-65 Задовільно
64-60 Достатньо
Менше 60 Незадовільно
Не виконані умови допуску Не допущено

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

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

Робочу програму навчальної дисципліни (Силабус):

Складено професор, д.ф.-м.н., Дорошенко Анатолій Юхимович, асистент Вітюк Альона Євгеніївна

Ухвалено кафедрою ІСТ (протокол № 1 від 27.08.2023 р.)

Погоджено Методичною комісією факультету (протокол № 1 від 02.09.2023 р.)

Додаток 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. Логічні виведення в логіці предикатів.