1. Introducció
1.1. Autòmats, computabilitat, i complexitat
1.2. Notació matemàtica i terminologia
1.3. Definicions, teoremes, i demostracions
1.4. Tipus de demostracions
2. Llenguatges regulars
2.1. Gramàtiques regulars
2.2. Autòmats finits
2.3. Indeterminisme
2.4. Expressions regulars
2.5. Llenguatges no regulars
3. Llenguatges lliures de context
3.1. Gramàtiques lliures de context
3.2. Autòmats de pila
3.3. Llenguatges no lliures de context
4. Tesi de Church-Turing
4.1. Gramàtiques sense restriccions
4.2. Màquines de Turing
4.3. Variants de màquines de Turing
4.4. Definició d'algorisme
5. Decidibilitat
5.1. Llenguatges decidibles
5.2. El problema de l'aturada
6. Reduïbilitat
6.1. Problemes indecidibles
6.2. Un problema indecidible simple
6.3. Funció de reduïbilitat
7. Complexitat en temps
7.1. Mesura de complexitat
7.2. La classe P
7.3. La classe NP
7.4. NP-completesa
7.5. Alguns problemes NP-complets
Es faran classes de teoria setmanals més classes de suport a la teoria (exemples/exercicis) bisetmanals.
La qualificació de l’assignatura es realitzarà en base a dos aspectes:
A) Resolució d'exercicis (avaluació continuada).
Els alumnes resoldran duran el curs una sèrie d'exercicis relacionats amb el temari de l'assignatura, que caldrà lliurar obligatòriament dins del termini que s'estableixi. L'enunciat indicarà la forma i data límit de lliurament. S'avaluaran entre 0 i 10. La no presentació comptabilitzarà com a 0.
Hi haurà un bloc d'exercicis de la part de llenguatges, gramàtiques i autòmats (A1) i un bloc d'exercicis de la part de calculabilitat i complexitat (A2).
B) Examen (avaluació del coneixement del temari treballat a classe i de la bibliografia de l'assignatura).
Es basarà en una prova individual per escrit i sense cap suport documental. La data i hora serà la determinada en l'horari d'exàmens de l'EPS. Aquest apartat es valorarà entre 0 i 10 excepte si l'estudiant no es presenta a la prova (nota apartat = NP).
La nota final (NF) es calcularà de la següent manera:
NF := NP si B = NP
NF := B si B < 3
NF := max(B, ((A1 + A2) / 2 + B) / 2) si B >= 3
Sempre que es consideri oportú, es podrà citar personalment a un alumne per tal de que demostri el seu coneixement i participació en l'apartat A. Es recorda als estudiants que es disposen de programes automàtics de detecció de còpia d'una eficàcia demostrada. La còpia comporta un 0 en la qualificació final per a tots els implicats.
Per als alumnes no presencials o semipresencials, el sistema d'avaluació és exactament el mateix atès que s'empra el nucli d'un llibre de text que facilita el seguiment de l'assignatura (veure bibliografia).
Per accedir a l'examen de recuperació caldrà haver-se presentat a l'examen final (excepte casos justificats) i tenir l'assignatura suspesa. Notar que un examen suspès no dóna dret a recuperació si l'assignatura queda aprovada. La qualificació de l'examen de recuperació substituirà la de l'examen final.
Es recomana llegir també l'apartat 'Observacions i Recomanacions'.
Criteris específics de la nota «No Presentat»:
L'alumne obrindrà la nota de 'No Presentat' si no es presenta a examen.
Avaluació única:
L'avaluació única consistirà únicament de l'examen final, amb un valor del 100% en lloc del 50%.
Requisits mínims per aprovar:
Per considerar superada l’assignatura, caldrà obtenir una qualificació més gran o igual que 5 de la nota final (NF) calculada com s'ha descrit a l'apartat 'Criteris de qualificació'.
a) Tota la documentació necessària la podreu trobar al web de l'assignatura en el moment adequat.
b) De lectura OBLIGATÒRIA:
Del llibre de text de Michael Sipser (veure bibliografia):
- Part 1: capítols 1 i 2.
- Part 2: capítols 3, 4, i 5.
- Part 3: capítol 7.
El capítol 0 d'introducció es bàsic per situar-se en el vocabulari, notació, i com a recordatori de conceptes previs de matemàtiques. L'ús continu del text al llarg de totes les classes expositives facilitarà el treball als estudiants amb assistència discontínua per motius de treball (o altres).