НИУ МЭИ. Дискретная математика.

Дискретная математика. Темы для подготовки к экзамену

МЭИ(ТУ), 2021/22г

экзамен янв. 2022
Кафедра РМДПМ

  1. Множество, подмножество, собственное подмножество. Объединение множеств, пересечение, разность, симметрическая разность, абсолютное дополнение. Универсальное множество. Свойства операций (коммутативность, ассоциативность, дистрибутивность, идемпотентность). Свойства универсального и пустого множеств. Закон двойного дополнения. Законы де Моргана. Парадокс Рассела.
  2. Булеан. Мощность множества. Мощность булеана. Прямое произведение. Упорядоченная пара. Три свойства прямого произведения. Соответствие между множествами. Область определения соответствия. Первая проекция соответствия. Область значений соответствия. Вторая проекция. Сечение соответствия. Обратное соответствие. Пустое соответствие. Полное соответствие. Композиция соответствий. Условие существования композиции.
  3. Отображение. Отображение функциональное. Шесть свойств отображений. Сюръективное, инъективное, биективное отображение. Композиция отображений. Ассоциативность композиции отображений. Обратное отображение. Единичное отображение. Левое и правое обратное отображение. Лемма о единичной композиции двух отображений. Теорема о существовании обратного отображения.
  4. Отношения унарные и бинарные. Граф отношения. Матрица отношения. Единичное отношение. Полное отношение. Обратное отношение. Свойства отношений (рефлексивность, антирефлексивность, симметричность, антисимметричность, асимметричность, транзитивность). Композиция бинарных отношений. Необходимое и достаточное условие транзитивности. Замыкание отношения. Рефлексивное замыкание. Транзитивное замыкание. Теорема о виде транзитивного замыкания. Вид транзитивного рефлексивного замыкания. Два алгоритма нахождения транзитивного замыкания. Отношение эквивалентности. Класс эквивалентности. Фактор-множество. Разбиение. Индекс разбиения. Отношение порядка. Предпорядок. Полный порядок. Частичный порядок. Строгий порядок. Диаграмма Хассе. Отношение Паретто. Алфавит. Лексикографический порядок.
  5. Бинарная операция на множестве. Ассоциативность, коммутативность бинарной операции. Единичный элемент. Единственность единичного элемента. Полугруппа. Моноид. Обратный элемент моноида. Группа. Четыре аксиомы, которым удовлетворяет группа. Мультипликативная и аддитивная группа. Абелева группа. Подгруппа. Собственная подгруппа. Таблица Кэли. Свойство столбцов (строк) таблицы Кэли. Симметрическая группа. Циклическая группа. Конечная и бесконечная группа. Сравнение по модулю m. Кольцо. Поле. Теорема о связи циклической группы порядка m и группы классов вычетов. Кольцо, поле и классы вычетов по модулю m.
  6. Элементы математической логики. Конъюнкция, дизъюнкция, отрицание, импликация, эквиваленция, сложение по модулю 2. Штрих Шеффера. Стрелка Пирса. Основные законы логики. Булевы функции. Совершенные дизъюнктивные нормальные формы (СДНФ). Сокращенная и минимальная ДНФ. Упрощение логических функций. Упрощение переключательных схем. Карты Карно. Полиномы Жегалкина.
  7. Матрица Квайна. Импликанты. Простые импликанты. Конституенты единицы.
  8. Решение однородных и неоднородных рекуррентных уравнений.
  9. Ладейные полиномы. Правило суммирования. Правило умножения.
  10. Инверсии. Таблица инверсии. Восстановление перестановок по инверсии.
  11. Функция Эйлера .
  12. Решение сравнений. Китайская теорема об остатках.
  13. Лемма о рукопожатиях, два следствия. Число ребер в полном графе.
  14. Мультиграф, псевдограф. Петли.
  15. Неограф и орграф. Дуги и ребра. Взвешенный граф. Евклидов граф.
  16. Матрица смежности, матрица Кирхгофа, список ребер, матрица инцидентности. Связность. Сильная связность орграфа. Алгебраические дополнения матрицы Кирхгофа равны.
  17. Число остовов полного графа.
  18. Теорема о двухсторонней оценке числа ребер в обыкновенном графе.
  19. Изоморфные графы. Однородные графы. Характеристический полином графа. Оценка корней характеристического полинома регулярного графа.
  20. Число вершинной и реберной связности графа. Двухсторонняя оценка числа реберной связности.
  21. Разрезающее множество, разрез, мост. Теорема о необходимом и достаточном условии существования мостов.
  22. Теорема Кегнига о двудольном графе.
  23. Эйлеровы графы. Эйлеров цикл и эйлерова цепь. Теоремы о эйлеровых графах.
  24. Дополнение графа. Ориентируемый граф. Теорема об ориентируемых графах.
  25. Центр графа. Эксцентриситет вершины. Радиус и диаметр графа. Теорема Жордана.
  26. Центроид графа. Вес вершины. Теорема Жордана.
  27. Ранг-полином. Ранг графа. Коранг. Цикломатическое число графа.
  28. Теорема о числе маршрутов определенной длины в графе.
  29. Теорема о числе ребер в обыкновенном связном графе. Теорема о числе ребер в произвольном графе.
  30. Теорема об алгебраических дополнениях в матрице Кирхгофа.
  31. Число остовов полного графа.
  32. Кодировка дерева. Двоичная кодировка и кодировка Прюфера.
  33. Реберный граф. Размер реберного графа.
  34. Дерево. Листья. Лес. Ярус. Ствол. Высота. Код Прюфера.
  35. Сеть. Сток. Исток. Алгоритм Форда-Фалкерсона. Чередующаяся цепь.
  36. Двудольный граф. Покрытие. Максимальное, наибольшее и совершенное покрытие. Перманент. Необходимое и достаточное условие равенства нулю перманента.
  37. Задача о назначениях. Венгерский алгоритм (Куна). Альфа-преобразование.
  38. Кратчайший путь в орграфе. Алгоритм Дейкстры.
  39. Остов минимального веса. Два алгоритма решения задачи.
  40. Планарность. Плоский граф. Жорданова кривая. Подразбиение. Гомеоморфность. Теорема Понтрягина-Куратовского. Задача о трех домах и трех колодцах. Толщина графа.
  41. Теорема Эйлера о плоском графе. Максимально плоский граф. Триангуляция. Теорема о связи триангуляции с планарностью. Размер максимального планарного графа.
  42. Раскраски. Хроматический индекс и хроматическое число. Оценки. Теорема о редукции. Стягивание.
  43. Числа Стирлинга 1 и 2-го рода. Хроматическое число дерева. Картографическая раскраска.
  44. Основание графа. Сильно связный граф. Евклидов граф.
  45. Гамильтоновы и полугамильтоновы графы. Евклидовы графы. Задача коммивояжера.
  46. Алгебраический алгоритм нахождения гамильтоновых циклов.
  47. Доминирующее множество. Число доминирования. Внутренняя и внешняя устойчивость графа. Полностью зависимое и полностью независимое множество вершин. Число вершинной независимости. Реберная независимость. Теорема о связи независимости и доминирования. Клики.
  48. Реберный граф. Число ребер.
  49. Два алгоритма нахождения наибольшего паросочетания в двудольном графе.

На экзамене (60 минут) будет предложено 6 теоретических вопросов по 1 баллу и 2 задачи по 2 балла. В число задач входят вопросы с доказательством (в том числе те, которые в списке выделены цветом).

10 баллов -отл., 9,8 - хор., 7,6, уд.

9 и 7 баллов дают право на 1 дополнительный вопрос для повышения оценки.