СПЕЦІАЛЬНІ РОЗДІЛИ МАТЕМАТИКИ. ЧАСТИНА 1. ДИСКРЕТНА МАТЕМАТИКА - Робоча програма навчальної дисципліни (Силабус)
Реквізити навчальної дисципліни
| Рівень вищої освіти | Перший (бакалаврський) |
| Галузь знань | 12 Інформаційні технології |
| Спеціальність | 126 Інформаційні системи та технології |
| Освітня програма | Інформаційні управляючі системи та технології |
| Статус дисципліни | Нормативна |
| Форма навчання | очна(денна)/дистанційна/змішана |
| Рік підготовки, семестр | 1 курс, осінній семестр |
| Обсяг дисципліни | 6 кредитів / 180 годин |
| Семестровий контроль/ контрольні заходи | Екзамен / МКР |
| Розклад занять | http://rozklad.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. Опис навчальної дисципліни, її мета, предмет вивчення та результати навчання
Мета вивчення дисципліни – набуття ключових фахових компетентностей, теоретичних знань і практичних навичок з дискретної математики.
Предметом вивчення дисципліни є основні поняття і твердження з різних розділів дискретної математики.
Завдання вивчення дисципліни – оволодіння основними поняттями теорії множин, теорії відношень, теорії графів, математичної логіки та комбінаторики; набуття практичних навичок використання понять теорії множин, теорії відношень, теорії графів, математичної логіки та комбінаторики для розв'язування задач.
Навчальна дисципліна покликана допомогти студенту отримати:
знання методів та базових алгоритмів дискретної математики, теоретичних та експериментальних досліджень в дискретній математиці; уміння використовувати базові алгоритми дискретної математики при проектуванні та розробці інформаційних систем, вибирати методи і засоби дискретної математики за критеріями мінімізації витрат, стійкості, складності тощо*; ***
здатність вибирати та модифікувати алгоритми для їх ефективної програмно-
апаратної реалізації; аналізувати, теоретично та експериментально досліджувати методи, алгоритми дискретної математики; вибирати базові алгоритми дискретної за критеріями мінімізації витрат, стійкості, складності тощо.
КОМПЕТЕНТНОСТІ
Загальні компетентності
К01. Здатність до абстрактного мислення, аналізу та синтезу.
К02. Здатність застосовувати знання у практичних ситуаціях.
Спеціальні (фахові, предметні) компетентності
К14. Здатність брати участь у проектуванні програмного забезпечення, включаючи проведення моделювання (формальний опис) його структури, поведінки та процесів функціонування. К20. Здатність застосовувати фундаментальні і міждисциплінарні знання для успішного розв'язання завдань інженерії програмного забезпечення. К26. Здатність до алгоритмічного та логічного мислення.
ПРОГРАМНІ РЕЗУЛЬТАТИ НАВЧАННЯ
ПР05. Знати і застосовувати відповідні математичні поняття, методи доменного, системного і об'єктно-орієнтованого аналізу та математичного моделювання для розробки програмного забезпечення.
2. Пререквізити та постреквізити дисципліни (місце в структурно-логічній схемі навчання за відповідною освітньою програмою)
При вивченні цієї дисципліни використовуються знання студентів з дисциплін:
"Вища математика";
"Аналітична геометрія та лінійна алгебра";
Знання, одержані студентами при вивченні дисципліни, використовуються у наступних курсах:
„Теорія алгоритмів”;
„Математичні методи дослідження операцій”;
„Теорія прийняття рішень”;
„Організація баз даних та знань”; „Інтелектуальний аналіз даних”; „Системний аналіз”.
Матеріали дисципліни застосовуються для формування математичного фундаменту аналітика комп’ютерних систем, спроможного застосовувати отриманні знання для проектування, впровадженні та експлуатації інформаційних систем і технологій, систем обробки інформації на базі комп’ютерних систем і мереж.
3. Зміст навчальної дисципліни
| Найменування розділів, тем |
|---|
| Вступ. Опис навчальної дисципліни, її мета, предмет вивчення |
| Розділ 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 Пошукові автомати |
4. Навчальні матеріали та ресурси Базова література
Андресон Джеймс А. Дискретная математика и комбинаторика: Пер. С англ.. – М.: Издательский дом “Вильямс”.
Бардачов Ю.М., Соколова Н.А., В.Є. Ходаков. Дискретна математика: Підручник. –К.: Вища шк., 2002.
Капітонова Ю.В., Кривий С.Л., Летичевський О.А., Луцький Г.М., Печурін М.К. Основи дискретної математики: Підручник. – Київ: Видавництво “ЛітСофт”, 2000.
Нікольський Ю.В., Пасічник В.В., Щербина Ю. М. Дискретна математика. – К.: Видавнича група BHV, 2007.
Новиков Ф.А. Дискретная математика для программистов. Учебник для вузов. 2–е изд. – СПб.:
Питер, 2006.
Таран Т.А. Основы дискретной математики. – К.: Просвіта, 2003.
Таран Т.А., Мыценко Н.А., Темникова Е.Л. Сборник задач по дискретной математике. – К.: Просвіта, 2001.
Тишин В.В. Дискретная математика в примерах и задачах. – СПб.: БХВ-Петербург, 2008.
Методичні вказівки до самостійної роботи з курсу «Основи дискретної математики» для студентів спеціальності «Автоматизовані системи обробки інформації та управління». Частина 2. Збірник вправ для контролю ефективності самостійної роботи./ Уклад. С.Ф. Теленик. – К.: КПІ, 1991.
Додаткова література
Донской В.И. Дискретная математика. – Симферополь: СОНАТ, 2000.
Куратовский К., Мостовский А. Теория множеств. – М.: Мир, 1970.
Мальцев А.И. Алгебраические системы. – М.: Наука, 1975.
Робертс Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. – М.: Наука, 1986.
Успенский В.А., Верещагин Н.К., Плиско В.Е. Вводный курс математической логики. – 2-е изд. – М.: ФИЗМАТЛИТ, 2002.
Інформаційні ресурси https://do.ipo.kpi.ua/course/view.php?id=4847
https://classroom.google.com/c/MTQ1NjE5MjM4OTE4?cjc=4en5uj6
- містять повний конспект лекцій та матеріали для практичних занять
Навчальний контент
5. Методика опанування навчальної дисципліни (освітнього компонента)
Методи навчання
Лекційні заняття проходять з використанням:
пояснювально-ілюстративного методу. Послідовна та логічно ув’язана подача матеріалу надає уявлення та знання його логічної цілісності;
метод проблемного викладу надає уяву та методи отримання нових знань та фактів з використанням вже відомих фактів та тверджень;
інтерактивний метод під час лекційних занять використовується для встановлення діалогу з аудиторією та залучення студентів у принципові кроки теоретичного матеріалу.
При виконання комп’ютерних практикумів використовується:
репродуктивний метод, завдяки якому студенти закріплюють вивчений теоретичний матеріал та навчаються використовувати його в конкретних задачах;
інтерактивний метод під час лабораторних занять використовується для залучення студентів у методи розв’язання задач та теоретичні факти, які для цього використовуються.
Самостійна робота з можливістю особистих консультацій з викладачем.
Структура навчальної дисципліни
| Найменування розділів, тем | Розподіл навчального часу | ||||
|---|---|---|---|---|---|
| Всього | Лекції | Практичні | СРС | ||
| Опис навчальної дисципліни, її мета, предмет вивчення | 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. Мінімізація булевих функцій | 8 | 2 | 2 | 4 | |
| Тема 3.4. Повні системи функцій | 8 | 2 | 2 | 4 | |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|||||
|
|
|
|
||
|
|
|
|
||
|
|
|
|
||
|
|
|
|
||
|
|
|
|
||
|
|
|
36 |
|
|
Комп’ютерні практикуми
|
Тема |
|---|---|
| 1 | ПЗ № 1 «Множини. Операції над множинами»
cтор.39 Завдання 1-3 (табл. 8.1-8.3)
|
| 2 | ПЗ № 2 «Множини. » 1) Таран № 1.2, 1.3 (довести тотожності алгебраїчно) 2) Тишин № 1.1.7, 1.1.8, 1.1.9, 1.1.10 (було на 2-ій лекції) Домашнє завдання № 2:
|
| 3 | ПЗ № 3 «Декартів добуток множин. Відношення. Властивості відношень» 1) Тишин № 1.2.1 (1), 1.2.2
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.4.4 (завдання 1-6)
|
| 6 | ПЗ № 6 «Відображення та функції» Домашнє завдання № 6:
(Визначити, чи є дане відношення функціональним, відображенням. Якщо є, визначити тип відображення. Відповідь обґрунтувати.)
Завдання № 3.1 1)-30) (Варіанти 1-30)
|
| 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:
|
| 9 | ПЗ № 9 «Мінімальні форми. Скорочена форма. Метод алгебраїчного зведення функції до мінімальної форми. Метод мінімізаційних карт (діаграми Карно-Вейча). Алгебра Жегалкіна. Канонічні поліноми» Домашнє завдання № 9: |
стор. 46, табл. 8.11 4-місна функція задається набором своїх значень. Знайти мінімальні ДНФ та КНФ за допомогою діаграм Карно-Вейча
Завдання № 7.4 1)-25) (Варіанти 1-25) (Знайти мінімальні ДНФ та КНФ за допомогою діаграм Карно-Вейча)
стор.99 Завдання № 2.3.3 п.1 (побудувати поліном Жегалкіна двома методами) |
|
|---|---|
|
ПЗ № 10 «Функціонально замкнуті класи булевих функцій. Набори повних систем. Теорема Поста» Домашнє завдання № 10:
стор. 44 № 1 (табл. 8.9) п.6,7 (Чи є функція самодвоїстою; чи зберігає 0, 1; монотонна; лінійна?) стор. 45 № 2 (табл. 8.10) (Чи система функцій є повною?) Підготуватись до МКР № 2 |
|
ПЗ № 11 «Математична логіка. Логіка висловлювань» Домашнє завдання № 11:
стор. 46 Завдання 1 (табл. 8.12) стор. 47 Завдання 2
|
|
ПЗ № 12 «Числення виловлювань (логіка L)» Домашнє завдання № 12:
Завдання № 9.1 Довести в логіці L |
|
ПЗ № 13 «Логіка предикатів» Домашнє завдання № 13: Таран Т.А. Сборник задач по дискретной математике стор. 42 Завдання № 10.1, 10.2, 10.3 |
|
ПЗ № 14 « Основні поняття теорії графів» Домашнє завдання № 14: Таран Т.А. Сборник задач по дискретной математике стор.22 Завдання № 6.1 1)-15) стор.28 Завдання № 6.2 1)-15) |
|
ПЗ № 15 « Властивості графів» Домашнє завдання № 15: Таран Т.А. Сборник задач по дискретной математике стор.22 Завдання № 6.1 1)-15) |
| стор.28 Завдання № 6.2 1)-15) | |
|
ПЗ № 16 « Зв’язність графів» Домашнє завдання № 16: Таран Т.А. Сборник задач по дискретной математике стор.22 Завдання № 6.1 1)-15) стор.28 Завдання № 6.2 1)-15) |
|
ПЗ № 17 « Обхід вершин графу» Домашнє завдання № 17: Таран Т.А. Сборник задач по дискретной математике стор.22 Завдання № 6.1 1)-15) стор.28 Завдання № 6.2 1)-15) |
|
Підготовка до модульної контрольної роботи |
Тестові (домашні) завдання до комп’ютерних практикумів
|
Тест |
|---|---|
|
Тест № 1 «Множини. Операції над множинами» Тест № 2 «Множини. Властивості операцій над множинами» |
|
Тест № 3 «Декартів добуток. Відношення» |
|
Тести № 4-5 «Відношення. Властивості відношень» |
|
Тест № 6 «Відображення і функції» |
|
Тести № 7-8 «Булеві функції» |
|
Тест № 9 «Нормальні форми булевих функцій» |
|
Тест № 10 «Мінімізація булевих функцій» |
|
Тест № 11 «Повні системи функцій» |
|
Тест № 12 «Логіка висловлювань. Числення висловлювань» |
|
Тест № 13 «Основні поняття теорії графів. Властивості графів» |
|
Тест № 14 «Зв’язність графів» |
|
Тест № 15 «Обхід вершин графу» |
6. Самостійна робота студента
Розділ 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,
- 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]
Політика та контроль
7. Політика навчальної дисципліни (освітнього компонента)
Форми організації освітнього процесу, види навчальних занять і оцінювання результатів навчання регламентуються Положенням про організацію освітнього процесу в Національному технічному університеті України «Київському політехнічному інституті імені Ігоря Сікорського». https://kpi.ua/regulations
Політика виставлення оцінок: кожна оцінка виставляється відповідно до розроблених викладачем та заздалегідь оголошених студентам критеріїв, а також мотивується в індивідуальному порядку на вимогу студента; у випадку не виконання студентом усіх передбачених навчальним планом видів занять (лабораторних робіт, тесту) до екзамену він не допускається; пропущені заняття обов’язково мають бути відпрацьовані.
**Відвідування є обов'язковим (**за винятком випадків, коли існує поважна причина, наприклад, хвороба чи дозвіл працівників деканату). Якщо студент не може бути присутніми на заняттях, він все одно несете відповідальність за виконання завдань, що проводились на занятті та винесені в домашне завдання.
Політика академічної поведінки та доброчесності: конфліктні ситуації мають відкрито обговорюватись в академічних групах з викладачем, необхідно бути взаємно толерантним, поважати думку іншого. Плагіат та інші форми нечесної роботи неприпустимі. Всі види завдань студент має виконувати самостійно із використанням рекомендованої літератури й отриманих знань та навичок. Цитування в письмових роботах допускається тільки із відповідним посиланням на авторський текст. Недопустимі підказки і списування у ході захисту лабораторних робіт, на контрольних роботах, на іспиті.
Норми академічної етики: дисциплінованість; дотримання субординації; чесність; відповідальність; робота в аудиторії з відключеними мобільними телефонами. Повага один до одного дає можливість ефективніше досягати поставлених командних результатів. При виконанні лабораторних робіт студент може користуватися ноутбуками. Проте під час лекційних занять та обговорення завдань лабораторних робіт не слід використовувати ноутбуки, смартфони, планшети чи комп’ютери. Це відволікає викладача і студентів групи та перешкоджає навчальному процесу. Якщо ви використовуєте свій ноутбук чи телефон для аудіо- чи відеозапису, необхідно заздалегідь отримати дозвіл викладача.
Дотримання академічної доброчесності студентів й викладачів регламентується кодекс честі Національного технічного університету України «Київський політехнічний інститут», положення про організацію освітнього процесу в КПІ ім. Ігоря Сікорського https://kpi.ua/code
8. Види контролю та рейтингова система оцінювання результатів навчання (РСО)
1) Рейтинг студента з кредитного модуля розраховується зі 100 балів, з них 60 балів складає стартова шкала RC та 40 балів – екзаменаційна шкала RE\ .
Стартовий рейтинг (протягом семестру) складається з балів, що студент отримує за:
відповіді на комп’ютерних практикумах – 6 балів (3 б. × 2);
виконання тестових (домашніх) завдань до комп’ютерних практикумів – 45 балів (3 б. × 15);
виконання модульної контрольної роботи – 9 балів.
Критерії нарахування балів:
- Робота на комп’ютерному практикумі
− повне володіння матеріалом під час відповіді – 3 бали;
− часткове володіння матеріалом – 2 бали;
− задовільне володіння матеріалом – 1 бал;
− незадовільне володіння матеріалом – 0 балів;
- *Виконання тестового (домашнього) завдання до комп’ютерного
практикуму*
(термін виконання та формат перевірки/захисту визначається викладачем) − повне виконання – 3 бали;
− неповне виконання – 0-2 балів.
- Виконання модульної контрольної роботи
− повне виконання – 9;
− неповне виконання – 0-8 балів.
- Умовою зарахування першого календарного контролю (6-ий тиждень, з 19.09.2022 по 29.10.2022) є отримання не менше 9 балів. За результатами навчальної роботи за перші 6 тижнів навчання максимально можлива кількість балів – 18 балів (5 тестів × 3 бал. + 3 бал. за відповідь).
Умовою зарахування другого календарного контролю (13-ий тиждень, з 05.12.2022 по 17.12.2022) є отримання не менше 21 балу. За результатами 13 тижнів навчання максимально можлива кількість балів – 42 бали (12 тестів × 3 бал. + 6 бал. за відповіді).
Умовою допуску до екзамену є стартовий рейтинг не менше 30 балів.
На екзамені студенти виконують письмову екзаменаційну контрольну роботу. Кожне завдання містить два теоретичних питання і два практичних. Перелік екзаменаційних питань доводиться до відома студентів на початку семестру. Кожне запитання (завдання) оцінюється у 10 балів за такими критеріями:
«відмінно», повна відповідь, не менше 90% потрібної інформації (повне, безпомилкове розв’язування завдання) – 10 балів;
«добре», достатньо повна відповідь, не менше 75% потрібної інформації або незначні неточності (повне розв’язування завдання з незначними неточностями) – 8-9 балів;
«задовільно», неповна відповідь, не менше 60% потрібної інформації та деякі помилки (завдання виконане з певними недоліками) – 6-7 балів;
«незадовільно», відповідь не відповідає умовам до «задовільно» – 0 балів.
6) Сума стартових балів та балів за екзаменаційну контрольну роботу переводиться до
екзаменаційної оцінки згідно з таблицею:
| Бали (RC + RE ) |
|
|---|---|
| 95…100 | Відмінно |
| 85…94 |
|
| 75…84 |
|
| 65…74 | Задовільно |
| 60…64 |
|
| Менше 60 |
|
| Стартовий рейтинг менше 30 балів |
|
9. Додаткова інформація з дисципліни (освітнього компонента) Питання, які виносяться на іспит:
Поняття множини. Способи представлення множин. Поняття підмножини. Порожня та універсальна множини. Булеан. Навести приклади.
Операції над множинами: об’єднання, перетин, доповнення, різниця, симетрична різниця.
Означення, представлення за допомогою діаграм Ейлера-Венна. Навести приклади.
Властивості операцій над множинами: ідемпотентність, дистрибутивність, закони де Моргана, властивості доповнення, різниці та симетричної різниці. Навести доведення 2-ма способами: аналітичним шляхом та за допомогою діаграм Ейлера-Венна. Навести приклади.
Властивості операцій над множинами: комутативність, асоціативність, дистрибутивність, властивості та U, поглинання, закони де Моргана. Навести доведення 2-ма способами: аналітичним шляхом та за допомогою діаграм Ейлера-Венна. Навести приклади.
Скінченні та нескінченні множини. Потужність множин. Потужність булеана скінченної множини. Обчислення потужностей множин. Рівнопотужні множини. Навести приклади.
Декартів добуток множин і його потужність. Кортежі, елементи кортежів. Навести приклади.
Методи доведення тотожностей в алгебрі множин: аналітичний (алгебраїчний), модельний, за допомогою діаграм Ейлера-Венна. Навести приклади.
Поняття відношення. n-арне відношення. Область визначення відношення. Множина значень відношення. Повне (універсальне) відношення. Тотожне (діагональне) відношення. Порожнє відношення. Навести приклади.
Бінарні відношення. Способи задання відношень (фактор-множиною, матричним способом, за допомогою графу). Навести приклади.
Операції над бінарними відношеннями: об’єднання, перетин, доповнення, різниця, обернення і композиція. Навести приклади.
Степінь відношення. Властивості операцій над бінарними відношеннями. Навести приклади.
Властивості бінарних відношень (рефлексивне, антирефлексивне (іррефлексивне), симетричне, асиметричне, антисиметричне, транзитивне). Навести приклади.
Замикання відношень. Симетричне, рефлексивне та транзитивне замикання, способи їх одержання. Алгоритм Уоршелла. Навести приклади.
Функціональне відношення, області визначення та значень. Всюди визначене відношення. Прообраз, образ функціонального відношення. Відображення. Типи відображень (сюр’єкція, ін’єкція, бієкція). Композиція відображень. Навести приклади.
Відношення еквівалентності. Класи еквівалентності. Матриця та граф відношення еквівалентності. Навести приклади. 16) Відношення порядку. Частковий порядок. Строгий порядок. Незрівнянні елементи. Множина частково впорядкована. Елемент найменший (найбільший). Мінімальний (максимальний) елемент. Діаграма Гассе. Навести приклади.
17) Алгебраїчні операції та їх властивості. Навести приклади. 18) Поняття та складові алгебраїчної структури. Алгебраїчні структури з однією операцією (півгрупа, моноїд, група, абелева група). Навести приклади.
Поняття та складові алгебраїчної структури. Алгебраїчні структури з двома операціями (кільце, алгебра, поле). Алгебра Буля. Навести приклади.
Гратки, булеві гратки. Навести приклади.
Булеві змінні та функції. Набори. Місність функцій. Способи задання булевих функцій (таблицею істинності, порядковим номером, аналітично). Навести приклади.
Булеві функції однієї та двох змінних. Навести приклади.
Властивості булевих функцій. Поняття суттєвих та несуттєвих змінних. Рівність функцій.
Навести приклади.
Двоїста функція, самодвоїста функція. Два способи знаходження двоїстої функції. Навести приклади.
Закони булевої алгебри. Навести доведення та приклади.
Диз'юнктивне розкладання булевих функцій за k змінними, за однією змінною, за всіма n (k<n) змінними. Навести приклади.
Диз’юнктивна нормальна форма. Досконала диз’юнктивна нормальна форма. Способи їх отримання. Навести приклади.
Кон'юнктивне розкладання булевих функцій за k змінними, за однією змінною, за всіма n
(k<n) змінними. Навести приклади.
- Кон’юнктивна нормальна форма. Досконала кон’юнктивна нормальна форма. Способи їх отримання. Навести приклади. 30) Задача мінімізації булевих функцій. Мета мінімізації булевих функцій. Індекс простоти. Імпліканти, прості імпліканти, повна система імплікант. Навести приклади.
Операції склеювання та поглинання. Скорочена, тупикова та мінімальна диз’юнктивні нормальні форми. Навести приклади.
Загальний алгоритм мінімізації булевих функцій. Метод мінімізаційних карт (діаграми Карно-Вейча). Навести приклади.
Алгебра Жегалкіна. Поліномом Жегалкіна та його побудова. Лінійна функція. Навести приклади. 34) Повні системи функцій. Функція, що зберігає 0 чи зберігає 1. Відношення передування. Монотонна функція. Критерій повноти Поста. Класи Поста. Навести приклади.
35) Основні поняття теорії графів. Неорієнтовані та орієнтовані графи. Інцидентність та суміжність. Граф простий, мультиграф, псевдограф. Види графів. Навести приклади. 36) Способи представлення графів (список ребер, матриця інцидентності, матриця суміжності, список суміжностей) для неорієнтованих та орієнтованих графів. Навести приклади.
Ізоморфізм графів. Графи та бінарні відношення. Навести приклади.
Степені вершин. Вершина ізольована, висяча. Граф однорідний степеня k. Півстепінь виходу, півстепінь заходу. Теорема Ейлера та наслідки. Повний граф. Дводольний граф. Повний дводольний граф. Підграфи. Навести приклади.
Маршрути, ланцюги та цикли. Простий ланцюг. Граф ациклічний. Шлях. Контур. Навести приклади.
Метричні характеристики графів: відстань між двома вершинами, ярус, діаметр, радіус, центр графу. Навести приклади.
Операції на графах: об’єднання, перетин, видалення вершини, стягування ребра. Навести приклади.
Зв’язність графів. Компоненти зв’язності. Число вершинної зв’язності. Число реберної зв’язності. Точка з’єднання. Розріз. Міст. Навести приклади.
Зв’язність орієнтованих графів: сильно-зв’язний, однобічно-зв’язний, слабко-зв’язний, незв’язний. Теорема про визначення типу зв’язності графу за допомогою матриць. Навести приклади.
Алгоритм побудови матриці відстаней і матриці досяжності (методом піднесення в степінь). Навести приклади.
Поняття дерева. Властивості дерев. Корінь, внутрішня вершина дерева, лист. Рівень вершини та висота дерева. Навести приклади.
Способи обходу дерева. Відповідні форми запису виразів. Навести приклади.
Обхід графів: пошук вшир (BFS-метод). Навести приклад.
Обхід графів: пошук вглиб (DFS-метод). Навести приклад.
Топологічне сортування методом Кана. Навести приклад.
Логіка висловлювань. Поняття висловлювання. Атоми та пропозиційні зв’язки. Формули логіки висловлювань. Навести приклади.
Інтерпретації, тавтології та суперечності. Таблиці істинності. Логічне слідування. Навести приклади.
Формальна теорія L (логіка L). Теорема дедукції. Методи перевірки тотожної істинності формул логіки висловлювань (за таблицею істинності, побудовою виводу у теорії L). Навести приклади.
Методи перевірки тотожної істинності формул логіки висловлювань (метод Квайна, метод редукції). Навести приклади.
Логіка предикатів. Поняття логіки предикатів. Квантори загальності й існування. Формули логіки предикатів. Зв’язані та вільні змінні. Навести приклади.
Основні тотожності логіки предикатів. Побудова таблиці істинності для предиката. Навести приклади.
Робочу програму навчальної дисципліни (силабус):
Складено доцент, к.ф.-м.н., Рибачук Л.В.
Ухвалено кафедрою ІСТ (протокол № 13 від 15.06.2022 р.)
Погоджено Методичною комісією факультету (протокол № 11 від 07.07.2022 р.)
