Дискретна математика

Спеціальність: Комп'ютерні науки (Системи штучного інтелекту)
Код дисципліни: 6.122.13.O.008
Кількість кредитів: 5.00
Кафедра: Системи штучного інтелекту
Лектор: Мельникова Н.І.
Семестр: 2 семестр
Форма навчання: денна
Мета вивчення дисципліни: Вивчення основних методичних засад та опанування теоретичних основ математичної логіки, теорії множин, комбінаторики та теорії графів
Завдання: Вивчення навчальної дисципліни передбачає формування у здобувачів освіти компетентностей: 1. Здатність до абстрактного мислення, аналізу та синтезу. 2. Здатність застосовувати знання у практичних ситуаціях. 3. Знання та розуміння предметної області та розуміння професійної діяльності. 4. Здатність до пошуку, оброблення та аналізу інформації з різних джерел. Фахові компетентності: 1. Здатність до математичного формулювання та досліджування неперервних та дискретних математичних моделей, обґрунтовування вибору методів і підходів для розв’язування теоретичних і прикладних задач у галузі комп’ютерних наук, аналізу та інтерпретування. 2. Здатність до виявлення статистичних закономірностей недетермінованих явищ, застосування методів обчислювального інтелекту, зокрема статистичної, нейромережевої та нечіткої обробки даних, методів машинного навчання та генетичного програмування тощо. 3. Здатність використовувати сучасні методи математичного моделювання об’єктів, процесів і явищ, розробляти моделі й алгоритми чисельного розв’язування задач математичного моделювання, враховувати похибки наближеного чисельного розв’язування професійних задач.
Результати навчання: ПР1. Застосовувати знання основних форм і законів абстрактно-логічного мислення, основ методології наукового пізнання, форм і методів вилучення, аналізу, обробки та синтезу інформації в предметній області комп'ютерних наук. ПР2. Використовувати сучасний математичний апарат неперервного та дискретного аналізу, лінійної алгебри, аналітичної геометрії, в професійній діяльності для розв’язання задач теоретичного та прикладного характеру в процесі проектування та реалізації об’єктів інформатизації. ПР5. Проектувати, розробляти та аналізувати алгоритми розв’язання обчислювальних та логічних задач, оцінювати ефективність та складність алгоритмів на основі застосування формальних моделей алгоритмів та обчислюваних функцій.
Необхідні обов'язкові попередні та супутні навчальні дисципліни: Алгоритмізація та програмування Математичний аналіз
Короткий зміст навчальної програми: Логіка та методи доведення Множини та відношення Графи Дерева Булеві функції Комбінаторика Формальні мови та граматики
Опис: ЛЕКЦІЯ 1. ЛОГІКА ТА МЕТОДИ ДОВЕДЕННЯ. Логіка висловлювань. Закони логіки висловлювань. Нормальні форми логіки висловлювань. Логіка першого ступеня. Закони логіки першого ступеня. Випереджена нормальна форма. Логічне виведення в логіці висловлювань. Застосування правил виведення в логіці висловлювань. Метод резолюцій. Правила виведення в численні предикатів. Методи доведення теорем. ЛЕКЦІЯ 2. БУЛЕВІ ФУНКЦІЇ Означення булевої функції. Алгебри булевих функцій: алгебра Буля та алгебра Жегалкіна. Спеціальні форми подання булевих функцій. Повнота та замкненість. Мінімізація булевих функцій. Реалізація булевих функцій схемами ЛЕКЦІЯ 3. МНОЖИНИ ТА ВІДНОШЕННЯ Множина. Кортеж, Декартів добуток. Операції над множинами. Доведення рівностей з множинами. Комп’ютерне подання множин. Відношення та їх властивості. Відношення еквівалентності. Відношення часткового порядку. Топологічне сортування. Операції над відношеннями. Замикання відношень. ЛЕКЦІЯ 4. ГРАФИ Основні означення та властивості. Спеціальні класи простих графів. Способи подання графів. Шляхи та цикли. Зв’язність. Ізоморфізм графів. Ейлерів та Гамільтонів цикли у графі. Зважені графи й алгоритми пошуку найкоротших шляхів. Обхід графів. Планарні графи. Розфарбовування графів. Незалежні множини вершин. Кліки. Паросполучення в графах. Теорема Холла. Найбільше паросполучення у дводольних графах ЛЕКЦІЯ 5. ДЕРЕВА Основні означення та властивості. Рекурсія. Обхід дерев. Префіксна та постфіксна форми запису виразів. Бінарне дерево пошуку. Дерево рішень. Бектрекінг (пошук із поверненнями). Каркаси (з’єднувальні дерева) ЛЕКЦІЯ 6. ЕЛЕМЕНТИ КОМБІНАТОРНОГО АНАЛІЗУ Основні правила комбінаторного аналізу. Розміщення та сполучення. Перестановки. Біном Ньютона. Поліноміальна теорема. Задача про цілочислові розв’язки. Генерування комбінаторних об’єктів. Рекурентні рівняння. Принцип коробок Діріхле. Принцип включення-виключення. ЛЕКЦІЯ 7. МОВИ, ГРАМАТИКИ ТА АВТОМАТИ Мови. Формальні породжувальні граматики. Типи граматик (ієрархія Хомські). Дерева виведення. Форми Бекуса-Наура. Скінченні автомати з виходом. Скінченні автомати без виходу. Подання мов. ЛЕКЦІЯ 8. ОСНОВИ ТЕОРІЇ АЛГОРИТМІВ Основні вимоги до алгоритмів. Машини Тьюрінга. Обчислення числових функцій на машинах Тьюрінга. Теза Тьюрінга. Рекурсивні функції. Теза Чорча. ЛЕКЦІЯ 9. ОСНОВИ ТЕОРІЇ КОДУВАННЯ Алфавітне й рівномірне кодування Достатні умови однозначності декодування. Властивості роздільних кодів. Оптимальне кодування. Коди, стійкі до перешкод. Коди Хеммінга.
Методи та критерії оцінювання: 1. Виконання лабораторних та практичних робіт та їх захист. 2. Написання контрольних робіт. 3. Написання розрахунково-графічної роботи 4. Екзамен.
Критерії оцінювання результатів навчання: 1. Поточний контроль - 45 балів; 2. Екзамен - 55 балів.
Порядок та критерії виставляння балів та оцінок: 100–88 балів – («відмінно») виставляється за високий рівень знань (допускаються деякі неточності) навчального матеріалу компонента, що міститься в основних і додаткових рекомендованих літературних джерелах, вміння аналізувати явища, які вивчаються, у їхньому взаємозв’язку і роз витку, чітко, лаконічно, логічно, послідовно відповідати на поставлені запитання, вміння застосовувати теоретичні положення під час розв’язання практичних задач; 87–71 бал – («добре») виставляється за загалом правильне розуміння навчального матеріалу компонента, включаючи розрахунки, аргументовані відповіді на поставлені запитання, які, однак, містять певні (неістотні) недоліки, за вміння застосовувати теоретичні положення під час розв’язання практичних задач; 70 – 50 балів – («задовільно») виставляється за слабкі знання навчального матеріалу компонента, неточні або мало аргументовані відповіді, з порушенням послідовності викладення, за слабке застосування теоретичних положень під час розв’язання практичних задач; 49–26 балів – («не атестований» з можливістю повторного складання семестрового контролю) виставляється за незнання значної частини навчального матеріалу компонента, істотні помилки у відповідях на запитання, невміння застосувати теоретичні положення під час розв’язання практичних задач; 25–00 балів – («незадовільно» з обов’язковим повторним вивченням) виставляється за незнання значної частини навчального матеріалу компонента, істотні помилки у відповідях на запитання, невміння орієнтуватися під час розв’язання практичних задач, незнання основних фундаментальних положень.
Рекомендована література: Нікольський Ю.В. Дискретна математика. Ю.В.Нікольський, В.В.Пасічник, Ю.М. Щербина. Львів, Магнолія Плюс, 2005, 2006 (1-е видання), 2007 (2-е видання, виправлене й доповнене), 2008 (3-є видання, виправлене й доповнене). Журавчак Л.М. Практикум з комп’ютерної дискретної математики: навч. посібник / Л.М. Журавчак, Н.І. Мельникова, П. В. Сердюк. – Львів : Видавництво Львівської політехніки, 2019. – 279 с Журавчак Л. М. Дискретна математика для програмістів. Навчальний посібник. Львів : Видавництво Львівської політехніки, 2019. 420 с. Rosen, Kenneth H. Discrete mathematics and its applications / Kenneth H. Rosen. — 7th ed. p. cm. Includes index. ISBN 0–07–338309–0 1. Mathematics. 2. Computer science—Mathematics. I. Title. QA39.3.R67 2012 511–dc22 Капітонова Ю.В. Основи дискретної математики. Ю.В. Капітонова, С.Л. Кривий, О.А. Летичевський, М.К. Печурін. К., Наукова думка, 2002.
Уніфікований додаток: Національний університет «Львівська політехніка» забезпечує реалізацію права осіб з інвалідністю на здобуття вищої освіти. Інклюзивні освітні послуги надає Служба доступності до можливостей навчання «Без обмежень», метою діяльності якої є забезпечення постійного індивідуального супроводу навчального процесу студентів з інвалідністю та хронічними захворюваннями. Важливим інструментом імплементації інклюзивної освітньої політики в Університеті є Програма підвищення кваліфікації науково-педагогічних працівників та навчально-допоміжного персоналу у сфері соціальної інклюзії та інклюзивної освіти. Звертатися за адресою: вул. Карпінського, 2/4, І-й н.к., кімн. 112 E-mail: nolimits@lpnu.ua Websites: https://lpnu.ua/nolimits https://lpnu.ua/integration
Академічна доброчесність: Політика щодо академічної доброчесності учасників освітнього процесу формується на основі дотримання принципів академічної доброчесності з урахуванням норм «Положення про академічну доброчесність у Національному університеті «Львівська політехніка» (затверджене вченою радою університету від 20.06.2017 р., протокол № 35).