Тематический обзор* введение. Предмет дискретной математики

Дискретная математика (ДМ), или дискретный анализ – область математики, которая занимается исследованиями структур и задач на конечных множествах. Поэтому в качестве синонима иногда используется термин «конечная математика». Можно считать общепринятым деление математики на континуальную (непрерывную) и дискретную. Последняя представляет собой важное направление, имеющее характерные для него предмет исследований, методы и задачи. Специфика задач дискретной математики в первую очередь предполагает отказ от основных понятий классической математики – предела и непрерывности. Поэтому для задач ДМ обычные средства классического анализа являются вспомогательными.

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

Сегодня ДМ является важным звеном математического образования. Умение проводить анализ, композицию и декомпозицию информационных комплексов и информационных процессов – обязательное квалификационное требование к специалистам в области информатики.

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

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

Еще в доньютоновский период появились простейшие понятия комбинаторики (Франция, XVII в.: П. Ферма, Б. Паскаль). Комбинаторика возникла как основа дискретной теории вероятностей в связи с исследованиями в области азартных игр. Л. Эйлер в середине XVIII в. закладывает основы теории графов; в середине XIX в. Дж. Буль, опираясь на некоторые идеи Г. Лейбница, придумывает свою «универсальную алгебру» в продолжение наметившегося еще в средние века стремления к формализации аристотелевой логики. В конце XIX в., характеризующегося, с одной стороны, обобщающе-синтетическим подходом к различным разделам математики, а с другой – стремлением к строгости математических обоснований, происходит поворот к созданию и быстрому расцвету математической логики.

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