Анотація: Студенти повинні опанувати значний обсяг математичних фактів та способів їх застосування.
Основні знання, що їх повинні набути студенти, стосуються таких розділів: основи теорії множин і комбінаторний аналіз, основи математичної логіки, теорія графів, відношення, основи теорії формальних граматик і автоматів, моделі обчислень, моделі кодування, застосування теорії автоматів і графів у комп’ютерних інформаційних технологіях, методи пошуку доведення теорем у логіці предикатів. Спеціальну увагу приділено застосуванням в інформатиці. З цією метою курс розділено на два модулі — “Математичні основи” і “Математичні моделі і застосування”. Значна увагу приділено побудові алгоритмів для розв’язування задач дискретної математики. Поняття, факти, алгоритми, що вивчаються у курсі “Дискретна математика” використовуються у курсах “Основи програмування”, “Теорія ймовірностей”, “Основи штучного інтелекту”, “Аналіз даних”, “Моделювання систем”.
Теми:
Модуль 2. Математичні моделі та алгоритми
Змістовий модуль 5. Дерева та їх застосування
Тема 16. Вступ у дерева.
Тема 17. Рекурсія. Застосування дерев в інформаційних технологіях.
Тема 18. Каркаси графів.
Змістовий модуль 6. Основи теорії кодів
Тема 19. Алфавітне й рівномірне кодування.
Тема 20. Оптимальне кодування.
Тема 21. Коди, стійкі до перешкод.
Змістовий модуль 7. Теорія чисел і криптографія
Тема 22. Подільність і модулярна арифметика. Прості числа.
Тема 23. Алгоритм Евкліда. Лінійні конгруенції.
Тема 24. Застосування конгруенцій. Класична криптографія.
Тема 25. Криптосистеми з відкритим ключем. Криптографічні протоколи.
Змістовий модуль 8. Булеві функції
Тема 26. Означення б.ф. Формули. Алгебри б.ф.
Тема 27. Повнота системи б.ф. Теорема Поста
Змістовий модуль 9. Моделювання обчислень
Тема 28. Мови і граматики.
Тема 29. Скінченні автомати.
Тема 30. Машини Тьюрінга. Алгоритмічно нерозв’язні проблеми
Викладачі:
