Cтраница 1
Теория неподвижной точки первоначально создавалась в теории рекурсии - подраздела математической логики - как средство объяснения рекурсивных функций. Позднее она была использована в ряде других областей математики - таких, как алгебра и функциональный анализ. В информатике эта теория может с успехом применяться, когда требуется формальное описание семантики рекурсивных программ или систем. В частности, денотационная семантика основана на теории неподвижной точки. [1]
В теории неподвижной точки индекс определен для совершенно общих семейств пространств. Для совпадения, однако, необходимо накладывать больше ограничений. В 1993 г. Добренко и Ежерски [44] определили индекс в случае, когда многообразия не обязательно ориентируемы. Они адаптировали метод Хопфа, применявшийся им в случае неподвижных точек. Более точно, работая в дифференцируемой категории, первоначально они деформируют отображения таким образом, чтобы точки совпадения стали регулярными. Тогда они определяют индекс изолированной точки совпадения как элемент Z или Z2, принимая во внимание ориентирующую систему многообразия, заданную фундаментальной группой. [2]
После краткого описания основных элементов теории неподвижной точки в разд. Дейталоге может быть определена как наименьшая неподвижная точка трансформации Тр. Алгоритм INFER приведенный в разд. Вместе с тем возможно определение более простой трансформации Тр, которая приводит к несколько более эффективному алгоритму. Дальнейшая оптимизация этого алгоритма ( его алгебраической версии) обсуждается в разд. [3]
Ниже мы представим сначала элементарные результаты теории неподвижной точки в весьма общем виде. Затем покажем, как эти результаты связаны с Дейталогом. [4]
Нами введены все понятия и результаты теории неподвижной точки, необходимые для определения семантики программ на Дейталоге в терминах наименьших неподвижных точек. Заметим, что теория неподвижной точки может быть использована для определения семантики большинства языков, в которых используется рекурсия. [5]
Несмотря на то, что он интересовался теорией неподвижной точки, применявшиеся им методы, обусловленные знанием им алгебраической геометрии, естественно приводили к случаю совпадения. [6]
Наиболее хорошо разработана и наиболее богата содержательными фактами теория неподвижных точек вполне непрерывных операторов. [7]
Для исследования уравнения ( 23) уже полностью применима теория неподвижных точек вполне непрерывных операторов. [8]
Одной из главных особенностей языков логического программирования является их способность изображать рекурсию. Следовательно, теория неподвижной точки пригодна для определения семантики этих языков. Этот вид семантики, называемой обычно семантикой неподвижной точки, имеет ряд достоинств, таких, как непроцедурность, совмещаемая со способностью точного изображения вычислений. [9]
Нами введены все понятия и результаты теории неподвижной точки, необходимые для определения семантики программ на Дейталоге в терминах наименьших неподвижных точек. Заметим, что теория неподвижной точки может быть использована для определения семантики большинства языков, в которых используется рекурсия. [10]
В этой главе рассмотрены различные парадигмы вычисления программ на Дейталоге, в том числе алгоритм INFER, представляющий собой простейшую стратегию восходящего вычисления. Представлены основные результаты теории неподвижной точки и показано, что выполняемые алгоритмом INFER вычисления соответствуют вычислению наименьшей неподвижной точки. Описан класс нисходящих методов, использующих принцип обратного вывода. Принципы и алгоритмы формулируются независимо от вопросов поиска данных и обращения к базе данных. Важно вместе с тем понимать, как эти методы могут быть применены, когда факты EDB хранятся в массовой памяти. В этом случае необходимы специальные методы для минимизации числа обращений к внешней памяти. Эти вопросы обсуждаются в гл. [11]
Согласно [83] все группы Ли, более общо, все Jf-пространства являются пространствами Янга. В теории совпадения может быть использована та же техника, что и в теории неподвижной точки, и аналогичные результаты справедливы для замкнутых ориентируемых многообразий одинаковой размерности. [12]
Тогда нахождение решения x g ( t) уравнения (19.1), удовлетворяющего начальному условию g ( 0) xa, равносильно нахождению функции g, для которой g Tg. Идея, лежащая в основе метода решения, совершенно естественна с точки зрения теории неподвижных точек. Если такой предел g существует, то он будет пределом и для Tv 1gll, и, таким образом, g - T imTvga Tg. В учебниках по дифференциальным уравнениям этот метод называется методом последовательных приближений Пикара. [13]
Например, хорошо изучены рекурсивные схемы программ, корректность вычислений в функциональных системах ( теория неподвижной точки), рекурсивное программирование ( язык ЛИСП, функциональные системы Бэкуса и им подобные), трансляция языков программирования и ряд других задач. Однако возникающие при этом подходы во многом не связаны между собой, ориентированы на решение хотя и важных, но частных проблем, и носят специальный характер. [14]
Например, введение в модель алгоритма в качестве переменных величин функций ( что является неизбежным в языках высокого уровня) привело к установлению различия между алгоритмическими системами на уровне функционалов На этой основе возникла теория схем программ, теория неподвижной точки, математическая или денотационная семантика и ряд других теорий. [15]