CUESTIONARIOS GENERALES DE "TEORIA DE LA COMPUTACIÓN"

Unidad 1.- Introducción

1. Define los siguientes conceptos: Autómatas, computabilidad y complejidad computacional.
2. Ilustre un listado de Nociones matemáticas que se aplican en la Teoría de la Computación (20 minimos).
3. En que consiste la teoría de Conjuntos y cual es su aplicación.
4. Define y explique ampliamente que son las Funciones y las Relaciones e ilustre su aplicación en la Teoría de la Computación.
5. Define los siguientes conceptos: Cadenas y Lenguajes e ilustre su aplicación en la Teoría de la Computación.
6. Explique ampliamente en que consiste la “Inducción matemática” e ilustre esta con 5 ejemplos diferentes donde se aplica.
7. Defina los siguientes conceptos: Autómatas, computabilidad y complejidad computacional.
8. Explique ampliamente en que consiste la Teoría de Conjuntos y cuales son sus aplicaciones.
9. Explique ampliamente en que consiste la Lógica Proposicional y cuales son sus aplicaciones.
10. Defina y de tres ejemplos de los siguientes conceptos: Conjuntos, Funciones y Relaciones, Cadenas y Lenguajes.
11. Explique ampliamente que es la “Inducción matemática”, para que se utiliza y de tres ejemplos de su aplicación.
12. Defina los siguientes conceptos y de tres ejemplos de cada uno de ellos: Carácter, Símbolo, Alfabeto, palabra, cadena de caracteres, lenguaje, gramática, sintaxis, semántica.
13. Explique cual es la diferencia entre un cuantificador existencial y un cuantificador universal y de tres ejemplos de la aplicación de cada uno de ellos.
14. Defina los siguientes conceptos y de tres ejemplos de cada uno de ellos: Fórmulas equivalentes, Forma Normal Conjuntiva, Forma Normal Disyuntiva
15. Realice las siguientes demostraciones:

( p "y" q )’ <--> p’ "o" q’
( p "o" q ) "o" r <--> p "o" ( q "o" r )
( p <--> q ) <--> r <--> p <--> ( q <--> r )

16. Explique ampliamente cuales son los axiomas de Peano y de tres ejemplos de su aplicación.

Unidad 2.- Lenguajes Regulares

1. Define que es un Autómatas finitos determinísticos y cuales son sus elementos consitutivos (explique cada uno de ellos).
2. Define en que consiste un Autómatas finitos No determínisticos y cuales son sus elementos consitutivos (explique cada uno de ellos).
3. Define en que consisten las Expresiones regulares e ilustre su modelo matemático explcando cada uno de sus elementos.
4. Define en que consisten los Lenguajes no regulares e ilustre su modelo matemático explcando cada uno de sus elementos.
5. Explique en que consisten las Expresiones Regulares y los Lenguajes Regulares y de 5 ejemplos reales de cada uno de estos.
6. Explique en que consiste el AFD y el AFND y de 5 ejemplos reales de su aplicación (que ilustre cada uno de sus elementos).
7. Explique ampliamente el lema de Bombeo y su aplicación práctica en la Teória de la Computación.
8. Explique ampliamente en que consiste la notación BNF e ilustre su aplicación en un lenguaje de programación de alto nivel.
9. Realice el Análisis y Diseño de un Lenguaje Regular y su Autómata correspondiente que valide diferentes expresiones polinómicas de segundo grado.

Unidad 3.- Lenguajes Libres de Contexto

1. Define en que consisten las Gramáticas libres de contexto.
2. Define en que consisten los Árboles de derivación.
3. Explique ampliamente cuales son las propiedades de los Arboles de Derivación.
4. Define en que consisten las Formas normales de Chomsky.
5. Define en que consisten las Formas normales de Greibach.
6. Explique en que consiste la Eliminación de Factores Comunes izquierdos.
7. Explique en que consiste la Eliminación de recursividad izquierda.
8. Explique en que consiste la Eliminación de la ambigüedad.
9. Define en que consiste un Autómatas Push-Down y cuales son sus elementos (describe cada uno de ellos).
10. Define en que consisten los Lenguajes no regulares.
11. Ilustre el diseño de un Autómata Push-Down.
12. Explique ampliamente en que consiste la función de un Compilador.
13. Cuales son las clasificaciones de un Compilador

Unidad 4.- Maquinas de Turing

1. Que es y en que consiste una Maquina de Turing
2. Cuales son los elementos que constituyen una Maquina de Turing
3. ¿Qué operaciones puede realizar una Maquina de Turing
4. Como se lleva a cabo el proceso de reconocimiento de una cadena con una Maquina de Turing
5. Define en que consiste una Máquina de Turing Cuántica
6. Como se denominan los lenguajes aceptados por una Máquina de Turing
7. Ilustre la clasificación extensa de las MT y sus derivados
8. En que consiste la MT de varias cintas
9. Que son las MT deterministas y No deterministas
10. De que depende el movimiento de una MT
11. Cuales son los procesos que puede realizar una MT
12. Como se codifica una MT
13. Como decide una MT determinar que acción debe de tomar
14. Explique en que consiste la Construcción modular de una MT
15. Defina matemáticamente cuales son los lenguajes que acepta una MT
16. Defina que es el problema de Hilbert

Unidad 5.- DECIBILIDAD

1. ¿En que consiste la decibilidad de Teorías Lógicas?
2. ¿En Teoría de la Computación, a que se refiere con el concepto de “decibilidad”?
3. ¿En que consiste la Teoría de la Complejidad?
4. Explicar ampliamente en que consiste el primer Teorema de Recursión
5. Que son los lenguajes decidibles
6. ¿Cuál es el objetivo de la Teoría de la Computabilidad?
7. ¿De acuerdo a que criterios, la teoría de la complejidad computacional?
8. ¿En que difiere la Teoría de la Complejidad Computacional respecto a la Teoría de la Computabilidad?
9. Define los Lenguajes Aceptables y Decidibles
10. ¿En que consiste el problema de Halting?

Unidad 6.- REDUCIBILIDAD

1. ¿Qué es reducibilidad?
2. ¿Qué son las funciones computables?
3. ¿Explica en que consiste la Reducibilidad de Turing?
4. ¿Qué es la reducibilidad por mapeo?
5. ¿Para que nos sirve la Reducibilidad?
6. ¿Qué estudia la Teoría de las funciones recursiva?
7. ¿Qué son los axiomas de Blum?
8. ¿Para que pueden ser usados los axiomas de Blum?
9. Ilustra la clasificación de los problemas Resolubles
10. Define en que consiste la Complejidad Temporal y la Complejidad Espacial