1. 0.- Preliminar. (Temporalització: 3 h.)
2. 0.1.- Llenguatges formals.
3. 0.2.- Jerarquia de Chomsky.
4. 0.3.- Enumerabilitat.
5. 1.- Calculabilitat I: Màquines de Turing. (Temporalització: 7 h.)
6. 1.1.- Model bàsic.
7. 1.2.- Disseny.
8. 1.3.- Models equivalents.
9. 1.4.- MT Universal
10. 1.5.- Llenguatges estructurats per frase.
11. 1.6.- Hipòtesi de Church.
12. 2.- Calculabilitat II: Models de Càlcul equivalents. (Temporalització: 5 h.)
13. 2.1.- Funcions Recursives.
14. 2.2.- Màquines RAMs.
15. 2.3.- Llenguatges de Programació Elemental.
16. 2.4.- Conclusions.
17. 3.- Indecidibilitat. (Temporalització: 9 h.)
18. 3.1.- Indecidibilitat en llenguatges.
19. 3.2.- Reduccions.
20. 3.3.- Teorema de Rice.
21. 3.4.- Indecidibilitat en llenguatges incontextuals.
22. 4.- Complexitat. (Temporalització: 6 h.)
23. 4.1.- Les classes P i NP.
24. 4.2.- La classe NP-Complet.
25. 4.3.- La classe co-NP.
Mètodes docents:
(Mig quadrimestre)
Classes de teoria: 4 hores setmanals
Laboratori: 2 hora setmanal
Tipus d'exàmens:
Teoria: Prova final (0..10)
Laboratori:Treballs personals (0..10)
Nota final:teoria x 0,80 + laboratori x 0,20(Sempre i quan es superin ambdues parts).