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

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

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

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

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

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

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

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

	Copyright © 1999-2023 Oval.ru, All Rights Reserved.