Комп'ютерна дискретна математика
Спеціальність: Інженерія програмного забезпечення
Код дисципліни: 6.121.00.O.004
Кількість кредитів: 5.00
Кафедра: Програмне забезпечення
Лектор: Журавчак Любов Михайлівна
Семестр: 1 семестр
Форма навчання: денна
Завдання: Вивчення навчальної дисципліни передбачає формування у здобувачів освіти компетентностей:
загальних:
• ЗК01. Здатність до абстрактного мислення, аналізу та синтезу;
фахових:
• ФК20. Здатність застосовувати і розвивати фундаментальні і міждисциплінарні знання для успішного розв’язання завдань інженерії програмного забезпечення.
• ФК26. Здатність до алгоритмічного та логічного мислення.
• ФК28. Здатність демонструвати розуміння наукових та математичних принципів, що лежать в основі інформаційних технологій.
Результати навчання: 1) вміти користуватися методами дискретної математики, зокрема, методами комбінаторики, теорії відношень, математичної логіки, для формалізації і розв’язування задач розроблення програмних продуктів;
2) мати уяву про коло задач комп’ютерної дискретної математики та теоретичні основи сучасних інформаційних технологій;
3) знати способи задання і властивості множин, відношень, функцій і відображень; форми подання, методи перетворення і мінімізації булевих функцій, методи теорії графів;
4) використовувати основні закони алгебри логіки;
5) застосовувати основні поняття теорії множин, основні операції над множинами;
6) використовувати символіку дискретної математики для вираження кількісних та якісних відношень об’єктів, проводити комбінаторні обчислення;
7) застосовувати на практиці відношення і функції;
8) володіти методами теорії графів.
У результаті вивчення навчальної дисципліни здобувач освіти повинен бути здатним продемонструвати такі програмні результати навчання:
ПР05. Знати і застосовувати відповідні математичні поняття, методи доменного, системного і об’єктноорієнтованого аналізу та математичного моделювання для розробки програмного забезпечення. Лекційні, практичні та лабораторні заняття -
інформаційно-рецептивний метод,
репродуктивний метод, евристичний
метод, метод проблемного викладу,
самостійна робота – репродуктивний
метод, дослідний метод. Поточний контроль. Методи оцінювання знань:
вибіркове усне опитування, контрольні заходи (письмове опитування), виконання лабораторних робіт, оцінка активності.
ПР13. Знати і застосовувати методи розробки алгоритмів, конструювання програмного забезпечення та структур даних і знань. Лекційні, практичні та лабораторні заняття -
інформаційно-рецептивний метод,
репродуктивний метод, евристичний
метод, метод проблемного викладу,
самостійна робота – репродуктивний
метод, дослідний метод. Поточний та екзаменаційний контроль. Методи оцінювання знань:
вибіркове усне опитування, контрольні заходи (письмове опитування), виконання лабораторних робіт. Екзамен – письмове опитування, тестовий контроль.
ПР27. Використовувати теорію та методи вибраних розділів математики та фізики для побудови обчислю-вальних алгоритмів, які реалізуються в програмних системах різного призначення Лекційні, практичні та лабораторні заняття -
інформаційно-рецептивний метод,
репродуктивний метод, евристичний
метод, метод проблемного викладу,
самостійна робота – репродуктивний
метод, дослідний метод. Поточний та екзаменаційний контроль. Методи оцінювання знань:
вибіркове усне опитування, контрольні заходи (письмове опитування), виконання лабораторних робіт. Екзамен – письмове опитування, тестовий контроль.
ПР28. Вміти математично формулю-вати технічні задачі, що використовуються в інженерії програмного забезпечення. Лекційні, практичні та лабораторні заняття -
інформаційно-рецептивний метод,
репродуктивний метод, евристичний
метод, метод проблемного викладу,
самостійна робота – репродуктивний
метод, дослідний метод. Поточний та екзаменаційний контроль. Методи оцінювання знань:
вибіркове усне опитування, контрольні заходи (письмове опитування), виконання лабораторних робіт. Екзамен – письмове опитування, тестовий контроль.
Необхідні обов'язкові попередні та супутні навчальні дисципліни: Основи програмування (супутна)
Основи програмування (супутна)
Основи електроніки
Алгоритми і структури даних
Дослідження операцій
Безпека програм і даних
Статистичні методи аналізу даних
Короткий зміст навчальної програми: Дисципліна належить до обов'язкових циклу професійної підготовки, вивчається у першому семестрі.
Дискретна математика – одна з найважливіших складових сучасної математики. З одного боку, вона включає фундаментальні основи математики – теорію множин, математичну логіку, теорію алгоритмів, теорію графів; з другого боку є основним математичним апаратом інформатики і обчислювальної техніки, і тому є базою численних застосувань в техніці, економіці, соціальній сфері. На відміну від традиційної математики (математичного аналізу, лінійної алгебри та ін.), методи і конструкції якої мають в основному числову інтерпретацію, дискретна математика має справу з об’єктами нечислової природи: множинами, логічними висловлюваннями, алгоритмами, графами. Завдяки цьому дискретна математика вперше дозволила розповсюдити математичні методи на сфери і задачі, які раніше були далекі від математики.
Знання теорії множин, булевої алгебри, математичної логіки і теорії графів є необхідним для чіткого формулювання понять і постановок різних прикладних задач, їх формалізації і комп’ютеризації, а також для освоєння і розробки сучасних інформаційних технологій. Поняття і методи теорії алгоритмів і алгебри логіки лежать в основі сучасної теорії і практики розробки програмного забезпечення, а відтак і програмної інженерії.
Вивчення даної дисципліни передбачає, окрім курсу лекцій, набуття і засвоєння практичних навичок розв’язування задач на практичних та лабораторних заняттях.
Опис: Тема 1. Логіка і методи доведень. Логіка висловлювань та її закони. Закони логіки предикатів, кванторні операції над предикатами. Методи доведення теорем: пряме доведення, доведення від протилежного, математична індукція
Тема 2. Основні поняття та операції теорії множин. Елементи, множини, підмножини, способи задавання множин, представлення множин, булеан. Зліченні і незліченні множини. Властивості операцій, діаграми Ейлера, декартів добуток. Подання множин бітовими рядками.
Тема 3. Неорієнтовані графи. Поняття графа, операції над графами, спеціальні типи простих графів, способи подання графів. Маршрути, зв’язність. Ейлерові та гамільтонові графи. Обхід графів, їх ізоморфізм. Планарні та плоскі графи.
Тема 4. Орієнтовані графи. Топологічне сортування. Способи подання орієнтованих графів. Шляхи в орграфах, алгоритм Воршелла. Пошук найкоротших шляхів у графі. Алгоритм Дейкстри. Алгоритм Флойда.
Тема 5. Дерева та їх застосування. Пошук мінімального остовного дерева. Способи подання дерев. Обхід дерева. Польські вирази. Бектрекінг. Бінарне дерево пошуку. AVL-дерева. Червоно-чорні дерева.
Тема 6. Відношення. Функції. Бінарні відношення, способи їх задання, властивості відношень. Відношення еквівалентності. Відношення часткового (нестрогого) та строгого порядку. Відношення толерантності. Обернені відношення і композиція відношень. Замикання відношення за властивістю. Властивості функцій. Обернені функції і композиція функцій.
Тема 7. Булева алгебра. Досконалі нормальні форми. Побудова формул за таблицями істинності, нормальні і досконалі нормальні форми. Мінімізація булевих функцій, карта Карно, синтез та аналіз функціональних схем. Повні системи. Коди, стійкі до перешкод.
Тема 8. Комбінаторний аналіз. Правила суми і добутку. Основні принципи комбінаторики, перестановки, розміщення, сполучення без повторень і з повтореннями, біном Ньютона. Алгоритми генерування та лексикографічний порядок. Задача про цілочислові розв’язки.
Методи та критерії оцінювання: 1) Виконання кожної з чотирьох лабораторних робіт включає розв'язування двох задач згідно варіанту (ДФН).
2) Вибіркове усне опитування відбувається на практичних заняттях. Воно полягає в розв'язуванні біля дошки задач та відповідях на питання зі сформованих списків до кожної теми.
3) Контрольні заходи передбачають тестування у ВНС та письмове розв'язування задач (ДФН).
4) Виконання кожної з двох контрольних робіт включає розв'язування 10 задач згідно варіанту (ЗФН).
5) Екзаменаційна робота складається з письмової та усної компонент.
Критерії оцінювання результатів навчання: Методи діагностики знань: усне опитування, виконання лабораторних робіт, контрольні заходи, екзаменаційна робота.
Критерії оцінювання результатів навчання студентів:
Максимальна оцінка в балах 100
Поточний контроль: 45
контрольні заходи (письмове
опитування) 22=5+6+6+5
лабораторні роботи 16=4+4+4+4
практичні заняття 7
Екзаменаційний контроль: 55
письмова компонента 45
усна компонента 10
Порядок та критерії виставляння балів та оцінок: 100–88 балів – («відмінно») виставляється за високий рівень знань (допускаються деякі неточності) навчального матеріалу компонента, що міститься в основних і додаткових рекомендованих літературних джерелах, вміння аналізувати явища, які вивчаються, у їхньому взаємозв’язку і роз витку, чітко, лаконічно, логічно, послідовно відповідати на поставлені запитання, вміння застосовувати теоретичні положення під час розв’язання практичних задач; 87–71 бал – («добре») виставляється за загалом правильне розуміння навчального матеріалу компонента, включаючи розрахунки , аргументовані відповіді на поставлені запитання, які, однак, містять певні (неістотні) недоліки, за вміння застосовувати теоретичні положення під час розв’язання практичних задач; 70 – 50 балів – («задовільно») виставляється за слабкі знання навчального матеріалу компонента, неточні або мало аргументовані відповіді, з порушенням послідовності викладення, за слабке застосування теоретичних положень під час розв’язання практичних задач; 49–26 балів – («не атестований» з можливістю повторного складання семестрового контролю) виставляється за незнання значної частини навчального матеріалу компонента, істотні помилки у відповідях на запитання, невміння застосувати теоретичні положення під час розв’язання практичних задач; 25–00 балів – («незадовільно» з обов’язковим повторним вивченням) виставляється за незнання значної частини навчального матеріалу компонента, істотні помилки у відповідях на запитання, невміння орієнтуватися під час розв’язання практичних задач, незнання основних фундаментальних положень.
Рекомендована література: 1. Журавчак Л.М. Дискретна математика для програмістів: навч. посібник / Л.М. Журавчак. – Львів: Видавництво Львівської політехніки, 2019. – 420 с.
2. Журавчак Л.М. Практикум з комп’ютерної дискретної математики: навч. посібник / Л.М. Журавчак, Н.І. Мельникова, П.В. Сердюк. – Львів: Видавництво Львівської політехніки, 2020. – 316 с.
3. Журавчак Л.М., Івасько Н.М. Комп’ютерна дискретна математика /Елект. навчально-методичний комплекс. [http://vns.lpnu.ua/course/view.php?id=738] – 2020.
4. Коцовський В. М. Основи дискретної математики: навчальний посібник. Ужгород: ПП «АУТДОР- ШАРК», 2020. 128 с.
5. Порубльов І. М. Дискретна математика. Навчальний посібник для студентів 1-го курсу бакалаврату галузі знань «Інформаційні технології» та споріднених. – Черкаси: видавець ФОП Гордієнко Є. І., 2018. – 220 с.
Уніфікований додаток: Національний університет «Львівська політехніка» забезпечує реалізацію права осіб з інвалідністю на здобуття вищої освіти. Інклюзивні освітні послуги надає Служба доступності до можливостей навчання «Без обмежень», метою діяльності якої є забезпечення постійного індивідуального супроводу навчального процесу студентів з інвалідністю та хронічними захворюваннями. Важливим інструментом імплементації інклюзивної освітньої політики в Університеті є Програма підвищення кваліфікації науково-педагогічних працівників та навчально-допоміжного персоналу у сфері соціальної інклюзії та інклюзивної освіти. Звертатися за адресою:
вул. Карпінського, 2/4, І-й н.к., кімн. 112
E-mail: nolimits@lpnu.ua
Websites: https://lpnu.ua/nolimits https://lpnu.ua/integration
Академічна доброчесність: Політика щодо академічної доброчесності учасників освітнього процесу формується на основі дотримання принципів академічної доброчесності з урахуванням норм «Положення про академічну доброчесність у Національному університеті «Львівська політехніка» (затверджене вченою радою університету від 20.06.2017 р., протокол № 35).