В информатике , а точнее в теории вычислимости и теории сложности вычислений , модель вычислений - это модель, которая описывает, как вычисляются выходные данные математической функции при заданных входных данных. Модель описывает, как организованы единицы вычислений, памяти и связи. [1] вычислительная сложность из алгоритма может быть измерена с учетом модели вычисления. Использование модели позволяет изучать производительность алгоритмов независимо от вариаций, характерных для конкретных реализаций и конкретной технологии.
Модели
Модели вычислений можно разделить на три категории: последовательные модели, функциональные модели и параллельные модели.
Последовательные модели включают:
Функциональные модели включают:
- Лямбда-исчисление
- Общие рекурсивные функции
- Комбинаторная логика
- Системы рерайтинга абстрактных текстов
Параллельные модели включают:
- Клеточный автомат
- логические вентили и цифровые схемы
- Технологические сети Кан
- Сети Петри
- Синхронный поток данных
- Сети взаимодействия
- Актерская модель
Модели отличаются выразительной силой; например, каждая функция, которая может быть вычислена конечным автоматом, также может быть вычислена машиной Тьюринга , но не наоборот.
Недетерминирована модель вычислений связана с некоторыми из этих моделей вычислений. Недетерминированные модели бесполезны для практических вычислений; они используются при исследовании вычислительной сложности алгоритмов.
Использует
В области анализа алгоритмов во время выполнения обычно определяют вычислительную модель в терминах разрешенных примитивных операций, которые имеют удельную стоимость, или просто операций с удельной стоимостью . Обычно используемым примером является машина с произвольным доступом , которая имеет удельную стоимость доступа для чтения и записи ко всем ячейкам памяти. В этом отношении она отличается от упомянутой выше модели машины Тьюринга.
Категории
Существует множество моделей вычислений, различающихся набором допустимых операций и стоимостью их вычислений. Они делятся на следующие широкие категории:
- Абстрактная машина и эквивалентные ей модели (например, лямбда-исчисление эквивалентно машине Тьюринга ) - используются в доказательствах вычислимости и верхних оценок вычислительной сложности алгоритмов.
- Модели деревьев решений - используются при доказательстве нижних оценок вычислительной сложности алгоритмических задач.
Смотрите также
- Стек-машина ( машина с 0 операндами)
- Аккумуляторная машина ( машина с одним операндом)
- Регистрационная машина (2,3, ... машина-операнд)
- Машина с произвольным доступом
- Модель клетки-зонда
- Модель запроса Робертсона – Уэбба
Рекомендации
- ^ "Модели вычислений" (PDF) .
дальнейшее чтение
- Фернандес, Марибель (2009). Модели вычислений: введение в теорию вычислимости . Бакалавриат по информатике. Springer. ISBN 978-1-84882-433-1.
- Сэвидж, Джон Э. (1998). Модели вычислений: изучение мощности вычислений . Эддисон-Уэсли. ISBN 978-0201895391.