Teoría de la Computación (TC)

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.

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.

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.

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.

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

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

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.