Реальная оперативная память

Математическая модель компьютера

В вычислениях, особенно в вычислительной геометрии , реальная оперативная память ( машина с произвольным доступом ) — это математическая модель компьютера, которая может выполнять вычисления с точными действительными числами вместо двоичных чисел с фиксированной или плавающей запятой , используемых большинством реальных компьютеров. Настоящая RAM была сформулирована Майклом Яном Шамосом в его докторской диссертации 1978 года. диссертация. ^[1]

Модель

Часть «RAM» в названии реальной модели RAM означает « машина с произвольным доступом ». Это модель вычислений, напоминающая упрощенную версию стандартной компьютерной архитектуры. Он состоит из хранимой программы , блока памяти компьютера , состоящего из массива ячеек, и центрального процессора с ограниченным числом регистров . Каждая ячейка памяти или регистр может хранить действительное число. Под управлением программы реальная оперативная память может передавать действительные числа между памятью и регистрами, а также выполнять арифметические операции над значениями, хранящимися в регистрах.

Разрешенные операции обычно включают сложение, вычитание, умножение и деление, а также сравнение, но не модуль или округление до целых чисел. Причина, по которой следует избегать операций округления целых чисел и операций по модулю, заключается в том, что разрешение этих операций может дать реальному ОЗУ необоснованный объем вычислительной мощности, что позволит ему решать PSPACE-полные задачи за полиномиальное время. ^[2]

При анализе алгоритмов для реальной оперативной памяти обычно предполагается, что каждая разрешенная операция занимает постоянное время .

Выполнение

Были разработаны библиотеки программного обеспечения , такие как LEDA , которые позволяют программистам писать компьютерные программы, которые работают так, как если бы они работали в реальной оперативной памяти. Эти библиотеки представляют реальные значения, используя структуры данных , которые позволяют им выполнять арифметические операции и сравнения с теми же результатами, что и реальная ОЗУ. Например, в LEDA действительные числа представлены с использованием leda_realтипа данных, который поддерживает корни k -й степени для любого натурального числа k , рациональные операторы и операторы сравнения. ^[3] Временной анализ базового алгоритма реального ОЗУ с использованием этих реальных типов данных можно интерпретировать как подсчет количества вызовов библиотеки, необходимых для данного алгоритма. ^[4]

Сравнение с другими вычислительными моделями

• В модели машины Тьюринга базовая единица вычислений включает один бит. Следовательно, временная и пространственная сложность числовых алгоритмов зависит от количества битов, необходимых для представления чисел. Напротив, в модели Real RAM базовая единица вычислений включает в себя действительное число, независимо от того, сколько битов требуется для его представления. Это различие важно при анализе таких алгоритмов, как исключение Гаусса : этот алгоритм требует полиномиального числа арифметических операций над действительными числами, поэтому он является полиномиальным в модели Real RAM; однако числа, используемые в промежуточных вычислениях, могут (если реализованы наивно) расти экспоненциально, поэтому время их выполнения в модели машины Тьюринга является экспоненциальным. ^{[5] : Раздел 1.4.}
• Настоящее ОЗУ очень напоминает более позднюю машину Блюма-Шаба-Смейла . ^[6] Однако реальная оперативная память обычно используется для анализа конкретных алгоритмов в вычислительной геометрии , в то время как машина Блюма-Шуба-Смейла вместо этого формирует основу для расширения теории NP-полноты до вычислений с действительными числами.
• Альтернативой реальному ОЗУ является слово RAM , в котором входные данные задачи и значения, хранящиеся в памяти и регистрах, считаются целыми числами с фиксированным количеством бит. Модель словесного ОЗУ может выполнять некоторые операции быстрее, чем реальная ОЗУ; например, он позволяет использовать быстрые алгоритмы сортировки целых чисел , тогда как сортировка в реальной оперативной памяти должна выполняться с помощью более медленных алгоритмов сортировки сравнения . Однако некоторые задачи вычислительной геометрии имеют входные или выходные данные, которые невозможно точно представить с использованием целочисленных координат; см., например, конфигурацию Perles , расположение точек и отрезков линий, не имеющее представления в целочисленных координатах.

Рекомендации

1. Шамос, Майкл Ян (1978), Вычислительная геометрия , доктор философии. диссертация, Йельский университет.
2. Шёнхаге, Арнольд (1979), «О возможностях машин с произвольным доступом», Труды шестого международного коллоквиума по автоматам, языкам и программированию (ICALP '79) , Конспекты лекций по информатике , том. 71, Springer, стр. 520–529, номер документа : 10.1007/3-540-09510-1_42, ISBN. 978-3-540-09510-1, МР  0573259.
3. Мельхорн, Курт; Нэхер, Стефан (1999). Платформа комбинаторных и геометрических вычислений LEDA. Издательство Кембриджского университета . Проверено 12 ноября 2019 г. .
4. Мельхорн, Курт ; Ширра, Стефан (2001), «Точные вычисления с помощьюleda_real — теория и геометрические приложения» (PDF) , Символьные алгебраические методы и методы проверки (Dagstuhl, 1999) , Springer, стр. 163–172, doi : 10.1007/978-3- 7091-6280-4_16, ISBN 978-3-211-83593-7, МР  1832422.
5. Гретшель, М.; Ловас, Л.; Шрийвер, А. (1 июня 1981 г.). «Метод эллипсоидов и его последствия в комбинаторной оптимизации». Комбинаторика . 1 (2): 169–197. дои : 10.1007/BF02579273. ISSN  1439-6912. S2CID  43787103.
6. Блюм, Ленор ; Шуб, Майк ; Смейл, Стив (1989), «К теории вычислений и сложности над действительными числами: NP-полнота, рекурсивные функции и универсальные машины», Бюллетень Американского математического общества , 21 (1): 1–46, doi : 10.1090 /S0273-0979-1989-15750-9 , Збл  0681.03020.

Внешние ссылки

• Возможные ссылки на реальные машины произвольного доступа
• Геометрические вычисления: наука о том, как заставить геометрические алгоритмы работать