Дискретный Анализ

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

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

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

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

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

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

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

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

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

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