Головная страница ИПМ Библиотеки, издания  •  Поиск публикаций  English 
Публикация

Статья в сборнике "Математические вопросы кибернетики" №7, Москва, 1998
Авторы: Подловченко Р.И.
От схем Янова к теории моделей программ
Аннотация:
1958 году работами Ляпунова А.А. и Янова Ю.И. заложено новое направление научных исследований - теория схем программ. Первыми изучаемыми в ней объектами стали схемы программ, именуемые в дальнейшем схемами Янова. В последующие годы были предложены и развиты разнообразные варианты моделей программ. В их числе - модели рекурсивных программ. Они служат подходящей математической абстракцией для изучения последовательных программ, снабженных аппаратом процедур. В этой статье определены основные понятия теории моделей рекурсивных программ и представлены некоторые результаты изучения основных задач этой теории. Показано, что подкласс гладких моделей рекурсивных программ с отношением аппроксимации образует верхнюю полурешетку. Затем продемонстрированы некоторые модели рекурсивных программ как с разрешимой, так и с неразрешимой проблемой эквивалентности. Проведен отбор классов моделей рекурсивных программ, наиболее перспективных для построения в них алгоритмов проверки эквивалентности. Описана методика поиска алгоритмов, разрешающих проблему эквивалентности в моделях рекурсивных программ. Также описаны правила (аксиомы) эквивалентных преобразований рекурсивных программ и показано, что в некоторых моделях существуют полные системы эквивалентных преобразований.
Ключевые слова:
модель программ, рекурсивная программа, отношение аппроксимации, проблема эквивалентности, разрешающая процедура, эквивалентное преобразование
Язык публикации: русский, страниц: 22 (с. 281-302)
Направление исследований:
Математические вопросы и теория численных методов
Полный текст: Сведения об авторах:
  • Подловченко Римма Ивановна,  МГУ им. М.В. Ломоносова, Научно-исследовательский вычислительный центр