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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Дискре́тная матема́тика — часть математики, изучающая дискретные математические структуры, такие, как графы и утверждения в логике[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 с.
  • Андерсон Дж. Дискретная математика и комбинаторика. — М.: Вильямс, 2006. — 960 с. — ISBN 0-13-086998-8.
  • Белоусов А. И., Ткачев С. Б. Дискретная математика. — М.: МГТУ им. Н. Э. Баумана, 2001. — 744 с. — ISBN 5-7038-1769-2.
  • Ерусалимский Я. М. Дискретная математика. — М., 2000.
  • Иванов Б. Н. Дискретная математика. Алгоритмы и программы. — М.: Физматлит, 2007. — 408 с. — ISBN 978-5-9221-0787-7.
  • Кемени Дж., Снелл Дж., Томпсон Дж. Введение в конечную математику. — М., 1963. — С. 486.
  • Редькин Н. П. Дискретная математика. — М.: Лань, 2006. — 96 с. — ISBN 5-8114-0522-7.
  • Яблонский С. В. Введение в дискретную математику. — М.: Наука, 1986. — С. 272.

Ссылки[править | править вики-текст]