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