ПИТАННЯ НА ІСПИТ З КУРСУ „ДИСКРЕТНА МАТЕМАТИКА”
ПИТАННЯ НА ІСПИТ З КУРСУ
„ДИСКРЕТНА МАТЕМАТИКА”
- Логіка висловлювань. Основні означення та властивості
- Закони логіки висловлювань
- Нормальні форми логіки висловлювань
- Логіка першого ступеня
- Закони логіки першого ступеня
- Правила синтаксису та семантики. Таблиця істинності
- Поняття множини. Способи задання множин.
- Операції над множинами.
- Кортеж. Декартів добуток множин.
- Доведення рівностей з множинами.
- Комп’ютерне зображення множин.
- Основні правила комбінаторики.
- Розміщення та сполуки.
- Підрахунок кількості розміщень і сполук.
- Перестановки.
- Біном Ньютона.
- Поліноміальна теорема.
- Задача про цілочисельні розв’язки рівняння.
- Генерування перестановок.
- Генерування сполук.
- Рекурентні рівняння.
- Принцип включення-виключення.
- Розв’язування рекурентних рівнянь.
- Графи. Основні означення та властивості.
- Деякі спеціальні класи графів.
- Способи задання графів.
- Шляхи та цикли в графах.
- Зв’язність графів.
- Ейлерів цикл у графі.
- Гамільтонів цикл у графі.
- Дерева. Основні означення та властивості.
- Рекурсія. Обхід дерев.
- Бінарне дерево пошуку.
- Дерево прийняття рішень.
- Бектрекінг
- Означення булевих функції.
- Способи задання булевих функцій.
- Реалізація булевих функцій формулами.
- Елементарні булеві функції
- Алгебри булевих функцій.
- Основні еквівалентності в алгебрах булевих функцій
- Спеціальні форми зображення булевих функцій: диз’юнктивні нормальні форми (ДНФ).
- Спеціальні форми зображення булевих функцій: кон’юктивні нормальні форми (КНФ).
- Поліном Жегалкіна
- Мови. Приклади мов та їх використання
- Поняття формальних породжувальних граматик.
- Типи граматик.
- Дерева виведення.
- Скінченні автомати з виходом.
- Скінченні автомати без виходу.
