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: De Fires Girona -> Nadal)
Classes de teoria: 4 hores setmanals
Problemes/Pràctiques: 2 hora setmanals
L’avaluació de l’assignatura es realitzarà en base a:
- Un examen teòric (sense apunts ni llibres) en la data de cada convocatòria.
- Treball pràctic (individual o compartit amb un altre alumne) a lliurar en un termini preestablert (pot constar d'un o diversos exercicis).
En la convocatòria ordinària l’avaluació es realitzarà en base a l’examen teòric (50%) i a la pràctica (50%). Per fer la mitjana cal un mínim de 4 a la part de teoria. Altrament, la nota és la mitjana que pertoqui amb un màxim possible de 4.5.
En la qualificació definitiva, el professor també podrà tenir en compte altres aspectes en relació a la participació de l’alumne en la dinàmica de la classe, i a la realització de treballs voluntaris.
En la convocatòria extraordinària, es manté la qualificació de la part pràctica obtinguda per l’alumne en la convocatòria ordinària, per la qual cosa només haurà de realitzar l’examen teòric. Les condicions de la convocatòria ordinaria es mantenen (50%-50% i mínim). Tanmateix, si l’alumne ho prefereix, podrà voluntariament renunciar a la qualificació obtinguda de la part pràctica i optar perquè la qualificació final es basi només en un examen teòric-pràctic (més extens), en el qual haurà de demostrar que ha assolit els objectius mínims que es perseguien en el treball pràctic. En aquests casos especials, la qualificació màxima queda acotada a 6.
Criteris específics de la nota «No Presentat»:
Es considerarà No Presentat si l'alumne no porta a terme l'exàmen de la part teòrica o bé no presenta el treball pràctic.