Специальность Прикладная математика
дисциплина Дискретная математика
Ответы на билеты + шпаргалка. формат docx
Список вопросов (есть 26 из 39):
- Основные определения. Операции над множествами и их свойства.
- Отношение эквивалентности.
- Отношения. Композиция отношений.
- Разбиение на классы.
- Счетные множества.
- Упорядоченные множества. Отношение порядка.
- Полугруппы. Группы.
- Группы. Циклические группы.
- Группы подстановок.
- Кольца. Тела. Поля.
- Полукольца.
- Замкнутые полукольца.
- Решение линейных уравнений в полукольцах.
- Решение систем в полукольцах.
- Булевы алгебры. Принцип двойственности.
- Решетки.
- Задачи комбинаторики. Правила суммы и произведения.
- Размещения и сочетания.
- Бином Ньютона. Свойства биномиальных коэффициентов.
- Неориентированные графы. Основные определения.
- Ориентированные графы. Основные определения.
- Связность графов. Компоненты связности.
- Формы представления графов: матрицы инциденций, смежности, достижимости, списки смежности.
- Операции над графами.
- Деревья. Лес.
- Остовное дерево наименьшего веса. Задача Штейнера. Алгоритм Краскала.
- Алгоритм поиска в глубину в ориентированном графе.
- Алгоритм поиска в ширину в ориентированном графе.
- Задача о путях во взвешенных ориентированных графах. Общая задача о путях.
- Алгоритм Дейкстеры
- Изоморфизм графов.
- Топологическая сортировка. Алгоритм Демукрона.
- Понятие булевой функции. Булев куб.
- Таблицы истинности.
- Фиктивные переменные. Равенство булевых функций.
- Формулы и суперпозиции.
- Дизъюнктивные и конъюнктивные нормальные формы.
- Построение МДНФ. Алгоритм Квайна-Мак-Клоски.
- Построение МДНФ. Карты Карно.
|