Algorísmia, Calculabilitat i Complexitat (ALCC)

Conèixer els elements bàsics de la teoria de la computació, incloent una introducció a l'algorísmia, a les teories de la complexitat i de la calculabilitat, i a la teoria d'autòmats i llenguatges.

Adquirir els coneixements necessaris per classificar problemes segons l'existència o no d'algorismes per a la seva resolució i, en aquest darrer cas, segons la possibilitat de trobar una solució eficient.

Coneixements

1. Conèixer alguns models abstractes de càlcul clàssics i les seves limitacions i possibilitats.
2. Saber classificar els problemes en les classes de complexitat definides pels diferents models de càlcul. En particular, entendre la significació dels resultats negatius (no regularitat, intractabilitat, indecidibilitat).
3. Comprendre el concepte de reducció entre problemes i la seva utilització per mostrar-ne la tractabilitat o intractabiliat.
4. Aprendre a analitzar el cost d'un algorisme i la complexitat computacional d'un problema. Entendre la diferència qualitativa entre temps polinòmic i temps exponencial.
5. Conèixer problemes computacionals per als quals, a hores d'ara, no es coneixen algorismes amb cost polinòmic.
6. Aprendre algunes tècniques algorísmiques per tractar problemes difícils; en particular, els problemes NP-complets.
7. Entendre l'ús de la notació lògico-matemàtica per representar els problemes computacionals i els models de càlcul.

Habilitats

Competències

1. Capacitat per al raonament crític i lògico-matemàtic
2. Capacitat per entendre i construir demostracions lògico-matemàtiques.
3. Capacitat per resoldre problemes aplicant els mètodes de la ciència i l'enginyeria.
4. Capacitat d'aplicar els coneixements de matemàtiques i lògica a la resolució de problemes.
5. Capacitat d'abstracció. Capacitat d'enfrontar-se a problemes nous recorrent conscientment a estratègies que han estat útils en problemes resolts anteriorment.
6. Capacitat d'actuar autònomament: saber treballar de forma independent, rebent només la informació indispensable i un mínim de guiatge.
7. Capacitat per transmetre idees efectivament de forma escrita.
8. Obertura i curiositat intel·lectual.

Cada classe de dues hores es divideix en una primera hora de teoria i una segona de problemes. A més, en diverses ocasions al llarg del curs (en finalitzar un grup d'un o dos temes), els estudiants rebran uns exercicis per resoldre durant l'hora de problemes, que permetran l'avaluació continuada de l'assignatura. Els estudiants també poden optar per una avaluació de tot el temari en l'examen final.

L'assignatura té un sistema d'avaluació continuada i un examen final. L'avaluació continuada consta de k proves (3 <= k <= 10) fetes al llarg del quadrimestre, mentre que l'examen final consta de k preguntes, cadascuna de les quals té el mateix pes que la prova corresponent. Si les notes de les proves són c_1, ..., c_k i les notes de les preguntes de l'examen final són f_1, ..., f_k, la nota global de l'assignatura és

max(c_1,f_1) + ... + max(c_k,f_k).

Cada prova de l'avaluació continuada (i la pregunta corresponent de l'examen final) avalua un o dos temes, i el seu pes és la suma dels pesos dels temes que avalua. Els pesos de cada tema estaran entre 0.5 i 1.5 punts, i els seus valors exactes s'anunciaran al Racó a començament de curs.

Les proves tindran lloc a l'aula de classe dins de l'hora de problemes, poc després d'acabar la matèria que inclouen, i s'anunciaran al Racó almenys amb un dia d'antelació.

• Sipser, M. Introduction to the Theory of Computation, PWS, 1997.
• Brassard, G. i Bratley, P. Fundamentos de Algoritmia, Prentice Hall, 1997.
• Serna, M, Àlvarez, C., Cases, R. i Lozano, A. Els límits de la computació. Indecidibilitat i NP-completesa, Edicions UPC, 2001.
• Cormen, T.H., Leiserson C.E., Rivest, R.L. i Stein, C. Introduction to Algorithms, second edition, MIT i McGraw-Hill, 2001.

• Kinber, E. i Smith, C. Theory of Computing. A Gentle Introduction., Prentice Hall, 2001.
• Papadimitriou, C. Computational Complexity, Addison Wesley, 1994.
• Garey, M. i Johnson, D. Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, 1978.
• Parberry I., Gasarch W. Problems on Algorithms (2nd edition), http://hercule.csci.unt.edu/ian/books/free/, 2002.
• Cases, R. i Màrquez, L. Llenguatges, gramàtiques i autòmats, Edicions UPC, 2000.

Coneixements de programació i estructures de dades.
Familiaritat amb el raonament lògico-matemàtic.