Algorísmia, Calculabilitat i Complexitat ( ALCC )

Professors

Responsable:	M Jose Serna Iglesias (mjsernalsi.upc.edu).
Altres:	Antoni Lozano Bojados (antonilsi.upc.edu).

Objectius Generals

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

Els coneixements i l'experiència necessària 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.

Objectius Específics

Coneixements

1. Com analitzar el cost d'un algorisme i la complexitat computacional d'un problema. Comprenent la diferència qualitativa entre temps polinòmic i temps exponencial.
2. Què és un problema indecidible i algunes classes de complexitat per a problemas decidibles.
3. Les tècniques i els esquemes algorísmics bàsics i de nivell mitjà.
4. Els models de computació clàssics i les seves limitacions.
5. Conèixer problemes computacionals per als quals, hores d'ara, no es coneixen algorismes amb cost polinòmic.
6. Comprendre el concepte de reducció entre problemes, i la seva utilització per mostrar decidibilitat/tractabilitat o indecibilitat/no-tractabiliat.

Habilitats

Competències

1. Capacitat per al raonament crític i lògico-matemàtic
2. (1) Capacitat per aplicar les tècniques per construir demostracions lògico-matemàtiques.
3. Capacitat de 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. (1) 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.

Continguts

Hores estimades de:

Metodologia docent

L'assignatura tindrà classes de teoria i de problemes en el format habitual. A més,
en diverses ocasions durant el curs, els estudiants rebran uns problemes llargs (estil "casos")
per resoldre en hores de treball personal, que hauran de lliurar per escrit uns dies després.

Mètode d'avaluació

Qualificació dels problemes llargs/casos lliurats (Pro). Examens Parcial (Par) i Final (Fin). Altres treballs voluntaris (Vol).

La nota final es calcula d'acord amb la fòrmula

min(0.8*max((Par+Fin)/2, Fin) + 0.2*Pro + Vol, 10)

La nota dels treballs voluntaris (si n'hi ha) estarà entre 0 i 1,5.

Bibliografía bàsica

• Brassard, G. i Bratley, P. Fundamentos de Algoritmia, Prentice Hall, 1997.
• Garey, M. i Johnson, D. Computers and Intractability: A guide to the theory of NP-completeness., Freeman, 1978 .
• Hopcroft. J.D, Motwani, R. i Ullman, Introduction to Automata Theory, Languages, and Computation , Addison-Wesley, 2001.
• Serna, M, Àlvarez, C., Cases, R. i Lozano, A. Els límits de la computació. Indecidibilitat i NP-completesa, Edicions UPC, 2001.
• Sipser, M. Introduction to the theory of computation, PWS, 1997.

Bibliografía complementària

• Skiena, S. The algorithm design manual, Springer, 1998.
• Cormen, T.H., Leiserson C.E., Rivest, R.L. i Stein, C. Introduction to algorithms, second edition, MIT i McGRaw-Hill, 2001.
• Cases, R. i Marquez, L. Llenguatges, gramàtiques i autòmats, Edicions UPC, 2000.
• Michalewicz, Z. i Fogel, D.B. How to solve it: modern heuristics., Springer-Verlag , 2000.

Enllaços web

Capacitats prèvies

Coneixements de programació i estructures de dades.