В информатике , а точнее в теории вычислимости и теории сложности вычислений , модель вычислений — это модель, описывающая, как вычисляется выход математической функции при заданных входных данных. Модель описывает, как организованы единицы вычислений, памяти и коммуникации. [1] Вычислительную сложность алгоритма можно измерить при заданной модели вычислений. Использование модели позволяет изучать производительность алгоритмов независимо от вариаций, характерных для конкретных реализаций и конкретной технологии.
Модели вычислений можно разделить на три категории: последовательные модели, функциональные модели и параллельные модели.
Последовательные модели включают в себя:
Функциональные модели включают в себя:
К параллельным моделям относятся:
Некоторые из этих моделей имеют как детерминированные , так и недетерминированные варианты. Недетерминированные модели соответствуют пределам определенных последовательностей конечных компьютеров, но не соответствуют ни одному подмножеству конечных компьютеров; [ необходима цитата ] они используются при изучении вычислительной сложности алгоритмов.
Модели различаются по своей выразительной силе; например, каждая функция, которая может быть вычислена конечным автоматом, может быть вычислена и машиной Тьюринга , но не наоборот.
В области анализа времени выполнения алгоритмов принято указывать вычислительную модель в терминах примитивных операций, разрешенных с единичной стоимостью, или просто операций с единичной стоимостью . Распространенным примером является машина с произвольным доступом , которая имеет единичную стоимость доступа для чтения и записи ко всем своим ячейкам памяти. В этом отношении она отличается от вышеупомянутой модели машины Тьюринга.