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