RAM-машина
Цю статтю потрібно повністю переписати відповідно до стандартів якості Вікіпедії. Ви можете допомогти, переробивши її. Можливо, сторінка обговорення містить зауваження щодо потрібних змін. (грудень 2019) |
Ця стаття не містить посилань на джерела. Ви можете допомогти поліпшити цю статтю, додавши посилання на надійні (авторитетні) джерела. Матеріал без джерел може бути піддано сумніву та вилучено. (грудень 2019) |
Машина з довільним доступом до пам'яті (рівнодоступна адресна машина, скорочено РАМ-машина) — модель машини з одним суматором, команди програми не можуть змінювати самі себе. Служить теоретичною моделлю, зокрема, для аналізу алгоритмів.[1]
Структура
РАМ-машина складається з вхідної стрічки, з якої вона може лише зчитувати, та вихідної стрічки, на яку вона може лише записувати, та пам'яті.
Вхідна стрічка складається з послідовності комірок, в яких записані цілі числа (можливо від'ємні). Щоразу, коли машина зчитує число з вхідної стрічки, зчитуюча голівка пересувається на наступну комірку вправо.
На вихідну стрічку машина може лише записувати; її розбито на комірки, які спочатку порожні. При виконанні команди запису в комірку, на яку вказує записуюча голівка, зберігається ціле число, а голівка пересувається на наступну комірку вправо. Записане вихідне число змінити вже неможливо.
Пам'ять складається з послідовності регістрів r0, r1, …, ri, …, кожен з яких може зберігати довільне ціле число.
Програма для RAM-машини зберігається не в її пам'яті. Тому припускають, що програма не здатна змінювати сама себе. Програма складається з послідовності (можливо) помічених команд. Перелік команд залежить від постановки задачі, але схожий на типову мову асемблера.
Обчислення здійснюють в першому регістрі — r0, який називають суматором. Кожна команда складається з двох частин: коду операції та адреси.
Див. також
Примітки
- ↑ Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 2.2 Аналіз алгоритмів. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.
Література
- Альфред Ахо; Джон Гопкрофт; Джеффрі Ульман (1974). 1. The Design and Analysis of Computer Algorithms (англ.). Addison-Wesley.
![]() | Це незавершена стаття про інформаційні технології. Ви можете допомогти проєкту, виправивши або дописавши її. |