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

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

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

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