Вычислительные ресурсы в теории сложности вычислений
Computational resource
Вычислительные ресурсы: время, память и др. – ключевые факторы сложности решения задач в теории вычислений. Анализ ресурсов для эффективных алгоритмов.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Что-то, что необходимо компьютеру для решения задачи, например, шаги вычислений или память.
Something a computer needs needed to solve a problem, such as processing steps or memory
В теории вычислительной сложности вычислительный ресурс — это ресурс, используемый некоторыми вычислительными моделями при решении вычислительных задач. Наиболее простыми вычислительными ресурсами являются время вычислений, количество шагов, необходимых для решения задачи, и объём памяти, необходимый в процессе решения. Однако определено гораздо больше сложных ресурсов. Вычислительная задача обычно определяется с точки зрения её действия над любым допустимым входом. Примерами задач могут быть: "для заданного целого числа n определить, является ли n простым", или "для двух чисел x и y вычислить произведение x*y". По мере увеличения входных данных объём вычислительных ресурсов, необходимых для решения задачи, возрастает. Таким образом, ресурсы, необходимые для решения задачи, описываются с помощью асимптотического анализа, определяя ресурсы как функцию от длины или размера входных данных. Использование ресурсов часто частично оценивается с использованием нотации «Большое О». Вычислительные ресурсы полезны, поскольку позволяют изучать, какие задачи могут быть решены за определённое количество каждого вычислительного ресурса. Таким образом, можно определить, оптимальны ли алгоритмы для решения задачи, и делать выводы об эффективности алгоритма. Множество всех вычислительных задач, которые могут быть решены с использованием определённого количества определённого вычислительного ресурса, называется классом сложности, а взаимосвязи между различными классами сложности — одна из важнейших тем в теории сложности.
In computational complexity theory, a computational resource is a resource used by some computational models in the solution of computational problems. The simplest computational resources are computation time, the number of steps necessary to solve a problem, and memory space, the amount of storage needed while solving the problem, but many more complicated resources have been defined. A computational problem is generally defined in terms of its action on any valid input. Examples of problems might be "given an integer n, determine whether n is prime", or "given two numbers x and y, calculate the product x*y". As the inputs get bigger, the amount of computational resources needed to solve a problem will increase. Thus, the resources needed to solve a problem are described in terms of asymptotic analysis, by identifying the resources as a function of the length or size of the input. Resource usage is often partially quantified using Big O notation. Computational resources are useful because we can study which problems can be computed in a certain amount of each computational resource. In this way, we can determine whether algorithms for solving the problem are optimal and we can make statements about an algorithm's efficiency. The set of all of the computational problems that can be solved using a certain amount of a certain computational resource is a complexity class, and relationships between different complexity classes are one of the most important topics in complexity theory.
Описание общедоступного вычислительного оборудования
Термин "вычислительный ресурс" обычно используется для описания доступного вычислительного оборудования и программного обеспечения. См. Облачные вычисления.
The term "Computational resource" is commonly used to describe accessible computing equipment and software. See Utility computing.
Были предприняты попытки формально оценить вычислительную мощность. Ограниченная машина Тьюринга использовалась для моделирования конкретных вычислений, где количество переходов состояний и размер алфавита служили для количественной оценки вычислительных затрат, необходимых для решения определенной задачи.
There has been some effort to formally quantify computing capability. A bounded Turing machine has been used to model specific computations using the number of state transitions and alphabet size to quantify the computational effort required to solve a particular problem.