Дискретная математика — область математики, занимающаяся изучением дискретных структур, которые возникают как в пределах самой математики, так и в её приложениях.
В контексте математики в целом дискретная математика часто отождествляется с конечной математикой — направлением, изучающим конечные структуры — конечные графы, конечные группы, конечные автоматы. И при этом можно выделить некоторые особенности, не присущие разделам, работающим с бесконечными и непрерывными структурами. Так, в дискретных направлениях как правило обширнее класс разрешимых задач, так как во многих случаях возможен полный перебор вариантов, тогда как в разделах, имеющих дело с бесконечными и непрерывными структурами, для разрешимости обычно требуются существенные ограничения на условия.
Шпаргалка по дискретной математике:
- Множества и их спецификации. Подмножества
- Операции над множествами. Свойства
- Декартово произведение
- Отношения. Свойства отношений
- Графическое представление бинарных отношений
- Матрица бинарного отношения
- Отношение эквивалентности
- Отношение порядка
- Функции. Мощность множеств
- Представление множеств в ЭВМ
- Определение графов
- Смежность, инцедентность, степени
- Маршруты, пути, циклы
- Изоморфизм графов
- Представление графов в ЭВМ
- Полные графы и двудольные графы
- Операции с графами
- Связность в неориентированных графах
- Связность в орграфах
- Нахождение компонент связности на ЭВМ
- Поиск в ширину и глубину
- Свободные деревья
- Ориентированные и упорядоченные деревья
- Бинарные деревья. Обходы
- Деревья сортировки
- Сравнение представлений ассоциативной памяти
- Кратчайший остов
- Планарные графы. Теорема Понтягина-Куратовского
- Раскраска графов. Алгоритмы
- Построение фундаментального множества циклов
- Эйлеровы циклы
- Гамильтоновы графы
- Графы и бинарные отношения
