Схемы Янова

Материал из WikiGrapp
Перейти к:навигация, поиск

Схемы Янова (Yanov schemata) — схемы программ, которые были введены в литературу А.А.Ляпуновым и Ю.И.Яновым в 1958 г. и направлены на разработку общей теории условий, управляющих последовательностью выполнений операторов в программе.

Yanov schemata.gif

В отличие от схемы Мартынюка Схемы Янова содержит помимо одной переменной (скажем, \,x), имеющейся в схеме Мартынюка, множество специальных логических переменных p_1,
p_2,\ldots,p_k, управляющих вычислениями, и состоит из преобразователей, каждый из которых помимо обязательного аргумента и необязательного результата x имеет произвольное подмножество логических переменных в качестве результатов, и распознавателей, каждый из которых имеет ровно две исходящие дуги и состоит из слова выбора, имеющего вид произвольной логической функции от переменных p_1, p_2,\ldots,p_k. Множество логических переменных, являющихся результатами оператора-преобразователя, называется его сдвигом. Дуги, исходящие из распознавателя, различаются и называются соответственно плюс-стрелкой и минус-стрелкой.

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

См. также

Литература

  • Ершов А.П. Введение в теоретическое программирование. Беседы о методе. — М.: Наука, 1977.
  • Ершов А.П. Избранные труды. — Новосибирск: Наука. Сиб. отд-ние, 1994.