Дискретная математика. Шпаргал

A collection of cheat sheets for discrete mathematics. Answers to questions, theory

Дискретная математика — область математики, занимающаяся изучением дискретных структур, которые возникают как в пределах самой математики, так и в её приложениях.

В контексте математики в целом дискретная математика часто отождествляется с конечной математикой — направлением, изучающим конечные структуры — конечные графы, конечные группы, конечные автоматы. И при этом можно выделить некоторые особенности, не присущие разделам, работающим с бесконечными и непрерывными структурами. Так, в дискретных направлениях как правило обширнее класс разрешимых задач, так как во многих случаях возможен полный перебор вариантов, тогда как в разделах, имеющих дело с бесконечными и непрерывными структурами, для разрешимости обычно требуются существенные ограничения на условия.

Шпаргалка по дискретной математике:

- Множества и их спецификации. Подмножества

- Операции над множествами. Свойства

- Декартово произведение

- Отношения. Свойства отношений

- Графическое представление бинарных отношений

- Матрица бинарного отношения

- Отношение эквивалентности

- Отношение порядка

- Функции. Мощность множеств

- Представление множеств в ЭВМ

- Определение графов

- Смежность, инцедентность, степени

- Маршруты, пути, циклы

- Изоморфизм графов

- Представление графов в ЭВМ

- Полные графы и двудольные графы

- Операции с графами

- Связность в неориентированных графах

- Связность в орграфах

- Нахождение компонент связности на ЭВМ

- Поиск в ширину и глубину

- Свободные деревья

- Ориентированные и упорядоченные деревья

- Бинарные деревья. Обходы

- Деревья сортировки

- Сравнение представлений ассоциативной памяти

- Кратчайший остов

- Планарные графы. Теорема Понтягина-Куратовского

- Раскраска графов. Алгоритмы

- Построение фундаментального множества циклов

- Эйлеровы циклы

- Гамильтоновы графы

- Графы и бинарные отношения