Вычислительный ресурс - Computational resource
В теории сложности вычислений , вычислительный ресурс представляет собой ресурс , используемый некоторые вычислительные модели в решении вычислительных задач .
Простейшие вычислительные ресурсы - это время вычислений , количество шагов, необходимых для решения проблемы, и объем памяти , объем памяти, необходимый для решения проблемы, но были определены гораздо более сложные ресурсы.
Вычислительная проблема обычно определяется в терминах ее действия на любой допустимый ввод. Примерами проблем могут быть: «дать целое число n , определить, является ли n простым», или «учитывая два числа x и y , вычислить произведение x * y ». По мере увеличения входных данных увеличивается количество вычислительных ресурсов, необходимых для решения проблемы. Таким образом, ресурсы, необходимые для решения проблемы, описываются в терминах асимптотического анализа путем определения ресурсов как функции длины или размера входных данных. Использование ресурсов часто частично количественно с использованием Big O обозначения .
Вычислительные ресурсы полезны, потому что мы можем изучить, какие задачи могут быть вычислены в определенном количестве каждого вычислительного ресурса. Таким образом, мы можем определить, являются ли алгоритмы для решения проблемы оптимальными, и мы можем сделать заявления об эффективности алгоритма . Набор всех вычислительных задач, которые могут быть решены с использованием определенного количества определенных вычислительных ресурсов, представляет собой класс сложности , а отношения между различными классами сложности являются одной из наиболее важных тем в теории сложности.
Описание общедоступного вычислительного оборудования
Термин «вычислительный ресурс» обычно используется для описания доступного вычислительного оборудования и программного обеспечения. См. Коммунальные вычисления .
Формальная количественная оценка вычислительных возможностей
Были предприняты некоторые усилия для формальной количественной оценки вычислительных возможностей. Ограниченная машина Тьюринга использовалась для моделирования конкретных вычислений с использованием количества переходов между состояниями и размера алфавита для количественной оценки вычислительных усилий, необходимых для решения конкретной проблемы.