Экзаменационные вопросы по дискретной математике
Описание файла
Документ из архива "Экзаменационные вопросы по дискретной математике", который расположен в категории "". Всё это находится в предмете "дискретная математика" из 4 семестр, которые можно найти в файловом архиве РТУ МИРЭА. Не смотря на прямую связь этого архива с РТУ МИРЭА, его также можно найти и в других разделах. Архив можно найти в разделе "к экзамену/зачёту", в предмете "дискретная математика" в общих файлах.
Онлайн просмотр документа "Экзаменационные вопросы по дискретной математике"
Текст из документа "Экзаменационные вопросы по дискретной математике"
2
ЭКЗАМЕНАЦИОННЫЕ ВОПРОСЫ
по курсу
«ДИСКРЕТНАЯ МАТЕМАТИКА»
-
Особенности рассматриваемых в дискретной математике моделей объектов, задач и алгоритмов их решения.
Теория множеств
-
Задание множеств. Пустое и универсальное множества. Понятие подмножества. Мощность множества. Верхняя и нижняя границы множества.
-
Операции над множествами. Свойства операций над множествами.
-
Доказательство тождественности формул в теории множеств.
-
Семейства множеств. Операции над семействами.
-
Прямое и обратное соответствия. Композиция соответствий.
-
Отображения множеств и их свойства. Отображения, заданные на одном множестве. Функция, функционал, оператор.
-
Отношения, их задание и свойства. Операции над отношениями.
-
Отношения эквивалентности. Отношения порядка.
Булева алгебра
-
Функции булевой алгебры, понятие фиктивной переменной.
-
Суперпозиция логических функций.
-
Законы и тождества булевой алгебры.
-
Способы задания и свойства логических функций.
-
Разложение булевых функций по переменным.
-
Совершенные нормальные формы булевых функций.
-
Понятие двойственной функции.
-
Полином Жегалкина, способы его получения.
-
Классы логических функций. Функционально полные системы функций.
-
Примеры функционально полных базисов, доказательство их полноты.
-
Минимизация логических функций, интервалы и покрытия.
-
Карты Карно.
-
Анализ и синтез логических схем. Реализация не полностью определенных логических функций.
Теория графов
-
Основные понятия и определения теории графов.
-
Гомоморфизм и изоморфизм графов. Подграфы и части графа.
-
Способы задания графов: матричная и векторная формы.
-
Операции над графами.
-
Маршруты, достижимость, связность.
-
Метрические характеристики графов: обхват, радиус и диаметр графа.
-
Нахождение маршрутов, в том числе и кратчайших.
-
Нахождение сильных компонент и компонент связности графов.
-
Вершинные базы, внутренне и внешне устойчивые множества вершин графа. Вершинная и реберная связность графа.
-
Эйлеровы и гамильтоновы графы, покрытие графа простыми цепями. Алгоритм построения эйлерова цикла.
-
Обходы графа по глубине и ширине.
-
Остовы графа. Алгоритм нахождения остова минимального веса.
-
Фундаментальные циклы графа.
-
Фундаментальные разрезы графа.
-
Планарные графы. Критерий планарности. Алгоритм построения плоского изображения графа. Толщина графа.
-
Раскраска графов, хроматическое число и его оценка.
-
Алгоритмы раскраски.
-
Двудольные графы и их свойства.
-
Сети.