Вычислительная машина с хранением программ в памяти с произвольной выборкой

Развитием формализма вычислительной машины с произвольной выборкой является вычислительная машина с хранением программ в памяти с произвольной выборкой (Random Access Stored Program Machine, RASPM), отличие которой состоит только в том, что программа сохраняется в памяти, а значит может изменять сама себя в процессе выполнения.

Набор инструкций для RASPM в общем случае может не отличаться от набора инструкций RAM. Впрочем, некоторые инструкции могут быть упрощены. Так, вместо непрямой адресации можно использовать возможность модификации инструкций программы для получения того же эффекта.

Известно, что имеют место две теоремы:

Теорема 2.1. Если стоимость инструкции является величиной постоянной или находится в логарифмической зависимости от длины операнда, то для любой программы RAM, имеющей сложность T(n), найдется константа k и эквивалентная программа RASPM, сложность которой будет не больше kT(n).

Теорема 2.2. Если стоимость инструкции является величиной постоянной или находится в логарифмической зависимости от длины операнда, то для любой программы RASPM, имеющей сложность T(n), найдется константа k и эквивалентная программа RAM, сложность которой будет не больше kT(n).








Дата добавления: 2015-06-12; просмотров: 555;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.004 сек.