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