1. Llenguatges Regulars
1.1. Autòmats Finits
1.2. Indeterminisme
1.3. Expressions Regulars
1.4. Llenguatges No-regulars
2. Llenguatges Lliures de Context
2.1. Gramàtiques Lliures de Context
2.2. Autòmats de Pila
2.3. Llenguatges No-lliures de Context
3. Tesis de Church-Turing
3.1. Maquines de Turing
3.2. Variants de Màquines de Turing
3.3. Definició d'algorisme
4. Decidibilitat
4.1. Llenguatges decidibles
4.2. El problema de l'aturada
5. Reducibilitat
5.1. Problemes indecidibles
5.2. Un simple problema indecidible
5.3. Funció de Reducibilitat
6. Complexitat en Temps
6.1. Mesura de complexitat
6.2. La classe P
6.3. La classe NP
6.4. NP-completessa
6.5. Problemes NP-complets
Classes de teoria: 2 hores setmanals
Classes de suport a la teoria (exemples/exercicis): 2 hores bisetmanals (s'imparteixen d'acord a la seqüència marcada pel contingut teòric setmanal).
La qualificació de l’assignatura es realitzarà en base a dos aspectes:
A) Resolució de problemes
Els alumnes resoldran (en paral·lel a les classes i en grups de 2) un conjunt de 4 problemes que s'aniran enunciant en el moment de teoria adecuat, i que obligatòriament s'hauran d'entregar dins d'un termini preestablert (veure apartat c.3 a "Observacions i Recomanacions" d'aquesta assignatura). Els enunciats indicaràn la forma i data d'entrega. Aquest apartat es valorarà de 0..10 on cadascún dels problemes hi aportarà un pes específic corresponent al seu propi número (de 1 a 4). Compte: cal entregar TOTS els problemes per poder aprovar l'assignatura. Un sol problema no entregat comporta un no-presentat (NP) en aquest apartat i per extensió, al promig de l'assignatura.
B) Coneixement sobre el contingut del temari
Es basarà en una prova individual per escrit i sense cap suport documental. La data i hora és la determinada en l'horari d'exàmens de l'EPS. Aquest apartat es valorarà de 0..10 excepte si l'estudiant no es presenta a la prova (nota apartat = NP).
Nota final: si A o B són un no-presentat (NP), la nota final serà NP. Altrament, és la mitjana dels dos apartat previs (i.e., (A+B)/2).
No hi haurà cap altra prova ni entrega per l'evaluació de l'assignatura. En conseqüència, la nota final comença a definir-se a partir de la primera entrega de l'apartat A i finalitza amb l'apartat B. Cal ser-ne conscient i treballar des del primer dia. No existeix el concepte de recuperació ni pels problemes a entregar (A) ni per la prova de continguts (B).
Sempre que es consideri oportú, es podrà citar personalment a un alumne per tal de que demostri el seu coneixement i participació en les solucions dels problemes. Tanmateix, es recorda als estudiants que es disposen de programes automàtics de detecció de còpia d'una eficacia demostrada. La còpia comporta un 0 per tots els implicats.
Pels alumnes no-presencials o semi-presencials, el sistema d'evaluació és exactament el mateix.
Es recomana llegiu també l'apartat "Observacions i Recomanacions" d'aquesta assignatura.
Criteris específics de la nota «No Presentat»:
Es considerarà no-presentat a l'estudiant que no entregui un dels problemes de l'apartat d'evaluació A o bé, que no es presenti a la prova escrita indicada a l'apartat B d'evaluació.
a) Les comunicacions de l'assignatura es faran per escrit mitjançant "Avisos" a la Meva-UdG de l'assignatura.
b) Tota la documentació necessaria la podreu trobar a http://ima.udg.edu/~rigau/FC/
c) És de lectura OBLIGATÒRIA:
c.1) Tota la informació relativa a l'assignatura constarà al document electrònic "Syllabus" de l'assignatura.
c.2) Seguirem el llibre de text de Michael Sipser (veure Bibliografia). Específicament:
- 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 situarse en el vocabulari, notació, i com a recordatori de conceptes previs de matemàtiques. L'ús continuu del text al llarg de totes les classes expositives facilitarà el treball als estudiants amb assistència discontinua per motius de treball (o altres).
c.3) Tanmateix, es facilitarà el document electrònic "Complementary Theory & Problems". Informació adicional de teoria i problemes. En aquest document hi consten també els problemes corresponents a l'apartat A de l'evaluació.