MATE2181 Introducción a la Teoría de la Computación
Este curso opcional dirigido a estudiantes de pregrado es una introducción rigurosa a los fundamentos matemáticos de la teoría de computación. Se estudian las correspondencias fundamentales entre los tipos de autómatas y lenguajes formales que participan en la jerarquía de Chomsky, las nociones básicas de computabilidad (máquinas de Turing y tesis de Church-Turing) y nociones básicas de complejidad computacional (clases P, NP, reductibilidad, problemas NP-completos.
Se espera que el estudiante que tome este curso ya conozca las nociones básicas de teoría de conjuntos (operaciones básicas de conjuntos y demostración de propiedades de conjuntos) y los métodos de demostración elementales, en particular el de demostración por inducción.
En el curso no se hará programación, pero sí se espera que el estudiante que tome que el curso está familiarizado con las nociones y estructuras básicas de programación (ciclos, instrucciones condicionales, recursión, etc.).
Periodo en el que se ofrece el curso
201720
Idioma en el que se ofrece el curso
Español
Página del catálogo en este curso