Сложность РАМ-программ

 

4.1. Блок-схема алгоритма решения задачи

 

 

4.2. Распределение памяти для РАМ и РАМ-программа (с комментариями)

 

Распределение памяти:

 

 

РАМ-программа:

 

1. LOAD =0 \\Присваиваем Sum=0

2. STORE 3

3. READ 1 \\Читаем S

4. ADD =1 \\Избавляемся от деления на ноль в сравнении

5. STORE 1

6. READ 2 \\Читаем N (оно же будет счётчиком)

\\Начинается цикл из N итераций

7. READ 4 \\Читаем следующий элемент

8. DIV 1 \\Проверяем условие a<S. Для этого выясняем, не равно ли нулю

9. JZERO 13 \\Если , то пропускаем часть повышения значения Sum

10. LOAD 3 \\Повышаем значение Sum – загружаем Sum в сумматор

11. ADD 4 \\Прибавляем a к Sum

12. STORE 3 \\Обновляем значении Sum

13. LOAD 2 \\Декрементируем счётчик – загружаем N в сумматор

14. SUB =1 \\Уменьшаем значение N

15. JZERO 18 \\Если счётчик обнулён – выходим из цикла

16. STORE 2 \\Иначе обновляем значение N

17. JUMP 4 \\Переходим к началу цикла

\\Оканчивается описание цикла

18. WRITE 3 \\Выводим результат на экран

19. HALT \\Завершаем программу

 

4.3. Оценка сложности РАМ (с объяснениями)

 

Количество занимаемой программой памяти всегда одинаково – 4 ячейки.

Выделим три части программы – до цикла, цикл (с 7 по 17 команду) и после цикла. Первая и последняя часть содержат в себе 8 команд.

Рассмотрим цикл. На всех итерациях, кроме последней, выполняются все 11 команд цикла. На последней итерации выполнение цикла прерывается на команде 15 (выполняются только 9). Всего цикл, очевидно, имеет N операций.

Соответственно, асимптотика времени работы:

 

Выводы: изучены вычислительные модели машины Тьюринга, рекурсивных функций и машины с произвольным доступом (Random Access Machine), были получены навыки построения алгоритмов на машине Тьюринга, доказательства рекурсивных функций и вычисления сложности RAM-программ.