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


Дискре́тная матема́тика — неклассифицируемое объединение нескольких разделов математики, изучающее дискретные математические структуры, такие как графы и утверждения в логике[1].

В контексте математики в целом дискретная математика часто отождествляется с конечной математикой — направлением, изучающим конечные структуры — конечные графы, конечные группы, конечные автоматы. Также в качестве синонима для «конечной математики» и «дискретной математики» часто используется понятие дискретный анализ[2], в котором дискретность как антипод непрерывности отражает нацеленность на получение целочисленных результатов вычислений. Конечность определяет некоторые особенности, не присущие разделам, работающим с бесконечными и непрерывными структурами, например, в дискретных направлениях как правило обширнее класс разрешимых задач, так как во многих случаях возможен полный перебор вариантов, тогда как при работе с бесконечными и непрерывными структурами для разрешимости обычно требуются существенные ограничения. В связи с этим в дискретной математике особо важную роль играют задачи построения конкретных алгоритмов, и в том числе, эффективных с точки зрения вычислительной сложности. Ещё одна особенность дискретной математики — невозможность применения для её экстремальных задач техник анализа, существенно использующих недоступные для дискретных структур понятия гладкости[2]. В широком смысле, можно считать, что дискретная математика охватывает значительные части алгебры, теории чисел, математической логики[3].

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