Найти статью
Дискретная математика
Дискре́тная матема́тика — часть математики, изучающая дискретные математические структуры, такие как графы и утверждения в логике[1].
В контексте математики в целом дискретную математику часто отождествляют с конечной математикой — направлением, изучающим конечные структуры — конечные графы, конечные группы, конечные автоматы[2]. Конечность определяет ряд особенностей, не присущих разделам, работающим с бесконечными и непрерывными структурами. В частности, в дискретных направлениях класс разрешимых задач, как правило, шире, поскольку во многих случаях возможен полный перебор вариантов. Для работы с бесконечными и непрерывными структурами для разрешимости обычно требуются существенные ограничения.
В связи с этим в дискретной математике особо важную роль играют задачи построения конкретных алгоритмов и, в том числе, эффективных с точки зрения вычислительной сложности. Ещё одна особенность дискретной математики — невозможность применения для её экстремальных задач техник математического анализа, существенно использующих недоступные для дискретных структур понятия гладкости[2].
В широком смысле дискретная математика охватывает значительные части алгебры, теории чисел и математической логики. В рамках учебных программ её обычно рассматривают как совокупность разделов, связанных с приложениями к информатике и вычислительной технике: теория функциональных систем, теория графов, теория автоматов, теория кодирования, комбинаторика, целочисленное программирование[3].
В рамках учебных программ дискретная математика обычно рассматривается как совокупность разделов, связанных с приложениями к информатике и вычислительной технике: теория функциональных систем, теория графов, теория автоматов, теория кодирования, комбинаторика, целочисленное программирование[4].
История
Корни дискретной математики уходят в античность: Пифагор и его последователи исследовали свойства целых чисел, а в античной традиции, в частности у Аристотеля, различались дискретные величины (число) и непрерывные величины (протяжённость). В Средние века Аль-Хорезми заложил основы алгоритмических методов[5].
В XVII—XVIII веках Паскаль и Ферма заложили основы теории вероятностей, а Эйлер в 1736 году решил задачу о кёнигсбергских мостах, что считается рождением теории графов. В XIX веке Кантор создал теорию множеств, а Абель и Галуа заложили основы теории групп.
В XX веке развитие дискретной математики было тесно связано с появлением компьютеров[6]. Тьюринг в 1936 году ввёл понятие машины Тьюринга, а ранее, в 1931 году, теорема Гёделя о неполноте показала ограничения формальных систем. В 1970-х годах были разработаны криптографические алгоритмы RSA и протокол Диффи-Хеллмана, а также сформировалась теория сложности вычислений с центральной проблемой P = NP.
Сегодня дискретная математика — теоретический фундамент информатики и компьютерных наук, её методы применяются в социологии, биологии, экономике и лингвистике.
Примечания
Литература
- Дискретная математика. Энциклопедия / Гл. ред. В. Я. Козлов. — М.: Большая российская энциклопедия, 2004. — 382 с.
- Кемени Дж., Снелл Дж., Томпсон Дж. Введение в конечную математику. — М., 1963. — С. 486.
- Яблонский С. В. Введение в дискретную математику. — М.: Наука, 1986. — С. 272.
Дополнительно по теме
 | |
|---|---|
| В библиографических каталогах |
