Математическая энциклопедия - дискретный анализ

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

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

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

Элементы Д. а. возникли в глубокой древности и, развиваясь, параллельно с другими разделами математики, в значительной мере являлись их составной частью. Типичными для того периода были задачи, связанные со свойствами целых чисел, приведшие затем к созданию теории чисел. Позже, в основном в связи с игровыми задачами, появились элементы комбинаторного анализа и дискретной теории вероятностей, а в связи с общими проблемами теории чисел, алгебры и геометрии возникли важнейшие понятия алгебры такие, как группа, поле, кольцо и др., определившие развитие и содержание алгебры на много лет вперед и имевшие по существу дискретную природу. Стремление к строгости математич. рассуждений и анализ рабочего инструмента математики логики привели к выделению еще одного важного раздела математики математич. логики. Однако наибольшего развития Д. а. достиг в связи с появлением кибернетики и ее теоретич. части математич. кибернетики. Математич. кибернетика, непосредственно изучающая с позиций математики самые разнообразные проблемы, к-рые ставит перед кибернетикой практика, является важным поставщиком идей и задач для Д. а., вызывая в нем целые новые направления. Так, прикладные вопросы, требующие большой числовой обработки, стимулировали появление сильных численных методов решения задач, оформившихся затем в вычислительную математику, а анализ понятий вычислимости и алгоритма привел к появлению важного раздела математич. логики алгоритмов теории. Растущий поток информации и связанные с ним задачи хранения, обработки и передачи информации привели к возникновению теории кодирования; экономич. задачи, задачи электротехники, равно как и внутренние задачи математики, потребовали разработки теории графов; задачи конструирования и описания работы сложных управляющих систем привели к теории функциональных систем и т. д. В то же время математич. кибернетика использует результаты Д. а. при решении своих задач. Наряду с отмеченными, Д. а. обладает рядом и других особенностей. Так, вместе с задачами типа существования, имеющими общематематич. характер, важное место в Д. а. занимают задачи, связанные с алгоритмич. разрешимостью и построением конкретных решающих алгоритмов, что характерно именно для Д. а. Особенностью Д. а. является и то, что он по существу первым столкнулся с необходимостью глубокого исследования так наз. дискретных многоэкстремальных задач, часто возникающих в математич. кибернетике. Соответствующие методы классич. математики для поиска экстремумов, существенно использующие гладкость функций, в этих случаях оказываются мало эффективными. Типичными задачами такого рода в Д. а. являются, напр., задачи об отыскании в нек-ром смысле оптимальных стратегий в шахматной партии при ограниченном числе ходов, а также важный вопрос математич. кибернетики о построении минимальных дизъюнктивных нормальных форм для булевых функций, т. е. так наз. проблема булевых функций минимизации. Особенностью Д. а., связанной уже с задачами для конечных структур, является и то, что для многих из этих задач, как правило, существует алгоритм решения, в то время как в классич. математике полное решение задачи часто возможно лишь при весьма жестких ограничениях. Примером такого алгоритма может служить алгоритм просмотра всех возможных вариантов, т. е. алгоритм типа "полного перебора". К числу задач указанного вида можно отнести, напр., упомянутые задачи о стратегиях в шахматной партии, о минимизации булевых функций и др. Вместо с тем решения типа "полного перебора" очень трудоемки и практически мало приемлемы, в связи с чем возникает ряд новых задач, связанных с условиями, ограничивающими перебор и приводящими к сведению индивидуальных задач, характеризующихся конкретными значениями параметров, к массовой проблеме, характеризующейся бесконечным множеством значений параметров; возникают задачи наложения ограничений на средства решения, естественных для этого класса задач, и др. Постановка такого рода вопросов и разработка методик осуществляется на конкретных моделях, доставляемых различными разделами математики, напр, на моделях минимизации булевых функций н синтеза управляющих систем из математич. кибернетики.

Лит.:[1] Яблонский С. В., Обзор некоторых результатов в области дискретной математики, "Информационные материалы", 1970, 5, с. 5 -15; [2] Кемеви Дж., Снелл Дж., Томпсон Дж., Введение в конечную математику, пер. с англ., 2 изд., М., 1965. См. сб. "Проблемы кибернетики" и "Дискретный анализ", ж. "Кибернетика".

В. Б. Кудрявцев.

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985