Абстрактная машина

редактировать

Абстрактная машина, также называемая абстрактным компьютером, представляет собой теоретическую модель вычислительного устройства . er аппаратное или программное обеспечение, используемое в теории автоматов. Абстракция вычислительных процессов используется в дисциплинах информатика и компьютерная инженерия и обычно предполагает парадигму дискретного времени .

Содержание

  • 1 Информация
  • 2 См. Также
  • 3 Ссылки
  • 4 Дополнительная литература

Информация

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

Абстрактные типы данных могут быть указаны в терминах их операционной семантики на абстрактной машине. Например, стек может быть определен в терминах операций на абстрактной машине с массивом памяти. Используя абстрактные машины, можно вычислить количество ресурсов (время, память и т. Д.), Необходимых для выполнения конкретной операции, без необходимости конструирования физической системы.

Более сложные определения создают абстрактные машины с полные наборы команд , регистры и модели памяти. Одной из популярных моделей, более похожих на настоящие современные машины, является модель RAM, которая позволяет произвольный доступ к индексированным ячейкам памяти. По мере роста разницы в производительности между разными уровнями кэш-памяти все большее значение приобретают модели, чувствительные к кеш-памяти, такие как модель внешней памяти и модель без учета кеша.

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

См. Также

Ссылки

Дополнительная литература

  • Питер ван Эмде Боас, Machine Models and Simulations, стр. 3–66, появляется в:
Ян ван Леувен, изд. "Справочник по теоретической информатике. Том A: Алгоритмы и сложность, MIT PRESS / Elsevier, 1990. ISBN 0-444-88071-2 (том A). QA 76.H279 1990.
Последняя правка сделана 2021-06-08 19:46:48
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте