Большая советсткая энциклопедия Конечная математика

Конечная математика

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

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

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

Элементы К. м. возникли в глубокой древности и, развиваясь параллельно с другими разделами математики, в значительной мере являлись их составной частью. Типичными для того периода были задачи, связанные со свойствами целых чисел и приведшие затем к созданию теории чисел. К их числу могут быть отнесены отыскания алгоритмов сложения и умножения натуральных чисел у древних египтян (2-е тыс. до н. э.), задачи о суммировании и вопросы делимости натуральных чисел в пифагорийской школе (6 в. до н. э.) и т. п. Позже (17—18 вв.), в основном в связи с игровыми задачами, появились элементы комбинаторного анализа и дискретной теории вероятностей (Б. Паскаль, П. Ферма и др.), а в связи с общими проблемами теории чисел, алгебры и геометрии (18—19 вв.) возникли важнейшие понятия алгебры, такие как группа, поле, кольцо и др. (Ж. Лагранж, Э. Галуа и др.), определившие развитие и содержание алгебры на много лет вперёд и имевшие по существу дискретную природу. Стремление к строгости математических рассуждений и анализ рабочего инструмента математики — логики привели к выделению ещё одного важного раздела математики — математической логики (19— 20 вв.). Однако наибольшего развития К. м. достигла в связи с запросами практики, приведшими к появлению новой науки — кибернетики и её теоретической части—математической кибернетики (20 в.). Математическая кибернетика, непосредственно изучающая с позиций математики самые разнообразные проблемы, которые ставит перед кибернетикой практическая деятельность человека, является мощным поставщиком идей и задач для К. м., вызывая к жизни целые новые направления в К. м. Так, прикладные вопросы, требующие большой числовой обработки, стимулировали появление сильных численных методов решения задач, оформившихся затем в вычислительную математику, а анализ понятий "вычислимость" и "алгоритм" привёл к созданию важного раздела математической логики — теории алгоритмов. Растущий поток информации и связанные с ним задачи хранения, обработки и передачи информации привели к возникновению теории кодирования; экономические задачи, задачи электротехники, равно как и внутренние задачи математики, потребовали разработки теории графов; задачи конструирования и описания работы сложных управляющих систем составили теорию функциональных систем и т. д. В то же время математическая кибернетика широко использует результаты К. м. при решении своих задач.

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

Лит.: Яблонский С. В., Обзор некоторых результатов в области дискретной математики, "Информационные материалы", 1970, №5(42), с. 5—15; Кемени Дж., Снелл Дж., Томпсон Дж., Введение в конечную математику, пер. с англ., М., 1965; Дискретный анализ. Сб. трудов (Новосиб., 1963).

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