Вопросы к экзамену по дискретной математике
(Предварительный вариант)
Множества и отношения
- Понятие множества. «Наивная теория множеств» и аксиоматический подход к построению теории. Примеры множеств. Семейство; класс. Универсум. Способы задания множеств. Парадокс Рассела.
- Алгебра подмножеств. Сравнение множеств. Собственные и несобственные подмножества. Равномощные множества; свойства равномощности. Конечные и бесконечные множества. Формулировки теорем о бесконечности множества, мощности конечного множества, конечности отрезка натурального ряда.
- Операции над множествами и их свойства. Диаграммы Эйлера-Венна. Разбиения и покрытия; дизъюнктные семейства; блоки. Формулировка теоремы о связи дизъюнктного семейства и разбиения. Булеан; формулировка теоремы о мощности.
- Отношения. Упорядоченные пары и наборы; их равенство. Прямое (декартово) произведение множеств; степень; формулировка теоремы о мощности. Бинарные отношения; график отношения. Тождественное и универсальное отношения. Обратное отношение и дополнение.
- Композиция отношений. Доказательство теоремы об ассоциативности композиции. Степень отношения. Классификация отношений по их свойствам. Формулировка теоремы о свойствах отношения. Ядро отношения. Формулировка теоремы о свойствах ядра.
- Транзитивное и рефлексивное замыкания. Алгоритм Уоршалла.
- Функциональные (однозначные) отношения. Аргумент и значение; области определения и значений; тотальность и частичность; сужение и продолжение. Характеристические функции подмножеств и отношений. Инъективные, сюрьективные и биективные функции. Образ и прообраз. Суперпозиция; доказательство теоремы о функциональности.
- Отношение эквивалентности. Классы эквивалентности. Фактормножество. Ядро функционального отношения и множества уровня; формулировка теоремы о ядре.
- Отношение порядка. Частичный и линейный порядок; свойства отношений. Минимальные и наименьшие элементы. Формулировка теоремы о существовании минимального элемента. Доказательство теоремы о единственности наименьшего элемента.
- Верхние и нижние границы. Формулировка теоремы о наименьшем элементе и инфимуме. Монотонные функции. Доказательство теоремы о монотонности суперпозиции монотонных функций. Вполне упорядоченные множества.
Булевы функции
- Аксиомы булевой алгебры. Булевы функций. Таблицы истинности. Элементарные булевы функции. Существенные и несущественные переменные. Тернарная логика как пример булевой алгебры на множестве более чем двух элементов.
- Реализации функций формулами. Интерпретация формул. Равносильные формулы. Подстановка и замена. Алгебра булевых функций.
- Двойственные функции. Доказательство теоремы о реализации двойственной функции. Принцип двойственности. Симметрические функции. Доказательство теоремы о количестве различных симметрических функций.
- Разложение булевых функций по переменным. Минимальные термы. Нормальные формы и совершенные нормальные формы. Доказательство единственности СДНФ.
- Эквивалентные преобразования. Правило склеивания—расщепления. Преобразование формулы в СДНФ.
- Минимальные и совершенные дизъюнктивные формы. Геометрическая интерпретация. Код Грея и карты Карно.
- Замыкание и замкнутые классы. Классы T0, T1, T∗, T⩽, TL и доказательство их замкнутости.
- Полные системы функций. Примеры полных систем. Полином Жегалкина. Полнота двойственной системы. Доказательство теоремы Поста.
Комбинаторика
- Комбинаторные задачи и комбинаторные конфигурации. Размещения; размещения без повторений.
- Перестановки. Таблицы подстановки. Транспозиции и инверсии. Двойные факториалы; доказательство равенств (2k)!! = 2k ⋅ k!, (2k + 1)!! = (2k + 1)! ∕ (2k ⋅ k!).
- Сочетания; сочетания с повторениями. Бином Ньютона и свойства биномиальных коэффициентов. Треугольник Паскаля.
- Разбиения. Числа Стирлинга второго и первого рода. Число Белла.
- Вывод формулы включений и исключений.
- Число булевых функций, существенно зависящих от всех своих переменных.
- Доказательство теоремы обращения. Формулы обращения для биномиальных коэффициентов. Формулы для чисел Стирлинга.
- Производящие функции и метод неопределенных коэффициентов. Вывод формулы для чисел Фибоначчи.
Графы
- Определение графа. Инцидентность и смежность; окрестность. Диаграммы. Ориентированные графы, псевдографы, мультиграфы, гиперграфы. Помеченные и нумерованные графы.
- Изоморфизм. Инварианты графа. Степень (валентность) вершины; полустепени. Регулярные (однородные) и полные графы. Клика графа. Подграфы. Правильные и остовные подграфы.
- Маршруты, цепи, циклы; пути и контуры. Ациклические графы. Связные, несвязные и вполне несвязные графы; компоненты связности. Геодезические цепи и графы; расстояние между вершинами; ярусы; диаметр графа. Эксцентриситет; радиус; центральные и переферийные вершины; центр графа.
- Двудольные графы. Доказательство теоремы о четности длин всех простых циклов двудольного графа. Направленные (антисимметричные) орграфы; турниры. Сети.
- Операции над графами: дополнение; (дизъюнктное) объединение и соединение; удаление и добавление вершины (ребра); стягивание правильного подграфа к вершине; размножение вершины. Обратимость и коммутативность операций.
- Представления графов: матрица смежности, матрица инциденций, списки последователей, список ребер. Оценки для объема памяти. Представление ориентированных графов, графов с петлями, мультиграфов.
- Связь ориентированных графов и бинарных отношений. Транзитивное замыкание отношения. Диаграммы Хассе.
Связность
- Связные графы. Точки сочленения; мосты; блоки. Доказательство теоремы о маршрутах и точках сочленения в связном графе.
- Вершинная и реберная связность; n-связные графы. Вершинно- и реберно-непересекающиеся цепи. Разделяющее множество; разрез; коцикл. Формулировка теоремы Менгера (в «вершинной форме».)
- Алгоритм нахождения всех возможных систем различных представителей (трансверсалей.) Паросочетание; максимальное паросочетание; совершенное паросочетание. Формулировка теоремы Холла.
- Сеть; источник; сток. Пропускная способность дуги. Алгоритм нахождения пропускной способности сети.
- Лес; (свободное) дерево. Древочисленные и субциклические графы. Формулировка теоремы, устанавливающей основные свойства деревьев. Доказательство теоремы о центре дерева. Ориентированные деревья. Код Прюфера.
Циклы, раскраска, планарность
- Эйлеровы циклы и эйлеровы графы. Доказательство теоремы об эйлеровом графе. Гамильтоновы циклы и задача коммивояжера.
- Раскраска графа. Хроматическое число и оценки для него. Одноцветные классы. Формулировка теоремы о связи хроматических чисел графа и его дополнения.
- Укладка графа. Плоские и планарные графы; грани. Доказательство теоремы Эйлера о плоских графах. Непланарность графов K5, K3, 3. Подразбиение ребра и гомеоморфизм. Формулировка критерия Понтрягина-Куратовского.
- Доказательство теоремы о пяти красках.
Кодирование
- Кодирование и декодирование. Сообщения и коды. Двоичное кодирование. Алфавитное кодирование; схема; элементарные коды. Разделимые и префиксные схемы. Доказательство неравенства Макмиллана. Формулировка теоремы о существовании префиксной схемы алфавитного кодирования.
- Кодирование с минимальной избыточностью. Цена кодирования. Равномерное кодирование. Алгоритм Фано.
Литература
- Новиков, Ф. А. Дискретная математика для программистов. — СПб.: Питер, 2013.
- Судоплатов С. В., Овчинникова Е. В. Элементы дискретной математики. — М.: ИНФРА-М, Новосибирск: Изд-во НГТУ, 2002.
- Шевелев, Ю. П. Дискретная математика. Ч. 2: Теория конечных автоматов. Комбинаторика. Теория графов. (Для автоматизированной технологии обучения «Символ».) — Томск: Том. гос. ун-т систем упр. и радиоэлектроники, 2003.