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

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

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

Примечания

Литература

• Дискретная математика. Энциклопедия / Гл. ред. В. Я. Козлов . — М. : Большая российская энциклопедия, 2004. — 382 с.
• Кемени Дж. , Снелл Дж., Томпсон Дж. Введение в конечную математику. — М. , 1963. — С. 486.
• Яблонский С. В. Введение в дискретную математику. — М. : Наука, 1986. — С. 272.

Ссылки