Опис курсу

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

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

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

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

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