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

Тип: Нормативний

Відділення: викладачі фундаментальних дисциплін

Навчальний план

СеместрКредитиЗвітність
1Залік
2Іспит

Лекції

СеместрК-сть годинЛекторГрупа(и)
136Вельгош С. Р.КНК-11
217Вельгош С. Р.КНК-11

Лабораторні

СеместрК-сть годинГрупаВикладач(і)
136КНК-11Вельгош С. Р.
234КНК-11Вельгош С. Р.

Практичні

СеместрК-сть годинГрупаВикладач(і)
1

Опис курсу

Мета – 
Програма предмета передбачає ознайомлення студентів з теоретичними основами математичної логіки, теорії множин, комбінаторики та теорії графів.

Завдання –  навчити студентів користуватися методами дискретної математики (зокрема методами математичної логіки, теорії множин, комбінаторики та теорії графів) для формалізації й вирішення прикладних завдань та складати комп’ютерні програми на основі базових алгоритмів.

Після вивчення даної дисципліни  студент повинен

знати:
• основні поняття, закони та теореми логіки висловлювань, теорії множин, комбінаторного аналізу та теорії графів;
• методи перевірки логічних функцій на тавтологію, протиріччя, еквівалентність;
• методи розв’язування комбінаторних задач на сполучення, розміщення та перестановки з повтореннями і без;
• методи розв’язування комбінаторних задач з використанням принципу Діріхле та принципу включення-виключення;
• методи розв’язування лінійних рекурентних рівнянь зі сталими коефіцієнтами;
• основні поняття про твірні функції;
• види графів та способи їх задання;
• методи перевірки графів на ізоморфізм, зв’язність, дводольність, планарність, гомеоморфність, існування Ейлерових та Гамільтонових циклів.

студент повинен вміти:
• знаходити таблиці і значення істинності заданих логічних функцій;
• перевіряти логічні функції на відповідність заданим таблицям істинності;
• спрощувати логічні функції за допомогою еквівалентних перетворень;
• зводити логічні функції до нормальних форм;
• обраховувати декартів добуток множин, будувати діаграми Ейлера, працювати з бітовими рядками;
• розв’язувати комбінаторні задачі на сполучення, розміщення та перестановки з повтореннями і без;
• розв’язувати комбінаторні задачі з використанням принципу Діріхле та принципу включення-виключення;
• розв’язувати лінійні рекурентні рівняння зі сталими коефіцієнтами;
• генерувати у лексикографічному порядку перестановки, сполучення, розміщення;
• використовувати твірні функції при розв’язуванні комбінаторних задач та рекурентних рівнянь;
• задавати графи на комп’ютері;
• розв’язувати задачу пошуку найкоротшого шляху, розфарбовування графа, обходу графа, перевірки графа на відповідність заданим критеріям;

Рекомендована література

Базова

1. Нікольский Ю., Пасічник В., Щербина Ю. Дискретна математика. – Львів, 2006.
2. Емеличев В., Мельников О., Сарванов В., Тышкевич Р. Лекции по теории графов. – Москва, 1990.
3. Яблонский С. Введение в дискретную математику. 2-е изд.– Москва, 1986.
4. Горбатов В. Основы дискретной математики. – Москва, 1986.
5. Андерсон Д. Дискретная математика и комбинаторика. – Санкт-Петербург, 2003.

Допоміжна

1. Липский В. Комбинаторика для программистов. – Москва, 1988.
2. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. – Санкт-Петербург, 2003.
4. Новиков Ф. Дискретная математика для программистов. – Санкт-Петербург, 2000.
5. Оре О. Теория графов. – Москва, 1980.