Enginyeria en Informàtica (3371)

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

Objectius

L'objetiu d'aquesta assignatura és estudiar quines són les capacitats i limitacions fonamentals inherents als ordinadors.

Temari

Tema 1. Màquines de Turing.

Què és un ordinador?

Tema 2. Resolubilitat (Computability Theory).

Quins problemes poden o no ser resolts per un ordinador?

Tema 3. Complexitat.

Quins problemes poden o no ser resolts de manera eficient?

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