Saltar al contenido

Introducción a los autómatas y la teoría de la complejidad

Introducción a los Autómatas y la Teoría de la Complejidad

Profesor Motwani

Introducción a los autómatas y la teoría de la complejidad
Introducción a los autómatas y la teoría de la complejidad

La mayor parte de lo que se cubre en la primera parte de este curso se requerirá en el diseño o análisis de casi cualquier sistema de software o hardware razonablemente complejo. La descripción de los lenguajes de programación y el diseño de analizadores para ellos requerirá un conocimiento íntimo de las gramáticas sin contexto. La segunda parte del curso se ocupa de un enfoque más filosófico de la informática. Aquí nos ocuparemos de las cuestiones básicas de la computabilidad y la trazabilidad. Utilizando el concepto de las máquinas de Turing intentaremos precisar la noción de un algoritmo y explorar sus limitaciones. Nos encontraremos con problemas indecidibles, es decir, aquellos que no pueden ser resueltos por ningún algoritmo o computadora. Incluso si un problema es decidible, puede resultar intratable, es decir, no existe ningún algoritmo eficiente para resolver ese problema. Estas nociones han tenido (y continuarán teniendo) una profunda influencia en nuestro enfoque sobre el uso de las computadoras para resolver problemas. Prerrequisitos:CS109 o CS109B

4 unidades