Recurso computacional
En 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 la complejidad temporal, la cantidad de pasos necesarios para resolver un problema, y el espacio de memoria, la cantidad de almacenamiento necesaria para resolver el problema, pero se han definido muchos recursos más complicados.[cita requerida]
Un problema computacional es generalmente[cita requerida] definido en términos de su acción en cualquier entrada válida. Ejemplos de problemas podrían ser "dado un número entero n, determine si n es primo", o "dados dos números x e y, calcule el producto x * y ". A medida que las entradas aumentan, la cantidad de recursos computacionales necesarios para resolver un problema aumentará. Así, los recursos necesarios para resolver un problema se describen en términos de análisis asintótico, identificando los recursos en función de la longitud o el tamaño de la entrada. El uso de recursos a menudo se cuantifica parcialmente utilizando la cota superior asintótica.
Los recursos computacionales son útiles porque podemos estudiar qué problemas se pueden calcular en una cierta cantidad de cada recurso computacional. De esta forma, podemos determinar si los algoritmos para resolver el problema son óptimos y podemos hacer afirmaciones sobre la eficiencia algorítmica. El conjunto de todos los problemas computacionales que se pueden resolver usando una cierta cantidad de un cierto recurso computacional es una clase de complejidad, y las relaciones entre diferentes clases de complejidad son uno de los temas más importantes en la teoría de la complejidad.
Cuantificación formal de la capacidad informática
editarHa habido algún esfuerzo para cuantificar formalmente la capacidad computacional. Se ha utilizado una máquina de Turing limitada para modelar cálculos específicos usando el número de transiciones de estado y el tamaño del alfabeto para cuantificar el esfuerzo computacional requerido para resolver un problema en particular.[1][2]
Referencias
editar- ↑ Gregory J., Chaitin (1966). «On the Length of Programs for Computing Finite Binary Sequences». Journal of the ACM 13 (4): 547-569. S2CID 207698337. doi:10.1145/321356.321363. Archivado desde el original el 5 de febrero de 2007. Consultado el 25 de septiembre de 2007.
- ↑ Sow, Daby; Eleftheriadis, Alexandros (1998). «Representing Information with Computational Resource Bounds». Signals, Systems & Computers. Conference Record of the Thirty-Second Asilomar Conference on 1. pp. 452-456. ISBN 0-7803-5148-7. 10.1109/ACSSC.1998.750904. Consultado el 25 de septiembre de 2007.