Дискретна математика
Спеціальність: Системна інженерія (Інтернет речей)
Код дисципліни: 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-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).