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

Иные значения см. разделе в Компьютерное моделирование.

Теория вычислимости и теория сложности вычислений трактует модель вычисления (англ. model of computation) не только как определение множества допустимых операций, использованных для вычисления, но также и относительных издержек их применения. Охарактеризовать необходимые вычислительные ресурсы — время выполнения, объём памяти, а также ограничения алгоритмов или компьютера — можно только в том случае, если выбрана определённая модель вычислений.

В модельно-ориентированной инженерии модель вычислений и её выбор дают ответ на вопрос, как ведёт себя система в целом, если известно поведение её отдельных частей.

При асимптотической оценке сложности вычислений модель вычислений определяется через допустимые примитивные операции с известной ценой.

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

См. также

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

Примечания

Ссылки

Эта страница в последний раз была отредактирована 30 сентября 2014 в 19:44.