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