Вопросы к экзамену
- Основные понятия теории множеств (определение, задание, операции, примеры, демонстрация кругов Эйлера-Венна).
- Алгебра подмножеств (определение, свойства операций, примеры).
- Функции и отображения (инъекция, сюръекция, биекция, фактормножества, ядро функции).
- Отношение (прямое произведение множеств, композиция отношений, степень отношения, свойства отношений).
- Отношение эквивалентности.
- Отношение порядка.
- Элементы математической логики (определения, законы логики, закон двойственности, закон разрешимости).
- Элементы математической логики (проблема разрешимости, построение СДНФ, СКНФ, контактные схемы).
- Основные положения булевой алгебры (аксиомы и законы булевой алгебры, основные функции, базисы).
- Основные положения булевой алгебры (базисы, преобразование функций от одного базиса к другому, эквивалентные преобразование).
- Минимизация БФ и ПФ (метод Куайна, пример).
- Минимизация БФ и ПФ (карты Карно, пример).
- Представление булевой функции в виде совершенной нормальной формы.
- Замкнутые классы.
- Полнота. Теорема о функциональной полноте.
- Основные понятия теории графов (понятие графа, смежность, изоморфизм графов, подграфы, валентность, примеры).
- Маршруты, цепи, циклы.
- Виды графов и операции над графами.
- Связность (основные понятия, меры связности, теорема Менгера, вершинная и реберная связность).
- Потоки в сетях (определение потока, разрезы, теоремы Форда и Фанкерсона).
- Деревья.