- El curso CS251 de CMU trata sobre el estudio riguroso de la computación, un elemento fundamental del universo, la sociedad, las nuevas tecnologías y de nuestra mente para comprenderlos.
- Es importante contar con el lenguaje y las herramientas adecuadas para estudiar la computación.
- En este curso se exploran resultados y preguntas centrales sobre la naturaleza de la computación.
Formalización de la computación
Módulo 1: Introducción
- El objetivo principal es explicar a alto nivel qué es la ciencia de la computación teórica y establecer el contexto adecuado para lo que se verá más adelante.
- Se comienza con cómo representar formalmente los datos y cómo definir formalmente el concepto de problema computacional.
Módulo 2: Autómatas finitos
- El objetivo es introducir los autómatas finitos deterministas (DFA), un modelo de computación simple y limitado.
- Los DFA son interesantes por sí mismos y tienen aplicaciones útiles, pero aquí se usan como un primer paso para definir formalmente el concepto de algoritmo.
Módulo 3: Formalización de la computación
- El objetivo principal es introducir la definición de la máquina de Turing, el modelo matemático estándar para todo tipo de dispositivos de cómputo.
- El estudio riguroso de la máquina de Turing ofrece perspectivas no solo sobre lo que una laptop puede hacer, sino también sobre lo que el universo puede y no puede hacer computacionalmente.
Módulo 4: Límites de la computación
- Se demuestra que la mayoría de los problemas son indecidibles y se presentan ejemplos concretos de problemas indecidibles.
- Se utilizan dos técnicas clave: diagonalización y reducción.
Módulo 5: Límites del razonamiento humano
- Fue necesario formalizar matemáticamente el razonamiento matemático, lo que incluía formalizar el "algoritmo" o la "computación".
- Se responden eficazmente preguntas importantes sobre los fundamentos de las matemáticas usando el lenguaje de la ciencia de la computación teórica.
Complejidad computacional
Módulo 6: Complejidad temporal
- Muchos problemas son, de hecho, decidibles, pero si el algoritmo más eficiente requiere una enorme cantidad de pasos de cálculo, entonces el problema es prácticamente indecidible.
- Se estudia la complejidad computacional respecto a diversos recursos, incluida la complejidad temporal, aunque el enfoque está en esta última.
Módulo 7: Teoría de grafos
- Los grafos cumplen un papel muy básico en la abstracción de problemas computacionales que surgen en informática.
- Aprovechando la vasta literatura sobre teoría de grafos, es posible comprender mejor la complejidad computacional de los problemas sobre grafos.
Módulo 8: P vs NP
- Se introduce la clase de complejidad NP y se discute el problema P vs NP, el problema abierto más importante de la informática.
- Si muchos lenguajes naturales y bien estudiados que pertenecen a NP pudieran decidirse en tiempo polinomial, serían posibles aplicaciones sorprendentes.
Módulo 9: Algoritmos aleatorizados
- La aleatoriedad es un concepto y una herramienta esenciales para modelar y analizar la naturaleza.
- Los algoritmos aleatorizados son algoritmos que pueden acceder a una fuente de aleatoriedad, como un generador de números aleatorios, y pueden equivocarse con una probabilidad de error muy pequeña.
Módulo 10: Criptografía
- Con la revolución de la informática, el campo de la criptografía comenzó a florecer enormemente.
- El estudio de la complejidad computacional revolucionó por completo la criptografía.
Aspectos destacados de la ciencia de la computación teórica
Módulo 11: Temas adicionales
- Se presentan algunos aspectos destacados seleccionados de la ciencia de la computación teórica.
Opinión de GN⁺
- Este curso ofrece una comprensión profunda de los aspectos teóricos de la informática y brinda a los estudiantes la oportunidad de explorar la naturaleza de la computación y aprender temas importantes como la teoría de la complejidad y la criptografía.
- En particular, la discusión de problemas abiertos como P vs NP ofrece a los estudiantes una visión de la investigación que ocurre en la frontera de la informática.
- Este curso desempeña un papel importante en la construcción de bases sólidas en informática y proporciona conocimientos esenciales para convertirse en un ingeniero de software con formación teórica.
- El módulo de criptografía destaca la importancia de la seguridad de los datos y la privacidad en la sociedad moderna, y sienta las bases para convertirse en un profesional en este campo.
- Este curso es muy valioso porque ayuda a los estudiantes que quieren desarrollar una carrera en informática a adquirir la base teórica y las habilidades de resolución de problemas que son indispensables.
2 comentarios
Ah... me acordé de cuando en la universidad me rompía la cabeza sufriendo con esto.
Probablemente todavía no lo entienda, pero igual tendré que escucharlo con ganas.
Opiniones de Hacker News
Esta clase presenta diversos conceptos y se enfoca especialmente en mejorar la capacidad de resolver problemas.
La teoría de la computación puede ser divertida, pero a veces también puede ser muy irritante.
Vi una publicación en Reddit preguntando cómo resolver un problema de teoría de la computación, y resultó ser un intento de hacer trampa para resolver una tarea de COMS 331 (Theory of Computing) de Iowa State University.
Si quieres aprender estas ideas directamente a través de la programación, recomiendo el libro de Tom Stuart, "Understanding Computation From Simple Machines to Impossible Programs".
Se puede ver una versión más completa de esta clase en una lista de reproducción de YouTube.
Hay otra versión de esta clase que incluye el "método probabilístico", y no puedo imaginar una demostración sobre obstáculos en espacios topológicos de soluciones sin la forma moderna de pensar las pruebas ontológicas (no constructivas).
Si te interesa este tema, puedes revisar el sitio web de Boaz Barak y el libro de texto disponible en PDF.
Las dos ideas más importantes de la teoría de la computación:
¿Cómo sería una versión de esta clase en otros campos?
Recuerdo una clase sobre complejidad temporal en la universidad. El profesor escogía estudiantes al azar y les preguntaba la complejidad temporal de algoritmos complicados, y si la respuesta era incorrecta, escogía a otro estudiante.
¿Cómo se puede entender la computación como una propiedad fundamental del universo? ¿Cómo realizan cómputo las plantas y los animales?