Вопросы к экзамену

  1. Основные понятия теории множеств (определение, задание, операции, примеры, демонстрация кругов Эйлера-Венна).
  2. Алгебра подмножеств (определение, свойства операций, примеры).
  3. Функции и отображения (инъекция, сюръекция, биекция, фактормножества, ядро функции).
  4. Отношение (прямое произведение множеств, композиция отношений, степень отношения, свойства отношений).
  5. Отношение эквивалентности.
  6. Отношение порядка.
  7. Элементы математической логики (определения, законы логики, закон двойственности, закон разрешимости).
  8. Элементы математической логики (проблема разрешимости, построение СДНФ, СКНФ, контактные схемы).
  9. Основные положения булевой алгебры (аксиомы и законы булевой алгебры, основные функции, базисы).
  10. Основные положения булевой алгебры (базисы, преобразование функций от одного базиса к другому, эквивалентные преобразование).
  11. Минимизация БФ и ПФ (метод Куайна, пример).
  12. Минимизация БФ и ПФ (карты Карно, пример).
  13. Представление булевой функции в виде совершенной нормальной формы.
  14. Замкнутые классы.
  15. Полнота. Теорема о функциональной полноте.
  16. Основные понятия теории графов (понятие графа, смежность, изоморфизм графов, подграфы, валентность, примеры).
  17. Маршруты, цепи, циклы.
  18. Виды графов и операции над графами.
  19. Связность (основные понятия, меры связности, теорема Менгера, вершинная и реберная связность).
  20. Потоки в сетях (определение потока, разрезы, теоремы Форда и Фанкерсона).
  21. Деревья.