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

TC Trabajo de investigación.

Realizar una investigación del Estado del Arte de las Teorías de DECIBILIDAD Y REDUCIBILIDAD así como la aplicación de las mismas en la Teoría de la Computación (Lenguajes y Autómatas).
Entregar una carpeta digital conteniendo: una subcarpeta con el material investigado (archivos html, pdf, doc, etc.), una síntesis en Word 2003 y una presentación multimedia en power-point 2003.

Unidad 5.- Decibilidad.

5.1 Lenguajes Decidibles.
5.2 El problemas de Halting.
5.3 Decidibilidad de Teorías Lógicas.

Introducción:

Decidibilidad (Introducción)
De Wikipedia, la enciclopedia libre

En lógica, el término decidible se refiere a la existencia de un método efectivo para determinar si un objeto es miembro de un conjunto de fórmulas.
Un sistema lógico o teoría es decidible si el conjunto de todas las fórmulas válidas en el sistema es decidible. Es decir, existe un algoritmo tal que para cada fórmula del sistema es capaz de decidir en un número finito de pasos si la fórmula es válida o no en el sistema.

Ejemplo: La Lógica proposicional es decidible, porque existe para ella un algoritmo; la tabla de verdad tal que para cada fórmula que combina M formulas atómicas, hay un número máximo N = 2M de pasos tal que tras completar estos N pasos el algoritmo siempre decidirá si la fórmula es válida o no. Cada "paso" del algoritmo ha sido definido como una línea de la tabla de verdad.

La lógica de primer orden es decidible si se limita a predicados con un solo argumento (ver cálculo de predicados monódicos). Si se incluyen predicados con dos o más argumentos, no es decidible.

Toda teoría completa recursivamente enumerable es decidible. Por otro lado, toda teoría que incluya aritmética básica es no decidible.

Lenguajes decideibles: http://webdiis.unizar.es/~elvira/lengForm.pdf
Lógica y Computación: http://www.filosoficas.unam.mx/~morado/LogicaHoy/alvarado.htm
Lenguajes decidibles por una Máquina de Turing: http://www.filosoficas.unam.mx/~morado/LogicaHoy/alvarado.htm
Problemas de decisión:
http://www2.ing.puc.cl/~jabaier/iic2212/decision.pdf
http://es.wikipedia.org/wiki/Problema_de_decisión
Demostración del problema del paro: http://antoniojaimes.tripod.com/icc/presentaciones/c4-demo-paro.pdf
Algoritmo de Inferencia Gramatical: http://www.uv.es/hmr/Tesis/HTML/

Unidad 6.- Reducibilidad.

6.1 Problemas insolubles para la teoría de
lenguajes.
6.2 Un problema simple insoluble.
6.3 Funciones computables.
6.4 Reducibilidad de Turing.

Complejidad Computacional: https://www.unoweb-s.uji.es/0304/IS17/ficheros0/theList/tema10.pdfIntroducciòn a la TCC: http://www3.uji.es/~martine/DOC/E45/apuntes/node47.htmlEnsayo TCC: http://sisbib.unmsm.edu.pe/bibvirtualdata/publicaciones/risi/N1_2004/a14.pdfComo ganar a la Ruleta en 21 dias: http://www-2.dc.uba.ar/materias/plp/20052C/download/charla_figueira.pdfNP-Completitud: https://www.fdi.ucm.es/profesor/csegura/mtp0304/apuntes/NPcompletitud.pdf
Computabilidad y Algoritmos: http://juanfc.lcc.uma.es/EDU/EP/2.DescrAlgoritmos.pdf
Clases Polinómiales: http://delta.cs.cinvestav.mx/~gmorales/complex/node149.html
Presentación uniforme de la teória descriptiva de la complejidad computacional: http://www2.scielo.org.ve/scielo.php?script=sci_arttext&pid=S0001-55042002000200003&lng=pt...&nrm=iso

Otros enlaces de interes:
Sitio general de IA y Sistemas: http://pub.ufasta.edu.ar/ohcop/mapa.html

TEORIA DE LA COMPUTACION.

OBJETIVO DE LA MATERIA: OBJETIVO DE LA MATERIA: EL ESTUDIANTE COMPRENDERÁ LA BASE TEÓRICA PARA LA CONSTRUCCIÓN DE SISTEMAS FORMALES Y UTILIZARÁ TÉCNICAS DE PROGRAMACIÓN PARA MODELARLOS.

Profesor: M.C. José Angel Toledo Alvarez
http://angel-toledo.blogspot.com/
taja2005@gmail.com

EXAMEN DE RECONOCIMIENTO

1.- Defina los siguientes conceptos: alfabeto, carácter, palabra y lenguaje.

2.- Explique ampliamente que es la Teoría de Conjuntos y para que sirve.

3.- Describa de manera esquemática como esta construido (estructuralmente) nuestro idioma ESPAÑOL.

4.- Explique ampliamente que es la LOGICA PROPOSICIONAL y para que sirve.

5.- Explique que diferencias existen entre una TAUTOLOGIA y una CONTRADICCION.

6.- Describa el concepto de AUTOMATA, su clasificación y sus aplicaciones.

7.- Con la ayuda de un ejemplo, describa que es una TABLA DE VERDAD y como se utiliza.

8.- Realice un GRAFO (o DIGRAFO) que ilustre el comportamiento de una máquina expendedora de refrescos.

9.- Explique ampliamente cuales son las fases de un COMPILADOR (al realizar la ejecución de un programa).

10.- Explique ampliamente cual es el factor común entre un COMPILADOR, un TRADUCTOR, un ENCRIPTADOR y el IDIOMA ZAPOTECO.

Unidad 1.- Introducción.

1.1 Autómatas, computabilidad y
complejidad.
1.2 Nociones matemáticas.
1.2.1 Conjuntos
1.2.2 Funciones y Relaciones
1.2.3 Cadenas y Lenguajes
1.3 Inducción matemática.

Transparencia de Informática teórica (Grupo EVANNAI): http://et.evannai.inf.uc3m.es/docencia/it_II/transparencias.html

The Alan Turing Home Page: http://www.turing.org.uk/turing/

The Virtual Museum of Computing: http://vmoc.museophile.sbu.ac.uk/

Informática y Matemáticas: http://biblioweb.sindominio.net/telematica/conf-ernesto/node1.html

Lenguajes Formales: http://webdiis.unizar.es/~elvira/lengForm.pdf

Teoría de la Computabilidad Computacional: http://sisbib.unmsm.edu.pe/bibvirtualdata/publicaciones/risi/N1_2004/a14.pdf
Recordatorio de Lógica Proposicional: http://es.wikipedia.org/wiki/Lógica_proposicional

Recordatorio de Teoría de Conjuntos: http://es.wikipedia.org/wiki/Teorìa_de_conjuntos

Ejercicios de Matemáticas Discretas: http://canek.uam.mx/MatDis/Matdis.htm

Actividad 1 U1: Tomando como refrencia las lecturas recomendadas, realice un mapa mental-conceptual que ilustre y clarifique el tema de la unidad 1.

TC Cuestionario 1 Introducción.

1.- Defina los siguientes conceptos: Autómatas, computabilidad y complejidad computacional.

2.- Explique ampliamente en que consiste la Teoría de Conjuntos y cuales son sus aplicaciones.

3.- Explique ampliamente en que consiste la Lógica Proposicional y cuales son sus aplicaciones.

4.- Defina y de tres ejemplos de los siguientes conceptos: Conjuntos, Funciones y Relaciones, Cadenas y Lenguajes.

5.- Explique ampliamente que es la “Inducción matemática”, para que se utiliza y de tres ejemplos de su aplicación.

6.- 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.

7.- 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.

8.- Defina los siguientes conceptos y de tres ejemplos de cada uno de ellos: Fórmulas equivalentes, Forma Normal Conjuntiva, Forma Normal Disyuntiva

9.- 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 )

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

Unidad 2.- Lenguajes regulares.

2.1 Autómatas finitos
2.1.1 Autómatas finitos
determinísticos.
2.1.2 Autómatas finitos No
determínisticos
2.2 Expresiones regulares.
2.3 Lenguajes no regulares.

Expresiones Regulares: http://es.wikipedia.org/wiki/Expresiones_regulares

Conociendo a las expresiones regulares: http://www.zonasiete.org/manual/ch13s03.html

Sitio de Expresiones Regulares: http://www.regular-expressions.info/

Lenguajes Regulares: http://es.wikipedia.org/wiki/Lenguaje_regular

Lenguajes regulares: http://www.itculiacan.edu.mx/apuntes/maestros/Ricardo%20Quintero/Mis%20Webs/parte%202%20Lenguajes%20Regulares/2Lenguajes%20regulares.htm

http://ji.ehu.es/kea-mac1/cas/Temario_fitxategiak/Tema2.pdf

Autómatas y Lenguajes Formales: http://pisuerga.inf.ubu.es/cgosorio/ALeF/#contenidos

Lenguajes, Gramáticas y Autómatas: http://pisuerga.inf.ubu.es/cgosorio/ALeF/UD23/lenguajes.pdf

Apuntes de Lenguajes y Autómatas: http://platon.escet.urjc.es/grupo/docencia/automatas/apuntes/

Autómatas Finitos y Lenguajes Regulares: http://dac.escet.urjc.es/~lrincon/uned/ta1/ta1-tema1.pdf

Actividad 1 U2: Tomando como refrencia las lecturas recomendadas, realice un mapa mental-conceptual que ilustre y clarifique el tema de la unidad 2.

Cuestionario de la unidad 2:

1.- Explique en que consisten las Expresiones Regulares y los Lenguajes Regulares y de 5 ejemplos reales de cada uno de estos.

2.- Explique en que consiste el AFD y el AFD y de 5 ejemplos reales de su aplicación (que ilustre cada uno de sus elementos).

3.- Explique ampliamente el lema de Bombeo y su aplicación práctica en la Teória de la Computación.

4.- Explique ampliamente en que consiste la notación BNF e ilustre su aplicación en un lenguaje de programación de alto nivel.

5.- 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.

3.1 Gramáticas libres de contexto.
3.2 Árboles de derivación.
3.3 Formas normales de Chomsky.
3.4 Formas normales de Greibach.
3.5 Eliminación de Factores Comunes
izquierdos.
3.6 Eliminación de recursividad izquierda.
3.7 Eliminación de la ambigüedad.
3.8 Autómatas Push-Down.
3.9 Lenguajes no regulares.

Gramamática Libre de Contexto: http://es.wikipedia.org/wiki/Gramática_libre_de_contexto

Lenguajes Libres de Contexto: http://delta.cs.cinvestav.mx/~gmorales/ta/node103.html

Ciencias de la computación: http://www.exa.unicen.edu.ar/catedras/ccomp1/

LLC y Compiladores: http://www.geocities.com/marioztobon/compiladores.htm

LIC y AP: http://www.infor.uva.es/~mluisa/talf/docs/teoria/final1.pdf

Noam Chomsky, Politics or Science: http://homepages.uel.ac.uk/C.Knight/chomsky.htm

AP y LIC: http://dac.escet.urjc.es/~lrincon/uned/ta1/ta1-tema2.pdf

English Lecture: http://en.wikipedia.org/wiki/Context-free_language

Actividad 1 U3: Tomando como refrencia las lecturas recomendadas, realice un mapa mental-conceptual que ilustre y clarifique el tema de la unidad 3.

Ejercicio Práctico U3:

Escriba un programa en JAVA que traduzca una expresión regular en un autómata finitio.

Ref.- Libro "Introducción a la teoría de Autómatas, Lenguajes y Computación." de John E. Hopcroft y Jeffrey D. Ullman.

Unidad 4.- Máquinas de Turing.

4.1 Definición formal de una máquina de
Turing.
4.2 Construcción modular de una máquina
de Turing.
4.3 Lenguajes aceptados por la MT.
4.4 Variantes de una máquina de Turing.
4.5 Problemas de Hilbert.
Máquina de Computación Lógica: http://www.zator.com/Cpp/E0_1_1.htm

MT con Lego: http://www.microsiervos.com/archivo/juegos-y-diversion/maquina-de-turing-de-lego.html

Funciones calculables: http://www.usergioarboleda.edu.co/matematicas/memorias/memorias13/Máquinas%20de%20Post%20y%20de%20Turing.pdf

Máquinas de Turing: http://www.infor.uva.es/~mluisa/talf/docs/teoria/final2.pdf

Máquina de Turing Universal: http://www.infor.uva.es/~mluisa/talf/docs/teoria/final3.pdf

MT y LEF: http://dac.escet.urjc.es/~lrincon/uned/ta1/ta1-tema3.pdf

MT CINVESTAV: http://acme.math.cinvestav.mx/~basico/siete.html

English Lecture: http://www.turing.org.uk/turing/scrapbook/machine.html

Actividad 1 U4: Tomando como refrencia las lecturas recomendadas, realice un mapa mental-conceptual que ilustre y clarifique el tema de la unidad 4.

Actividad 2 U4: Realizar un análisis de los enlaces recomendados (incluyendo la "English Lecture") y realizar un Mapa Mental (Multimedia en ppt) que explique el Que, Quien, Como, Donde, Cuando, Porqué y Para qué de la Máquina de Turing argumentando ampliamente su Modelado Matemático y Algoritmo de funcionamiento.

Unidad 5.- Decibilidad.

5.1 Lenguajes Decidibles.
5.2 El problemas de Halting.
5.3 Decidibilidad de Teorías Lógicas.

Lenguajes decideibles: http://webdiis.unizar.es/~elvira/lengForm.pdf

Lógica y Computación: http://www.filosoficas.unam.mx/~morado/LogicaHoy/alvarado.htm

Lenguajes decidibles por una Máquina de Turing: http://www.filosoficas.unam.mx/~morado/LogicaHoy/alvarado.htm

Problemas de decisión:
http://www2.ing.puc.cl/~jabaier/iic2212/decision.pdf
http://es.wikipedia.org/wiki/Problema_de_decisión

Demostración del problema del paro: http://antoniojaimes.tripod.com/icc/presentaciones/c4-demo-paro.pdf

Algoritmo de Inferencia Gramatical: http://www.uv.es/hmr/Tesis/HTML/

Actividad 1 U5: Tomando como refrencia las lecturas recomendadas, realice un mapa mental-conceptual que ilustre y clarifique el tema de la unidad 5.

Unidad 6.- Reducibilidad.

6.1 Problemas insolubles para la teoría de
lenguajes.
6.2 Un problema simple insoluble.
6.3 Funciones computables.
6.4 Reducibilidad de Turing.

Complejidad Computacional: https://www.unoweb-s.uji.es/0304/IS17/ficheros0/theList/tema10.pdf
Introducciòn a la TCC: http://www3.uji.es/~martine/DOC/E45/apuntes/node47.html

Ensayo TCC: http://sisbib.unmsm.edu.pe/bibvirtualdata/publicaciones/risi/N1_2004/a14.pdf

Como ganar a la Ruleta en 21 dias: http://www-2.dc.uba.ar/materias/plp/20052C/download/charla_figueira.pdf

NP-Completitud: https://www.fdi.ucm.es/profesor/csegura/mtp0304/apuntes/NPcompletitud.pdf

Computabilidad y Algoritmos: http://juanfc.lcc.uma.es/EDU/EP/2.DescrAlgoritmos.pdf

Clases Polinómiales: http://delta.cs.cinvestav.mx/~gmorales/complex/node149.html

Presentación uniforme de la teória descriptiva de la complejidad computacional: http://www2.scielo.org.ve/scielo.php?script=sci_arttext&pid=S0001-55042002000200003&lng=pt...&nrm=iso
Otros enlaces de interes:

Sitio general de IA y Sistemas: http://pub.ufasta.edu.ar/ohcop/mapa.html

Actividad 1 U5: Tomando como refrencia las lecturas recomendadas, realice un mapa mental-conceptual que ilustre y clarifique el tema de la unidad 5.

TC Cierto o Falso: Define los conceptos y Analiza los comentarios que se encuentran en este espacio y verifica si es ciero o falso...

CONCEPTOS:
Gramatica Formal
Arbol de derivacion
Formas normales de Greibach
Formas normales de Chomsky

FRASE DE CONCEPTOS
”La gramatica formal permite especificar un lenguaje o lengua aunque para representar graficamente la forma normal de chomsky y su cadena de lenguaje un arbol de derivacion aunque para gramaticas libres de contexto enta la forma normal de Greibach.”
Cierto? o Falso?

Enlaces de interés para:
Gramática Libre de Contexto: http://es.wikipedia.org/wiki/Gramática_libre_de_contexto
Lenguajes Libres de Contexto: http://delta.cs.cinvestav.mx/~gmorales/ta/node103.html
Ciencias de la computación: http://www.exa.unicen.edu.ar/catedras/ccomp1/
LLC y Compiladores: http://www.geocities.com/marioztobon/compiladores.htm
Noam Chomsky, Politics or Science: http://homepages.uel.ac.uk/C.Knight/chomsky.htm

CONCEPTOS:
- Máquina de Turing
- Teoria de la Computabilidad
- Almacenamiento en la unidad
- Algoritmo

FRASE:
"Una máquina de Turing es una máquina que resuelve problemas que tienen solución algoritmica y son estudiaos por la Teoria de la Computabilidad, necesita un conjunto de 'reglas de transición' o 'pasos' para hacer su 'trabajo', una MT consta de una cinta con caracteres del lenguaje, un cabezal lectura/escritura y un cabezal donde almacena o borra los caracteres del lenguaje que ha validado."
Cierto? o Falso?

Enlaces:
1.- Máquina de Turing y alamacenamiento en la unidad: http://es.wikipedia.org/wiki/M%C3%A1quina_de_Turing2.- Algoritmo: http://luda.uam.mx/curso1/Introduccion%20a%20la%
20Programacion/algoritmo.htm3.- Teoría de la Computabilidad: http://es.wikipedia.org/wiki/Teor%C3%ADa_de_la_computabilidad

CONCEPTOS:
Induccion matematica
Automata
Ambigüedad
Eliminacion de la recursividad por la izquierda

FRASE
" La teoria de la computacion inicio con la induccion matematica la cual conllevo a hacer automatas las cuales pueden tener ambigüedad y estos pueden ser validadas con una gramatica la cual puede emplearse la eliminacion de la recursividad por la izquierda"
¿Cierto? o ¿Falso?

ENLACES DE INTERES:
http://es.wikipedia.org/wiki/Aut%C3%B3mata
http://es.wikipedia.org/wiki/Inducci%C3%B3n_matem%C3%A1tica

CONCEPTOS
*Chomsky
*Maquina de Turing
*Forma normal de chomshy

FRASE
"CHOMSKY DOMINO LA GRAMATICA GENERATIVA DONDE SE FORMULA LA FORMA NORMAL DE CHOMSKY QUE SIRVE PARA REPRESENTAR GRAMATICAS DONDE UTILIZO COMO BASE LA MAQUINA DE TURING EN LA CUAL SE FORMALIZA EL CONCEPTO DE ALGORITMO"
¿Cierto? o ¿Falso?

REFERENCIAS:
*MAQUINA DE TURING
http://etsiit.ugr.es/alumnos/mlii/Maquina%20de%20Turing.htm
http://www.zator.com/Cpp/E0_1_1.htm
*CHOMSKY
http://es.wikipedia.org/wiki/Noam_Chomsky
*FORMA NORMAL DE CHOMSKY
http://trevinca.ei.uvigo.es/~formella/doc/talf05/talf/node42.html

CONCEPTOS:
*Gramática de tipo 0.
*Maquina de turing.
*Lenguajes aceptados por la maquina de turing.
*Problemas computables y no computables.

"Para toda gramática de tipo 0 existe una maquina de Turing que se mueve sobre una secuencia lineal de datos que pueden resolver problemas computables y no computables."
¿Cierto o Falso?

ENLACES:
GRAMATICA TIPO 0 : http://www.frt.utn.edu.ar/sistemas/sintaxis/page15.html
MAQUINA TURING: http://es.wikipedia.org/wiki/M%C3%A1quina_de_Turing
LENGUAJES COMPUTABLES Y NO COMPUTABLES: http://campusvirtual.unex.es/cala/epistemowikia/index.php?title=Funciones_computables
LENGUAJES ACEPTADOS POR UNA MAQUINA DE TURING: http://es.wikipedia.org/wiki/Teor%C3%ADa_de_la_computabilidad

CONCEPTOS:
• Computabilidad.
• Componentes de un Automata (AFD).
• Lenguajes No Regulares.
• Lema de Bombeo.

FRASE:
“La teoria de la computabilidad es la parte de la computación que estudia los problemas de descicion que pueden ser resueltos con un algoritmo o equivalentemente con una maquina de Turing, una maquina de Turing tiene caracteristicas para leer información, esta información es un lenguaje para ello existen lenguajes que no son regulares y tecnicas para demostrarlo un ejemplo de ellos es el Lema de bombeo. Si el lenguaje L es regular existe un AFD que o reconoce. Un AFD esta constituido por una 5-tupla, estos componentes son: un conjunto de estados, un alfabeto, un estado inicial, un estado final y una regla de transicion”
¿Cierto? ó ¿Falso?

Enlaces de Interes.
Computabilidad
http://es.wikipedia.org/wiki/Teor%C3%ADa_de_la_computabilidad

Componentes de un Automata (AFD).
http://es.wikipedia.org/wiki/Aut%C3%B3mata_finito
Lenguajes No Regulares.
http://es.wikipedia.org/wiki/Lenguaje_regular
Lema de Bombeo.
http://www.itculiacan.edu.mx/apuntes/maestros/Ricardo%20Quintero/Mis%20Webs/parte%202%20Lenguajes%20Regulares/38El%20lema%20de%20bombeo.htm

CONCEPTOS:
*Simbolo
*Numero Computable
*Lenguajes aceptados por la Maquina de Turing

FRASES
"Los simbolos pueden ser caracteres o digitos(numeros) que pueden ser aproximados por un algoritmo y estos pueden ser aceptados por una Maquina de Turing ya que los lenguajes formales son aceptados por este."
-- Cierto? ó Falso?--

Links:
http://es.wikipedia.org/wiki/Teor%C3%ADa_de_la_computabilidad
http://es.wikipedia.org/wiki/Simbolo
http://biblioweb.sindominio.net/telematica/conf-ernesto/node15.html
http://mx.geocities.com/pcmuseo/infmaquinaturing.htm

CONCEPTOS:
Construcción de maquinas de turing
Bloques de construcción básicos
Expresiones regulares
Forma normal de greibach

“Frase”:

La construcción de maquinas de turing se hace mediante los bloques de construcción los cuales nos sirven para analizar expresiones regulares los cuales a su ves están formados por la forma normal de greibach
Cierto???? o falso????

Referencias:

http://es.wikipedia.org/wiki/M%C3%A1quina_de_Turing
http://es.wikipedia.org/wiki/Expresi%C3%B3n_regular
http://es.wikipedia.org/wiki/Lenguaje_regular

CONCEPTOS:
ANALISIS FUNCIONAL
FUNCIONES
AUTOMATA FINITO NO DETERMINISTICO


FRASE:
”El análisis funcional de las matemáticas donde la transición que se ejecuta en una etapa dada de un AFN puede ser incierta, y específicamente del análisis que trata del estudio de espacios de funciones.”
¿CIERTO? ¿FALSO?

ENLACES:
http://es.wikipedia.org/wiki/An%C3%A1lisis_funcional
http://www.itp.edu.mx/Tutoriales/Lenguajes_y_automatas/Principal.htm

CONCEPTOS:
Conjunto
grafo
recursividad
maquina de turing

Un grafo es un conjunto de objetos llamados vertices o nodos unidos por enlaces llamados aristas y Un conjunto es recursivo si la correspondiente función característica (que asigna el número 1 a los objetos que pertenecen al conjunto, y 0 a los que no le pertenecen) es computable en si toda definición recursiva es Turing-computable, y a la inversa, toda función computable en el sentido de Turing es recursiva
Cierto? o Falso?

Enlaces de interés para:
Conjunto: http://es.wikipedia.org/wiki/Conjunto
grafo: http://es.wikipedia.org/wiki/Grafo
recursividad: http://www.exa.unicen.edu.ar/catedras/ccomp1/
Maquina de turing: http://es.wikipedia.org/wiki/M%C3%A1quina_de_Turing

CONCEPTOS:
- Lenguaje Formal
- Máquina de Turing
- Algoritmo

" Un algoritmo es una herramienta que permite hallar la solución de un problema y su definición queda formalizada por la Máquina de Turing"

Links:
Algoritmo
http://es.wikipedia.org/wiki/Algoritmo
Maquina de Turing
http://es.wikipedia.org/wiki/M%C3%A1quina_de_Turing
Lenguajes Regulares
http://es.wikipedia.org/wiki/Lenguaje_formal

CONCEPTOS:
función computable
árbol de derivación
cadena de caracteres
maquina de turing

"UNA FUNCIÓN COMPUTABLE ES UNA CADENA DE CARACTERES QUE PUEDE SER LEIDA POR UNA MQUINA DE TURING,ESTE ENUNCIADO ES CONOCIDO COMO LA TESIS CHURCH-TURING"
¿Cierto? o ¿Falso?

LINK
www.geocities.com/pilosopica/filosofica13.htm
es.wikipedia.org/wiki/Función_computable
es.wikipedia.org/wiki/Tesis_de_Church-Turing

CONCEPTOS:
Yacc y Lex
Eliminacion de factores comunes izquierdos.
Tablas de transición


FRASE:
”Las tablas de transiciones se da entre ambas funciones de estado finito de un sistema que recibe una cadena en cada caso exactamente lo mismo que retorna la que genera las mas usuales.”
¿Cierto? ¿Falso?

ENLACES:

http://es.wikipedia.org/wiki/Yacc
http://es.wikipedia.org/wiki/Herramienta_de_programaci%C3%B3n_Lex
http://es.wikipedia.org/wiki/Tabla_de_transici%C3%B3n_de_estados

CONCEPTOS:
gramática
gramática libre de contexto
autómata finito no deterministico
maquina de turing


FRASE DE CONCEPTOS:
”La gramatica es el estudio de las reglas y principios. Donde existe gramaticas libres de contexto que parte de un simbolo no terminal, donde son las base para la creacion de automas, como lo es la maquina de turing.”
CIERTO O FALSO??

REFERENCIA:
http://es.wikipedia.org/wiki/Gram%C3%A1tica_libre_de_contexto
http://es.wikipedia.org/wiki/Aut%C3%B3mata_finito
http://es.wikipedia.org/wiki/M%C3%A1quina_de_Turing

CONCEPTOS: DECIBILIDAD, LENGUAJES DECIDIBLES, LEX YACC Y BISON.

FRASE:
Bison convierte la descripcion formal de un lenguaje, escrita como una gramatica libre de contexto. Los lenguajes decidibles so cadenas de palabras calculabres mediante funciones recursivas, un sistema formal es decidible si existe un algoritmo que diga en tiempo finito si una cadena cualquiera es un teorema o no lo es.

¿CIERTO? O ¿FALSO?

REFERENCIAS:

http://www.dsic.upv.es/~jsilva/uned/automatas1/Teoria%20de%20Automatas%20I%20(sesion%209).ppt
http://www.filosoficas.unam.mx/~morado/LogicaHoy/alvarado.htm
http://www.mitecnologico.com/Main/Decibilidad
http://es.wikipedia.org/wiki/Decibilidad
http://www.velug.org.ve/archivo/l-linux-2001-March/025778.html
http://www.ii.uam.es/~mdlcruz/docencia/compiladores/2002_2003/compiladores_02_03_yacc_bison.pdf

Responsable: Evert Valencia Chung
web:http://mx.geocities.com/takiwebox.com
Blog: http://takiwebox.blogspot.com
mail: taki_87@hotmail.com

Conceptos:

Arbol Sintáctico
Funcion
Eliminacion
Concatenacion

Frase:

"El ARBOL SINTACTICO es un árbol que refleja la estructura sintáctica de la entrada de datos. Este se representa mediante nodos, los cuales tienen una determinada FUNCION dentro del arbol. A la relacion entre cada nodo se le denomina CONCATENACION, la cual indica que de un nodo A se deriva un nodo B. Asimismo cuando un nodo no cumple las condiciones requeridas se procede a la ELIMINACION de dicho nodo".

Cierto? o Falso?

Enlances de Apoyo:

http://www.suigeneris.org/kb/display/UCABTI/Fases+de+un+Compilador

http://www.dcc.uchile.cl/~lmateu/CC10A99/Apuntes/sintaxis/index.html

CONCEPTOS:

automata finito deterministico
gramatica libre de contexto
formulacion de halting
funcion

frase de conceptos:


la gramatica libre de contexto es un conjunto de variables con los cuales representa un lenguaje, que se describen de manera de simbolos en funcion del AFD el cual puede formar estados y conjunto de transiciones, para poder hacer la formulacion de halting...



¿cierto? o ¿falso?


enlaces de interes para ....
gramatica y lenguajes
http://tomba.blogdiario.com/

automatas
http://www.mitecnologico.com/Main/AutomatasFinitosDeterministicosYNoDeterministicos
http://es.wikipedia.org/wiki/Aut%C3%B3mata_finito

funciones
http://abulafia.fciencias.unam.mx/~favio/tc71n1.pdf

CONCEPTOS:
Conjunto
Lenguajes libres de contexto
Autómatas lineales de indices
Recursividad directa

Frase

“Un conjunto de símbolos pueden ser aceptados o rechazados por un autómata lineal de índice que es parte de los lenguajes libes de contexto que se crean a partir de una gramática libre de contexto, esta a su vez puede tener una recursividad directa.”

Cierto o falso?
Referencias:
http://www.exa.unicen.edu.ar/catedras/ccomp1/Apunte5.pdf
http://es.wikipedia.org/wiki/Conjunto
http://209.85.165.104/search?q=cache:5vE7bTR1IicJ:www.matematicas.unam.mx/jloa/publicaciones/automatasyLenguajes.ps.gz+automata+lineal&hl=es&ct=clnk&cd=1&gl=mx
http://delta.cs.cinvestav.mx/~mcintosh/oldweb/tesis/genaro/node3.html
http://www.lcc.uma.es/~pastrana/EP/trabajos/17.pdf

CONCEPTOS:
Gramatica libre de contexto
Gramatica enformal normal de chomsky
Lenguaje libre de contexto

Oracion de los conceptos

Analice y decida

"Un lenguaje libre de contexto es aque producido por un gramatica libre de contexto, estas a su ves pueden ser llamadas gramaticas enformal normal de Chomsky"

Cierto? o Falso?


Ref:
http://es.wikipedia.org/wiki/Gram%C3%A1tica_libre_de_contexto
http://es.wikipedia.org/wiki/Lenguaje_libre_de_contexto
http://es.wikipedia.org/wiki/Forma_normal_de_Chomsky

CONCEPTOS:
lenguajes no regulares
conjunto
jerarquia de chomsky
gramatica libre de contexto

MI FRASE:
un ejemplo de conjunto seria
utilizar a la jerarquia de chomsky como entidad y como atributos a la gramatica libre de comntexto, la clasificacion de lenguajes como los no regulares.

cierto o falso?

ENLACES DE INTERES:

http://es.wikipedia.org/wiki/Jerarqu%C3%ADa_de_Chomsky

http://es.wikipedia.org/wiki/Gram%C3%A1tica_libre_de_contexto

http://es.wikipedia.org/wiki/Lenguaje_regular

http://es.wikipedia.org/wiki/Conjunto

Preguntas:

1. ¿Que funcion realiza un analizador lexico?
2. ¿En base a que se realizara el automata, en base al proyecto o funcion?
3. ¿Caracteristicas importantes del analizador?
4. ¿Cuales son las reglas basicas que realiza a un analizador lexico?
5. ¿Como se crea un analizador lexico?


Links de apoyo para las respuestas de las preguntas:

http://es.wikipedia.org/wiki/Analizador_l%C3%A9xico

http://nereida.deioc.ull.es/~lhp/perlexamples/node436.html

http://www.dsic.upv.es/~jsilva/uned/compiladores/Apuntes02.pdf

CONCEPTOS:
Arbol sintáctico
Forma normal de Greibach
Automatas de Push-Down
Automatas de dos pilas

FRASE:
Una gramática libre de contexto puede ser representada gracias a la forma normal de greibach, las gramaticas pueden ser representadas por un arbol sintactico y por un automata, de los cuales se derivan los automatas push-down y los automatas de dos pilas.

¿cierto? o ¿falso?

enlaces para

forma normal de greibach
es.wikipedia.org/wiki/Forma_normal_de_Greibach

arbol sintactico
www.uni.edu/~castillo/arbol-how.htm

automatas push-down
www.monografias.com/trabajos16/automatas-y-gramaticas/automatas-y-gramaticas.shtml

automatas de dos pilas
es.wikipedia.org/wiki/Tesis_de_Church-Turing

TRADUCTOR

1. ¿Cuàl seria la gramatica de un traductor?

2.Dentro de la gramatica en lo que corresponde al vocabulario ¿estarìan todos los signos de puntuacion?

3. Qué es un traductor de texto ?


4. ¿que se necesita para hacer un traductor de idioma extranjero?

5. Ventajas y desventajas de un traductor
enlaces

http://www.misrespuestas.com/que-es-un-traductor-de-texto.html

http://www.solociencia.com/informatica/06020728.htm
http://www.depi.itch.edu.mx/apacheco/expo/html/ai11/nl.html

http://www.c5.cl/Congreso/HTML/paper11.htm

http://lorien.die.upm.es/~lapiz/rtth/JORNADAS/II/articulos/6.pdf


CONCEPTOS:
- Máquina de Turing
- Contexto
- Forma normal de Greibach
- Gramatica

FRASE:

"La forma normal de greibach es un tipo estandar para representar gramaticas ya que la gramatica es el estudio de la lengua en cuanto a forma y estructura y significado."

Cierto? o Falso?

Enlaces:

1.- Gramatica: http://es.wikipedia.org/wiki/Gram%C3%A1tica

2.- forma normal de greibach: http://delta.cs.cinvestav.mx/~gmorales/ta/node113.html

3.- maquina de turing: http://www.zator.com/Cpp/E0_1_1.htm

4.- Contexto
http://es.wikipedia.org/wiki/Contexto

Exposición de proyectos de fin de semestre.

Preparar el estand de Teoría de la Computación para presentar todos los proyectos resultantes del semestre en curso. Todos participarán en un rol de guardias (de 10:00 a 16:00 hrs el día previsto para la exposición) para explicar el estand y los proyectos a los visitantes, jefes y directivos del ITM.Lugar de exposición para ISC en el Centro de Computo.

Nota: Esta es la actividad de cierre para todo el curso, se tomará en cuenta para la calificación final.

Así mismo se les invita a participar en la 2a. exposición de proyectos de investigación, en la cual se presentaran avances, protocolos y reflexiones sobre la investigación como opción de titulación.

Esperando contar con su participación activa, los saludo cordialmente.

M.C. José Angel Toledo Alvarez