course 2013-2014

Enginyeria Tècnica en Informàtica de Sistemes

Teoria d'Autòmats i Llenguatges Formals II (12449)

Objetivos
El objetivo de esta asignatura es estudiar cuáles son las capacidades y limitaciones fundamentales inherentes a los ordenadores.

Tema 1. Máquinas de Turing.
¿Qué es un ordenador?

Tema 2. Resolubilidad (Computability Theory).
¿Qué problemas pueden o no ser resueltos por un ordenador?

Tema 3. Complejidad.
¿Qué problemas pueden o no ser resueltos de manera eficiente?

Bibiliografía
J.E. HOPCROFT, R. MOTWANI, J.D. ULLMAN: Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 2001.
J.G. BROOKSHEAR. Teoría de la computación, Addison-Wesley Iberoamericana, 1993.
M. SIPSER: Introduction to the theory of computation, PWS Publishing, 1997. __