Спеціальні розділи математики. Частина 1. Дискретна математика - Робоча програма навчальної дисципліни (Силабус)
Реквізити навчальної дисципліни
| Рівень вищої освіти | Перший (бакалаврський) |
| Галузь знань | 12 Інформаційні технології |
| Спеціальність | 126 Інформаційні системи та технології |
| Освітня програма | Інформаційне забезпечення робототехнічних систем |
| Статус дисципліни | Нормативна |
| Форма навчання | очна(денна)/заочна/дистанційна/змішана |
| Рік підготовки, семестр | 1 курс, осінній семестр |
| Обсяг дисципліни | 4 кредитів |
| Семестровий контроль/ контрольні заходи | іспит |
| Розклад занять | http://rozklad.kpi.ua |
| Мова викладання | Українська |
| Інформація про керівника курсу / викладачів | Лектор, практичні: к.т.н., Солдатова М. О., benten1093@gmail.com |
| Розміщення курсу |
Програма навчальної дисципліни
Опис навчальної дисципліни, її мета, предмет вивчання та результати навчання
Мета курсу– сприяти більш глибшому розумінню та засвоєнню основних теоретичних положень з дискретної математики та формуванню здатності застосовувати ці положення для розв’язання практичних задач.
Предметом вивчення дисципліни є множини, відношення, відображення, логічні функції та висловлювання, графи, методи і засоби роботи з ними при розв’язання практичних задач.
Завдання вивчення дисципліни є:
вивчення та засвоєння теоретичних даних з теорії множин, математичної логіки та теорії графів;
набуття практичних навичок використання отриманих теоретичних знань для розв’язання задач.
Навчальна дисципліна покликана допомогти студенту отримати:
знання основних понять, методів, засобів, моделей та алгоритмів теорії
оптимізації;
розуміння суті процесу оптимізації на основі аналізу різних чинників,
принципів застосування методів теорії оптимізації;
уміння здійснювати математичну постановку і алгоритмізацію задач теорії
оптимізації, обґрунтовано обирати метод та алгоритм оптимізації рішень для
побудованої моделі, комп'ютерну реалізацію розрахунків та знаходити оптимальне
рішення поставленої задачі; практично застосовувати експертні процедури, методи
та технології теорії оптимізації; настроювати параметри вибраного програмного
забезпечення відповідно до конкретної задачі або класу задач;
здатність аналізувати завдання в своїй предметній області і вибирати
відповідне математичне і програмне забезпечення для моделювання і розв'язання
задач теорії оптимізації, враховуючи міжнародний і вітчизняний досвід.
КОМПЕТЕНТНОСТІ
Інтегральна компетентність Здатність розв'язувати складні спеціалізовані задачі та практичні проблеми у галузі інженерії програмного забезпечення, що характеризується комплексністю та невизначеністю умов із застосування теорій та методів інформаційних технологій.
Загальні компетентності
КЗ 1. Здатність до абстрактного мислення, аналізу та синтезу.
КЗ 2. Здатність застосовувати знання у практичних ситуаціях.
КЗ 3. Здатність до розуміння предметної області та професійної діяльності
КЗ 5. Здатність вчитися і оволодівати сучасними знаннями.
КЗ 6. Здатність до пошуку, оброблення та аналізу інформації з різних джерел.
Спеціальні (фахові, предметні) компетентності
КС 1. Здатність аналізувати об’єкт проектування або функціонування та його предметну область.
КС 11. Здатність до аналізу, синтезу і оптимізації інформаційних систем та технологій з використанням математичних моделей і методів.
КС 12. Здатність управляти та користуватися сучасними інформаційно-комунікаційними системами та технологіями (у тому числі такими, що базуються на використанні Інтернет).
Програмні результати навчання
ПР 2. Застосовувати знання фундаментальних і природничих наук,системного аналізу та технологій моделювання, стандартних алгоритмів та дискретного аналізу при розв’язанні задач проектування і використання інформаційних систем та технологій.
ПР 4. Проводити системний аналіз об’єктів проектування та обґрунтовувати вибір структури, алгоритмів та способів передачі інформації в інформаційних системах та технологіях.
Пререквізити та постреквізити дисципліни (місце в структурно-логічній схемі навчання за відповідною освітньою програмою)
Пререквізити – відсутні, дисципліна є базовою.
Постреквізити – Теорія алгоритмів, Програмування, Теорія і методи оптимізації, Теорія систем та системний аналіз, Моделювання технічних систем, Управління проєктами.
Зміст навчальної дисципліни
Розділ 1. Множини
1.1.Множини. Способи задання множин
1.2.Основні поняття теорії множин
1.3.Геометрична інтерпретація множин
1.4.Операції на множинах
1.5.Алгебра множин
Розділ 2. Відношення
2.1.Поняття відношення. Задання відношень
2.2.Операції над відношеннями
2.3.Властивості бінарних відношень
2.4.Відношення еквівалентності, толерантності, порядку
2.5.Функціональні відношення
Розділ 3. Алгебраїчні структури
3.1.Алгебраїчні операції та їх властивості
3.2.Поняття алгебраїчної структури
3.3.Найпростіші алгебраїчні структури
3.4.Ґратки
Розділ 4. Булеві функції та перетворення
4.1.Булеві змінні і функції
4.2.Способи задання булевих функцій
4.3.Двоїстість
4.4.Закони булевої алгебри
4.5.Диз'юнктивні та кон'юнктивні розкладання булевих функцій
4.6.Нормальні форми зображення булевих функцій
4.7.Мінімізація булевих функцій
4.8.Алгебра Жегалкіна. Лінійні функції
4.9.Функції, що зберігають нуль та одиницю. Монотонні функції
Розділ 5. Математична логіка
5.1.Історія і задачі математичної логіки
5.2.Поняття логіки висловлень
5.3.Дедуктивні висновки у логіці висловлень
5.4.Обчислення висловлень
5.5.Логіка предикатів
5.6.Квантори
5.7.Формули у логіці предикатів
5.8.Закони і тотожності у логіці предикатів
5.9.Випереджені нормальні форми і логічний висновок
5.10.Обчислення предикатів
5.11.Багатозначна логіка
Розділ 6. Теорія графів
6.1.Основні терміни
6.2.Способи задання графа
6.3.Операції над графами
6.4.Ейлерові та напівейлерові графи
6.5.Гамільтонові та напівгамільтонові графи
6.6.Планарність графів
6.7.Розфарбування графа
6.8.Дерева
6.9.Бінарні дерева пошуку
6.10.Остови (каркаси) графа
6.11.Найкоротші відстані та шляхи у мережах
6.12.Течії у мережах
Розділ 7. Автомати
7.1.Основні поняття
7.2.Скінченні автомати
7.3.Перетворювачі. Автомати Мура та Мілі
7.4. Розпізнавачі.
7.5. Мінімізація автоматів.
7.6. Недетерміновані автомати. Часткові автомати. Епсилон-автомати.
7.7. Мови та граматики. Алгебраїчні операції з мовами. Регулярні мови.
7.8. Пошукові автомати.
7.9. Формальні граматики. Ієрархія граматик.
7.10. Нормальні форми Хомського та Грейбах.
7.11. Розпізнавання контекстно вільних мов.
Навчальні матеріали та ресурси
Основна:
1. Бондаренко М. Ф., Білоус Н. В., Руткас А. Т. Комп’ютерна дискретна математика / Х.: Компанія СМІТ, 2004 – 480 с.
2. Нікольський Ю.В., Пасічник В.В., Щербина Ю. М. Дискретна математика. – К.: Видавнича група BHV, 2007
3. Капітонова Ю.В., Кривий С.Л., Летичевський О.А., Луцький Г.М., Печурін М.К. Основи дискретної математики: Підручник. – Київ: Видавництво “ЛітСофт”, 2000.
4.. Бардачов Ю.М., Соколова Н.А., В.Є. Ходаков. Дискретна математика: Підручник. –К.: Вища шк., 2002.
5. Новиков Ф.А. Дискретная математика для программистов. Учебник для вузов. 2–е изд. – СПб.: Питер, 2006.
6. Таран Т.А. Основы дискретной математики. – К.: Просвіта, 2003.
7. Таран Т.А., Мыценко Н.А., Темникова Е.Л. Сборник задач по дискретной математике. – К.: Просвіта, 2001.
Додаткова:
1. Бардачов Ю. М., Соколова Н. А., Ходаков В. Е. Дискретна математика / К.: 2002 – 288 с.
2. Белоусов А. И., Ткачев С. Б.. Дискретная математика, учебник / М/: МГУ, 2002 – 744 с.
3. Гаврилов Г. П. Сборник задач по курсу дискретной математики / М.: Наука, 1992 – 408 с.
4. Капітонова Ю. В., Кривий С. Н., Летичевський О. А. Основи дискретної математики / К.: Наукова думка, 2002 – 380 с.
5. Спекторський І. Я. Дискретна математика / К.: Політехніка, 2004 – 220 с.
Інформаційні ресурси
https://classroom.google.com/u/1/c/Mzg1OTM3NzY2ODI5
Навчальний контент
Методика опанування навчальної дисципліни (освітнього компонента)
| Форма навчання | Семестрові (кредитні) модулі | Всього кредитів /годин | Розподіл навчального часу за видами занять | Семестрова атестація | |||
| Лекції | Практичні (семінарські) заняття | Лабораторні роботи | СРС | ||||
| Денна | Всього | 4/120 | 36 | 36 | - | 48 | |
| 2 | 4/120 | 36 | 36 | - | 48 | іспит |
Лекційні заняття
| № з/п | Назва теми лекції та перелік основних питань | |
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
Математична логіка 1. Історія і задачі математичної логіки. Історична довідка про розвиток математичної логіки. Типові задачі. ([1] с.183, [2] с.9) 2. Поняття логіки висловлень. Висловлення, істиннісне значення, атом, логічні зв'язки, правильно побудована формула, інтерпретація висловлення, пріоритет і ранг операцій, тавтологія, тотожно хибна формула, незагальнозначуща формула. ([1] с.185, [2] с.9) 3. Дедуктивні висновки у логіці висловлень. Логічний наслідок та його властивості, аксіоми, доведення, правила дедуктивних висновків. ([1] с.197, [2] с.26) 4. Обчислення висловлень. Мова, аксіоми і правила висновку, повнота та несуперечність, правила відділення і підстановки, теорема дедукції та її наслідок, доведення методом від супротивного. ([1] с.201, [2] с.15, [4] с.151) |
||
1. Логіка предикатів. Порядок предиката, область визначення предиката, терм, предметні змінні та константи. ([1] с.207, [2] с.23, [4] с.158) 2. Квантори. Квантор загальності, квантор існування, зв'язана та вільна змінна, зменшення порядку n-місних предикатів. ([1] с.212, [2] с.25, [4] с.158) 3. Формули у логіці предикатів. Елементарна формула, правильно побудовані формули, область дії квантора, інтерпретація формул логіки предикатів, загальнозначущі та суперечливі формули, логічний наслідок. ([1] с.217, [2] с.23) 4. Закони і тотожності у логіці предикатів. Заміна зв'язаної змінної, комутативні і дистрибутивні властивості кванторів, закон де Моргана для кванторів. ([1] с.220, [2] с.32) 5. Випереджені нормальні форми і логічний висновок. Випереджена нормальна форма, алгоритм зведення до випередженої нормальної форми, правила видалення/ введення квантора загальності/існування. ([1] с.223, [2] с.25) 6. Обчислення предикатів. Структура обчислення предикатів, правила відділення та узагальнення, правила і -введення, перейменування вільних і зв'язаних змінних. ([1] с.227, [2] |
||
|
||
3. Зв'язність графів. ([1] с.239, [2] с.88) |
||
1. Ейлерові та напівейлерові графи. Маршрути, ланцюги та цикли. Поняття ейлерового та напівейлерового графів. Теореми про необхідні та достатні умови існування ейлерового циклу у графі. ([1] с.246, [2] с.108, [4] с.250) 2. Гамільтонові та напівгамільтонові графи. Поняття гамільтонового та напівгамільтонового графів. Теореми про необхідні та достатні умови існування гамільтонового циклу у графі. ([1] с.304, [2] с.111, [4] с.252) 3. Планарність графів. Ізоморфізм та гомоморфізм графів. Теорема Понтрягіна-Куратовського. ([1] с.253, [2] с.124, [4] с.253) 4. Розфарбування графа. Хроматичне число графа. Теореми про оцінку хроматичного числа. Проблема чотирьох фарб. Двоїстий граф. Задачі, що можна розв’язувати за допомогою розфарбування графів. ([1] с.260, [2] с.126, [4] с.249) |
||
1. Дерева. Поняття та властивості дерева. Основні терміни. Кореневі та позначені дерева. Орієнтовані дерева. Пошук углиб. Пошук ушир. Обхід дерев. ([1] с.269, [2] с.150, [4] с.249) 2. Остови (каркаси) графа. Остов (каркас) графа. Застосування. Алгоритм побудови остова. Остів мінімальної ваги. Алгоритм Краскала. ([1] с.269, [2] с.175, [4] с.248) |
||
1. Найкоротші відстані та шляхи у незважених графах. Хвильовий алгоритм. Алгоритм Террі. 2. Найкоротші відстані та шляхи у незважених графах.Алгоритми Дейкстри, Форда-Беллмана для пошуку найкоротшого шляху між двома вершинами. Алгоритми Флойда і Данцига для пошуку найкоротших шляхів між всіма вершинами. ([1] с.292, [2] с.113, [4] с.277) |
||
1. Дослідження перерізів і циклів у мережі. Фундаментальні матриці перерізів та циклів. Застосування. Теорема Пуанкаре. ([1] с.286) 2. Течії у мережах. Джерела і стоки. Алгоритми розрахунку максимальної течії у мережі з одним джерелом і одним стоком та з багатьма джерелами і стоками. ([1] с.322) |
||
Автомати 1. Основні поняття. Історична довідка про розвиток теорії автоматів. Типові задачі. ([1] с.385) 2. Скінченні автомати. Способи опису. ([1] с.391, [2] с.285) 3. Перетворювачі. Способи опису. Типові задачі. Автомат Мура. Автомат Мілі ([1] с.399, [2] с.314) |
||
|
Практичні заняття (комп’ютерні практикуми)
| Практична робота | Тема | Години |
|---|---|---|
| Практична робота 1 | Розділ 1. Множини Способи задання множин. Геометрична інтерпретація множин. Операції на множинах. Алгебра множин. | 2 |
| Практична робота 2 | Розділ 2. Відношення Задання відношень. Операції над відношеннями. Властивості бінарних відношень. | 2 |
| Практична робота 3 | Відношення еквівалентності, толерантності, порядку | 2 |
| Практична робота 4 | Функціональні відношення. | 2 |
| Практична робота 5 | Розділ 3. Алгебраїчні структури Алгебраїчні операції та їх властивості. Найпростіші алгебраїчні структури. | 2 |
| Практична робота 6 | . Розділ 4. Булеві функції та перетворення Способи задання булевих функцій. Двоїстість. Закони булевої алгебри. | 2 |
| Практична робота 7 | Диз'юнктивні та кон'юктивні розкладання булевих функцій. Нормальні форми зображення булевих функцій. | 2 |
| Практична робота 8 | . Мінімізація булевих функцій методом карт Карно (діаграм Вейча). Мінімізація функцій методом Порецького - Блейка. Мінімізація функцій методом Квайна - Мак-Класкі. | 2 |
| Практична робота 9 | Тотожності алгебри Жегалкіна. Поліном Жегалкіна. Лінійні функції. Функції, що зберігають нуль та одиницю. Монотонні функції. | 2 |
| Практична робота 10 | Контрольна робота | 2 |
| Практична робота 11 | Розділ 5. Математична логіка Дедуктивні висновки у логіці висловлень. Обчислення висловлень. | 2 |
| Практична робота 12 | Логіка предикатів. Квантори. Формули у логіці предикатів. Закони і тотожності у логіці предикатів. Обчислення предикатів. | 2 |
| Практична робота 13 | Розділ 6. Комп’ютерний практикум. Представлення графів, характеристики графів. | |
| Практична робота 14 | Комп’ютерний практикум. Операції над матрицями графів | 2 |
| Практична робота 15 | Комп’ютерний практикум. Ейлерів та гамільтонів цикли.. | 2 |
| Практична робота 16 | Комп’ютерний практикум. Планарні графи, розфарбування графів. | 2 |
| Практична робота 17 | Комп’ютерний практикум. Найкоротший шлях в графі. | 2 |
| Практична робота 18 | Контрольна робота. |
Всього на практичні заняття виділено36 годин.
Самостійна робота студента
Самостійна робота студентів складається з:
підготовки до аудиторних занять;
підготовка до виконання практичних робіт;
підготовка до контрольних робіт
підготовка до іспиту.
Самостійна робота
| Тема | Години | |
| . Скінченні та нескінченні множини, упорядковані множини. | 4 | |
| Відношення толерантності. Функціональне відношення, області визначення і значень, відображення, сюр'єкція, ін'єкція, бієкція. | 4 | |
| Гомоморфізм, ізоморфізм. Найпростіші алгебраїчні структури. Півгрупа, моноїд, група, абелева група, кільця і поля. Ґратки. Верхня та нижня грані у частково упорядкованій множині, ґратка, повна ґратка, одиниця і нуль ґратки. | 6 | |
| Мінімізація функцій методом Нельсона. Мінімізація функцій методом Порецького — Блейка. Відношення порядку для інтерпретацій, ознаки монотонності функції. | 6 | |
| Обчислення висловлень. Мова, аксіоми і правила висновку, повнота та несуперечність, правила відділення і підстановки, теорема дедукції та її наслідок, доведення методом від супротивного. ([1] с.201, [2] с.15, [4] с.151) Багатозначна логіка. Виникнення багатозначних логік, значення істинності висловлення, алфавіт багатозначної логіки, унарні і бінарні функції, повна система функцій багатозначної логіки | 10 | |
| Ейлерові та напівейлерові графи. Теореми про необхідні та достатні умови існування ейлерового циклу у графі. ([1] с.246, [2] с.108, [4] с.250) Гамільтонові та напівгамільтонові графи. Теореми про необхідні та достатні умови існування гамільтонового циклу у графі. ([1] с.304, [2] с.111, [4] с.252) Планарні графи. Теорема Понтрягіна-Куратовського. Розфарбування графа. Задачі, що можна розв’язувати за допомогою розфарбування графів. ([1] с.260, [2] с.126, [4] с.249) Дослідження перерізів і циклів у графі. Застосування. ([1] с.286) Течії у мережах. Алгоритми розрахунку максимальної течії у мережі з одним джерелом і одним стоком та з багатьма джерелами і стоками. | 10 | |
Автомати Мілі та Мура |
8 |
Політика та контроль
Політика навчальної дисципліни (освітнього компонента)
Форми організації освітнього процесу, види навчальних занять і оцінювання результатів навчання регламентуються Положенням про організацію освітнього процесу в Національному технічному університеті України «Київському політехнічному інституті імені Ігоря Сікорського».
Політика виставлення оцінок: кожна оцінка виставляється відповідно до розроблених викладачем та заздалегідь оголошених студентам критеріїв, а також мотивується в індивідуальному порядку на вимогу студента; у випадку не виконання студентом усіх передбачених навчальним планом видів занять (практичних робіт, контрольних робіт) до екзамену він не допускається; пропущені заняття обов’язково мають бути відпрацьовані.
Відвідування є обов'язковим (за винятком випадків, коли існує поважна причина, наприклад, хвороба чи дозвіл працівників деканату). Якщо студент не може бути присутніми на заняттях, він все одно несете відповідальність за виконання завдань, що проводились в комп’ютерному класі.
Порядок зарахування пропущених занять. Відпрацювання пропущеного заняття з лекційного курсу здійснюється шляхом підготовки і захисту реферату за відповідною темою у вигляді презентації. Захист реферату відбувається відповідно до графіку консультацій викладача, з яким можна ознайомитись на кафедрі. Відпрацювання пропущеного практичного заняття здійснюється шляхом самостійного виконання завдання і його захисту відповідно до графіку консультацій викладача.
Реферати також можуть підготувати студенти, у яких недостатньо рейтингових балів.
Політика академічної поведінки та доброчесності: конфліктні ситуації мають відкрито обговорюватись в академічних групах з викладачем, необхідно бути взаємно толерантним, поважати думку іншого. Плагіат та інші форми нечесної роботи неприпустимі. Всі індивідуальні завдання та курсову роботу студент має виконати самостійно із використанням рекомендованої літератури й отриманих знань та навичок. Цитування в письмових роботах допускається тільки із відповідним посиланням на авторський текст. Недопустимі підказки і списування у ході захисту лабораторних робіт, на контрольних роботах, на іспиті.
Норми академічної етики: дисциплінованість; дотримання субординації; чесність; відповідальність; робота в аудиторії з відключеними мобільними телефонами. Повага один до одного дає можливість ефективніше досягати поставлених командних результатів. При виконанні лабораторних робіт студент може користуватися ноутбуками. Проте під час лекційних занять та обговорення завдань лабораторних робіт не слід використовувати ноутбуки, смартфони, планшети чи комп’ютери. Це відволікає викладача і студентів групи та перешкоджає навчальному процесу. Якщо ви використовуєте свій ноутбук чи телефон для аудіо- чи відеозапису, необхідно заздалегідь отримати дозвіл викладача.
Дотримання академічної доброчесності студентів й викладачів регламентується кодекс честі Національного технічного університету України «Київський політехнічний інститут», положення про організацію освітнього процесу в КПІ ім. Ігоря Сікорського
Види контролю та рейтингова система оцінювання результатів навчання (РСО)
РОЗПОДІЛ БАЛІВ, ЯКІ ОТРИМУЮТЬ СТУДЕНТИ ПІД ЧАС ВИВЧЕННЯ ДИСЦИПЛІНИ
| Види контролю | бали |
|---|---|
| Домашні роботи (10 робіт) | 2 |
| Самостійні роботи ( 3 роботи) | 1 |
| Контрольна робота ( 2 роботи) | 5 |
| Комп’ютерні практикуми (5 практикумів) | 3 |
| Індивідуальне завдання | 12 |
| Іспит | 40 |
R=2*10+1*3+5*2+3*5+12+40=100
Календарний контроль: провадиться двічі на семестр як моніторинг поточного стану виконання вимог силабусу.
За результатами навчальної роботи за перші 7 тижнів максимально можлива кількість балів – 14 балів. На першій атестації (8-й та 9-й тиждень) студент отримує “зараховано”, якщо його поточний рейтинг не менше 8 балів.
За результатами 13 тижнів навчання максимально можлива кількість балів – 30 балів. На другій атестації (14-й тиждень) студент отримує “зараховано”, якщо його поточний рейтинг не менше 16 бали.
Семестровий контроль: іспит.
Умови допуску до семестрового контролю: мінімально позитивна оцінка за індивідуальне завдання / зарахування усіх практичних робіт та підсумкова кількість балів не менше 35.
Таблиця відповідності рейтингових балів оцінкам за університетською шкалою:
| Кількість балів | Оцінка |
| 100-95 | Відмінно |
| 94-85 | Дуже добре |
| 84-75 | Добре |
| 74-65 | Задовільно |
| 64-60 | Достатньо |
| Менше 60 | Незадовільно |
| Не виконані умови допуску (<40) | Не допущено |
Додаткова інформація з дисципліни (освітнього компонента)
Рекомендовані теми рефератів.
Теми рефератів для отримання додаткових балів:
Історія розвитку розділів дискретної математики.
Задача комівояжера.
Сфери застосування в програмуванні та моделюванні систем.
Робочу програму навчальної дисципліни (силабус):
Складено ст. викладач, к.т.н. Солдатова М. О.
Ухвалено кафедрою ІСТ(протокол № 1 від 30.08.2021 р.)
Погоджено Методичною комісією факультету[1] (протокол № 1 від 30.08.2021 р.)
[1] Методичною радою університету – для загальноуніверситетських дисциплін.
