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

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

Рівень вищої освіти	Перший (бакалаврський)
Галузь знань	12 Інформаційні технології
Спеціальність	126 Інформаційні системи та технології
Освітня програма	Інформаційні управляючі системи та технології
Статус дисципліни	Нормативна
Форма навчання	Очна (денна)
Рік підготовки, семестр	1 курс, осінній семестр
Обсяг дисципліни	6 кредитів / 180 годин
Семестровий контроль/ контрольні заходи	Екзамен / МКР
Розклад занять	Лекції: відповідно до розкладу занять 1-го семестру http://roz.kpi.ua Лабораторні заняття: відповідно до розкладу занять 1-го семестру http://roz.kpi.ua
Мова викладання	Українська
Інформація про керівника курсу / викладачів	Лектор: к.ф.-м.н., доц., доц. кафедри ІСТ Рибачук Л.В., rybachuk.liudmyla@lll.kpi.ua Лабораторні заняття: к.ф.-м.н., доц., доц. кафедри ІСТ Рибачук Л.В., rybachuk.liudmyla@lll.kpi.ua
Розміщення курсу	https://do.ipo.kpi.ua/course/view.php?id=4847 https://classroom.google.com/c/MTQ1NjE5MjM4OTE4?cjc=4en5uj6 https://campus.kpi.ua

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

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

Мета вивчення дисципліни – набуття ключових фахових компетентностей, теоретичних знань і практичних навичок з дискретної математики.

Предметом вивчення дисципліни є основні поняття і твердження з різних розділів дискретної математики.

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

Навчальна дисципліна покликана допомогти студенту отримати:

знання методів та базових алгоритмів дискретної математики, теоретичних та експериментальних досліджень в дискретній математиці;

уміння використовувати базові алгоритми дискретної математики при проектуванні та розробці інформаційних систем, вибирати методи і засоби дискретної математики за критеріями мінімізації витрат, стійкості, складності тощо**;**

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

КОМПЕТЕНТНОСТІ

Інтегральна компетентність. Здатність розв’язувати складні спеціалізовані задачі та практичні проблеми в області інформаційних систем та технологій, або в процесі навчання, що характеризуються комплексністю та невизначеністю умов, які потребують застосування теорій та методів інформаційних технологій.

Загальні компетентності:

ЗК-1. Здатність до абстрактного мислення, аналізу та синтезу;
ЗК-2. Здатність застосовувати знання у практичних ситуаціях.

Спеціальні (фахові, предметні) компетентності:

ФК-11. Здатність до аналізу, синтезу і оптимізації інформаційних систем та технологій з використанням математичних та імітаційних моделей і методів;
ФК-13. Здатність проводити обчислювальні експерименти, порівнювати результати експериментальних даних і отриманих рішень;
ФК-15. Здатність до алгоритмічного та логічного мислення.

ПРОГРАМНІ РЕЗУЛЬТАТИ НАВЧАННЯ

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

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

При вивченні цієї дисципліни використовуються знання студентів з дисциплін:

"Вища математика";
"Аналітична геометрія та лінійна алгебра";

Знання, одержані студентами при вивченні дисципліни, використовуються у наступних курсах:

"Теорія алгоритмів";
"Математичні методи дослідження операцій";
"Теорія прийняття рішень";
"Організація баз даних та знань";
"Інтелектуальний аналіз даних";
"Системний аналіз".

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

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

Найменування розділів, тем

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

Розділ 1. Множини та відношення

Тема 1.1 Множини

Тема 1.2 Відношення

Тема 1.3 Відношення еквівалентності та порядку

Тема 1.4 Відображення і функції

Розділ 2. Алгебраїчні структури

Тема 2.1 Алгебраїчні операції та їх властивості

Тема 2.2 Поняття алгебраїчної структури. Найпростіші алгебраїчні структури

Тема 2.3 Ґратки

Розділ 3. Булеві функції

Тема 3.1 Булеві функції

Тема 3.2 Нормальні форми булевих функцій

Тема 3.3 Мінімізація булевих функцій

Тема 3.4 Алгебра Жегалкіна

Тема 3.5 Повні системи функцій

Розділ 4. Математична логіка

Тема 4.1 Логіка висловлювань

Тема 4.2 Числення виловлювань (логіка L)

Тема 4.3 Логіка предикатів

Розділ 5. Теорія графів

Тема 5.1 Основні поняття теорії графів

Тема 5.2 Властивості графів

Тема 5.3 Зв’язність графів

Тема 5.4 Обхід вершин графу

Тема 5.5 Дерева

Розділ 6. Основи теорії граматик, формальних мов та теорії автоматів

Тема 6.1 Мови та граматики. Алгебраїчні операції з мовами. Регулярні мови

Тема 6.2 Граматики Хомського. Ієрархія граматик

Тема 6.3 Розпізнавачі для різних класів граматик

Тема 6.4 Пошукові автомати

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

Основна література

Дистанційний курс «Спеціальні розділи математики. Частина 1. Дискретна математика» для бакалаврів 1-го курсу спеціальності 126 «Інформаційні системи та технології». – Сертифікат Серія ДК № 0180, автор-розробник Рибачук Л.В. – Електронні дані – Київ: КПІ ім. Ігоря Сікорського, 2023 р. (затверджений Методичною радою КПІ ім. Ігоря Сікорського, протокол № 9 від 22.06.2023 р.). Адреса розміщення: https://do.ipo.kpi.ua/course/view.php?id=4847.
Навчальний посібник з дисципліни «Дискретна математика» Частина1 для студентів спеціальностей 126 «Інформаційні системи та технології» та 121 «Інженерія програмного забезпечення» / Гавриленко О.В., Клименко О.М., Рибачук Л.В. – К: КПІ, 2020. – 75 с. (доступ за посиланням https://ela.kpi.ua/bitstream/123456789/38717/1/posibnyk\_chys.metody.pdf)
Бондаренко М.Ф. Комп’ютерна дискретна математика / М.Ф. Бондаренко, Н.В. Білоус, А.Т. Руткас — Х.: Компанія СМІТ, 2004. – 480 с.
Нікольський Ю.В., Пасічник В.В., Щербина Ю. М. Дискретна математика. – К.: Видавнича група BHV, 2007.
Методичні вказівки до самостійної роботи з дисципліни «Комп’ютерна дискретна математика»/ Упоряд.: Н.В. Білоус, І. В. Куцевич, Т.А. Разівілова. – Харків: ХНУРЕ, 2010. – 98 с.

Додаткова література

Дискретна математика: розрахункові роботи [електронний ресурс] : Навч. посіб. / КПІ ім. Ігоря Сікорського; уклад.: І.Я. Спекторський, О.В. Стусь, В.М. Статкевич. – Електронні текстові дані (1 файл: 0,6 мбайт). – Київ : КПІ ім. Ігоря Сікорського, 2017. – 84 с.
Таран Т.А., Миценко Н.А., Темникова Е.Л. Збірник задач з дискретної математики. – К.: Просвіта, 2001.
Тішин В.В. Дискретна математика в прикладах і задачах. – К., 2008. – 352 с.
Бардачов Ю.М., Соколова Н.А., В.Є. Ходаков. Дискретна математика: Підручник. –К.: Вища шк., 2002.
Базилевич Л. Дискретна математика у прикладах і задачах: підручник. – Львів: видавець І.Е. Чижиков. – 2013. – 487 с.
Капітонова Ю.В., Кривий С.Л., Летичевський О.А., Луцький Г.М., Печурін М.К. Основи дискретної математики: Підручник. – Київ: Видавництво “ЛітСофт”, 2000.
Таран Т.А. Основи дискретної математики. – К.: Просвіта, 2003. – 288 с.
Anderson James A. Discrete Mathematics With Combinatorics. – Prentice Hall, 2003. – 956 p.
Haggarty Rod Discrete mathematics for computing. – Harlow, England ; New York : Addison-Wesley, 2002. – 235 p.
Harary Frank Graph Theory. – CRC Press, 1994. – 288 p.

Інформаційні ресурси

https://do.ipo.kpi.ua/course/view.php?id=4847

https://classroom.google.com/c/MTQ1NjE5MjM4OTE4?cjc=4en5uj6

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

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

Методи навчання

Лекційні заняття проходять з використанням:

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

При виконання комп’ютерних практикумів використовується:

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

Самостійна робота з можливістю особистих консультацій з викладачем.

Структура навчальної дисципліни

Найменування розділів, тем	Розподіл навчального часу
Найменування розділів, тем	Всього	Лекції	Практичні	СРС
Опис навчальної дисципліни, її мета, предмет вивчення	1	1
Розділ 1. Множини та відношення
Тема 1.1. Множини	9	3	4	2
Тема 1.2. Відношення	12	4	4	4
Тема 1.3. Відношення еквівалентності та порядку	8	2	2	4
Тема 1.4. Відображення і функції	6	2	2	2
Розділ 2. Алгебраїчні структури
Тема 2.1. Алгебраїчні операції та їх властивості	3	1		2
Тема 2.2. Поняття алгебраїчної структури. Найпростіші алгебраїчні структури	4	2		2
Тема 2.3. Ґратки	3	1		2
Розділ 3. Булеві функції
Тема 3.1. Булеві функції	10	4	4	2
Тема 3.2. Нормальні форми булевих функцій	6	2	2	2
Тема 3.3. Мінімізація булевих функцій	7	2	2	3
Тема 3.4. Алгебра Жегалкіна	4	1	1	2
Тема 3.5. Повні системи функцій	8	3	2	3
Розділ 4. Математична логіка
Тема 4.1. Логіка висловлювань	10	2	2	6
Тема 4.2. Числення виловлювань (логіка L)	13	3	2	8
Тема 4.3. Логіка предикатів	12	3	1	8
Розділ 5. Теорія графів
Тема 5.1 Основні поняття теорії графів	5	2	1	2
Тема 5.2 Властивості графів	7	2	1	4
Тема 5.3 Зв’язність графів	8	2	2	4
Тема 5.4 Обхід вершин графу	8	2	2	4
Тема 7.5 Дерева	6	2		4
Розділ 6. Основи теорії граматик, формальних мов та теорії автоматів
Тема 6.1. Мови та граматики. Алгебраїчні операції з мовами. Регулярні мови	5	2		3
Тема 6.2. Граматики Хомського. Ієрархія граматик	5	2		3
Тема 6.3. Розпізнавачі для різних класів граматик	5	2		3
Тема 6.4. Пошукові автомати	5	2		3
Модульна контрольна робота	10		2	8
Всього	180	54	36	90

Комп’ютерні практикуми

№	Тема
1	ПЗ № 1 «Множини. Операції над множинами» 1) Таран № 1.1 2) Тішин № 1.1.2 3) Методичка № 1-3 (п.2→ДЗ) Домашнє завдання № 1: 1) Методичні вказівки до самостійної роботи з дисципліни «Комп’ютерна дискретна математика» cтор.39 Завдання 1-3 (табл. 8.1-8.3) 2) Тішин В.В. Дискретна математика в прикладах і задачах стор.8 Завдання № 1.1.2-1.1.6
2	ПЗ № 2 «Множини» 1) Таран № 1.2, 1.3 (довести тотожності алгебраїчно) 2) Тішин № 1.1.7, 1.1.8, 1.1.9, 1.1.10 Домашнє завдання № 2: 1) Завдання 1 2) Тішин В.В. Дискретна математика в прикладах і задачах стор.21 Завдання № 1.1.7-1.1.10
3	ПЗ № 3 «Декартів добуток множин. Відношення. Властивості відношень» 1) Тишин № 1.2.1 (1), 1.2.2 2) Методичка № 2.1, 2.3 3) Таран № 2.1 (модельний метод доведення, аналог РГР №2) Домашнє завдання № 3: 1) Методичні вказівки до самостійної роботи з дисципліни «Комп’ютерна дискретна математика» Стор. 42 Завдання 1-3 (табл. 8.6–8.8) 2) Тішин В.В. Дискретна математика в прикладах і задачах стор. 36 Завдання № 1.2.1 (1), 1.2.2
4	ПЗ № 4 «Відношення. Замикання відношень. Властивості бінарних відношень» Домашнє завдання № 4: 1) Методичні вказівки до самостійної роботи з дисципліни «Комп’ютерна дискретна математика» (стор. 43) Завдання 2.2 (табл. 8.7) (Побудувати рефлексивне, симетричне та транзитивне замикання даного відношення) 2) Спекторський РГР_Дискретна математика (КПІ, ІПСА) Стор.23 № 2.2 3) Таран Т.А. Збірник задач з дискретної математики (стор.11) Завдання № 2.2 1)-25) (Варіанти 1-25) Спекторський РГР_Дискретна математика (КПІ, ІПСА) Стор.19 № 2.1 (Варіанти 26-35)
5	ПЗ № 5 «Відношення еквівалентності та порядку» Домашнє завдання № 5: 1) Тишин В.В. Дискретная математика в примерах и задачах (стор.70) Завдання № 1.4.4 (завдання 1-6) 2) Таран Т.А. Сборник задач по дискретной математике (стор.15) Завдання № 4.1 1)-25) (Варіанти 1-25)
6	ПЗ № 6 «Відображення та функції» Домашнє завдання № 6: 1) Методичні вказівки до самостійної роботи з дисципліни «Комп’ютерна дискретна математика» (стор. 43) Завдання 2.2 (табл. 8.7) (Визначити, чи є дане відношення функціональним, відображенням. Якщо є, визначити тип відображення. Відповідь обґрунтувати.) 2) Таран Т.А. Збірник задач з дискретної математики (стор.12) Завдання № 3.1 1)-30) (Варіанти 1-30) 3) Тішин В.В. Дискретна математика в прикладах і задачах (стор.46) Завдання № 1.3.1
7	ПЗ № 7 «Булеві функції однієї та двох змінних» Домашнє завдання № 7: Тішин В.В. Дискретна математика в прикладах і задачах (стор.76) Завдання № 2.1.1, № 2.1.2, 2.1.3, 2.1.4
8	ПЗ № 8 «Розвинення булевої функції за змінними. Диз’юнктивні нормальні форми. Кон’юнктивні нормальні форми» Домашнє завдання № 8: 1) Методичні вказівки до самостійної роботи з дисципліни «Комп’ютерна дискретна математика» (стор. 44) Завдання 1 (табл. 8.9) пункти 1-6: спростити формулу побудувати таблицю істинності Записати ДДНФ та ДКНФ для заданої формули Записати диз’юнктивне розкладання функції за змінними х,z Записати кон’юнктивне розкладання функції за змінними y,z 2) Тішин В.В. Дискретна математика в прикладах і задачах стор.94 Завдання № 2.3.1, № 2.3.2
9	ПЗ № 9 «Мінімальні форми. Скорочена форма. Метод алгебраїчного зведення функції до мінімальної форми. Метод мінімізаційних карт (діаграми Карно-Вейча). Алгебра Жегалкіна. Канонічні поліноми» Домашнє завдання № 9: 1) Методичні вказівки до самостійної роботи з дисципліни «Комп’ютерна дискретна математика» стор. 46, табл. 8.11 4-місна функція задається набором своїх значень. Знайти мінімальні ДНФ та КНФ за допомогою діаграм Карно-Вейча 2) Таран Т.А. Збірник задач з дискретної математики (стор.34) Завдання № 7.4 1)-25) (Варіанти 1-25) (Знайти мінімальні ДНФ та КНФ за допомогою діаграм Карно-Вейча) 3) Тішин В.В. Дискретна математика в прикладах і задачах стор.121 Завдання № 2.5.2 (розв’язати для функцій трьох та чотирьох змінних) стор.116 Завдання № 2.5.1 (Знайти мінімальні ДНФ та КНФ за допомогою діаграм Карно-Вейча) стор.99 Завдання № 2.3.3 п.1 (побудувати поліном Жегалкіна двома методами)
10	ПЗ № 10 «Функціонально замкнуті класи булевих функцій. Набори повних систем. Теорема Поста» Домашнє завдання № 10: 1) Тішин В.В. Дискретна математика в прикладах і задачах стор.103 Завдання № 2.4.1 2) Методичні вказівки до самостійної роботи з дисципліни «Комп’ютерна дискретна математика» стор. 44 № 1 (табл. 8.9) п.6,7 (Чи є функція самодвоїстою; чи зберігає 0, 1; монотонна; лінійна?) стор. 45 № 2 (табл. 8.10) (Чи система функцій є повною?)
11	ПЗ № 11 «Математична логіка. Логіка висловлювань» Домашнє завдання № 11: 1) Методичні вказівки до самостійної роботи з дисципліни «Комп’ютерна дискретна математика» стор. 46 Завдання 1 (табл. 8.12) стор. 47 Завдання 2 2) Таран Т.А. Збірник задач з дискретної математики стор.36 Завдання № 8.1 (довести 3–а методами) 3) Таран Т.А. Збірник задач з дискретної математики стор.37 Завдання № 8.2
12	ПЗ № 12 «Числення виловлювань (логіка L)» Домашнє завдання № 12: 1) РГР № 9 Довести 3-а методами (логіка , метод редукції та метод Квайна) 2) Таран Т.А. Збірник задач з дискретної математики Завдання № 9.1 Довести в логіці
13	ПЗ № 13 «Логіка предикатів» Домашнє завдання № 13: Таран Т.А. Збірник задач з дискретної математики стор. 42 Завдання № 10.1, 10.2, 10.3
14	ПЗ № 14 « Основні поняття теорії графів. Властивості графів» Домашнє завдання № 14: Таран Т.А. Збірник задач з дискретної математики стор.22 Завдання № 6.1 1)-15) стор.28 Завдання № 6.2 1)-15)
15	ПЗ № 16 « Зв’язність графів» Домашнє завдання № 16: Таран Т.А. Збірник задач з дискретної математики стор.22 Завдання № 6.1 1)-15) стор.28 Завдання № 6.2 1)-15)
16	ПЗ № 17 « Обхід вершин графу» Домашнє завдання № 17: Таран Т.А. Збірник задач з дискретної математики стор.22 Завдання № 6.1 1)-15) стор.28 Завдання № 6.2 1)-15)
17	Підготовка до модульної контрольної роботи
18	Підсумкове заняття

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

Розділ 1 Множини та відношення

Тема 1.1. Множини

Інтуїтивне означення множини. Способи задання множин: вербальний, перелік, характеристичний. Парадокс Рассела.

Література: [1, c. 67-68; 2, c.14-16; 3, c. 7-12; 4, c. 35-37; 5, c. 22-25]

Завдання на СРС. [6, c. 5-6; 6, c. 14]

Порожня множина. Універсум. Підмножини. Булеан. Операції над множинами. Властивості операцій. Діаграми Вена. Розбиття. Покриття. Узагальнення операцій.

Література: [1, c. 68-81; 2, c. 16-23; 3, c. 12-19; 4, c. 37-39]

Завдання на СРС. [5, c. 25-33; 6, c.9-13]

Тема 1.2. Відношення

Декартовий добуток. Декартовий квадрат. Кортеж. Відношення. Арність відношень. Область визначення. Множина значень відношення. Повне, тотожне, порожнє відношення. Обернене відношення. Композиція відношень. Способи задання відношень. Фактор-множина. Властивості відношень.

Література: [1, c. 90-96; 2, c. 81-88; 3, c. 19-37; 4, c. 185-188]

Завдання на СРС. [5, c. 43-50; 6, c. 15-21]

Тема 1.3. Відношення еквівалентності та порядку

Відношення еквівалентності. Класи еквівалентності. Матриця та граф відношення еквівалентності.

Література: [1, c.106-110; 2, c. 93-97; 4, c. 188-190]

Завдання на СРС. [5, c. 56-60; 6, c. 21-24]

Відношення порядку (строгого та нестрогого). Лінійно та частково впорядкована множина. Відношення толерантності. Вагові функції та відношення квазіпорядку. Структура впорядкованих множин. Мінімальні, максимальні, найбільші та найменші елементи. Діаграми впорядкованих множин (діаграми Хессе). Нижні та верхні грані.

Література: [1, c. 103-104; 2, c. 97-102; 4, c. 190-195]

Завдання на СРС. [5, c. 60-63; 6, c. 61-69]

Тема 1.4. Відображення і функції

Функціональні відношення. Образи та прообрази. Типи відображень: сюр’єкція, ін’єкція, бієкція. Властивості відображень. Обмеження та звуження відображення. Композиція відображень. Суперпозиція.

Література: [2, c. 88-93; 3, c. 37-45]

Завдання на СРС. [5, c. 51-56; 6, c. 25-36]

Розділ 2 Алгебраїчні структури

Тема 2.1. Алгебраїчні операції та їх властивості

Література: [2, c. 189-194; 3, c. 85-95]

Завдання на СРС. [5, c. 67-73]

Тема 2.2. Поняття алгебраїчної структури. Найпростіші алгебраїчні структури

Нейтральні елементи. Обернені елементи. Алгебри з однією операцією: моноїд, півгрупа, група. Група підстановок. Алгебри з двома операціями: кільце та поле.

Література: [1, c. 397-401; 2, c. 194-201; 3, c. 97-121]

Завдання на СРС. [5, c. 73-82]

Тема 2.3. Ґратки

Основні означення ґраток. Підґратки. Ґратки як алгебри. Нижні та верхні півґратки.

Література: [1, c. 392-394; 1, c. 403-404; 2, c. 201-204]

Завдання на СРС. [5, c. 87-91; 6, c.74-80]

Дистрибутивні ґратки. Булеві ґратки.

Література: [1, c. 405]

Завдання на СРС. [6, c. 81-86]

Розділ 3 Булеві функції

Тема 3.1. Булеві функції

Основні поняття та способи задання булевих функцій. Булеві функції однієї змінної. Булеві функції двох змінних. Булевий простір. Властивості функцій алгебри логіки. Реалізація булевих функцій формулами. Принцип двоїстості.

Література: [1, c. 84-89; 2, c. 29-39; 3, c. 121-136; 4, c. 235-240]

Завдання на СРС. [5, c. 99-109; 6, c. 148-154]

Тема 3.2. Нормальні форми булевих функцій

Проблема розв’язуваності. Розвинення булевої функції за змінними. Диз’юнктивні нормальні форми. Кон’юнктивні нормальні форми. Властивості досконалих форм.

Література: [1, c. 45-49; 2, c. 46; 2, c. 52-56; 4, c. 257-258]

Завдання на СРС. [5, c. 109-114; 6, c. 154-157]

Тема 3.3. Мінімізація булевих функцій

Індекс простоти. Мінімальні форми. Скорочена форма. Прості імплікації. Метод Квайна утворення скороченої диз’юнктивної нормальної форми.

Література: [2, c. 57-66; 4, c. 258-261]

Завдання на СРС. [5, c. 115-119; 6, c. 164-166]

Тупикові нормальні форми. Метод мінімізаційних карт (діаграми Карно-Вейча).

Література: [1, c. 50-54; 2, c. 66-73; 4, c. 261-267]

Завдання на СРС. [6, c. 166-167]

Тема 3.4. Повні системи функцій

Алгебра Жегалкіна. Канонічні поліноми. Відношення передування. Монотонні функції. Функції, що зберігають нуль та одиницю.

Література: [2, c. 47-52; 4, c. 250-257]

Завдання на СРС. [5, c. 119-124; 6, c. 158-164]

Функціонально замкнуті класи булевих функцій. Мінімальні повні базиси. Набори повних систем. Теорема Поста.

Література: [2, c. 47-52; 4, c. 250-257]

Завдання на СРС. [5, c. 119-124; 6, c. 158-164]

Розділ 4. Математична логіка

Тема 4.1. Логіка висловлювань

Принцип тотожності. Принцип несуперечливості. Принцип достатності засновків. Логіка висловлювань. Пропозиційні зв’язки. Логічне слідування. Логічно еквівалентні формули.

Література: [1, c. 15-28; 2, c. 147-152; 3, c. 198-202; 4, c. 9-15]

Завдання на СРС. [5, c. 133-138; 6, c. 168-175]

Тавтології. Правило виведення Modus Ponens. Формальні системи та аксіоматичний підхід. Властивості формальних теорій. Вивід. Властивості виводу. Властивості формальних теорій. Інтерпретації. Моделі. Повнота. Розв’язуваність. Повнота система аксіом. Несуперечливість.

Література: [2, c. 147-152; 3, c. 198-202; 4, c. 15-17]

Завдання на СРС. [5, c. 138-141; 6, c. 172-182]

Тема 4.2. Числення виловлювань (логіка L)

Числення висловлювань. Схеми аксіом. Теорема дедукції Ербрана. Наслідки теореми дедукції. Приклади виведення у численні L.

Література: [1, c. 34-42; 2, c. 151-154; 3, c. 202-212; 4, c. 26-28]

Завдання на СРС. [5, c. 141-147; 6, c. 182-188]

Інші формалізації логіки висловлювань. Модельні властивості теорії L. Метод Квайна перевірки тотожної істинності формул логіки висловлювань.

Література: [2, c. 154-158; 3, c. 212-215; 3, c. 218-220]

Завдання на СРС. [5, c. 147-152; 6, c. 190-197]

Тема 4.3. Логіка предикатів

Поняття предикату. Квантори. Терми та формули. Зв’язані та вільні змінні. Логіка першого порядку.

Література: [1, c. 113-118; 2, c. 158-167; 3, c. 228-235; 4, c. 19-23]

Завдання на СРС. [5, c. 152-155; 6, c. 198-203]

Інтерпретації формул логіки першого порядку. Властивості формул логіки першого порядку. Перевірка загальнозначущості формул логіки першого порядку.

Література: [1, c. 113-118; 2, c. 167-170; 3, c. 228-235; 4, c. 23-25]

Завдання на СРС. [5, c. 155-156; 6, c. 204-212]

Розділ 5 Теорія графів

Тема 5.1 Основні поняття теорії графів

Література: [4, c. 88-93]

Завдання на СРС. [5, c. 209-210]

Тема 5.2 Властивості графів

Література: [4, c. 94-99]

Завдання на СРС. [5, c. 209-210]

Тема 5.3 Зв’язність графів

Література: [5, c. 100-107]

Завдання на СРС. [5, c. 232-234]

Тема 5.4 Обхід вершин графу

Література: [4, c. 120-123]

Завдання на СРС. [5, c. 259-260]

Тема 5.5 Дерева

Література: [4, c. 150-159]

Завдання на СРС. [5, c. 259-260]

Застосування дерев

Література: [4, c. 160-174]

Завдання на СРС. [5, c. 259-260]

Розділ 6 Основи теорії граматик, формальних мов та теорії автоматів

Тема 6.1 Мови та граматики. Алгебраїчні операції з мовами. Регулярні мови

Література: [5, c. 276-280]

Завдання на СРС. [5, c. 284-285]

Тема 6.2 Граматики Хомського. Ієрархія граматик

Література: [5, c. 281-283]

Завдання на СРС. [5, c. 283-284]

Тема 6.3 Розпізнавачі для різних класів граматик

Література: [5, c. 285-288]

Завдання на СРС. [5, c. 289-293]

Тема 6.4 Пошукові автомати

Література: [5, c. 294-300]

Завдання на СРС. [5, c. 301-302]

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

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

Форми організації освітнього процесу, види навчальних занять і оцінювання результатів навчання регламентуються Положенням про організацію освітнього процесу в Національному технічному університеті України «Київському політехнічному інституті імені Ігоря Сікорського».

https://kpi.ua/regulations

Політика виставлення оцінок: кожна оцінка виставляється відповідно до розроблених викладачем та заздалегідь оголошених студентам критеріїв, а також мотивується в індивідуальному порядку на вимогу студента; у випадку не виконання студентом усіх передбачених навчальним планом видів занять (лабораторних робіт, тесту) до екзамену він не допускається; пропущені заняття обов’язково мають бути відпрацьовані.
**Відвідування є обов'язковим (**за винятком випадків, коли існує поважна причина, наприклад, хвороба чи дозвіл працівників деканату). Якщо студент не може бути присутніми на заняттях, він все одно несете відповідальність за виконання завдань, що проводились на занятті та винесені в домашне завдання.
Політика академічної поведінки та доброчесності: конфліктні ситуації мають відкрито обговорюватись в академічних групах з викладачем, необхідно бути взаємно толерантним, поважати думку іншого. Плагіат та інші форми нечесної роботи неприпустимі. Всі види завдань студент має виконувати самостійно із використанням рекомендованої літератури й отриманих знань та навичок. Цитування в письмових роботах допускається тільки із відповідним посиланням на авторський текст. Недопустимі підказки і списування у ході захисту лабораторних робіт, на контрольних роботах, на іспиті.
Норми академічної етики: дисциплінованість; дотримання субординації; чесність; відповідальність; робота в аудиторії з відключеними мобільними телефонами. Повага один до одного дає можливість ефективніше досягати поставлених командних результатів. При виконанні лабораторних робіт студент може користуватися ноутбуками. Проте під час лекційних занять та обговорення завдань лабораторних робіт не слід використовувати ноутбуки, смартфони, планшети чи комп’ютери. Це відволікає викладача і студентів групи та перешкоджає навчальному процесу. Якщо ви використовуєте свій ноутбук чи телефон для аудіо- чи відеозапису, необхідно заздалегідь отримати дозвіл викладача.
Дотримання академічної доброчесності студентів й викладачів регламентується кодекс честі Національного технічного університету України «Київський політехнічний інститут», положення про організацію освітнього процесу в КПІ ім. Ігоря Сікорського

https://kpi.ua/code

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

1) Рейтинг студента з кредитного модуля розраховується зі 100 балів, з них 50 балів складає стартова шкала та 50 балів – екзаменаційна шкала .

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

виконання тестових (домашніх) завдань до комп’ютерних практикумів –

42 бали (тести 1-16);
виконання модульної контрольної роботи – 8 балів.

Студенти, які активно працюють на комп’ютерному практикумі (розв’язують задачі на дошці, доповнюють з місця тощо) можуть бути позбавлені від виконання тестового (домашнього завдання) по даній темі.

Також студенти мають змогу отримати заохочувальні бали за активну роботу на лекції (на розсуд лектора), але не більше 10 балів за семестр.

2) Календарний контроль: проводиться двічі на семестр як моніторинг поточного стану виконання вимог силабусу.

Умовою зарахування першого календарного контролю (7-8-ий тижні) є отримання не менше 7,5 балів. За результатами навчальної роботи за перші 6 тижнів навчання максимально можлива кількість балів – 15 балів (тести 1-6).

Умовою зарахування другого календарного контролю (14-15-ий тижні) є отримання не менше 16 балів. За результатами 13 тижнів навчання максимально можлива кількість балів – 32 бали (тести 1-13).

3) Форма семестрового контролю – екзамен. Максимальна сума балів за роботу у семестрі складає 50 балів. Умовою допуску до екзамену є стартовий рейтинг не менше 25 балів.

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

Кожне теоретичне питання (завдання) оцінюється у 10 балів за такими критеріями:

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

балів;
«добре», достатньо повна відповідь, не менше 75% потрібної

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

та деякі помилки – 6-7 балів;
«незадовільно», відповідь не відповідає умовам до «задовільно» – 0

балів.

Кожне практичне завдання оцінюється у 15 балів за такими критеріями:

«відмінно», повна відповідь, не менше 90% потрібної інформації

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

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

та деякі помилки (завдання виконане з певними недоліками) – 9-11 балів;
«незадовільно», відповідь не відповідає умовам до «задовільно» – 0

балів.

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

Бали (+)	Оцінка
95…100	Відмінно
85…94	Дуже добре
75…84	Добре
65…74	Задовільно
60…64	Достатньо
Менше 60	Незадовільно
Стартовий рейтинг менше 25 балів	Не допущено

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

Питання, які виносяться на іспит:

Поняття множини. Способи представлення множин. Поняття підмножини. Порожня та універсальна множини. Булеан. Навести приклади.
Операції над множинами: об’єднання, перетин, доповнення, різниця, симетрична різниця. Означення, представлення за допомогою діаграм Ейлера-Венна. Навести приклади.
Властивості операцій над множинами: ідемпотентність, дистрибутивність, закони де Моргана, властивості доповнення, різниці та симетричної різниці. Навести доведення 2-ма способами: аналітичним шляхом та за допомогою діаграм Ейлера-Венна. Навести приклади.
Властивості операцій над множинами: комутативність, асоціативність, дистрибутивність, властивості ∅ та U, поглинання, закони де Моргана. Навести доведення 2-ма способами: аналітичним шляхом та за допомогою діаграм Ейлера-Венна. Навести приклади.
Скінченні та нескінченні множини. Потужність множин. Потужність булеана скінченної множини. Обчислення потужностей множин. Рівнопотужні множини. Навести приклади.
Декартів добуток множин і його потужність. Кортежі, елементи кортежів. Навести приклади.
Методи доведення тотожностей в алгебрі множин: аналітичний (алгебраїчний), модельний, за допомогою діаграм Ейлера-Венна. Навести приклади.
Поняття відношення. n-арне відношення. Область визначення відношення. Множина значень відношення. Повне (універсальне) відношення. Тотожне (діагональне) відношення. Порожнє відношення. Навести приклади.
Бінарні відношення. Способи задання відношень (фактор-множиною, матричним способом, за допомогою графу). Навести приклади.
Операції над бінарними відношеннями: об’єднання, перетин, доповнення, різниця, обернення і композиція. Навести приклади.
Степінь відношення. Властивості операцій над бінарними відношеннями. Навести приклади.
Властивості бінарних відношень (рефлексивне, антирефлексивне (іррефлексивне), симетричне, асиметричне, антисиметричне, транзитивне). Навести приклади.
Замикання відношень. Симетричне, рефлексивне та транзитивне замикання, способи їх одержання. Алгоритм Уоршелла. Навести приклади.
Функціональне відношення, області визначення та значень. Всюди визначене відношення. Прообраз, образ функціонального відношення. Відображення. Типи відображень (сюр’єкція, ін’єкція, бієкція). Композиція відображень. Навести приклади.
Відношення еквівалентності. Класи еквівалентності. Матриця та граф відношення еквівалентності. Навести приклади.
Відношення порядку. Частковий порядок. Строгий порядок. Незрівнянні елементи. Множина частково впорядкована. Елемент найменший (найбільший). Мінімальний (максимальний) елемент. Діаграма Гассе. Навести приклади.
Алгебраїчні операції та їх властивості. Навести приклади.
Поняття та складові алгебраїчної структури. Алгебраїчні структури з однією операцією (півгрупа, моноїд, група, абелева група). Навести приклади.
Поняття та складові алгебраїчної структури. Алгебраїчні структури з двома операціями (кільце, алгебра, поле). Алгебра Буля. Навести приклади.
Гратки, булеві гратки. Навести приклади.
Булеві змінні та функції. Набори. Місність функцій. Способи задання булевих функцій (таблицею істинності, порядковим номером, аналітично). Навести приклади.
Булеві функції однієї та двох змінних. Навести приклади.
Властивості булевих функцій. Поняття суттєвих та несуттєвих змінних. Рівність функцій. Навести приклади.
Двоїста функція, самодвоїста функція. Два способи знаходження двоїстої функції. Навести приклади.
Закони булевої алгебри. Навести доведення та приклади.
Диз'юнктивне розкладання булевих функцій за k змінними, за однією змінною, за всіма n (k<n) змінними. Навести приклади.
Диз’юнктивна нормальна форма. Досконала диз’юнктивна нормальна форма. Способи їх отримання. Навести приклади.
Кон'юнктивне розкладання булевих функцій за k змінними, за однією змінною, за всіма n (k<n) змінними. Навести приклади.
Кон’юнктивна нормальна форма. Досконала кон’юнктивна нормальна форма. Способи їх отримання. Навести приклади.
Задача мінімізації булевих функцій. Мета мінімізації булевих функцій. Індекс простоти. Імпліканти, прості імпліканти, повна система імплікант. Навести приклади.
Операції склеювання та поглинання. Скорочена, тупикова та мінімальна диз’юнктивні нормальні форми. Навести приклади.
Загальний алгоритм мінімізації булевих функцій. Метод мінімізаційних карт (діаграми Карно-Вейча). Навести приклади.
Алгебра Жегалкіна. Поліномом Жегалкіна та його побудова. Лінійна функція. Навести приклади.
Повні системи функцій. Функція, що зберігає 0 чи зберігає 1. Відношення передування. Монотонна функція. Критерій повноти Поста. Класи Поста. Навести приклади.
Основні поняття теорії графів. Неорієнтовані та орієнтовані графи. Інцидентність та суміжність. Граф простий, мультиграф, псевдограф. Види графів. Навести приклади.
Способи представлення графів (список ребер, матриця інцидентності, матриця суміжності, список суміжностей) для неорієнтованих та орієнтованих графів. Навести приклади.
Ізоморфізм графів. Графи та бінарні відношення. Навести приклади.
Степені вершин. Вершина ізольована, висяча. Граф однорідний степеня k. Півстепінь виходу, півстепінь заходу. Теорема Ейлера та наслідки. Повний граф. Дводольний граф. Повний дводольний граф. Підграфи. Навести приклади.
Маршрути, ланцюги та цикли. Простий ланцюг. Граф ациклічний. Шлях. Контур. Навести приклади.
Метричні характеристики графів: відстань між двома вершинами, ярус, діаметр, радіус, центр графу. Навести приклади.
Операції на графах: об’єднання, перетин, видалення вершини, стягування ребра. Навести приклади.
Зв’язність графів. Компоненти зв’язності. Число вершинної зв’язності. Число реберної зв’язності. Точка з’єднання. Розріз. Міст. Навести приклади.
Зв’язність орієнтованих графів: сильно-зв’язний, однобічно-зв’язний, слабко-зв’язний, незв’язний. Теорема про визначення типу зв’язності графу за допомогою матриць. Навести приклади.
Алгоритм побудови матриці відстаней і матриці досяжності (методом піднесення в степінь). Навести приклади.
Поняття дерева. Властивості дерев. Корінь, внутрішня вершина дерева, лист. Рівень вершини та висота дерева. Навести приклади.
Способи обходу дерева. Відповідні форми запису виразів. Навести приклади.
Обхід графів: пошук вшир (BFS-метод). Навести приклад.
Обхід графів: пошук вглиб (DFS-метод). Навести приклад.
Топологічне сортування методом Кана. Навести приклад.
Логіка висловлювань. Поняття висловлювання. Атоми та пропозиційні зв’язки. Формули логіки висловлювань. Навести приклади.
Інтерпретації, тавтології та суперечності. Таблиці істинності. Логічне слідування. Навести приклади.
Формальна теорія L (логіка L). Теорема дедукції. Методи перевірки тотожної істинності формул логіки висловлювань (за таблицею істинності, побудовою виводу у теорії L). Навести приклади.
Методи перевірки тотожної істинності формул логіки висловлювань (метод Квайна, метод редукції). Навести приклади.
Логіка предикатів. Поняття логіки предикатів. Квантори загальності й існування. Формули логіки предикатів. Зв’язані та вільні змінні. Навести приклади.
Основні тотожності логіки предикатів. Побудова таблиці істинності для предиката. Навести приклади.

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

Складено доцентом кафедри ІСТ, к.ф.-м.н., доц. Рибачук Л.В.

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

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