Ingenieria en Informática, Universidad Blas Pascal.

Miércoles 20hs30-22hs, lab

Planificación

Apuntes

• 14/8: Máquinas de Turing (binarias, sin input)
• 21/8: Máquinas de Turing con input.
• 28/8: Lenguajes. Decibilidad. Notación O. Complejidad Temporal. Clase P.
• 4/9: Clase P, ejemplos. Clase EXP.
• 11/9: Clase NP. Lenguaje 3SAT.
• 25/9: Reducciones. Completitud en NP. Teorema de Cook-Levin.
• 2/10: MT universal. Indecibilidad.
• 9/10: Repaso para parcial.
• 16/10: parcial 2
• 30/10: Automatas Finitos y Lenguajes Regulares
• 6/11: Expresiones regulares
• 13/11: idem
• 20/11: parcial 3
• 21/11: repaso para recuperatorios
• 27/11: recuperatorios

Bibliografía

• ‘Computational Complexity: A Modern Approach’, Arora y Barak, 2007
• ‘Introducción a la teoría de autómatas, lenguajes y computación’, Hopcroft, Motwani y Ullman, 2007
• ‘Quantum Computing Since Democritus’, Aaronson, 2006

Coloquio

• Proyecto de implementación

Examen final

El examen final consiste en dos partes, una corregida por la prof. Graciela Lerda, otra for el prof. Guillaume Hoffmann. Esta segunda parte consiste de 3 ejercicios entre los siguientes:

• mostrar que un lenguaje es decidible (dando la definición de una máquina de Turing que lo decida)
• mostrar que un lenguaje pertenece a la clase P (dando un algoritmo)
• mostrar que un lenguaje pertenece a la clase NP (dando un algoritmo)
• mostrar que existe una reducción polinomial entre dos lenguajes
• mostrar que un lenguaje es regular (dando la definicion de un AFD que lo reconozca)
• escribir una expresión regular que reconozca un lenguaje dado
• convertir una expresión regular a un AFND-ϵ equivalente
• convertir un AFD en una expresión regular equivalente (usando la eliminación de estados)