Teoria de la computacion

Teoría de la computación.
|Unidad |Temas |Subtemas |
|1 |Introducción. |Autómatas, computabilidad y complejidad. |
| | |Nociones matemáticas.|
| | |Conjuntos |
| | |Funciones y Relaciones |
| | |Cadenas yLenguajes |
| | |Inducción matemática. |
|2 |Lenguajes regulares. |Autómatas finitos |
| ||Autómatas finitos determinísticos. |
| | |Autómatas finitos No determínisticos |
| | |Expresiones regulares. |
| ||Lenguajes no regulares. |
|3 |Lenguajes libres de contexto. |Gramáticas libres de contexto. |
| | |Árboles de derivación. |
| ||Formas normales de Chomsky. |
| | |Formas normales de Greibach. |
| | |Eliminación de Factores Comunes izquierdos. |
| ||Eliminación de recursividad izquierda. |
| | |Eliminación de la ambigüedad. |
| | |Autómatas Push-Down. |
|| |Lenguajes no regulares. |
|4 |Máquina de Turing. |Definición formal de una máquina de Turing. |
| | |Construcción modular de una máquina de Turing.|
| | |Lenguajes aceptados por la MT. |
| | |Variantes de una máquina de Turing. |
| | |Problemas de Hilbert.|
|5 |Decibilidad. |Lenguajes Decidibles. |
| | |El problemas de Halting. |
| | |Decidibilidad de Teorías Lógicas....