Teoria De La Computacion

Unidad 1 Introduccion teoria de la computacion

1.1 Automatas, Computabilidad y Complejidad

1.2 Nociones Matematicas de Teoria de la Computacion

1.2.1 Conjuntos Tc

1.2.2 Funciones Y Relaciones TC

1.2.3 Cadenas y Lenguajes

1.3 Induccion Matematica

Unidad 2 Lenguajes Regulares

2.1 Automatas Finitos

2.1.1 Automatas Finitos Deterministicos

2.1.2 Automatas Finitos no Deterministicos

2.2 Expresiones Regulares

2.3 Lenguajes no Regulares

Unidad 3 Lenguajes Libres de contexto

3.1 Gramaticas Libres de Contexto

3.2 Arboles de Derivacion

3.3 Formas Normales de Chomsky

3.4 Formas Normales de Greibach

3.5 Eliminacion de Factores Comunes Izquierdos

3.6 Eliminacion Recursividad Izquierda

3.7 Eliminacion De Ambiguedad

3.8 Automatas PushDown

3.9 Lenguajes no Regulares

Unidad 4 Maquina de Turing

4.1 Definicion Formal Maquina de Turing

4.2 Construccion Modular Maquina de Turing

4.3 Lenguajes aceptados por Maquina de Turing

4.4 Variantes Maquina de Turing

4.5 Problemas de Hilbert

Unidad 5 Decibilidad

5.1 Lenguajes Decidibles

5.2 El Problemas de Halting

5.3 Decidibilidad Teorias Logicas

Unidad 6 Reducibilidad

6.1 Problemas Insolubles Teoria de Lenguajes

6.2 Un Problema simple Insoluble

6.3 Funciones Computables

6.4 Reducibilidad De Turing