Вопросы к экзамену по дисциплине «Дискретная математика»

Вопросы к экзамену по дисциплине «Дискретная математика» 2 курс ФИТ 2012г.

Комбинаторное правило произведения. Число выборок объема k из n элементов.
Число выборок объема k из n элементов. Комбинаторные тождества. Бином Ньютона.
Мультимножества, их спецификации. Полиномиальные коэффициенты.
Комбинаторное правило суммы. Формула включений и исключений.
Формула включений и исключений. Задача о беспорядках.
Функция Эйлера, формула для функции Эйлера. Формула для числа сюръективных отображений.
Число Стирлинга второго рода. Формула для числа Стирлинга второго рода. Рекуррентное соотношение для чисел Стирлинга второго рода.
Числа Бела. Теорема о числе Бела.
Число Стирлинга первого рода. Рекуррентное соотношение для чисел Стирлинга первого рода. Связь между числами Стирлинга.
Разложение xⁿ в базисе (x)_k. Разложение (x)_k в базисе xⁿ.
Разбиения чисел. Диаграмма Ферре. Свойства числа разбиений. Равенство числа разбиений на различные слагаемые и на нечетные слагаемые.
Разбиения чисел. Диаграмма Ферре. Свойства числа разбиений. Связь между числами разбиений на четное и нечетное число различных слагаемых.
Правильная скобочная структура, её код. Число правильных скобочных структур.
Производящие функции и их свойства. Элементарные производящие функции.
Числа Каталана, производящая функция последовательности чисел Каталана, формула для числа Каталана.
Числа Фибоначчи, производящая функция последовательности чисел Фибоначчи, формула для числа Фибоначчи.
Линейная однородная возвратная последовательность, ее производящая функция. Общее решение линейного однородного рекуррентного соотношения
Граф, мультиграф, псевдограф. Изоморфизм графов, автоморфизм. Лемма о рукопожатиях. Орграф, связный, сильно связный орграф.
Подграф, порожденный подграф, остовный подграф. Объединение, соединение, умножение графов. Связный граф, компонента связности.
Дополнение к графу, реберный граф. Двудольность, критерий двудольности.
Оценки числа ребер графа. Эксцентриситет, радиус, диаметр, центр графа.
Лес, дерево, характеризация деревьев. Центр дерева.
Остовное дерево, остов. Алгоритмы Краскала и Примы.
Код Прюфера помеченного дерева. Теорема Кэли.
Числа вершинной и реберной связности, их связь. Точка сочленения, характеризация точек сочленения. Мост, характеризация мостов.
Характеризация двусвязных графов. Блок, bc-дерево графа.
Теорема Менгера
Независимое множество. Оценки числа независимости. Вершинное покрытие. Связь чисел покрытия и независимости.
Теорема Рамсея для графов.
Паросочетание, реберное покрытие. Теорема о связи чисел паросочетания и реберного покрытия. Совершенное паросочетание.
Терема Кенига о числе паросочетания для двудольных графов. Теорема Кенига о (0,1)-матрицах.
Терема Холла о паросочетаниях. Теорема Фробениуса о свадьбах. Системы различных представителей, теорема Холла о СРП.
Теорема об увеличивающей цепи. Алгоритм построения наибольшего паросочетания в двудольном графе (венгерский метод).
Эйлеров цикл, эйлеров граф. Теорема Эйлера. Алгоритм Флёри.
Гамильтонов цикл, гамильтонов граф. Теорема Оре. Теорема Дирака. Гамильтоковость n-куба.
Укладка графа в пространство. Планарный граф, плоский граф, укладка на сфере.
Формула Эйлера. Непланарность K₅ и K_3,3. Характеризация плоских двусвязных графов.
Алгоритм укладки графа на плоскость.
Правильная раскраска вершин графа. Хроматическое число. Теорема Брукса
Правильная раскраска вершин графа. Хроматическое число. Теорема Зыкова
Раскраски планарных графов. Теорема о четырех красках. Теорема Хивуда.
Правильная раскраска ребер графа. Хроматический индекс. Теорема Кёнига о хроматическом индексе двудольных графов.
Теорема Визинга о хроматическом индексе графа.
Правильная раскраска ребер графа. Хроматический индекс. Теорема о хроматическом индексе полного графа.
Булева функция. Существенные и фиктивные переменные. Теорема о числе булевых функций, существенно зависящих от n переменных.
Формула. Функция, которую реализует формула. Эквивалентные формулы. Основные эквивалентности.
Теорема о разложении функций по переменным. Совершенная дизъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма. Двойственная функция. Принцип двойственности.
Замкнутое, полное множества булевых функций. Теорема о полноте двух систем.
Полином Жегалкина. Теорема Жегалкина. Три способа построения полинома Жегалкина.
Основные замкнутые классы булевых функций. Предполные классы.
Теорема Поста.
Минимизация ДНФ. Способы построения сокращенной ДНФ.
Способы построения тупиковых ДНФ. Теорема Журавлева.
Способы построения тупиковых ДНФ. ДНФ Квайна. Алгоритм Квайна. ДНФ пересечения.
Схема из функциональных элементов. Система функций, реализуемая схемой из функциональных элементов.
Сложность схемы из функциональных элементов. Реализация сумматора. Функция Шеннона для СФЭ. Метод Шеннона.
Метод Лупанова синтеза схем из функциональных элементов
Мощностной метод получения нижней оценки функции Шеннона для СФЭ
Классы P и NP. Полиномиальная сводимость. NP-полные задачи. NP-полнота задачи 3-выполнимость
Классы P и NP. Полиномиальная сводимость. NP-полные задачи. NP-полнота задачи о клике
Классы P и NP. Полиномиальная сводимость. NP-полные задачи. NP-полнота задачи о независимом множестве
Классы P и NP. Полиномиальная сводимость. NP-полные задачи. NP-полнота задачи о вершинном покрытии
Классы P и NP. Полиномиальная сводимость. NP-полные задачи. NP-полнота задачи гамильтонов цикл
Ограниченно-детерминированные функции. Способы их задания.
Конечный детерминированный автомат с выходом. Автоматные функции, связь с ограниченно-детерминированными функциями. Лемма о периодической функции.
Схема из автоматных элементов. Теорема о не существовании конечных полных систем автоматных функций.
Схемы из автоматных элементов с использованием операции обратной связи. Реализация произвольной автоматной функции.
Конечные автоматы Мили и Мура, их эквивалентность.
Конечный детерминированный инициальный автомат без выходов. Пример языка, не распознаваемого конечным автоматом.
Конечные автоматы без выходов. Регулярные языки. Теорема анализа автоматов
Конечные автоматы без выходов. Регулярные языки. Теорема синтеза автоматов