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

Перейти к навигацииПерейти к поиску

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

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

Широкое использование понятия о дискретной математике началось в 1960-е годы, по-видимому, в связи бурным развитием приложений к информатике: в СССР с 1971 года начал издаваться журнал «Дискретная математика», в 1979 году Американским математическим обществом учреждена премия Фалкерсона, вручаемая за «заслуги в области дискретной математики», в Германской ассоциации математиков образована секция дискретной математики, раз в два года присуждающая профильную премию.

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

Примечания

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

Литература

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

Ссылки