Лекции - Теория алгоритмов
Подождите немного. Документ загружается.
Вставка подпрограммы
(продолжение-1)
► Однако в ходе работы основной программы Q возможно
следующее. Настал момент для старта подпрограммы
P, которой нужны аргументы x
1
, x
2
, ..., x
n
. В данный
момент аргументы хранятся в каких-то регистрах R
i1
,
... , R
in
, а не в регистрах R
1
, ... , R
n
, как нужно.
Поэтому перед применением подпрограммы P мы
должны извлечь аргументы из R
i1
, ... , R
in
и переслать
их в регистры R
1
, ... , R
n
такой пересылки аргументов
выполняется следующее действие.
► 1) Перед командами из P размещается набор команд
T(i
1
,1), ... ,T(i
n
,n).
Вставка подпрограммы
(продолжение-2)
► Пусть основная программа Q вызвала подпрограмму P и
в начало зарезервированных регистров R
1
, ... , R
n
скопированы числа x
1
, x
2
, ..., x
n
, с которыми начнет
работать подпрограмма P. Однако в регистрах R
n+1
, ... ,
R
может оставаться «мусор» - произвольные числа,
оставшиеся от предыдущей работы Q. По правилам
работы МНР в последующих регистрах R
n+1
, ... , R
k
должны быть только одни нули. Поэтому нужно
выполнить обнуление этих регистров от мусора,
которое осуществляется следующим способом.
► 2) Выполняется набор команд Z(n+1), ... , Z().
Вставка подпрограммы
(продолжение-3)
► После выполнения подпрограммы P результат
находится в регистре R
1
. Однако регистр R
1
нужен для последующих вычислений
программы Q. Поэтому из регистра R
1
результат
выполнения подпрограммы P нужно
пересылать для его последующего
использования на хранение в некоторый
рабочий регистр R
i
, где i>(P). Это можно
осуществить следующим способом.
► 3) Выполняется команда переадресации T(1,i).
Вставка подпрограммы
(продолжение-4)
► Следующие действия назовем вставкой подпрограммы.
► 1) Распределение памяти. Вычисляется число = (P) и выделяется
память R
1
, … R
, достаточная для работы подпрограммы P. Задается
регистр R
i
, где i>, для хранения результата работы подпрограммы.
► 2) Извлечение аргументов. Для этого записываются следующие
команды: T(i
1
,1), ... ,T(i
n
,n). Для передачи аргументов из места их
хранения в регистры R
1
, ... , R
n
.
► 3) Очистка регистров. Для этого записываются следующие команды:
Z(n+1), … , Z ().
► 4) Вставка команд подпрограммы P.
► 5) Пересылка результата на хранение. Добавляется команда T(1,i).
Вставка подпрограммы
(окончание)
► В итоге в основной программе получается следующий фрагмент
T(i
1
,1)
...
T(i
n
,n)
Z(n+1)
...
Z()
P
T(1,i)
► Вставку данного фрагмента в основную программу обозначаем
через P[i
1
, ... , i
n
i].
Лекция 7. Вычислимость частично
рекурсивных функций на МНР
► Если функция f вычислима на некоторой
машине с неограниченными регистрами, то
говорим кратко «Функция f МНР вычислима».
► В предыдущей лекции установлена МНР
вычислимость простейших функций. Теперь
проверим, что применение операторов
суперпозиции, примитивной рекурсии и
минимизации к МНР вычислимым функциям
вырабатывает МНР вычислимые функции. В
результате получим основной результат -
► все частично рекурсивные функции вычислимы
на МНР.
Оператор суперпозиции.
► Теорема 1. Пусть функция f получена из
функций h, g
1
, g
2
, … , g
m
с помощью
оператора суперпозиции. Если функции h, g
1
,
g
2
, … , g
m
МНР вычислимы, то и функция f
также МНР вычислима.
► Доказательство. По условию функции h, g
1
, g
2
,
… , g
m
МНР вычислимы. Пусть H , G
1
, G
2
, … , G
m
- программы, вычисляющие эти функции.
Оператор суперпозиции
(Продолжение-1. Алгоритм вычисления)
► Процесс вычисления функции f(x
1
, x
2
, ... , x
n
) состоит в
следующем.
► Последовательно вычисляем числа
► y
1
= g
1
(x
1
, x
2
, ... , x
n
),
► y
2
= g
2
(x
1
, x
2
, ... , x
n
),
► ................................
► y
m
= g
m
(x
1
,x
2
, ... , x
n
)
► с помощью соответствующих программ G
1
, G
2
, … , G
m
.
► Затем вычисляем число h(y
1
, y
2
, ... , y
m
) с помощью
программы H. Получаем f(x
1
,x
2
, ... , x
n
).
Оператор суперпозиции
(Продолжение-2. Программа вычисления)
►T(1, +1)
►..............
►T(n, +n)
►G
1
[+1, +2, ... , +n +n+1]
►...............
►G
m
[+1, +2, ... , +n +n+m]
►H[+n+1, +n+2, ... , +n+m 1]
Оператор суперпозиции
(Продолжение-3. Блок-схема.)