Схемы Янова: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Схемы Янова''' (''Yanov schemata'') - ''схемы программ'', которые были введены в литер...)
 
Нет описания правки
Строка 1: Строка 1:
'''Схемы Янова''' (''Yanov schemata'') -  
'''Схемы Янова''' (''[[Yanov schemata]]'') -  
''схемы программ'', которые
''[[схема программ|схемы программ]]'', которые
были введены в литературу А.А.Ляпуновым и Ю.И.Яновым в 1958 г.
были введены в литературу А.А.Ляпуновым и Ю.И.Яновым в 1958 г.
и направлены на разработку общей теории условий, управляющих
и направлены на разработку общей теории условий, управляющих
последовательностью выполнений операторов в программе.
последовательностью выполнений операторов в программе.


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


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


См. также ''Неинтерпретированные схемы, Стандартные схемы, Схемы Лаврова, Схема программ,
==См. также ==
Схема с косвенной адресацией.''
''[[Неинтерпретированные схемы]], [[Стандартные схемы]], [[Схемы Лаврова]], [[Схема программ]],
[[Схема с косвенной адресацией]].''
==Литература==
==Литература==
[Ершов/77],
[Ершов/77],


[Ершов/94]
[Ершов/94]

Версия от 12:27, 4 февраля 2010

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

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

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

См. также

Неинтерпретированные схемы, Стандартные схемы, Схемы Лаврова, Схема программ, Схема с косвенной адресацией.

Литература

[Ершов/77],

[Ершов/94]