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

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

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

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

Примечания

править
  1. Richard Johnsonbaugh. Discrete Mathematics. — 7th edition. — Prentice Hall, 2008. — ISBN 0131354302.
  2. 1 2 Конечная математика // Большая советская энциклопедия : [в 30 т.] / гл. ред. А. М. Прохоров. — 3-е изд. — М. : Советская энциклопедия, 1969—1978.
  3. 1 2 Яблонский, 1986, с. 6.

Литература

править
  • Дискретная математика. Энциклопедия / Гл. ред. В. Я. Козлов. — М.: Большая российская энциклопедия, 2004. — 382 с.
  • Кемени Дж., Снелл Дж., Томпсон Дж. Введение в конечную математику. — М., 1963. — С. 486.
  • Яблонский С. В. Введение в дискретную математику. — М.: Наука, 1986. — С. 272.
  • Костенко К. И. Элементы дискретной математики. — М-во образования Рос. Федерации. Куб. гос. ун-т., 1999. — 269 с. — ISBN 5-8209-0020-0.

Ссылки

править