SOBRE ESTE CURSO
Comenzamos con un estudio de los autómatas finitos y los lenguajes que pueden definir (los llamados «lenguajes regulares». Los temas incluyen los autómatas deterministas y no determinantes, las expresiones regulares y la equivalencia de estos mecanismos de definición del lenguaje. También examinamos las propiedades de cierre de los lenguajes regulares, por ejemplo, el hecho de que la unión de dos lenguajes regulares es también un lenguaje regular. Consideramos las propiedades de decisión de los lenguajes regulares, por ejemplo, el hecho de que exista un algoritmo para decir si el lenguaje definido por dos autómatas finitos es o no el mismo lenguaje. Por último, vemos el lema de bombeo para los lenguajes regulares, una forma de probar que ciertos lenguajes no son lenguajes regulares.
Nuestro segundo tema es la gramática sin contexto y sus lenguajes. Aprendemos sobre los árboles de análisis y seguimos un patrón similar al de los autómatas finitos: propiedades de cierre, propiedades de decisión y un lema de bombeo para los lenguajes sin contexto. También introducimos el autómata de bombeo, cuya versión no determinista es equivalente en poder de definición del lenguaje a las gramáticas sin contexto.
A continuación, presentamos la máquina Turing, una especie de autómata que puede definir todos los lenguajes que se puede decir razonablemente que son definibles por cualquier tipo de dispositivo informático (los llamados «lenguajes enumerables recursivamente»). Aprenderemos cómo los «problemas» (preguntas matemáticas) pueden ser expresados como lenguajes. Esto nos permite definir los problemas como «decidibles» si su lenguaje puede ser definido por una máquina de Turing y «indecidibles» si no. Veremos algunos problemas básicos indecidibles, por ejemplo, es indecidible si la intersección de dos idiomas sin contexto está vacía.
Por último, miramos la teoría de los problemas intratables. Estos son problemas que, aunque son decidibles, casi seguro que no tienen ningún algoritmo que funcione en el tiempo menos que alguna función exponencial del tamaño de su entrada. Nos encontramos con los problemas NP-completos, una gran clase de problemas intratables. Esta clase incluye muchos de los problemas combinatorios difíciles que se ha asumido durante décadas o incluso siglos que requieren un tiempo exponencial, y aprendemos que ninguno o todos estos problemas tienen algoritmos de tiempo polinómico. Un ejemplo común de un problema NP-completo es SAT, la cuestión de si una expresión booleana tiene una asignación de verdad a sus variables que hace que la expresión en sí misma sea verdadera.
REQUISITOS
El prerrequisito principal de este curso es una razonable «sofisticación matemática». Es decir, usted debe sentirse cómodo con las matemáticas y las pruebas. Los temas específicos que son útiles incluyen un conocimiento de gráficos, árboles y lógica, así como estructuras básicas de datos y algoritmos.
PERSONAL DE CURSO
Jeffrey D. Ullman
Jeff Ullman es un profesor jubilado de Ciencias de la Computación en Stanford. Su página web ofrece información adicional sobre el instructor.