Saltar al contingut Menu
Mapa
  • Inicio
  • Información
  • Contacto
  • Mapa

Teoría de la Computación (TC)

Créditos Dept. Tipo Requisitos
9.0 (7.2 ECTS) CS
  • Obligatoria para la EI
  • Optativa para la ETIG
ADA - Prerequisito para la EI , ETIG
MATD - Prerequisito para la EI , ETIG

Profesores

Responsable:  (-)
Otros:(-)

Objectivos Generales

Ofrecer una estructura teórica que permita analizar los procesos de cálculo en función de la dificultad de computación. Estudiar la relación entre generatividad (gramáticas) y resolubilidad (autómatas), de cara a su utilización en compiladores. Adquirir un conocimiento teórico de las limitaciones de estos procesos (problemas indecidibles). Los estudiantes, después de cursar esta asignatura, deberían conocer los grados de complejidad intrínsecos de los lenguajes regulares e incontextuales. Dispondrán de algunas herramientas para describir estos lenguajes, reconocerlos y caracterizarlos.

Objectivos Específicos

Conocimientos

  1. Complejidad de algoritmos y complejidad de problemas.
  2. Procesos de computación que requieren sólo memoria finita.Autómatas finitos.
  3. Gramáticas formales. Análisis y compilación. Generatividad.
  4. Relación entre procesos generativos y procesos reconocitivos.
  5. Jerarquización de los problemas según la complejidad.
  6. Los límites lógicos de la capacidad computacional.
  7. Problemas indecidibles.

Habilidades

  1. Encontrar el modelo de computación más simple para cada problema.
  2. Disponer de herramientas que permitan descartar soluciones demasiado simples para problemas dados.
  3. Disponer de herramientas que permitan describir adecuadamente los procesos de cálculo.

Competencias

  1. Capacidad para el razonamiento crítico y lógico-matemático.
  2. Capacidad para transformar enunciados informales a enunciados formales, y al revés.
  3. Capacidad para aplicar los conocimientos de matemáticas y lógica a la resolución de problemas.
  4. Capacidad para crear y utilizar modelos de la realidad.
  5. Capacidad de análisis y de síntesis.

Contenidos

Horas estimadas de:

T P L Alt L Ext. Est O. Ext.
Teoria Problemas Laboratorio Otras actividades Laboratorio externo Estudio Otras horas fuera del horario fijado

1. Lenguajes formales
T      P      L      Alt    L Ext. Est    O. Ext. Total 
3,0 1,0 0 0 0 4,0 0 8,0
1. Introducción.

2. Alfabetos y palabras.

3. Operaciones con palabras.

4. Lenguajes. Concatenación.

5. Otras operaciones con lenguajes.

6. Morfismos y sustituciones.

2. Gramáticas incontextuales
T      P      L      Alt    L Ext. Est    O. Ext. Total 
4,0 6,0 0 0 0 10,0 0 20,0
1. Introducción.

2. Definición.

3. Árbol de derivación. Ambigüedad.

4. Verificación de gramáticas.

5. Operaciones básicas con gramáticas.

6. La intersección de dos CFL puede no ser CFL.

3. Normalización de gramáticas
T      P      L      Alt    L Ext. Est    O. Ext. Total 
2,0 2,0 0 0 0 4,0 0 8,0
1. Introducción.

2. Eliminación de producciones nulas.

3. Eliminación de producciones unarias.

4. Eliminación de símbolos inútiles.

5. Gramáticas depuradas.

6. Forma normal de Chomsky.

4. Autómatas finitos
T      P      L      Alt    L Ext. Est    O. Ext. Total 
4,0 4,0 0 0 0 8,0 0 16,0
1. Introducción.

2. Autómatas finitos deterministas.

3. Verificación de autómatas finitos.

4. Autómatas finitos indeterministas.

5. Equivalencia de los NFA con los DFA.

6. Autómatas finitos con lambda-transiciones.

7. Operaciones básicas con autómatas.

8. Lenguajes no regulares.

5. Minimización de autómatas finitos
T      P      L      Alt    L Ext. Est    O. Ext. Total 
2,0 2,0 0 0 0 4,0 0 8,0
1. Minimización de un DFA.

2. Algoritmo de minimización.

3. Sobre la talla del DFA mínimo.

4. Equivalencia entre autómatas.

6. Expresiones regulares y gramáticas regulares
T      P      L      Alt    L Ext. Est    O. Ext. Total 
4,0 4,0 0 0 0 8,0 0 16,0
1. Introducción.

2. Expresiones regulares.

3. Ecuaciones lineales entre lenguajes. Lema de Arden.

4. Sistemas de ecuaciones lineales asociados a un NFA.

5. Gramáticas regulares.

6. Correspondencia entre gramáticas regulares y autómatas finitos.

7. Morfismos y sustituciones de lenguajes regulares.

7. Propiedades de iteración
T      P      L      Alt    L Ext. Est    O. Ext. Total 
2,0 4,0 0 0 0 6,0 0 12,0
1. Lema de bombeo de lenguajes regulares.

2. Lemas de bombeo de lenguajes incontextuales.

8. Autómatas con pila
T      P      L      Alt    L Ext. Est    O. Ext. Total 
4,0 2,0 0 0 0 6,0 0 12,0
1. Introducción.

2. Autómatas con pila deterministas.

3. Autómatas con pila indeterministas.

4. Equivalencia entre autómatas con pila y gramáticas incontextuales.

5. Propiedades de cierre de los CFL y de los DCFL.

9. Autómatas bidireccionales y jerarquía de Chomsky
T      P      L      Alt    L Ext. Est    O. Ext. Total 
2,0 2,0 0 0 0 4,0 0 8,0
1. Introducción.

2. Autómatas finitos bidireccionales.

3. Autómatas con pila bidireccionales.

4. Relación entre las familias de lenguajes estudiadas.

5. La jerarquía de Chomsky. Gramáticas de tipo 0.

10. Máquinas de Turing
T      P      L      Alt    L Ext. Est    O. Ext. Total 
3,0 3,0 0 0 0 6,0 0 12,0
1. Introducción a la calculabilidad. Problemas indecidibles.
2. Definición de TM. Interpretación.
3. Computación. Convergencia y divergencia.
4. Lenguaje reconocido y función computada por una TM.
5. TM de parada segura. Tiempo de cálculo.
6. Lenguajes enumerables recursivamente y lenguajes decidibles.
7. Funciones computables.
8. Extensiones del modelo básico de TM.

11. Máquinas de Turing y algoritmos
T      P      L      Alt    L Ext. Est    O. Ext. Total 
2,0 2,0 0 0 0 4,0 0 8,0
1. Los esquemas algorítmicos básicos.

2. Codificación de las TM.

3. Intérpretes y simuladores. La TM universal.

4. La tesis de Church-Turing.

12. Computabilidad y decidibilidad
T      P      L      Alt    L Ext. Est    O. Ext. Total 
2,0 2,0 0 0 0 4,0 0 8,0
1. Teorema de la proyección.

2. Propiedades de cierre de los lenguajes e.r. y decidibles.

3. Teorema del complementario.

4. Algunos lenguajes e.r. El lenguaje K.

5. Lenguajes no decidibles.

13. Reductibilidad y completitud
T      P      L      Alt    L Ext. Est    O. Ext. Total 
2,0 5,0 0 0 0 7,0 0 14,0
1. Reducción entre problemas.

2. Propiedades de las reducciones. Ejemplos de reducciones.

3. Teorema de Rice.

4. Conjuntos enumerable recursivamente completos.

14. Algunos problemas indecidibles clásicos
T      P      L      Alt    L Ext. Est    O. Ext. Total 
3,0 0 0 0 0 3,0 0 6,0
1. El problema de las palabras de Thue.

2. El problema de la correspondencia de Post.

3. Problemas indecidibles sobre lenguajes incontextuales.

15. Computación acotada. Espacio y tiempo
T      P      L      Alt    L Ext. Est    O. Ext. Total 
2,0 0 0 0 0 2,0 0 4,0
1. Tiempo de cálculo.

2. Espacio de cálculo.

3. Clases de complejidad.

4. Propiedades.


Total por tipo T      P      L      Alt    L Ext. Est    O. Ext. Total 
41,0 39,0 0 0 0 80,0 0 160,0
Horas adicionales dedicadas a la evaluación 20,0
Total horas de trabajo para el estudiante 180,0

Metodología docente

La metodología docente y la evaluación tienen como objetivo incrementar el nivel de actividad de los alumnos en clase, potenciar el autoaprendizaje y mejorar el aprendizaje de la materia en general.

En clase no se imparten los contenidos de la materia. Estos se dan en vídeos accesibles a través de internet. Las clases se aprovechan para resolver dudas de los alumnos y realizar evaluación contínua.

Método de evaluación

La evaluación final se obtiene de 3 notas, el examen final F (valorado entre 0 y 10 puntos), 3 controles realizados a lo largo del curso C (que en total valen entre 0 y 1 punto), y la evaluación de las presentaciones en la pizarra de los problemas que se han asignado a los alumnos (entre 0 y 2.5 puntos). La evaluación de la asignatura se obtiene de la fórmula:

max(F,min(10,0.75+C+P))

Observamos que la expresión 0.75F+C+P puede sumar hasta 11. De ahí que se coja el mínimo con 10. El máximo con F se hace para evitar que la evaluación continua perjudique a quien haga bien el examen final.

Bibliografía básica

  • Rafel Cases, Lluís Màrquez Llenguatges, gramàtiques i autòmats : curs bàsic, Edicions UPC, 2003.
  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman Introduction to automata theory, languages, and computation, Pearson Education International, 2003.
  • Dean Kelley Automata and formal languages : an introduction, Prentice Hall, 1995.
  • Maria Serna ... [et al.] Els Límits de la computació : indecidibilitat i NP-completesa, Edicions UPC, 2001.
  • Michael Sipser Introduction to the theory of computation, Thomson Course Technology, 2006.

Bibliografía complementaria

  • J. Glenn Brookshear Teoría de la computación : lenguajes formales, autómatas y complejidad, Addison-Wesley Iberoamericana, 1993.
  • Joaquim Gabarró Vallès Informàtica clàssica : autòmats i gramàtiques, indecidibilitat, parallelisme massiu, Eumo, 1995.
  • Jozef Gruska Foundations of computing, International Thomson Computer Press, 1997.
  • Efim Kinber, Carl Smith Theory of computing : a gentle introduction, Prentice-Hall, 2001.
  • Dexter C. Kozen. Automata and computability, Springer-Verlag,, 1997.
  • Harry R. Lewis, Christos H. Papadimitriou Elements of the theory of computation, Prentice-Hall,, 1998.
  • Dan A. Simovici, Richard L. Tenney Theory of formal languages with applications, World Scientific, 1999.
  • Joan Vancells i Flotats Teoria d'autòmats i llenguatges formals I, Universitat Oberta de Catalunya, 2000.
  • Derik Wood Theory of computation, Harper & Row, 1987.

Enlaces web

(Información no introducida)

Capacidades previas

Capacidad para expresar en fórmulas lógicas los enunciados descritos en lengua común.
Capacidad para manipular fórmulas lógicas.
Conocimientos algebraicos fundamentales: monoides, grupos, cierres, morfismos.
Conocimientos básicos de combinatoria.
Capacidad para utilizar con facilidad las propiedades de un álgebra de Boole.
Conocimiento de las estructuras de datos básicos y de algoritmia fundamental.
Capacidad para evaluar la complejidad temporal de un algoritmo.


Compartir

 
logo FIB © Facultad de Informática de Barcelona - Contacto - RSS
Esta web utiliza cookies propias para ofrecerle una mejor experiencia y servicio. Si continúa la navegación, entendemos que acepta nuestra política de cookies. Versión clássica Versión móvil