Дискретная математика

Понятие дискретной математики

В понятие «дискретная математика» объединены все разделы математики, которые основаны на дискретных структурах. Между ними существуют определенные взаимосвязи, которые зачастую ссылаются друг на друга, но в общей совокупности они составляют единую теорию, к которой относится и вся математика в целом. Однако, дискретная математика строится на самостоятельных теориях и направлениях.

Дискретная математика, в контексте математики как науки, отождествляется с конечной математикой (направлением, основой знаний которой является исследование конечных структур – конечных графов, конечных автоматов, конечных групп). Конечность определяет некоторые особенности, которые не характерны разделам, изучающим бесконечные и непрерывные структуры (например, для дискретных направлений характерен более широкой круг решаемых задач, потому как во многих случаях возможен перебор различных вариантов, при том, как в изучении бесконечных и непрерывных структур характерны существенные ограничения для решения задач).

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

Дискретная математика рассматривается как совокупность разделов, которые связаны с информатикой и вычислительной техникой, в частности, к ним относятся: теория графов, теория функциональных систем, теория автоматов, комбинаторика и теория кодирования, целочисленное программирование.

История развития

С давних времен дискретные системы применялись в вычислительной практике. В древности были широко известны различные системы счисления и связанные с ними алгоритмы выполнения различных арифметических операций, решения уравнений и пр. Распространение получили различные дискретные инструменты: различные виды счетных досок, абак.

Дискретная математика развивалась параллельно с другими разделами математики, являясь составной частью единого целого.

Примерами дискретных математических объектов являются:

• функция (отображение из конечного множества в конечное множество);
• натуральный ряд чисел;
• конечное множество элементов произвольной природы;
• слово (как последовательность символов) и формальный язык (множество слов) в конечном алфавите;
• конечный граф и пр.

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

Разделение математики на «дискретную» и «непрерывную» условно, потому как математика представляет собой единую систему, пронизанную аналогиями. В ее разделах развиваются различные сходные конструкции и идеи, то есть происходит обмен идеями и методами, также зачастую возникает необходимость в исследовании моделей, которые обладают как дискретными, так и непрерывными функциями.

В широком смысле дискретная математика включает в себя такие разделы математики как: теория чисел, теория множеств, алгебра, математическая логика и прочие.

Узконаправленно дискретная математика формирует ряд специализированных разделов и новые разделы, которые интенсивно развиваются с середины прошлого века, что обусловлено новыми изобретениями и их внедрением с применение вычислительной техники и цифровых технологий (теория функциональных систем, теория сетей и графов, теория алгоритмов и автоматов, комбинаторный анализ, теория кодирования, теория синтеза управляющих систем, дискретная геометрия и пр.).

Этапы развития дискретной математики связаны с исследованиями Л. Эйлера (XVII в.), который ввел комбинаторный анализ и теорию графов, и Я. Бернулли, разработавшем комбинаторную теорию вероятностей. Большой вклад в идеологию дискретной математики вложили Г.В. Лейбниц, Ж.Л. Лагранж, А. Кэли, Дж. Буль, Ж. Жордан и прочие.