Модель вычисления - Model of computation

Для компьютерных моделей, имитирующих сложные системы, см. Вычислительная модель.

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

Модели

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

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

• Конечные автоматы
• Выталкивающие автоматы
• Машины с произвольным доступом
• Машины Тьюринга

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

• Лямбда-исчисление
• Общие рекурсивные функции
• Комбинаторная логика
• Системы рерайтинга абстрактных

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

• Клеточный автомат
• Цифровые схемы
• Технологические сети Кан
• Сети Петри
• Синхронный поток данных
• Сети взаимодействия
• Актерская модель

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

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

Использует

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

Категории

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

• Абстрактная машина и эквивалентные ему модели (например, лямбда-исчисление эквивалентен Машина Тьюринга ) - используется в доказательствах вычислимости и верхних оценок вычислительной сложности алгоритмов.
• Модели дерева решений - используется при доказательстве нижних оценок вычислительной сложности алгоритмических задач.

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

• Штабелеукладчик (0-операндная машина)
• Аккумуляторная машина (Машина с одним операндом)
• Зарегистрировать машину (2,3, ... машина операнда)
• Машина произвольного доступа
• Модель клетки-зонда

Рекомендации

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

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