Дискретная математика. Программа курса (1часть)/ 2011-2012

Дискретная математика. Темы для подготовки к экзамену (C12a,b,7)

МЭИ(ТУ), 2022/23г

экзамен 10 янв. 2023
Кафедра Робототехники, мехатроники, динамики и прочности машин

  1. Множество, подмножество, собственное подмножество. Объединение множеств, пересечение, разность, симметрическая разность, абсолютное дополнение. Универсальное множество. Свойства операций (коммутативность, ассоциативность, дистрибутивность, идемпотентность). Свойства универсального и пустого множеств. Закон двойного дополнения.
  2. Законы де Моргана. Парадокс Рассела.
  3. Булеан. Мощность множества. Мощность булеана Прямое произведение. Упорядоченная пара. Три свойства прямого произведения. Соответствие между множествами. Область определения соответствия. Первая проекция соответствия. Область значений соответствия. Вторая проекция. Сечение соответствия. Обратное соответствие. Пустое соответствие. Полное соответствие. Композиция соответствий. Условие существования композиции.
  4. Отображение. Отображение функциональное. Шесть свойств отображений. Сюръективное, инъективное, биективное отображение. Композиция отображений. Ассоциативность композиции отображений. Обратное отображение. Единичное отображение. Левое и правое обратное отображение. Лемма о единичной композиции двух отображений. Теорема о существовании обратного отображения.
  5. Отношения унарные и бинарные. Граф отношения. Матрица отношения. Единичное отношение. Полное отношение. Обратное отношение. Свойства отношений (рефлексивность, антирефлексивность, симметричность, антисимметричность, асимметричность, транзитивность). Композиция бинарных отношений. Условие транзитивности. Замыкание отношения. Рефлексивное замыкание. Транзитивное замыкание. Алгоритм Уоршелла. Теорема о виде транзитивного замыкания. Вид транзитивного рефлексивного замыкания. Два алгоритма нахождения транзитивного замыкания. Отношение эквивалентности. Класс эквивалентности. Фактор-множество. Разбиение. Отношение порядка. Предпорядок. Полный порядок. Частичный порядок. Строгий порядок. Диаграмма Хассе. Отношение Паретто. Алфавит. Лексикографический порядок.
  6. Бинарная операция на множестве. Ассоциативность, коммутативность бинарной операции. Единичный элемент. Единственность единичного элемента. Полугруппа. Моноид. Обратный элемент моноида. Группа. Четыре аксиомы, которым удовлетворяет группа. Мультипликативная и аддитивная группа. Абелева группа. Подгруппа. Собственная подгруппа. Таблица Кэли. Свойство столбцов (строк) таблицы Кэли. Симметрическая группа. Циклическая группа. Конечная и бесконечная группа. Сравнение по модулю m. Класс вычетов по модулю m. Кольцо. Поле. Теорема о кольце классов вычетов.
  7. Элементы математической логики. Конъюнкция, дизъюнкция, отрицание, импликация, эквиваленция, сложение по модулю 2. Штрих Шеффера. Стрелка Пирса. Основные законы логики. Обобщенное склеивание (с доказ.) Булевы функции. Совершенные дизъюнктивные нормальные формы. Сокращенная и минимальная ДНФ. Упрощение логических функций. Упрощение переключательных схем. Таблицы Квайна. Импликанта. Простая импликанта. Конституента единицы. Карты Карно. Полином Жегалкина.
  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. Эйлеров и полуэйлеров граф. Признак эйлерова графа.
  44. Гамильтоновы графы. Поиск гамильтонового цикла (способы NVa, NVi).
  45. Доминирующее множество. Число доминирования. Полностью зависимое и полностью независимое множество вершин. Число вершинной независимости. Реберная независимость. Теорема о связи независимости и доминирования. Клики.
  46. Реберный граф. Число ребер (с доказательством).
  47. Корени характеристического полинома реберного графа.
  48. Триангуляция.
  49. Порядок максимального планарного графа и его размер.
  50. Фундаментальный цикл графа. Матрица фундаментальных циклов графа.