4194
правки
Эквивалентность программ: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Эквивалентность программ''' (''[[Program equivalence]]'') - | '''Эквивалентность программ''' (''[[Program equivalence]]'') - | ||
существенная часть формализма понятия | существенная часть формализма понятия программы. | ||
В том случае, когда программа реализует некоторую функцию | В том случае, когда программа реализует некоторую функцию | ||
(а это, как правило, так), имеет место естественное и | (а это, как правило, так), имеет место естественное и | ||
| Строка 25: | Строка 25: | ||
Среди основных типов историй рассматриваются следующие: | Среди основных типов историй рассматриваются следующие: | ||
''Операционная история программы''. Под этим | ''[[Операционная история программы]]''. Под этим | ||
подразумевается запись последовательности преобразователей, | подразумевается запись последовательности преобразователей, | ||
выполняемых при работе программы. | выполняемых при работе программы. | ||
''Операционно-логическая история программы'' дополнительно | ''[[Операционно-логическая история программы]]'' дополнительно | ||
указывает на все распознаватели, пройденные при работе | указывает на все распознаватели, пройденные при работе | ||
программы. | программы. | ||
''Информационный граф реализации программы''. [[Вершина|Вершинами]] | ''[[Информационный граф реализации программы]]''. [[Вершина|Вершинами]] | ||
[[граф|графа]] являются преобразователи. Вершина <math>S_1</math> соединяется с | [[граф|графа]] являются преобразователи. Вершина <math>S_1</math> соединяется с | ||
вершиной <math>S_2</math>, если <math>S_2</math> использует результат <math>S_1</math> в | вершиной <math>S_2</math>, если <math>S_2</math> использует результат <math>S_1</math> в | ||
качестве аргумента. | качестве аргумента. | ||
''Информационно-логический граф реализации программы''. К | ''[[Информационно-логический граф реализации программы]]''. К | ||
информационному графу добавляются вершины проходимых | информационному графу добавляются вершины проходимых | ||
распознавателей. Их аргументы соединяются с соответствующими | распознавателей. Их аргументы соединяются с соответствующими | ||
результатами информационными связями. Кроме того, каждый | результатами информационными связями. Кроме того, каждый | ||
распознаватель соединяется связью особого рода с каждой | [[распознаватель]] соединяется связью особого рода с каждой | ||
вершиной информационно-логического графа, прохождение или | вершиной информационно-логического графа, прохождение или | ||
непрохождение которой непосредственно зависит от выполнения | непрохождение которой непосредственно зависит от выполнения | ||
данного распознавателя. | данного распознавателя. | ||
''Термальное значение результирующих переменных''. | ''[[Термальное значение результирующих переменных]]''. | ||
Очевидно, что информационный граф является ациклическим. Это | Очевидно, что информационный граф является ациклическим. Это | ||
позволяет для каждого аргумента <math>a</math> любой вершины <math>S</math> графа | позволяет для каждого аргумента <math>a</math> любой вершины <math>S</math> графа | ||
построить некоторое дерево, которое называется | построить некоторое [[дерево]], которое называется | ||
''термальным значением аргумента'' <math>a</math> и включает в себя все | ''термальным значением аргумента'' <math>a</math> и включает в себя все | ||
вершины, достижимые из <math>a</math> при движении навстречу дугам | вершины, достижимые из <math>a</math> при движении навстречу [[дуга|дугам]] | ||
информационнных связей. Продвигаясь "вниз" по | информационнных связей. Продвигаясь "вниз" по | ||
информационному графу, мы получим в конце концов термальные | информационному графу, мы получим в конце концов термальные | ||
значения результативных переменных. | значения результативных переменных. | ||
''Логико-термальная история'' реализации получается добавлением | ''[[Логико-термальная история]]'' реализации получается добавлением | ||
к термальному значению результативных переменных цепочки | к термальному значению результативных переменных [[цепочка|цепочки]] | ||
пройденных распознавателей вместе с термальными значениями | пройденных распознавателей вместе с термальными значениями | ||
их аргументов. Логико-термальная история строится по | их аргументов. Логико-термальная история строится по | ||
информационно-логическому графу. | информационно-логическому графу. | ||
См. также ''Неинтерпретированные схемы, Стандартные схемы, Схема программ, Схема с косвенной адресацией, Схемы Лаврова, Схемы Мартынюка, Схемы Янова.'' | ==См. также == | ||
''[[Неинтерпретированные схемы]], [[Стандартные схемы]], [[Схема программ]], [[Схема с косвенной адресацией]], [[Схемы Лаврова]], [[Схемы Мартынюка]], [[Схемы Янова]].'' | |||
==Литература== | ==Литература== | ||
[Ершов/77], | [Ершов/77], | ||
[Ершов/94] | [Ершов/94] | ||