Teoría de la Computación (Continuación)

---

Para poder entender la Teoría de la Computación se conocer y/o repasar algunos conceptos matemáticos que necesitarás más adelante, a saber: AUTÓMATAS, COMPUTABILIDAD Y COMPLEJIDAD.

Estas tres áreas tradicionalmente centrales de la teoría de la computación, vienen vinculadas con la siguiente pregunta:

---

¿Cuáles son las capacidades y limitaciones fundamentales de los computadores?

---

Esta pregunta se remonta a la década de 1930, cuando los lógicos matemáticos comenzaron a explorar el significado de la computación.

Desde entonces, los avances tecnológicos han aumentado enormemente nuestra capacidad de cálculo y han sacado esta cuestión del ámbito de la teoría para llevarla al mundo de la práctica.

---

En cada una de las tres áreas -autómatas, computabilidad y complejidad- esta cuestión se interpreta de forma diferente, y las respuestas varían según la interpretación.

Inicaremos hablando de estás áreas en orden inverso, ya que es posible que si empezamos por el final se puede entender mejor la razón del principio.

---

_{Imagen de Pixabay y editada por @abdulmath con GIMP.}

---

Teoría de la Complejidad

---

Los problemas informáticos se presentan en diferentes variedades; algunos son fáciles y otros difíciles.

Por ejemplo, el problema de ordenación es fácil.

Digamos que hay que ordenar una lista de números en orden ascendente. Incluso un pequeño ordenador puede ordenar un millón de números con bastante rapidez.

---

Comparándolo con un problema de programación.

Digamos que hay que encontrar un horario de clases para toda la universidad que satisfaga algunas restricciones razonables, como que no haya dos clases en la misma sala a la misma hora.

El problema de la programación parece mucho más difícil que el de la ordenación. Si sólo tiene mil clases, encontrar el mejor horario puede requerir siglos, incluso con un supercomputador.

---

¿Qué hace que algunos problemas sean computacionalmente difíciles y otros fáciles?

---

Esté es el punto central de la teoría de la complejidad.

Sorprendentemente, no sabemos la respuesta, aunque se ha investigado intensamente durante los últimos 60 años.

En uno de los logros importantes de la teoría de la complejidad hasta ahora, es que los investigadores han descubierto un elegante esquema para clasificar los problemas según su dificultad computacional.

---

Es análogo a la tabla periódica para clasificar los elementos según sus propiedades químicas.

Utilizando este esquema, podemos demostrar un método para dar pruebas de que ciertos problemas son computacionalmente difíciles, aunque no podamos demostrar que lo son.

---

Continuará . . .

---

_{Imagen de Pixabay y editada por @abdulmath con GIMP, e Inkscape.}

---

Si te gusto este tema y quieres seguir profundizando acerca de La Teoría de la Computación, no te pierdas la próxima publicación, pero si aún así deseas conocer otra perspectiva del mismo, te invito a investigar en las siguientes referencias que acá te comparto:

1. Aho, A. V., Sethi, R., and Ullman, J. D. (1986) Compilers: Principles, Techniques, Tools. Addison-Wesley.
2. Baase, S. (1978) Computer Algorithms: Introduction to Design and Analysis. Addison-Wesley.
3. Bach, E., and Sallit, J. (1996) Algorithmic Number Theory, Vol. 1. MIT Press.
4. Brassard, G., and Bratley, P. (1988) Algorithmics: Theory and Practice. Prentice-Hall.

---

---