Дискретный анализ
Дискре́тный ана́лиз, область математики, занимающаяся изучением свойств структур финитного (конечного) характера, которые возникают как в самой математике, так и в области её приложений. К числу таких конечных структур могут быть отнесены, например, конечные группы, конечные графы, а также некоторые математические модели преобразователей дискретной информации, такие как конечные автоматы, машины Тьюринга и др. Иногда допускают расширение предмета дискретного анализа до произвольных дискретных структур и приходят к дискретной математике, отождествляя последнюю с дискретным анализом. К числу таких структур могут быть отнесены некоторые алгебраические системы, бесконечные графы, некоторые виды вычислительных сред (например, однородные структуры) и т. п. В качестве синонима понятий дискретного анализа и дискретной математики иногда употребляется термин «конечная математика». Ниже дискретный анализ понимается в широком смысле, включающем дискретную математику.
В отличие от дискретного анализа, классическая математика в основном занимается изучением свойств объектов непрерывного характера. Использование классической или дискретной математики как аппаратов исследования связано с тем, какие задачи ставит перед собой исследователь и, в связи с этим, какую модель изучаемого явления он рассматривает – дискретную или непрерывную. Само деление математики на классическую и дискретную в значительной мере условно, поскольку, с одной стороны, происходит активная циркуляция идей и методов между ними, а с другой – часто возникает необходимость исследования моделей, обладающих одновременно как дискретными, так и непрерывными свойствами. Кроме того, в математике существуют подразделы, использующие средства дискретной математики для изучения непрерывных моделей, и, наоборот, часто средства и постановки задач классического анализа используются при исследовании дискретных структур. Это указывает на известное слияние рассматриваемых областей.
Дискретный анализ представляет собой важное направление в математике, имеющее характерные для него предмет исследования, методы и задачи, специфика которых обусловлена, в первую очередь, необходимостью отказа в дискретном анализе от основополагающих понятий классической математики – предела и непрерывности – и (в связи с этим) тем, что для многих задач дискретного анализа сильные средства классической математики оказываются, как правило, малоприемлемыми. Наряду с выделением дискретного анализа путём указания его предмета, методов и задач можно также охарактеризовать дискретный анализ посредством перечисления подразделов, составляющих его. К ним, в первую очередь, относятся комбинаторный анализ, теория графов, теория кодирования и декодирования, теория функциональных систем и некоторые другие. Часто под термином «дискретный анализ» (в предположении, что его предмет исчерпывается конечными структурами) понимается именно совокупность перечисленных дисциплин. За счёт расширения понимания его круга вопросов возможно и более широкое толкование дискретного анализа. С этой точки зрения, к дискретному анализу могут быть отнесены также как целые разделы математики, например математическая логика, так и части таких разделов, как теория чисел, алгебра, вычислительная математика, теория вероятностей и некоторых других, в которых изучаемый объект носит дискретный характер.
Элементы дискретного анализа возникли в глубокой древности и, развиваясь параллельно с другими разделами математики, в значительной мере являлись их составной частью. Типичными для того периода были задачи, связанные со свойствами целых чисел, приведшие затем к созданию теории чисел. Позже, в основном в связи с игровыми задачами, появились элементы комбинаторного анализа и дискретной теории вероятностей, а в связи с общими проблемами теории чисел, алгебры и геометрии возникли важнейшие понятия алгебры, такие как группа, поле, кольцо и другие, определившие развитие и содержание алгебры на много лет вперед и имевшие по существу дискретную природу. Стремление к строгости математических рассуждений и анализ рабочего инструмента математики – логики – привели к выделению ещё одного важного раздела математики – математической логики. Однако наибольшего развития дискретный анализ достиг в связи с появлением кибернетики и её теоретической части – математической кибернетики. Математическая кибернетика, непосредственно изучающая с позиций математики самые разнообразные проблемы, которые ставит перед кибернетикой практика, является важным поставщиком идей и задач для дискретного анализа, вызывая в нём целые новые направления. Так, прикладные вопросы, требующие большой числовой обработки, стимулировали появление сильных численных методов решения задач, оформившихся затем в вычислительную математику, а анализ понятий вычислимости и алгоритма привёл к появлению важного раздела математической логики – теории алгоритмов. Растущий поток информации и связанные с ним задачи хранения, обработки и передачи информации привели к возникновению теории кодирования; экономические задачи, задачи электротехники, равно как и внутренние задачи математики, потребовали разработки теории графов; задачи конструирования и описания работы сложных управляющих систем привели к теории функциональных систем и т. д. В то же время математическая кибернетика использует результаты дискретного анализа при решении своих задач.
Наряду с отмеченными дискретный анализ обладает рядом и других особенностей. Так, вместе с задачами типа существования, имеющими общематематический характер, важное место в дискретном анализе занимают задачи, связанные с алгоритмической разрешимостью и построением конкретных решающих алгоритмов, что характерно именно для дискретного анализа. Особенностью дискретного анализа является и то, что он по существу первым столкнулся с необходимостью глубокого исследования т. н. дискретных многоэкстремальных задач, часто возникающих в математической кибернетике. Соответствующие методы классической математики для поиска экстремумов, существенно использующие гладкость функций, в этих случаях оказываются малоэффективными. Типичными задачами такого рода в дискретном анализе являются, например, задачи об отыскании в некотором смысле оптимальных стратегий в шахматной партии при ограниченном числе ходов, а также важный вопрос математической кибернетики о построении минимальных дизъюнктивных нормальных форм для булевых функций – т. н. проблема минимизации булевых функций. Особенностью дискретного анализа, связанной уже с задачами для конечных структур, является и то, что для многих из этих задач, как правило, существует алгоритм решения, в то время как в классической математике полное решение задачи часто возможно лишь при весьма жёстких ограничениях. Примером такого алгоритма может служить алгоритм просмотра всех возможных вариантов, т. е. алгоритм типа «полного перебора». К числу задач указанного вида можно отнести, например, упомянутые задачи о стратегиях в шахматной партии, о минимизации булевых функций и др. Вместе с тем решения типа «полного перебора» очень трудоёмки и практически малоприемлемы, в связи с чем возникает ряд новых задач, связанных с условиями, ограничивающими перебор и приводящими к сведению индивидуальных задач, характеризующихся конкретными значениями параметров, к массовой проблеме, характеризующейся бесконечным множеством значений параметров; возникают задачи наложения ограничений на средства решения, естественных для этого класса задач, и др. Постановка такого рода вопросов и разработка методик осуществляются на конкретных моделях, доставляемых различными разделами математики, например, на моделях минимизации булевых функций и синтеза управляющих систем из математической кибернетики.