Plan del curso de Teoria de la Computación

Saludos,

A continuación el plan del curso de Teoría de la Computación. El material básico está disponible en línea por bondad de la Prof. Hilda Yelitza Contreras, aqui:

http://webdelprofesor.ula.ve/ingenieria/hyelitza

Tenemos pautado las evaluaciones siguientes:

Primer parcial: lunes, 7 de Noviembre de 2011.
Segundo parcial: lunes 28, de Noviembre de 2011.
Tercer parcial: miércoles, 18 de Enero de 2012.
Recuperativo: lunes, 23 de Enero de 2012.

El plan general puede verse en esta imagen:

Con mas de detalle y permitiendo flexibilidad para ajustes en el semestre:

Plan de Evaluación. Teoría de la Computación



Unidad I: Autómatas finitos y Expresiones Regulares.
Unidad II: Gramáticas Libres de Contexto.
Unidad III: Lenguajes Libres de Contexto y Autómatas de Pila.
Unidad IV: Máquinas de Turing.



3 parciales. 20% el primero. 30% el segundo y 50% el último. 1 recuperativo que sustituye al peor.



Planificación del curso de Teoría de la Computación
Semestre B2011
Profesor: Jacinto Dávila

Semana	Día	Contenido
1	1	Presentación del curso, plan de evaluación, repaso de conceptos básicos (conjuntos, inducción matemática), la historia de A. Turing, reflexiones sobre una práctica para una teoría (qué es un lenguaje de programación).
2	1	Autómatas Finitos (AF) Deterministas (AFD). Ejemplos y ejercicios (Grafos, Digrafos, Relaciones y Funciones). Seleccionando lenguajes de programación y aplicaciones para ejercicios (posix, grep, sed, awk, gedit, netbeans, eclipse, emacs, shells, xml, perl, c, c++, java, php, javascript, phyton, prolog, hasckel)
	2	Autómatas Finitos No Deteministas (AFND). Cómo reducir un AFND a un AFD. Ejemplos y ejercicios.
	3	Programación de un autómata finito.
3	1	Repaso. Editores (vi, gedit, emacs, netbeans).
	2	Autómatas con Salidas: Moore y Mealy. Relación entre Moore y Mealy. Ejemplos y ejercicios.
	3	Expresiones regulares: definición, ejemplos y ejercicios. Posix, Grep, Awk.
4	1	Equivalencia entre AF y expresiones regulares. Perl
	2	Más de la equivalencia entre AF y expresiones regulares. Revisión.
	3	Propiedades de los lenguajes regulares: Lema del bombeo.
5	1	Parcial 1.
	2	Propiedades de los lenguajes regulares: propiedades de clausura.
	3	Propiedades de los lenguajes regulares: algoritmos de decisión.
6	1	Propiedades de los lenguajes regulares: minimización. Ejemplos.
	2	Gramáticas: definición, clasificación de Chomsky, Gramáticas regulares, Gramáticas libres de contexto, GLC. Ejemplos.
	3	Repaso. (Shell)
7	1	Más sobre GLC: árboles de derivación, ambigüedad. Simplificación de GLC: eliminación de transiciones nulas (Árbol).
	2	Más sobre simplificación de GLC: eliminar producciones unitarias, símbolos inútiles. Forma Normal de Chomsky (FNC).
	3	Más sobre simplificación de GLC: Forma Normal de Greybach (FNG).
8	1	Parcial 2.
	2	Autómatas de Pila (AP): Definición, funcionamiento. Ejemplos.
	3	Tipos de autómatas de Pila: equivalencia entre AP de Estado Final y AP por Pila Vacía. Relación GLC y AP. Ejemplos.
9	1	Más de la relación GLC y AP. AP deterministas.
	2	XML para un lenguaje libre de contexto.
	3	Repaso (c, c++, java, php, javascript, phyton)
10	1	Propiedades de los lenguajes libre de contexto (LLC) : Lema del bombeo.
	2	Propiedades de los lenguajes libres de contexto (LLC): Lema de Orden, propiedades cerradas. Ejercicios.
	3	Propiedades de los lenguajes libres de contexto (LLC): Algoritmos de decisión y parser CYK.
11	1	Repaso (prolog y hasckel)
	2	Máquinas de Turing (MT): modelo básico. La hipótesis de Church/Turing. ¿Cómo podría computarse de otra manera?
	3	Modelos extendidos. Programación de máquinas de turing. Ejemplos.
12	1	MT Calculadora de funciones, MT generadora de lenguajes. Ejemplos.
	2	MT como modelo de la computación. Los límites de la computación.
	3	Parcial 3.
13	1	Recuperativo.