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. Autòmats finits
2.2. Indeterminisme
2.3. Expressions regulars
2.4. Llenguatges no regulars
3. Llenguatges lliures de context
3.1. Gramàtiques lliures de context
3.2. Autòmats amb pila
4. Tesi de Church-Turing
4.1. Màquines de Turing
4.2. Variants de màquines de Turing
4.3. Definició d'algorisme
5. Decidibilitat
5.1. Llenguatges decidibles
5.2. Indecidibilitat
6. Reduïbilitat
6.1. Problemes indecidibles
6.2. Un problema indecidible simple
6.3. Funcions de reducció
7. Complexitat en temps
7.1. Mesures 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 expositives de teoria setmanals i classes de suport a la teoria (repàs, discussions, exemples i exercicis) en grups reduïts, bisetmanalment.
La qualificació de l’assignatura es realitzarà en base a dos aspectes:
A) Resolució d'exercicis (avaluació continuada).
Els alumnes resoldran durant 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.
Important: caldrà l'assistència a un mínim de 2/3 (dos terços) de les classes de grup petit per tal que es tingui en compte la nota d'avaluació continuada. Addicionalment, sempre que es consideri oportú, es podrà citar personalment a un alumne per tal de que demostri el seu coneixement i participació en el exercicis no presencials d'avaluació continuada.
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 a 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 s'ha assistit a menys de 2/3 de les classes de grup petit o B < 4
NF := max(B, (A + B) / 2), altrament
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).
La qualificació de l'examen de recuperació substitueix la de l'examen final.
Es recomana donar un cop d'ull a 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 l'examen.
Avaluació única:
L'avaluació única consisteix 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ó'.
Les comunicacions de l'assignatura es faran per escrit mitjançant el fòrum d'avisos i notícies del Moodle.
La interacció escrita (bidireccional) amb els estudiants tindrà lloc via fòrums del Moodle, reservant el correu electrònic només per a qüestions privades. Qualsevol consulta que es realitzi per correu electrònic que sigui d'interès general serà redirigida al fòrum corresponent del Moodle.
a) Tota la documentació necessària la podreu trobar al web de l'assignatura en el moment adequat.
b) Lectura recomanada. Del llibre de text de Michael Sipser (veure bibliografia): capítols 1-5 i 7. El capítol 0 és una introducció bàsica per situar-se en el vocabulari i notació de l'assignatura, i també serveix de recordatori de conceptes previs de matemàtiques. L'ús continu del text al llarg del curs facilitarà el treball als estudiants amb assistència discontínua per motius de treball (o altres).