La foto de la portada es una imagen de libre uso de Pixabay y editada por @abdulmath con GIMP, los emoji son creados con Bitmoji
Teoría de la Complejidad (continuación)
Existen muchas opciones cuando se enfrenta a un problema que parece difícil desde el punto de vista computacional.
En primer lugar, si se entiende qué aspecto del problema es la causa de la dificultad, se puede modificar para que el problema sea más fácil de resolver.
En segundo lugar, es posible que pueda conformarse con una solución menos que perfecta del problema. En algunos casos, encontrar soluciones que sólo se aproximan a la perfecta es relativamente fácil.
En tercer lugar, algunos problemas son difíciles sólo en el peor de los casos, pero fáciles la mayor parte del tiempo.
Dependiendo de la aplicación, puede estar satisfecho con un procedimiento que ocasionalmente sea lento pero que normalmente se ejecute rápidamente.
Por último, puede considerar tipos alternativos de cálculo, como el cálculo aleatorio, que pueden acelerar ciertas tareas.
Un área aplicada que se ha visto directamente afectada por la teoría de la complejidad es el antiguo campo de la criptografía.
En la mayoría de los campos, un problema de cálculo fácil es preferible a uno difícil porque los fáciles son más baratos de resolver.
La criptografía es inusual porque requiere específicamente problemas computacionales que sean difíciles, en lugar de fáciles, porque los códigos secretos deben ser difíciles de romper sin la clave o contraseña secreta.
La teoría de la complejidad ha orientado a los criptógrafos hacia problemas computacionalmente difíciles en torno a los cuales han diseñado nuevos códigos revolucionarios.
Imagen de Pixabay y editada por @abdulmath con GIMP.
Teoría de la Computabilidad
Durante la primera mitad del siglo XX, matemáticos como Kurt Godel, Alan Turing y Alonzo Church descubrieron que ciertos problemas básicos no pueden ser resueltos por los computadores.
Un ejemplo de este fenómeno es el problema de determinar si un enunciado matemático es verdadero o falso.
Esta tarea es el pan de cada día de nosotros los matemáticos.
Parece una solución natural para el computador porque se encuentra estrictamente en el ámbito de las matemáticas.
Pero ningún algoritmo informático puede realizar esta tarea.
Una de las consecuencias de este profundo resultado fue el desarrollo de ideas relativas a los modelos teóricos de los computadores que, con el tiempo, contribuirían a la construcción de computadores más reales.
Las teorías de la computabilidad y la complejidad están estrechamente relacionadas.
En la teoría de la complejidad, el objetivo es clasificar los problemas en fáciles y difíciles, mientras que en la teoría de la computabilidad la clasificación de los problemas es por aquellos que son resolubles y los que no lo son.
La teoría de la computabilidad introduce varios de los conceptos utilizados en la teoría de la complejidad.
Teoría de los Autómatas
La teoría de los autómatas se ocupa de las definiciones y propiedades de los modelos matemáticos de la computación.
Estos modelos desempeñan un papel en varias áreas aplicadas de la informática.
Un modelo, llamado autómata finito, se utiliza en el procesamiento de textos, los compiladores y el diseño de hardware.
Otro modelo, llamado gramática libre de contexto, se utiliza en los lenguajes de programación y en la inteligencia artificial.
La teoría de autómatas es un lugar excelente para comenzar el estudio de la teoría de la computación.
Las teorías de la computabilidad y la complejidad requieren una definición precisa de lo que es un computador.
La teoría de autómatas permite practicar con definiciones formales de la computación, ya que introduce conceptos relevantes para otras áreas no teóricas de la informática.
Imagen de Pixabay y editada por @abdulmath con GIMP, e Inkscape.
Espero que les haya gustado este interesante tema acerca de La Teoría de la Computación, no te pierdas las próximas publicaciones donde abordaré otros temas interesantes. Si deseas ampliar más te invito a leer las siguientes referencias:
- Aho, A. V., Sethi, R., and Ullman, J. D. (1986) Compilers: Principles, Techniques, Tools. Addison-Wesley.
- Baase, S. (1978) Computer Algorithms: Introduction to Design and Analysis. Addison-Wesley.
- Bach, E., and Sallit, J. (1996) Algorithmic Number Theory, Vol. 1. MIT Press.
- Brassard, G., and Bratley, P. (1988) Algorithmics: Theory and Practice. Prentice-Hall.
