Algorísmia (ALG)

Ampliar el ventall de tècniques algorismiques i aprofundir en els seus fonaments teòrics. Aprofundir en el disseny i evaluació dels algorismes. Introduïr els algorismes probabilístics com a eina de disseny d'algorismes. Introduïr eines algorismiques pel tractament de problemes computacionalmente difícils com els algorismes d'aproximació i els mètodes basats en cerca local. Introduïr l'enginyeria algorísmica com a selecció de les estructures de dades i de les tècniques algorismiques mes adients per a la resolució d'un problema concret.

Coneixements

1. Anàlisi d'algorismes: Eficiència, costos, notació asimptòtica. Recurrències. Anàlisi en cas mitjà.
2. Fonaments teòrics dels esquemes algorísmics.
3. Algorismes fonamentals avançats: ordenació, grafs, hashing.
4. Algorismes aleatòris: Tipus, técnicas elementals de disseny. Primalitat. Tècniques d'anàlisi.
5. Algorismes d'aproximació: Concepte d'aproximació. Eficiència versus qualitat. Tècniques d'anàlisi i diseny.
6. Mètodes basats em cerca local: Cerca local i variacions. Evaluació experimental.

Habilitats

1. Ser capaç d'utilitzar tècniques avançades de disseny i anàlisi d'algorismes
2. Saber raonar sobre la correció i l'eficiencia d'algorismes probabilistics.
3. Conèixer alguns algorismes clàssics per problemes fonamentals.
4. Saber identificar les components més rellevants d'un problema i seleccionar la tècnica algorismica mes adient.
5. Ser capaç de seleccionar els tipus de dades mes adients per millorar la eficiència d'una solució algorísmica.

Competències

1. Capacitat per al raonament crític i lògico-matemàtic
2. Capacitat de resoldre problemes aplicant els mètodes de la ciència i l'enginyeria
3. Capacitat per dissenyar sistemes, components o processos que s'ajustin a unes necessitats, utilitzant els mètodes, tècniques i eines més adients en cada cas.
4. (1) Capacitat d'abstracció. Capacitat d'enfrontar-se a problemes nous recorrent conscientment a estratègies que han estat útils en problemes resolts anteriorment.
5. (1) Capacitat per estudiar de diverses fonts, identificant quan la informació rebuda a classe no és suficient i cercant informació complementària.
6. Capacitat per relacionar i estructurar informació de diverses fonts, per integrar idees i coneixements.
7. Capacitat per transmetre idees efectivament de forma escrita.
8. Disposició i capacitat per actualitzar-se al llarg de la carrera professional, quant a coneixements, procediments i tècniques.

Les classes es divideixen en dos tipus: sessions de teoria i sessions de problemes. En mitjana, la teoria ocupa tres hores setmanals i els problemes les altres dues hores. El professor adaptarà la repatició d'aquestes hores de la forma que millor s'ajusti al temari.

Les sessions de teoria són classes de tipus magistral en les que el professor aporta nous conceptes o noves tècniques conjuntament amb exemples que els motivin o els il.lustrin.

Les classes de problemes tenen com objectiu desenvolupar exercicis i es basen en la participació activa dels alumnes. Els professors proposen els problemes per avançat. La finalitat es que els alumnes presentin el treball fet i que es discuteixen les diverses solucions i/o alternatives.

Aportacions per escrit a les classes de problemes (Pro). Examen Final (Fin).

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

max(Fin, 0.7 * Fin + 0.3*Pro).

• CORMEN, Thomas H. et alt. Introduction to algorithms. 2nd edition, MIT Press i McGraw-Hill, 2001.
• KLEINBERG, Jon i TARDOS, Eva Algorithm design, Pearson/Addison Wesley, 2006.
• MITZENMACHER, Michael i UPFAL, Eli Probability and Computing. Randomized algorithms and Probabilistic Analysis, Cambridge University Press, 2005.
• VAZIRANI, Vijay V. Approximation Algorithms, Springer, 2001.
• HOOS, Holger H., STÚTZLE, Thomas Stochastic local search: Foundations and applications, Elsevier, 2005.

• FERRI, F. J., ALBERT, J. V., MARTÍN, G. Introducció a l'anàlisi i disseny d'algorismes, Universitat de València, 1998.
• MOTWANI, R. i RAGHAVAN, P. Randomized Algorithms, Cambridge University Press, 1995.
• SKIENA, Steven The algorithm design manual, Springer Verlag, 1998.
• GAREY, M. R. i JHONSON, D. S. Computers and intractability. A guide to the NP-completeness. , W.H. Freema, 1979.
• MICHALEWICZ, Z. i FOGEL, D.B. How to solve it: Modern Heuristics, Springer, 2000.

Coneixements basics sobre disseny i anàlisis d'algorismes