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