Teoría de la Computación

Instructor: Alberto Pacheco


Material | Bibliografía | Ponderación | Calificaciones | La Calculadora

Objetivo General

Al finalizar este curso se espera que el alumno:
  1. Conozca los elementos principales en que se sustenta la teoría de la computación
  2. Sea capaz de comprender y aplicar herramientas empleadas en diseño de lenguajes de programación

    Temario

  1. CONCEPTOS MATEMÁTICOS PRELIMINARES (5 horas).
  2. LENGUAJES (4 horas)
  3. TEORÍA DE AUTÓMATAS Y LENGUAJES REGULARES (10 horas)
  4. TEORÍA DE GRAMÁTICAS (10 horas)
  5. ANÁLISIS DETERMINÍSTICO (6 horas)
  6. MÁQUINAS DE TURING (4 horas)
  7. TÓPICOS AVANZADOS (4 horas)

Temas y Subtemas

1. CONCEPTOS MATEMÁTICOS PRELIMINARES
     1.1 RELACIONES Y FUNCIONES
     1.2 CONJUNTOS CONTABLES Y NO-CONTABLES
     1.3 DEFINICIONES RECURSIVAS
     1.4 INDUCCIÓN MATEMÁTICA

2. LENGUAJES
     2.1 ESPECIFICACIÓN DE UN LENGUAJE
     2.2 STRINGS Y LENGUAJES
     2.3 EXPRESIONES Y CONJUNTOS REGULARES

3. TEORÍA DE AUTÓMATAS Y LENGUAJES REGULARES
     3.1 AUTÓMATAS FINITOS DETERMINÍSTICOS
     3.2 AUTÓMATAS NO-DETERMINÍSTICOS
     3.3 AUTÓMATAS FINITOS Y CONJUNTOS REGULARES

4. TEORÍA DE GRAMÁTICAS
     4.1 JERARQUÍA DE CHOMSKY
     4.2 GRAMÁTICAS REGULARES Y AUTÓMATAS FINOS
     4.3 GRAMÁTICAS LIBRES DE CONTEXTO Y LENGUAJES
     4.4 AMBIGÜEDAD
     4.5 AUTÓMATAS PUSHDOWN Y LENGUAJES LIBRES DE CONTEXTO

5. ANÁLISIS DETERMINÍSTICOS
     5.1 GRAMÁTICAS LL(k)
     5.2 TOP-DOWN PARSING
     5.3 GRAMÁTICAS LR(k)
     5.4 BOTTOM-UP PARSING

6. MÁQUINAS DE TURING
     6.1 LA MÁQUINA ESTÁNDAR DE TURING
     6.2 MÁQUINAS DE DOBLE CINTA

7. TÓPICOS AVANZADOS
     7.1 DECIDIBILIDAD
     7.2 COMPUTABILIDAD
     7.3 PROBLEMAS P Y NP

Programación de Exámenes

  1. Primer Parcial: Ma 5 Sept
  2. Segundo Parcial: Ma 3 Oct
  3. Tercer Parcial: Ma 7 Nov
  4. Exámen Final: - - -

Ponderación

45 % Exámenes Parciales (3)
35 % Examen Final
20 % Tareas, Proyectos y exámenes rápidos
(
Tareas Extra: 2-5 décimas / reporte )

Bibliografía:


Alberto Pacheco (alberto@acm.org).
Ultima actualización: 2000/10/03


Material | Objetivo | Temario | Bibliografía | Calificaciones | Ponderación |