A2A: “¿Cuál es el lado teórico detrás de la informática?”
El lado teórico de la informática es el estudio matemático de la computación. Lo mejor que puedes hacer para prepararte es hacerlo bien en tus clases de matemáticas y no tener miedo a las abstracciones matemáticas .
Computabilidad
- ¿Dónde puedo conocer y salir con profesores que trabajan en la intersección de algoritmos de aproximación y teoría de números algebraicos?
- ¿Qué es la notación de sintaxis abstracta uno?
- ¿Por qué diferenciamos entre máquinas Turing universales y máquinas Turing normales?
- ¿Crees que una sólida formación en Matemáticas hará que un programador se destaque del resto? ¿Por qué o por qué no?
- ¿Podemos crear música original a través de la permutación digital?
Está recién comenzando a aprender Java, por lo que su baúl de herramientas y técnicas aún es relativamente pequeño. Probablemente concederías que podría pedirte que resuelvas un problema realmente complejo que está más allá de tu habilidad actual, o al menos te tomaría mucho tiempo escribir el programa para resolverlo. Pero pare y hágase la siguiente pregunta. ¿Podría ser lo suficientemente complicado como para darte un problema muy razonable para el cual es imposible que escribas un programa? La respuesta a eso es sí. Y lo aprenderá cuando estudie la teoría de la computabilidad.
El ejemplo clásico de un problema tan imposible se llama problema de detención: ¿existe un programa que me diga si otro programa se detendrá cuando se le dé un conjunto particular de entradas?
Piénsalo. Usted sabe que hay un compilador de Java que traduce un programa de Java en un formulario que puede ser ejecutable por la JVM. La primera idea obvia para resolver el problema de detención sería tomar el programa y comenzar a ejecutarlo en la JVM, darle las entradas y ver si finalmente se detiene. Si lo hace, entonces envíe “sí”. Si no es así … bueno, eso es un pequeño problema. Probablemente ya haya aprendido lo fácil que es escribir un programa que se integre en un bucle infinito. Por lo tanto, es bastante fácil decir “sí” cuando ve que el programa se detiene. Pero hay un problema persistente que si se mete en un bucle infinito, nunca lo verás detenerse y nunca saldrá “no”.
Si piensa más en este problema, puede encontrar algunas posibles soluciones inteligentes. Podrías reconocer algunas condiciones bajo las cuales podrías concluir que el programa estaba en un ciclo infinito y ser capaz de terminarlo y responder “no”. Pero habría algunos programas e insumos para los cuales aún tenía problemas para reconocer el bucle infinito. Encontraría formas más inteligentes de reconocer el comportamiento ‘no intermitente’. Aún así, siempre habrá algunos programas e insumos para los que no reconoció que el programa nunca se detendría.
Puedes intentarlo para siempre para resolver este problema. Por otro lado, con un poco de razonamiento matemático sobre la naturaleza de los programas, puede probar que no hay ningún programa que resuelva el problema de detención. Requiere que retroceda un nivel y vea programas (o algoritmos) como objetos matemáticos en sí mismos. Ese paso de abstracción puede ser confuso para algunas personas. Es la parte más difícil de la teoría de la computabilidad con la que te encontrarás en el nivel de pregrado. Si puede dar ese salto intelectual, entonces el resto de la teoría de la computabilidad estará trabajando en los detalles.
Complejidad e Intractabilidad
Al igual que con la computabilidad, la teoría de la complejidad requiere que veas los algoritmos como entidades matemáticas abstractas. Aprenderá un montón de técnicas para analizar las características de tiempo de ejecución de un algoritmo, en particular, la complejidad del tiempo y la complejidad del espacio. Si puede dar el salto desde la programación hasta el análisis de programas, y conoce bien las matemáticas discretas y las series matemáticas, entonces comprender la teoría de la complejidad será cuestión de superar todos los detalles. No solo aprenderá cómo analizar un algoritmo dado, sino que también verá clases de problemas que tienen una complejidad similar. Observará las características de los problemas que se pueden resolver, pero cuya complejidad es tan grande que no pueden ejecutarse en una cantidad de tiempo prácticamente útil en un dispositivo de computación del mundo real (es decir, intratabilidad).
Teoría formal del lenguaje
La teoría del lenguaje formal es una forma diferente de estudiar la naturaleza de la computación. Tiene conexiones con las teorías de computabilidad y complejidad. Se aplica a problemas de análisis, traducción y compilación. Puede profundizarse, pero no es demasiado difícil a nivel de pregrado si puedes asimilar las abstracciones matemáticas.
