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 avançats per problemes bàsics: 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.
7. Metaheurístics: mètodes per a la solució aproximada de problemes d'optimització combinatoria i continua

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. Capacitat d'abstracció. Capacitat d'enfrontar-se a problemes nous recorrent conscientment a estratègies que han estat útils en problemes resolts anteriorment.
5. 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 repartició 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).

• Thomas H. Cormen ... [et al.] Introduction to algorithms, MIT Press, 2001.
• Jon Kleinberg, Éva Tardos Algorithm design, Pearson/Addison-Wesley, 2006.
• Michael Mitzenmacher, Eli Upfal Probability and computing : randomized algorithms and probabilistic analysis, Cambridge University Press, 2005.
• Vijay V. Vazirani Approximation algorithms, Springer, 2003.
• Holger H. Hoos, Thomas Stützle Stochastic local research : foundations and applications, Morgan Kaufmann Publishers, 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.
• Steven S. Skiena The Algorithm design manual, TELOS--the Electronic Library of Science, 1998.
• Michael R. Garey, David S. Johnson Computers and intractability : a guide to the theory of NP-Completeness, W.H. Freeman, 1979.
• Zbigniew Michalewicz, David B. Fogel How to solve it : modern heuristics, Springer,, 2004.

Coneixements basics sobre disseny i anàlisis d'algorismes