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