Вопросы к экзамену по дискретной математике

(Предварительный вариант)

Множества и отношения

  1. Понятие множества. «Наивная теория множеств» и аксиоматический подход к построению теории. Примеры множеств. Семейство; класс. Универсум. Способы задания множеств. Парадокс Рассела.
  2. Алгебра подмножеств. Сравнение множеств. Собственные и несобственные подмножества. Равномощные множества; свойства равномощности. Конечные и бесконечные множества. Формулировки теорем о бесконечности множества, мощности конечного множества, конечности отрезка натурального ряда.
  3. Операции над множествами и их свойства. Диаграммы Эйлера-Венна. Разбиения и покрытия; дизъюнктные семейства; блоки. Формулировка теоремы о связи дизъюнктного семейства и разбиения. Булеан; формулировка теоремы о мощности.
  4. Отношения. Упорядоченные пары и наборы; их равенство. Прямое (декартово) произведение множеств; степень; формулировка теоремы о мощности. Бинарные отношения; график отношения. Тождественное и универсальное отношения. Обратное отношение и дополнение.
  5. Композиция отношений. Доказательство теоремы об ассоциативности композиции. Степень отношения. Классификация отношений по их свойствам. Формулировка теоремы о свойствах отношения. Ядро отношения. Формулировка теоремы о свойствах ядра.
  6. Транзитивное и рефлексивное замыкания. Алгоритм Уоршалла.
  7. Функциональные (однозначные) отношения. Аргумент и значение; области определения и значений; тотальность и частичность; сужение и продолжение. Характеристические функции подмножеств и отношений. Инъективные, сюрьективные и биективные функции. Образ и прообраз. Суперпозиция; доказательство теоремы о функциональности.
  8. Отношение эквивалентности. Классы эквивалентности. Фактормножество. Ядро функционального отношения и множества уровня; формулировка теоремы о ядре.
  9. Отношение порядка. Частичный и линейный порядок; свойства отношений. Минимальные и наименьшие элементы. Формулировка теоремы о существовании минимального элемента. Доказательство теоремы о единственности наименьшего элемента.
  10. Верхние и нижние границы. Формулировка теоремы о наименьшем элементе и инфимуме. Монотонные функции. Доказательство теоремы о монотонности суперпозиции монотонных функций. Вполне упорядоченные множества.

Булевы функции

  1. Аксиомы булевой алгебры. Булевы функций. Таблицы истинности. Элементарные булевы функции. Существенные и несущественные переменные. Тернарная логика как пример булевой алгебры на множестве более чем двух элементов.
  2. Реализации функций формулами. Интерпретация формул. Равносильные формулы. Подстановка и замена. Алгебра булевых функций.
  3. Двойственные функции. Доказательство теоремы о реализации двойственной функции. Принцип двойственности. Симметрические функции. Доказательство теоремы о количестве различных симметрических функций.
  4. Разложение булевых функций по переменным. Минимальные термы. Нормальные формы и совершенные нормальные формы. Доказательство единственности СДНФ.
  5. Эквивалентные преобразования. Правило склеивания—расщепления. Преобразование формулы в СДНФ.
  6. Минимальные и совершенные дизъюнктивные формы. Геометрическая интерпретация. Код Грея и карты Карно.
  7. Замыкание и замкнутые классы. Классы T0, T1, T∗, T⩽, TL и доказательство их замкнутости.
  8. Полные системы функций. Примеры полных систем. Полином Жегалкина. Полнота двойственной системы. Доказательство теоремы Поста.

Комбинаторика

  1. Комбинаторные задачи и комбинаторные конфигурации. Размещения; размещения без повторений.
  2. Перестановки. Таблицы подстановки. Транспозиции и инверсии. Двойные факториалы; доказательство равенств (2k)!! = 2k ⋅ k!, (2k + 1)!! = (2k + 1)! ∕ (2k ⋅ k!).
  3. Сочетания; сочетания с повторениями. Бином Ньютона и свойства биномиальных коэффициентов. Треугольник Паскаля.
  4. Разбиения. Числа Стирлинга второго и первого рода. Число Белла.
  5. Вывод формулы включений и исключений.
  6. Число булевых функций, существенно зависящих от всех своих переменных.
  7. Доказательство теоремы обращения. Формулы обращения для биномиальных коэффициентов. Формулы для чисел Стирлинга.
  8. Производящие функции и метод неопределенных коэффициентов. Вывод формулы для чисел Фибоначчи.

Графы

  1. Определение графа. Инцидентность и смежность; окрестность. Диаграммы. Ориентированные графы, псевдографы, мультиграфы, гиперграфы. Помеченные и нумерованные графы.
  2. Изоморфизм. Инварианты графа. Степень (валентность) вершины; полустепени. Регулярные (однородные) и полные графы. Клика графа. Подграфы. Правильные и остовные подграфы.
  3. Маршруты, цепи, циклы; пути и контуры. Ациклические графы. Связные, несвязные и вполне несвязные графы; компоненты связности. Геодезические цепи и графы; расстояние между вершинами; ярусы; диаметр графа. Эксцентриситет; радиус; центральные и переферийные вершины; центр графа.
  4. Двудольные графы. Доказательство теоремы о четности длин всех простых циклов двудольного графа. Направленные (антисимметричные) орграфы; турниры. Сети.
  5. Операции над графами: дополнение; (дизъюнктное) объединение и соединение; удаление и добавление вершины (ребра); стягивание правильного подграфа к вершине; размножение вершины. Обратимость и коммутативность операций.
  6. Представления графов: матрица смежности, матрица инциденций, списки последователей, список ребер. Оценки для объема памяти. Представление ориентированных графов, графов с петлями, мультиграфов.
  7. Связь ориентированных графов и бинарных отношений. Транзитивное замыкание отношения. Диаграммы Хассе.

Связность

  1. Связные графы. Точки сочленения; мосты; блоки. Доказательство теоремы о маршрутах и точках сочленения в связном графе.
  2. Вершинная и реберная связность; n-связные графы. Вершинно- и реберно-непересекающиеся цепи. Разделяющее множество; разрез; коцикл. Формулировка теоремы Менгера (в «вершинной форме».)
  3. Алгоритм нахождения всех возможных систем различных представителей (трансверсалей.) Паросочетание; максимальное паросочетание; совершенное паросочетание. Формулировка теоремы Холла.
  4. Сеть; источник; сток. Пропускная способность дуги. Алгоритм нахождения пропускной способности сети.
  5. Лес; (свободное) дерево. Древочисленные и субциклические графы. Формулировка теоремы, устанавливающей основные свойства деревьев. Доказательство теоремы о центре дерева. Ориентированные деревья. Код Прюфера.

Циклы, раскраска, планарность

  1. Эйлеровы циклы и эйлеровы графы. Доказательство теоремы об эйлеровом графе. Гамильтоновы циклы и задача коммивояжера.
  2. Раскраска графа. Хроматическое число и оценки для него. Одноцветные классы. Формулировка теоремы о связи хроматических чисел графа и его дополнения.
  3. Укладка графа. Плоские и планарные графы; грани. Доказательство теоремы Эйлера о плоских графах. Непланарность графов K5, K3, 3. Подразбиение ребра и гомеоморфизм. Формулировка критерия Понтрягина-Куратовского.
  4. Доказательство теоремы о пяти красках.

Кодирование

  1. Кодирование и декодирование. Сообщения и коды. Двоичное кодирование. Алфавитное кодирование; схема; элементарные коды. Разделимые и префиксные схемы. Доказательство неравенства Макмиллана. Формулировка теоремы о существовании префиксной схемы алфавитного кодирования.
  2. Кодирование с минимальной избыточностью. Цена кодирования. Равномерное кодирование. Алгоритм Фано.

Литература

  1. Новиков, Ф. А. Дискретная математика для программистов. — СПб.: Питер, 2013.
  2. Судоплатов С. В., Овчинникова Е. В. Элементы дискретной математики. — М.: ИНФРА-М, Новосибирск: Изд-во НГТУ, 2002.
  3. Шевелев, Ю. П. Дискретная математика. Ч. 2: Теория конечных автоматов. Комбинаторика. Теория графов. (Для автоматизированной технологии обучения «Символ».) — Томск: Том. гос. ун-т систем упр. и радиоэлектроники, 2003.