Hispanopedia WikiEn la teoría de la complejidad computacional , un recurso computacional es un recurso utilizado por algunos modelos computacionales en la solución de problemas computacionales .
Los recursos computacionales más simples son el tiempo de cálculo , que es el número de pasos necesarios para resolver un problema, y el espacio de memoria , que es la cantidad de almacenamiento necesaria mientras se resuelve el problema; sin embargo, se han definido muchos recursos más complejos.
Un problema computacional se define generalmente en términos de su acción sobre cualquier entrada válida. Ejemplos de problemas podrían ser: "dado un entero n , determinar si n es primo" o "dados dos números x e y , calcular el producto x * y ". A medida que las entradas aumentan, la cantidad de recursos computacionales necesarios para resolver un problema también aumenta. Por lo tanto, los recursos necesarios para resolver un problema se describen mediante análisis asintótico , identificando los recursos como una función de la longitud o el tamaño de la entrada . El uso de recursos a menudo se cuantifica parcialmente utilizando la notación Big O.
Los recursos computacionales son útiles porque nos permiten estudiar qué problemas pueden resolverse con una cantidad determinada de cada recurso. De esta forma, podemos determinar si los algoritmos para resolver el problema son óptimos y podemos hacer afirmaciones sobre la eficiencia de un algoritmo . El conjunto de todos los problemas computacionales que pueden resolverse utilizando una cantidad determinada de un recurso computacional específico constituye una clase de complejidad , y las relaciones entre las diferentes clases de complejidad son uno de los temas más importantes en la teoría de la complejidad.
Descripción de equipos informáticos de acceso general
El término "recurso computacional" se usa comúnmente para describir equipos y software informáticos accesibles. Véase Computación de utilidad .
Cuantificación formal de la capacidad de computación
Se han realizado algunos esfuerzos para cuantificar formalmente la capacidad de computación. Se ha utilizado una máquina de Turing limitada para modelar cálculos específicos, empleando el número de transiciones de estado y el tamaño del alfabeto para cuantificar el esfuerzo computacional necesario para resolver un problema particular. [ 1 ] [ 2 ]
Véase también
Referencias
- ↑ Gregory J., Chaitin (1966). "Sobre la longitud de los programas para calcular secuencias binarias finitas" (PDF) . Journal of the ACM . 13 (4): 547– 569. doi : 10.1145/321356.321363 . S2CID 207698337. Archivado del original (PDF) el 5 de febrero de 2007. Consultado el 25 de septiembre de 2007 .
- ↑ Sow, Daby; Eleftheriadis, Alexandros (1998). "Representación de información con límites de recursos computacionales" (PDF) . Signals, Systems & Computers. Actas de la trigésimo segunda conferencia de Asilomar . Vol. 1. págs. 452–456 . ISBN 0-7803-5148-7. 10.1109/ACSSC.1998.750904 . Consultado el 25 de septiembre de 2007 .
- Teoría de la complejidad computacional
- Recursos computacionales