Дискретна математика
Спеціальність: Системна інженерія (Інтернет речей)
Код дисципліни: 6.122.09.O.010
Кількість кредитів: 6.00
Кафедра: Комп'ютеризовані системи автоматики
Лектор: Дзелендзяк Уляна Юріївна
Семестр: 2 семестр
Форма навчання: денна
Завдання: Вивчення навчальної дисципліни передбачає формування у студентів необхідних компетентностей:
інтегральна компетентність (ІНТ):
Здатність розв’язувати складні спеціалізовані задачі та практичні проблеми у галузі комп’ютерних наук або у процесі навчання, що передбачає застосування теорій та методів інформаційних технологій і характеризується комплексністю та невизначеністю умов.
загальні компетентності:
ЗК1. Здатність до абстрактного мислення, аналізу та синтезу.
ЗК2. Здатність застосовувати знання у практичних ситуаціях.
ЗК3. Знання та розуміння предметної області та розуміння професійної діяльності.
ЗК7. Здатність до пошуку, оброблення та аналізу інформації з різних джерел.
?
фахові компетентності:
ФК1. Здатність до математичного формулювання та досліджування неперервних та дискретних математичних моделей, обґрунтовування вибору методів і підходів для розв’язування теоретичних і прикладних задач у галузі комп’ютерних наук, аналізу та інтерпретування.
Результати навчання: знати:
- роль та місце дискретної математики в типових задачах спеціальності;
- загальний математичний апарат та засоби дискретного аналізу;
- математичний апарат теорії графів;
- математичний апарат теорії автоматів;
- математичний апарат теорії множин;
- математичний апарат теорії граматик;
- основи теорії алгоритмів;
- сучасні засоби програмування дискретного аналізу на базі обчислювальної техніки.
вміти:
- формулювати прикладні проблеми у вигляді моделей дискретного аналізу;
- застосовувати методи дискретного аналізу для розв’язання цих проблем;
- досліджувати властивості моделей дискретного аналізу;
- описувати формально синтаксис мов;
- конструювати алгоритми розв’язування прикладних задач;
- аналізувати результати розв’язування цих задач.
програмні результати навчання:
ПР2. Використовувати сучасний математичний апарат неперервного та дискретного аналізу, лінійної алгебри, аналітичної геометрії в професійній діяльності для розв’язання задач теоретичного та прикладного характеру в процесі проектування та реалізації об’єктів інформатизації.
Необхідні обов'язкові попередні та супутні навчальні дисципліни: 1. Алгебра і геометрія
2. Організація баз даних та знань
3. Алгоритми і структури даних + КР
Короткий зміст навчальної програми: Навчальна дисципліна СК6 Дискретна математика включена до циклу дисциплін загальної підготовки за переліком освітньо-професійної програми бакалавра за спеціальністю 122 Комп’ютерні науки спеціалізації Системна інженерія (Інтернет речей)). У структурно-логiчнiй схемі навчання зазначена дисципліна розміщена на І-му курсі.
У процесі навчання студенти розробляють моделі дискретного аналізу для реальних задач, застосовуючи для цього методи дискретного аналізу, а також досліджують властивості цих моделей, вчаться описувати формально синтаксис мов; конструювати алгоритми розв’язування прикладних задач та аналізувати їх результати. Реалізація алгоритмів для розв’язування прикладних задач проводиться у програмних середовищах С++, Python, Java.
Опис: 1.1. Множини. Операції над множинами. Інтуїтивне означення множини. Способи задання множин. Парадокс Рассела. Універсум. Підмножини. Операції над множинами.
1.2. Відношення. Декартовий добуток. Відношення. Способи задання відношень. Властивості відношень. Алгоритм Уоршелла.
2.1 Відображення і функції. Функціональні відношення. Типи відображень. Властивості відображень. Композиція відображень.
2.2. Відношення еквівалентності та порядку. Відношення еквівалентності. Матриця та граф відношення еквівалентності. Відношення порядку. Вагові функції та відношення квазіпорядку. Структура впорядкованих множин. Повністю впорядкована множина.
2.3. Потужність множин. Визначення потужності. Кардинальні числа. Зліченні множини. Незліченні множини. Континуум-гіпотеза.
3.1. Алгебри. Композиція об’єктів. Означення алгебри. Замкнення. Властивості операцій. Гомоморфізм та ізоморфізм алгебр.
3.2. Типи алгебр. Початкові означення. Алгебри з однією операцією. Група підстановок. Алгебри з двома операціями.
3.3. Ґратки. Основні означення. Ґратки як алгебри. Дистрибутивні та модулярні ґратки. Булеві ґратки.
3.4. Математична логіка. Булеві функції. Булеві функції двох змінних. Булевий простір. Властивості функцій алгебри логіки. Реалізація булевих функцій формулами. Рівносильні формули.
3.5. Принцип двоїстості. Нормальні форми. Проблема розв’язуваності. Розвинення булевої функції за змінними. Диз’юнктивні нормальні форми. Кон’юнктивні нормальні форми. Властивості досконалих форм.
3.6. Мінімальні диз’юнктивні та кон’юнктивні нормальні форми. Індекс простоти. Скорочена форма. Метод Квайна утворення скороченої диз’юнктивної нормальної форми. Тупикові нормальні форми. Метод мінімізаційних карт (діаграми Карно-Вейча).
3.7. Повні системи функцій. Алгебра Жегалкіна. Властивості булевих функцій. Функціонально замкнуті класи булевих функцій. Набори повних систем.
3.8. Нечіткі множини. Характеристики нечітких множин. Методи побудови функцій приналежності нечітких множин. Операції над нечіткими множинами. Властивості операцій над нечіткими множинами.
4.1. Формальні системи. Логіка висловлювань. Логічне слідування. Тавтології. Формальні системи та аксіоматичний підхід. Властивості формальних теорій.
4.2. Числення висловлювань. Теорема дедукції. Приклади виведень у теорії L. Інші формалізації логіки висловлювань. Модельні властивості теорії L. Інші методи перевірки тотожної істинності формул логіки висловлювань.
4.3. Логіка першого порядку. Поняття предикату. Квантори. Терми та формули. Інтерпретації формул логіки першого порядку. Властивості формул логіки першого порядку. Перевірка загальнозначущості формул логіки першого порядку.
4.4. Числення предикатів. Формальна теорія K. Прикладні теорії першого порядку. Модельні властивості числення K.
4.5. Комбінаторні задачі. Правила суми та добутку. Розміщення, сполучення та перестановки. Схема визначення виду комбінації.
4.6. Біноміальні коефіцієнти. Розбиття. Біном Ньютона. Поліноміальна теорема. Задача про цілочислові розв’язки. Принцип включення-виключення. Розбиття. Числа Стірлінга другого роду та числа Белла.
4.7. Алгоритми комбінаторики. Генерування перестановок. Генерування сполучень. Генерування розбиттів множини.
4.8. Граматики. Формальні породжувальні граматики Типи граматик (ієрархія Хомскі).
4.9. Скінченні автомати. Скінченні автомати з виходом. Скінченні автомати без виходу. Подання мов.
Методи та критерії оцінювання: 1. Опитування на практичних заняттях.
2. Розрахунково-графічна робота.
3. Екзамен.
Критерії оцінювання результатів навчання: Максимальна оцінка в балах:
1. Виконання практичних завдань і розрахунково-графічної роботи (40 балів)
2. Екзамен письмова компонента (45 балів), усна компонента (15 балів).
Разом за дисципліну – 100 балів.
Порядок та критерії виставляння балів та оцінок: 100–88 балів – («відмінно») виставляється за високий рівень знань (допускаються деякі неточності) навчального матеріалу компонента, що міститься в основних і додаткових рекомендованих літературних джерелах, вміння аналізувати явища, які вивчаються, у їхньому взаємозв’язку і роз витку, чітко, лаконічно, логічно, послідовно відповідати на поставлені запитання, вміння застосовувати теоретичні положення під час розв’язання практичних задач; 87–71 бал – («добре») виставляється за загалом правильне розуміння навчального матеріалу компонента, включаючи розрахунки , аргументовані відповіді на поставлені запитання, які, однак, містять певні (неістотні) недоліки, за вміння застосовувати теоретичні положення під час розв’язання практичних задач; 70 – 50 балів – («задовільно») виставляється за слабкі знання навчального матеріалу компонента, неточні або мало аргументовані відповіді, з порушенням послідовності викладення, за слабке застосування теоретичних положень під час розв’язання практичних задач; 49–26 балів – («не атестований» з можливістю повторного складання семестрового контролю) виставляється за незнання значної частини навчального матеріалу компонента, істотні помилки у відповідях на запитання, невміння застосувати теоретичні положення під час розв’язання практичних задач; 25–00 балів – («незадовільно» з обов’язковим повторним вивченням) виставляється за незнання значної частини навчального матеріалу компонента, істотні помилки у відповідях на запитання, невміння орієнтуватися під час розв’язання практичних задач, незнання основних фундаментальних положень.
Рекомендована література: 1. Нікольський Ю.В., Пасічник В.В., Щербина Ю.М. Дискретна математика. – Львів.: Видавництво "Магнолія-2006", 2011. – 432 с.
2. Капітонова Д. В., Кривий С. Л., Летичевський О. А. Основи дискретної математики // Підручник / НАН України. МОН України – К. : Наукова думка, 2002. – 579 с..
3. Коцовський В.М. Основи дискретної математики: навчальний посібник. Ужгород: ПП «АУТДОР- ШАРК», 2020. - 128 с.
4. Матвієнко М.П. Дискретна математика: навч. посібник. Ліра-К, 2014. – 348 с.
5. В.Липский. Комбинаторика для программистов. М.: Мир, 1988.
6. Новицький І.В., Ус С.А. Дискретна математика в прикладах і задачах: навчальний посібник. – Д. :Національний гірничий університет, 2013. – 89 с.
Уніфікований додаток: Національний університет «Львівська політехніка» забезпечує реалізацію права осіб з інвалідністю на здобуття вищої освіти. Інклюзивні освітні послуги надає Служба доступності до можливостей навчання «Без обмежень», метою діяльності якої є забезпечення постійного індивідуального супроводу навчального процесу студентів з інвалідністю та хронічними захворюваннями. Важливим інструментом імплементації інклюзивної освітньої політики в Університеті є Програма підвищення кваліфікації науково-педагогічних працівників та навчально-допоміжного персоналу у сфері соціальної інклюзії та інклюзивної освіти. Звертатися за адресою:
вул. Карпінського, 2/4, І-й н.к., кімн. 112
E-mail: nolimits@lpnu.ua
Websites: https://lpnu.ua/nolimits https://lpnu.ua/integration
Академічна доброчесність: Політика щодо академічної доброчесності учасників освітнього процесу формується на основі дотримання принципів академічної доброчесності з урахуванням норм «Положення про академічну доброчесність у Національному університеті «Львівська політехніка» (затверджене вченою радою університету від 20.06.2017 р., протокол № 35).