Экзаменационные вопросы по дискретной математике (1023598)
Текст из файла
2
ЭКЗАМЕНАЦИОННЫЕ ВОПРОСЫ
по курсу
«ДИСКРЕТНАЯ МАТЕМАТИКА»
-
Особенности рассматриваемых в дискретной математике моделей объектов, задач и алгоритмов их решения.
Теория множеств
-
Задание множеств. Пустое и универсальное множества. Понятие подмножества. Мощность множества. Верхняя и нижняя границы множества.
-
Операции над множествами. Свойства операций над множествами.
-
Доказательство тождественности формул в теории множеств.
-
Семейства множеств. Операции над семействами.
-
Прямое и обратное соответствия. Композиция соответствий.
-
Отображения множеств и их свойства. Отображения, заданные на одном множестве. Функция, функционал, оператор.
-
Отношения, их задание и свойства. Операции над отношениями.
-
Отношения эквивалентности. Отношения порядка.
Булева алгебра
-
Функции булевой алгебры, понятие фиктивной переменной.
-
Суперпозиция логических функций.
-
Законы и тождества булевой алгебры.
-
Способы задания и свойства логических функций.
-
Разложение булевых функций по переменным.
-
Совершенные нормальные формы булевых функций.
-
Понятие двойственной функции.
-
Полином Жегалкина, способы его получения.
-
Классы логических функций. Функционально полные системы функций.
-
Примеры функционально полных базисов, доказательство их полноты.
-
Минимизация логических функций, интервалы и покрытия.
-
Карты Карно.
-
Анализ и синтез логических схем. Реализация не полностью определенных логических функций.
Теория графов
-
Основные понятия и определения теории графов.
-
Гомоморфизм и изоморфизм графов. Подграфы и части графа.
-
Способы задания графов: матричная и векторная формы.
-
Операции над графами.
-
Маршруты, достижимость, связность.
-
Метрические характеристики графов: обхват, радиус и диаметр графа.
-
Нахождение маршрутов, в том числе и кратчайших.
-
Нахождение сильных компонент и компонент связности графов.
-
Вершинные базы, внутренне и внешне устойчивые множества вершин графа. Вершинная и реберная связность графа.
-
Эйлеровы и гамильтоновы графы, покрытие графа простыми цепями. Алгоритм построения эйлерова цикла.
-
Обходы графа по глубине и ширине.
-
Остовы графа. Алгоритм нахождения остова минимального веса.
-
Фундаментальные циклы графа.
-
Фундаментальные разрезы графа.
-
Планарные графы. Критерий планарности. Алгоритм построения плоского изображения графа. Толщина графа.
-
Раскраска графов, хроматическое число и его оценка.
-
Алгоритмы раскраски.
-
Двудольные графы и их свойства.
-
Сети.
Характеристики
Тип файла документ
Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.
Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.
Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.