Модель расчета - Model of computation

В информатике , а точнее в теории вычислимости и теории сложности вычислений , модель вычислений - это модель, которая описывает, как вычисляется вывод математической функции при вводе. Модель описывает, как организованы единицы вычислений, памяти и связи. Вычислительная сложность из алгоритма может быть измерена с учетом модели вычислений. Использование модели позволяет изучать производительность алгоритмов независимо от вариаций, характерных для конкретных реализаций и конкретной технологии.

Модели

Модели вычислений можно разделить на три категории: последовательные модели, функциональные модели и параллельные модели.

Последовательные модели включают:

Функциональные модели включают:

Параллельные модели включают:

Некоторые из этих моделей имеют как детерминированные, так и недетерминированные варианты. Недетерминированные модели бесполезны для практических вычислений; они используются при исследовании вычислительной сложности алгоритмов.

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

Использует

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

Категории

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

Смотрите также

использованная литература

дальнейшее чтение

  • Фернандес, Марибель (2009). Модели вычислений: введение в теорию вычислимости . Бакалавриат по информатике. Springer. ISBN 978-1-84882-433-1.
  • Сэвидж, Джон Э. (1998). Модели вычислений: изучение мощности вычислений . Эддисон-Уэсли. ISBN 978-0201895391.