Teoria De La Computacion

INSTITUTO TECNOLOGICO DE ACAPULCO.







INDICE.
UNIDAD I: INTRODUCCIÓN.
1.1 AUTÓMATAS, COMPUTABILIDAD Y
COMPLEJIDAD. (4)
1.2 NOCIONES MATEMÁTICAS. (5)
1.3.1 CONJUNTOS (5-11)
1.3.2FUNCIONES Y RELACIONES (11-14)
1.2.3 CADENAS Y LENGUAJES (14)
1.3 INDUCCIÓN MATEMÁTICA. (14-15)

UNIDAD II: LENGUAJES REGULARES.

2.1 AUTÓMATAS FINITOS (15-16)
2.1.1 AUTÓMATAS FINITOS
DETERMINÍSTICOS. (16-17)
2.1.2 AUTÓMATAS FINITOS NO
DETERMÍNISTICOS (18)
2.2 EXPRESIONES REGULARES. (18-19)
2.3 LENGUAJES NO REGULARES. (19)UNIDAD III: LENGUAJES LIBRES DE
CONTEXTO.

3.1 GRAMÁTICAS LIBRES DE CONTEXTO. (20-21)
3.2 ÁRBOLES DE DERIVACIÓN. (21-23)
3.3 FORMAS NORMALES DE CHOMSKY. (23)
3.4 FORMAS NORMALES DE GREIBACH. (23-24)
3.5 ELIMINACIÓN DE FACTORES COMUNES
IZQUIERDOS. (24-25)
3.6 ELIMINACIÓN DE RECURSIVIDAD IZQUIERDA. (25-26)
3.7 ELIMINACIÓN DE LA AMBIGÜEDAD.(26-27)
3.8 AUTÓMATAS PUSH-DOWN. (27-28)
3.9 LENGUAJES NO REGULARES. (28-31)

UNIDAD IV: MÁQUINA DE TURING.

4.1 DEFINICIÓN FORMAL DE UNA MÁQUINA DE
TURING. (31-32)
4.2 CONSTRUCCIÓN MODULAR DE UNA MÁQUINA
DE TURING. (33-36)
4.3 LENGUAJES ACEPTADOS POR LA MT. (36-37)
4.4 VARIANTES DE UNA MÁQUINA DE TURING. (37-40)
4.5 PROBLEMAS DE HILBERT.(40-42)

UNIDAD V: DECIBILIDAD.

5.1 LENGUAJES DECIDIBLES. (42-43)
5.2 EL PROBLEMAS DE HALTING. (44)
5.3 DECIDIBILIDAD DE TEORÍAS LÓGICAS. (44-45)
UNIDAD VI: REDUCIBILIDAD.

6.1 PROBLEMAS INSOLUBLES PARA LA TEORÍA
DE LENGUAJES. (45-46)
6.2 UN PROBLEMA SIMPLE INSOLUBLE. (46)
6.3 FUNCIONES COMPUTABLES. (47)
6.4 REDUCIBILIDAD DE TURING.(47-48)

UNIDAD 1: INTRODUCCION.

* Herramienta para definir la gramática de los LP
* Modelo matemático.
* Programa automatizado.
Autómata Proceso automatizado.
* Modelo automatizado Programable (matemático), que se apoya de si mismo a través de ciclos o procesos para darnos un resultado o un programa automatizado.
CLASIFICACION DE LOS AUTOMATAS.

* AutómataFinito Determinantico.
Autómata
* Autómata Finito No Determinantico

Tiempo real: Al dar una instrucción o petición, el ordenador tiene que dar una respuesta instantáneamente.
1.1 AUTOMATAS, COMPUTABILIDAD Y COMPLEJIDAD.
COMPUTABILIDAD: Parte de la computación que resuelve problemas a través de procesos computables lógicamente.
La teoría de la computabilidad, es la parte de lacomputación que estudio los problemas de decisión que pueden ser resueltos con algoritmos o equivalentemente con una maquina de turing.
COMPLEJIDAD: Es el estudio de la cantidad de tiempo y espacio de memoria que toma la ejecución de un conjunto dado.
La teoría de la complejidad computacional, es la que estudia los recursos necesarios para resolver el problema en paralelo.

1.2 NOCIONESMATEMATICAS.

Agrupación, clase o colección de objetos
Conjunto denominados elementos.


Un conjunto determinado por extensión, es un conjunto donde todos los elementos se
* EXTENSION identifican.

DETERMINACION
DE UN
CONJUNTO Un conjunto determinado por comprensión,
* COMPRENSION se identifica por una sola
Característica.Representación de un conjunto: {…}
A= {0, 1, 2, 3, 4, 5, 6, 7}
B= {1, 3, 5, 7,…, n}
C= {X:x es una vocal}

1.3.1 CONJUNTOS.

OPERACIONES SOBRE CONJUNTOS.

* UNION.
La unión de una colección de conjuntos: S {s1, s2, s3, …,} es el conjunto de todos los elementos contenidos en al menos uno de los conjuntos s1, s2, s3, y se representa:
S= s1 U s2 U s3
La unión de dos conjuntos A y...