Модель вычислений

Информацию о компьютерных моделях, имитирующих сложные системы, см. в разделе «Вычислительная модель» .

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

Модели

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

Последовательные модели

К последовательным моделям относятся:

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

Функциональные модели

К функциональным моделям относятся:

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

Параллельные модели

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

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

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

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

Использование

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

См. также

• Стековая машина (машина с 0 операндами)
• Накопительная машина (машина с 1 операндом)
• Регистрационная машина (2,3,... операндная машина)
• Машина произвольного доступа
• Абстрактная машина
• Модель клеточного зонда
• Модель запроса Робертсона – Уэбба
• Иерархия Хомского
• Полнота по Тьюрингу

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

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