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