Recurso computacional - Computational resource

Na teoria da complexidade computacional , um recurso computacional é um recurso usado por alguns modelos computacionais na solução de problemas computacionais .

Os recursos computacionais mais simples são o tempo de computação , o número de etapas necessárias para resolver um problema e o espaço de memória , a quantidade de armazenamento necessária para resolver o problema, mas muitos recursos mais complicados foram definidos.

Um problema computacional é geralmente definido em termos de sua ação em qualquer entrada válida. Exemplos de problemas pode ser "dada um número inteiro n , determinar se n for primo", ou "dados dois números x e y , calcular o produto x * y ". Conforme as entradas ficam maiores, a quantidade de recursos computacionais necessários para resolver um problema aumentará. Assim, os recursos necessários para resolver um problema são descritos em termos de análise assintótica , identificando os recursos em função do comprimento ou do tamanho da entrada. O uso de recursos é muitas vezes parcialmente quantificada utilizando Big O notação .

Os recursos computacionais são úteis porque podemos estudar quais problemas podem ser computados em uma determinada quantidade de cada recurso computacional. Dessa forma, podemos determinar se os algoritmos para resolver o problema são ótimos e podemos fazer declarações sobre a eficiência de um algoritmo . O conjunto de todos os problemas computacionais que podem ser resolvidos usando uma certa quantidade de um determinado recurso computacional é uma classe de complexidade , e os relacionamentos entre diferentes classes de complexidade são um dos tópicos mais importantes na teoria da complexidade.

Descrever equipamentos de computação geralmente acessíveis

O termo "recurso computacional" é comumente usado para descrever equipamentos e softwares de computação acessíveis. Consulte Computação utilitária .

Quantificação formal da capacidade de computação

Tem havido algum esforço para quantificar formalmente a capacidade de computação. Uma máquina de Turing limitada foi usada para modelar cálculos específicos usando o número de transições de estado e o tamanho do alfabeto para quantificar o esforço computacional necessário para resolver um problema específico.

Referências