• Entendre bé el concepte d’esquema algorítmic i la necessitat de disposar de diferents esquemes per poder obtenir algoritmes.
• Fer un estudi dels principals esquemes algoritmics (divideix i venç, backtracking, mètode voraç i tècniques probabilistes).
• Fer un estudi dels grafs i els algoritmes de manipulació.
• Formalitzar l’estudi d’algoritmes des del punt de vista teòric.

1.- Introducció

1. Nomenclatura
2. Disseny d’algorismes (iteratiu, recursiu)
3. Eficiència (mesures d’eficiencia, cas mig, cas pitjor, relacions)
4. Estructures de dades (referències, estructures dinàmiques, classes definides)

2.- Introducció als esquemes: el tractament seqüencial.

1. Concepte d’esqueme algorítmic
2. Tractament seqüencial (recorregut, cerca)
3. Exemples

3.- Divideix i venç.

1. Introducció
2. Càlcul de l’eficiencia
3. L’esquema Divideix i venç
4. Exemples d’aplicació

4.- Algoritmes voraços i grafs.

1. Introducció
2. Esquema voraç i la seva demostració
3. Exemples
4. Grafs i algoritmes de tractament de grafs
5. Algoritmes voraços sobre grafs
6. Algoritmes quasi-òptims

5.- Exploració de grafs: Backtraking, Branch and bound i altres.

1. Introducció a l’exploració de grafs
2. Backtracking (una solució, totes les solucions, solució òptima)
3. Exemples d’aplicació
4. Altres recorreguts de grafs (en amplada, Brach & Bound,…)

6.- Algoritmes probabilistes.

1. Introducció
2. Generació de valors aleatoris
3. Algorismes numèrics
4. Algorismes de Monte-Carlo
5. Algorismes de Las Vegas
6. Algorismes de Sherwood
7. Estructures de dades i algorismes probabilistes

7.- Introducció a la calculabilitat

1. Introducció
2. Calculabilitat
3. Indecibilitat
4. Complexitat
5. Exemples i problemes

La bibliografia a la biblioteca

Bibliografia bàsica:

• Brassard, G.; Bratley, P.; ALGORITMIQUE. CONCEPTION ET ANALYSE; Masson, 1987 (Versió castellana de 1990).
• Brassard, G.; Bratley, P.; FUNDAMENTALS OF ALGORITHMICS; Prentice-Hall, 1996 (Versió castellana de 1997).
• Gonzalo, J.; Rodríguez, M.; ESQUEMAS ALGORITMICOS: ENFOQUE METODOLOGICO Y PROBLEMAS RESUELTOS; UNED, 1997.
• Horowitz, E.; Sahni, S.; COMPUTER ALGORITHMS IN C++; Computer Science Press, 1996.

Bibliografia complementària:

• Cormen, T.; Leiseson, C.; Rivest, R.; Stein, C.; INTRODUCTION TO ALGORITHMS; MIT Press, 2001.
• Coffin, S.; UNIX. Manual de referencia; McGraw-Hill, 1992.
• Preiss, B.R.; DATA STRUCTURES AND ALGORITMS; John Wiley and Sons, 1999.
• Stroustrup, B.; EL LENGUAJE DE PROGRAMACIÓN C++; Addison-Wesley, 2001 (versió original del 2000).
•  Wirth, N.; ALGORITMOS Y ESTRUCTURAS DE DATOS; Prentice-Hall Hispanoamericana, 1987.

Classes de teoria: 2 hores/setmana (3 crèdits)

Classes de problemes i laboratori: 2 hores/setmana (3 crèdits)

Qualificació:

• examen: 70%
• treballs de laboratori: 30%