ДИСКРЕТНЫЙ АНАЛИЗ
— раздел математики, занимающийся изучением свойств структур финитного (конечного) характера, которые возникают как внутри математики, так и в ее приложениях. К числу таких конечных структур могут быть отнесены, например, конечные группы, конечные графы, а также некоторые математические модели преобразователей информации, такие как автоматы конечные, Тьюринга машины, и т. п. Иногда допускают расширение предмета Д. а. до произвольных дискретных структур и приходят к дискретной математике, отождествляя ее с Д. а. К числу таких структур могут быть отнесены некоторые алгебр, системы, бесконечные графы, некоторые виды вычисл. сред такие, как клеточные автоматы и т. д. В качестве синонима понятий Д. а. и дискретной математики иногда употребляют термин «конечная математика». Ниже термин Д. а. понимается в широком смысле, включающем дискретную математику.
В отличие от Д. а. классическая математика, в основном, занимается изучением свойств объектов непрерывного характера. Использование классической или дискретной математики как аппаратов исследования связано с задачами, которые ставит перед собой исследователь, и с тем, какую модель изучаемого явления он рассматривает — дискретную или непрерывную. Так, например, при нахождении массы радиоактивного вещества в данный момент с определенной точностью можно считать, что процесс изменения массы при радиоактивном распаде носит непрерывный характер, и в то же время ясно, что на самом деле этот процесс дискретен. Само деление математики на классическую и дискретную в значительной мере условно, поскольку, например, с одной стороны, происходит активная циркуляция идей и методов между ними, а с другой стороны, часто возникает необходимость исследования моделей, обладающих как дискретными, так и непрерывными свойствами одновременно. Следует отметить также, что в математике существуют направления, использующие средства дискретной математики для изучения непрерывных моделей и, наоборот, часто средства и постановки задач классического анализа используются при исследовании дискретных структур. Это указывает на известное слияние рассматриваемых областей.
Специфика методов и задач Д. а. обусловлена, в первую очередь, необходимостью отказа от основополагающих понятий классической математики — предела и непрерывности - и в связи с этим тем, что для многих задач Д. а. сильные средства классической математики оказываются, как правило, малоприемлемыми. К подразделам Д. а. относят комбинаторный анализ, графов теорию, кодирования теорию, теорию функциональных систем и некоторые
другие. Часто под термином Д. а., предполагая, что его предмет исчерпывается конечными структурами, понимают именно совокупность перечисленных дисциплин. С точки зрения расширения понимания этого предмета к Д. а. можно также отнести как целые разделы математики, например, логику математическую, так и части таких разделов, как теория чисел, алгебра, вычислительная математика, вероятностей теория, и некоторые другие, в которых изучаемый объект носит дискретный характер.
Элементы Д. а. возникли в глубокой древности и, развиваясь параллельно с другими разделами математики, в значительной мере являлись их составной частью. Типичными для того периода являлись задачи, связанные со свойствами целых чисел и приведшие затем к созданию теории чисел. К их числу могут быть отнесены задачи отыскания алгоритмов сложения и умножения натуральных чисел у древних египтян (2 тысячелетие до н. э.), задачи о суммировании и о делимости натуральных чисел в пифагорийской школе (5—4 в. до н. э.) и т. п. Позже, в основном, в связи с игровыми задачами, появились элементы комбинаторного анализа и дискретной теории вероятностей, а в связи с общими проблемами теории чисел, алгебры и геометрии (18—19 в.) возникли важнейшие понятия алгебры, такие как группа, поле, кольцо и др., определившие развитие и содержание алгебры на много лет вперед и имевшие, по существу, дискретную природу. Стремление к строгости матем. рассуждений и анализ рабочего инструмента математики — логики — привели к выделению еще одного важного раздела математики — математической логики (19 в.). Однако наибольшего развития Д. а. достиг в связи с запросами практики, приведшими к появлению новой науки — кибернетики и ее теоретической части — теор. кибернетики (20 в.). Теор. кибернетика, непосредственно изучающая с позиций математики самые разнообразные проблемы, которые ставит перед кибернетикой практическая деятельность человека, является мощным поставщиком идей и задач для Д. а. Так, прикладные вопросы, требующие большой числовой обработки, стимулировали появление сильных численных методов решения задач, оформившихся затем в вычисл. математику, а анализ понятия «вычислимость» и «алгоритм» привели к появлению важного раздела математической логики — алгоритмов теории. Растущий поток информации и связанные с ним задачи хранения, обработки и передачи ее привели к возникновению теории кодирования; эконом, задачи, задачи электротехники, равно как и внутренние задачи математики, потребовали разработки теории графов; задачи конструирования и описания работы сложных управляющих систем привели к теории функциональных систем. Теор. кибернетика широко использует результаты Д. а. при решении задач.
Наряду с уже отмеченными, Д. а. имеет еще ряд особенностей. Так, вместе с задачами типа существования, имеющими общематематический характер, важное место в Д. а. занимают задачи типа алгоритмической разрешимости и построения конкретных решающих алгоритмов. Другой особенностью Д. а. является то, что он, по существу, первым столкнулся с необходимостью глубокого исследования т. н. дискретных многоэкстремальных задач, особенно часто возникающих в теор. кибернетике. Соответствующие методы классической математики для поиска экстремумов, существенно использующие определенную гладкость ф-ций, в этих случаях окааываются мало эффективными. Типичными задачами такого рода в Д. а. являются, например, задачи об отыскании в некотором смысле стратегий оптимальных в шахматной партии при ограниченном числе ходов, а также важный вопрос матем. кибернетики о построении дизъюнктивных нормальных форм минимальных для булевых функций, т. е. так называемая проблема минимизации булевых функций (см. Алгебра логики). Особенностью Д. а., связанной уже с задачами для конечных структур, является и то, что для многих из этих задач, как правило, существует алгоритм решения, в то время как в классической математике полное решение задачи часто возможно лишь при весьма жестких ограничениях. Примером такого алгоритма может служить алгоритм просмотра всех возможных вариантов, т. е. алгоритм типа «полного перебора». К числу задач указанного вида могут быть отнесены, например, упомянутые задачи о стратегиях в шахматной партии, о минимизации булевых функций и др. Однако методы решеиия типа «полного перебора» очень трудоемки и практически малоприемлемы, в связи с чем возникает ряд новых задач, связанных с условиями, ограничивающими перебор и приводящими к сведению индивидуальных задач, характеризующихся конкретными значениями параметров, к массовой проблеме, характеризующейся бесконечным множеством значений параметров; возникают задачи в наложении ограничений, естественных для этого класса задач, на средства решения и т. п. Постановка такого рода вопросов и разработка методик осуществляется на конкретных моделях, доставляемых различными разделами математики. К их числу относятся, например, модели минимизации булевых функций и синтеза управляющих систем из теор. кибернетики.
Лит. Яблонский С. В. Обзор некоторых результатов в области дискретной математики. «Информационные материалы Научного совета по комплексной проблеме «Кибернетика» АН СССР», 1970, № 5; Дискретный анализ, № 1—22. Новосибирск, 1963— 73; Проблемы кибернетики, J4S 1-26. М., 1958—73; Кемени Дж., Снелл Дж., Томпсон Дж. Введение в конечную математику. Пер. с англ. М., 1965. В. Б. Кудрявцев.
