% Matemáticas Discretas III: lenguajes, computabilidad y complejidad
Año 2020, Ingenieria en Informática, Universidad Blas Pascal.
Fecha | Tema |
---|---|
10/9 | Intro. Máquinas de Turing. |
17/9 | Lenguajes formales. Lenguajes decidibles. |
24/9 | Clase P. |
1/10 | Clase NP. |
8/10 | Reducciones. Completitud en NP. |
15/10 | Repaso ejercicios. |
22/10 | parcial 2 |
29/10 | Automatas finitos deterministas |
5/11 | Automatas finitos no deterministas |
12/11 | Automatas finitos con transiciones $\epsilon$ |
19/11 | parcial 3 |
26/11 | recuperatorios |
Bibliografía
- ‘Computabilidad, Complejidad y Verificación de Programas’, Rosenfeld e Irazábal, 2013
- ‘Introducción a la teoría de autómatas, lenguajes y computación’, Hopcroft, Motwani y Ullman, 2007
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 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)
- dar la definición de un AFD que reconozca algun lenguaje dado o modelice algun problema dado
- convertir un AFND en un AFD
- convertir un AFND-e en un AFD