Estudia

• Introducció a la indecidibilitat dels problemes.
• Anàlisi de diversos mòdels de càlcul.
• Estudi de la dificultad dels processos de càlcul i adquisició d'un coneixement teòric de les seves limitacions.
• Classificació dels problemes d'acord a la seva complexitat.

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.

• JG Brookshear (1993). Teroia de la computacion. Addison-Wesley.
• JE Hopcroft, R Motwani, JD Ullman (2001). Introduccion a la Teoria de Automatas, lenguajes, y computacion. Addison-Wesley.

Activitats d'avaluació:

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,75 + laboratori x 0,25(Sempre i quan es superin ambdues parts).

- Disseny i implementació d' algorismes en els diversos models de càlcul.
- Anàlisi de problemes indecidibles (reduccions)
Els alumnes desenvoluparan pel seu compte els següents treballs pràctics :
a) Disseny de MT's.
b) Resolucions d'indecidibilitat.
c) Càlculs de complexitat.