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