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

Дискретная математика (discrete mathematics) – область математики, занимающаяся изучением свойств дискретных структур, которые возникают как внутри математики, так и в ее приложениях. К числу таких структур могут быть отнесены, например, конечные группы, конечные графы, некоторые математические модели преобразователей информации, конечные автоматы, машины Тьюринга. Это примеры структур финитного (конечного) характера. Часть Д. м., изучающая их, иногда называется конечной математикой. Помимо финитных структур Д. м. изучает нек-рые дискретные бесконечные структуры, например, бесконечные алгебраические системы, бесконечные графы, бесконечные автоматы.

В отличие от Д. м. значительная часть классической математики занимается изучением свойств объектов непрерывного характера. Использование дискретной или непрерывной модели изучаемого объекта связано с тем, какие задачи ставит перед собой исследователь. Само деление математики на Д. м. и математику, занимающуюся непрерывными моделями, в значительной мере условно, поскольку, с одной стороны, происходит обмен идеями и методами между ними, а с другой – часто возникает необходимость исследования моделей, обладающих как дискретными, так и непрерывными свойствами одновременно. В математике существуют разделы, использующие средства Д. м. для изучения непрерывных моделей (например, алгебраическая геометрия), и наоборот, часто методы, развитые для анализа непрерывных моделей, используются при изучении дискретных структур (например, асимптотические методы в теории чисел, в перечислительных задачах комбинаторики). Однако специфика многих разделов Д. м. связана с необходимостью отказа от основополагающих понятий классической математики таких, как предел и непрерывность, в связи с чем для многих задач Д. м. некоторые методы классической математики оказываются неприменимыми.

Д. м. представляет собой важный раздел математики, в котором можно выделить характерные предмет и методы исследования. Наряду с выделением Д. м. путем указания ее предмета можно также определить Д. м. посредством перечисления составляющих ее разделов. К ним относятся комбинаторный анализ, графов теория, теория кодирования, теория функциональных систем, теория управляющих систем, теория автоматов, алгоритмы и анализ их сложности. При более широком толковании к Д. м. могут быть отнесены как целые разделы математики, например, математическая логика, так и части таких разделов, как теория чисел, алгебра, вычислительная математика, теория вероятностей, в которых изучаемый объект носит дискретный характер.

Элементы Д. м. возникли в глубокой древности; развиваясь параллельно с другими разделами математики, они являлись их составной частью. Типичными для того времени были задачи, связанные со свойствами целых чисел и приведшие затем к созданию теории чисел. Примерами являются задачи отыскания алгоритмов сложения и умножения натуральных чисел у древних египтян, вопросы делимости натуральных чисел и задачи суммирования в Пифагорейской школе. Позже (17-18 вв.), в основном в связи с игровыми задачами, появились элементы комбинаторного анализа и дискретной теории вероятностей, а в связи с общими проблемами теории чисел, алгебры и геометрии (18-19 вв.) возникли важнейшие понятия алгебры такие, как группа, поле, кольцо, определившие развитие и содержание алгебры на много лет вперед и имевшие, по существу, дискретную природу. Стремление к строгости математических рассуждений и анализ рабочего инструмента математики привели к выделению еще одного раздела математики – математичесой логики (19-20 вв.). Наибольшего развития Д. м. достигла в связи с запросами практики, приведшими к появлению новой науки – кибернетики и ее теоретической части – математической кибернетики (20 в.). Математическая кибернетика, изучающая с позиций математики разнообразные проблемы, которые ставит перед кибернетикой практическая деятельность человека, является поставщиком идей и задач Д. м. Так, прикладные вопросы, требующие большой числовой обработки, стимулировали появление и развитие численных методов решения задач, оформившихся затем в вычислительную математику, а анализ понятий <<вычислимость>> и <<алгоритм>> привел к созданию алгоритмов теории. Задачи хранения, обработки и передачи информации привели к возникновению информации теории, теории кодирования и теоретической криптографии. Экономически задачи, задачи электротехники, равно как и внутренние задачи математики, потребовали развития теории графов. Задачи конструирования и описания работы сложных управляющих систем составили предмет теории управляющих систем и теории автоматов.

Одна из особенностей Д. м. состоит в том, что вместе с задачами типа задач существования, имеющими общематематический характер, важное место в Д. м. занимают задачи, связанные с алгоритмической разрешимостью и построением конкретных решающих алгоритмов.

Другой особенностью Д. м. является то, что впервые в ней начались исследования т.н. дискретных многоэкстремальных задач. Соответствующие методы поиска экстремумов, использующие гладкость функций, в этих случаях оказываются неприменимыми. Типичными задачами такого рода в Д. м. являются, например, задачи отыскания в нек-ром смысле оптимальных стратегий в шахматах, а также задачи построения минимальных дизъюнктивных нормальных форм для булевых функций, то есть так наз. проблема минимизации булевых функций (см. также статью Алгебра логики).

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

Рекомендуемая литература

Яблонский С.В., Введение в дискретную математику, М., 1979;

Кемени Дж., Снелл Дж., Томпсон Дж., Введение в конечную математику, пер. с англ., 2 изд., М., 1965;

Кудрявцев В.Б., Функциональные системы, М., 1982;

Кудрявцев В.Б., Алешин С.В., Подколзин А.С., Введение в теорию автоматов, М., 1982;

Гашков С.Б., Чубариков В.Н., Арифметика. Алгоритмы. Сложность вычислений, М., 2000;

Кнут Д., Искусство программирования для ЭВМ, т. 1-3, 3 изд., пер. с англ., М., 2000.