Категория:Теория схем программ

Понятие схемы программ принадлежит А.А. Ляпунову и было введено им в 1953 г., исходя из общей концепции необходимости и возможности формализации процесса программирования. Первыми "заказчиками" математических моделей программ стали разработчики трансляторов, которые в конце 50-х и начале 60-х годов столкнулись с необходимостью обоснования алгоритмов оптимизирующей трансляции и доказательства их корректности. В настоящее время теория схем программ - это широко разветвленная область исследования, содержащая много фундаментальных результатов не только по операторным моделям последовательных программ, но и по рекурсивным схемам и схемам параллельных программ.

Первым всесторонне исследованным классом схем программ были схемы Янова. В работах Ю.И. Янова впервые выделены и формализованы основные компоненты теории схем и, в первую очередь, - понятие схемы программ и отношение эквивалентности. Яновым были найдены алгоритмы распознавания эквивалентности в этом классе схем, построена полная система преобразований, позволяющая трансформировать друг в друга любую пару эквивалентных схем. Схемы Янова активно изучались в различных модификациях и обобщениях. В частности, Ратледж упростил доказательство разрешимости эквивалентности, моделируя простые схемы Янова конечными автоматами, дал независимое определение функциональной эквивалентности схем Янова и доказал равнообъемность функциональной и формальной эквивалентностей.