TEORÍA DE LA COMPLEJIDAD COMPUTACIONAL Y TEORÍA DE LA COMPUTABILIDAD
Palabras clave:
Complejidad computacional, computabilidad, eficiencia de algoritmos.Resumen
La ciencia de la computación es un cuerpo sistematizado del conocimiento concerniente al cálculo, que se sostiene en dos áreas fundamentales: La Teoría de la Computabilidad, basada en las ideas y los modelos fundamentales subyacentes al cálculo, y las técnicas de la ingeniería para el diseño de algoritmos. Este artículo está pensando en la importancia del primer aspecto. La Teoría de la Complejidad computacional estudia los recursos requeridos para resolver un problema como son el tiempo y el espacio; por su parte la teoría de la computabilidad se interesa en expresar los problemas como algoritmos sin tener en cuenta la información sobre los recursos necesarios para ello. Para abstraer las variaciones entre los diferentes sistemas computacionales se utiliza una máquina de Turing como un referente fijo, considerado como un modelo de máquina isofórmica a cualquier otro sistema informático. La Tesis de Church-Turing nos dice que si la máquina de Turing no puede resolver un problema, ninguna otra computadora podrá hacerlo, puesto que no existe algoritmo para resolver el problema. Por esa razón, las limitaciones corresponderían a los procesos computacionales y no a la tecnología.Descargas
Descargas
Archivos adicionales
Publicado
Número
Sección
Licencia
Derechos de autor 2004 Augusto Cortéz Vásquez
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-CompartirIgual 4.0.
LOS AUTORES RETIENEN SUS DERECHOS:
a. Los autores retienen sus derechos de marca y patente, y también sobre cualquier proceso o procedimiento descrito en el artículo.
b. Los autores retienen el derecho de compartir, copiar, distribuir, ejecutar y comunicar públicamente el artículo publicado en la Revista de investigación de Sistemas e Informática (por ejemplo, colocarlo en un repositorio institucional o publicarlo en un libro), con un reconocimiento de su publicación inicial en la Revista de investigación de Sistemas e Informática.
c. Los autores retienen el derecho a hacer una posterior publicación de su trabajo, de utilizar el artículo o cualquier parte de aquel (por ejemplo: una compilación de sus trabajos, notas para conferencias, tesis, o para un libro), siempre que indiquen su publicación inicial en la Revista de investigación de Sistemas e Informática (autores del trabajo, revista, volumen, número y fecha).