БСЭ БСЭ - Большая Советская Энциклопедия (КО)

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

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

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

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

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

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