Teoria de la Computació

Aquest curs ofereix una introducció a la teoria de la computació. S’hi exploren temes clau com els models formals de llenguatges, els autòmats finits i els llenguatges regulars, els llenguatges incontextuals, les màquines de Turing i la teoria de la computabilitat, així com una ullada a la teoria de la complexitat computacional.

L’objectiu principal és aprofundir en la comprensió de la informàtica per part de l’estudiant tot introduint una perspectiva filosòfica—plantejant qüestions fonamentals com:

Què és computable i què no?

i

Per què alguns problemes computacionals són fàcils, d’altres difícils, i alguns impossibles de resoldre?

Els conceptes i tècniques presentats són deliberadament fonamentals, pensats per mantenir la seva rellevància independentment dels canvis en el maquinari o el programari.

El curs inclou un contingut matemàtic important. Es preveu que els estudiants tinguin experiència prèvia amb el concepte de demostració i un cert grau de maduresa matemàtica. Per a aquells que compleixin aquests requisits i sentin curiositat pels límits teòrics de la computació, el curs promet ser intel·lectualment estimulant i alhora gratificant.

Informació administrativa

Professors
Ilario Bonacina (email)
grups: 12P 21P 21L
Despatx: Omega-223
Consultes: Dc 11–13
Antoni Lozano (email)
grups: 22P 22L
Despatx: Omega-233
Consultes: envia un email
Enrique Romero (email)
grups: 11P 11L 12L
Despatx: Omega-319
Consultes: envia un email

Per qüestions administratives de l’assignatura, contacteu amb un dels coordinadors (Ilario Bonacina o Antoni Lozano).

Avisos

Tots els avisos i assignacions d’exercicis es faran a través del racó.

Estructura del curs

La principal característica de la metodologia docent és l’auto-aprenentatge que es basa en la utilització del material docent per conèixer els fonaments tèorics de l’assignatura així com en la resolució de problemes a la pissarra que consoliden aquests coneixements teòrics.

El professor introdueix els fonaments tèorics bàsics de cada tema i soluciona alguns problemes. Els estudiants aprenen la teoria durant el seu temps de treball personal mitjançant l’estudi dels temes indicats pel professor de la bibliografia o dels vídeos i d’altres materials complementaris com apunts, llibres i llistes de problemes resolts, tots ells lliurement accessibles a través de la web.

Durant les hores de problemes, els estudiants surten a la pissarra a explicar solucions a problemes que se’ls hi han assignat amb anterioritat. El professor intervé per corregir una solució, matitzar un argument, o posar émfasi en aquells aspectes que considera rellevants i que no han quedat del tot clars en l’explicació de l’alumne. També pren nota de cada presentació per tal de tenir-la en compte en l’avaluació de l’assignatura.

Durant les hores de laboratori, els estudiants miren de resoldre problemes davant de la màquina que són avaluats automàticament. El professor està present per tal d’atendre els dubtes que els alumnes li puguin plantejar. Els estudiants poden aprofitar aquestes classes per preparar els problemes que se’ls hi han assignat amb anterioritat, però també per estudiar el material teòric si no ho han fet abans pel seu compte, i per preguntar dubtes sobre la teoria.

Referències

El llibre principal de l’assignatura és (Sipser 2013). En català, els llibres (Cases i Màrquez 2003) and (Serna et al. 2004) també cobreixen el material del curs. Hi ha vídeos disponibles en anglès, català i castellà que cobreixen la major part del material del curs.

Cases, Rafel, i Lluís Màrquez. 2003. Llenguatges, gramàtiques i autòmats : curs bàsic. 2a ed. en Aula politècnica. Aula politècnica; 41. FIB. Barcelona: Edicions UPC. https://discovery.upc.edu/permalink/34CSUC_UPC/8e3cvp/alma991002699299706711.
Hopcroft, John E., Rajeev Motwani, i Jeffrey D. Ullman. 2007. Introduction to Automata Theory, Languages, and Computation. 3rd ed. Pearson Addison Wesley. https://discovery.upc.edu/permalink/34CSUC_UPC/1q393em/alma991003933959706711.
Kozen, Dexter. 1997. Automata and computability. Undergraduate texts a computer science. New York: Springer. https://discovery.upc.edu/permalink/34CSUC_UPC/8e3cvp/alma991001527289706711.
Serna, Maria José, Carme Àlvarez, Rafel Cases, i Antoni Lozano. 2004. Els Límits de la computació : indecidibilitat i NP-completesa. 2a ed. Aula politècnica.FIB ; 60. Barcelona: Edicions UPC. https://discovery.upc.edu/permalink/34CSUC_UPC/8e3cvp/alma991004025469706711.
Sipser, Michael. 2013. Introduction to the theory of computation. Third edition. Boston, MA: Cengage Learning. https://discovery.upc.edu/permalink/34CSUC_UPC/1q393em/alma991004025429706711.

Avaluació

Presentacions a pissarra (nota E: entre 0 i 2)
Per cadascuna de les llistes d’exercicis, cada estudiant té assignat aleatòriament un exercici per resoldre i presentar a pissarra. La nota E té en compte totes les presentacions.
Examen parcial 1 (nota P_1: entre 0 i 8)
3 de novembre, de 10:30 a 12:30
Examen parcial 2 (nota P_2: entre 0 i 8)
9 de gener, de 08:00 a 11:00
Examen final (nota F: entre 0 i 10)
19 de gener, de 11:30 a 14:30
Avaluació continuada (nota C: entre 0 i 10)
Es calcula segons la fórmula

C =\frac{P_1}{2}+\frac{P_2}{2}+E\ .

Hi ha dues maneres d’aprovar aquest curs: sense presentar-se a l’examen final o presentant-s’hi. La nota es calcula de manera diferent en cada cas:

  • Sense presentar-se a l’examen final, la nota final és C.

  • Presentant-se a l’examen final, la nota final és

    \max\left(F,\ \frac{F}{2}+\frac{C}{2}\right)\ .

L’avaluació de les competències transversals G7.3 i G9.3 la realitza cada professor individualment per a cada alumne del seu grup basant-se en les presentacions públiques de l’avaluació continuada. L’avaluació de les competències no afecta l’avaluació de l’assignatura.