Опис курсу

Мета. Вивчення основних понять і методів дискретної математики та їх застосувань в інформатиці.

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

Завдання. Оволодіти основними теоретичними положеннями дискретної математики та їх застосуваннями в інформатиці.

У результаті вивчення даного курсу студент повинен
знати
• основні положення математичної логіки;
• основні означення та теореми теорії графів;
• основні алгоритми на графах.

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