Esquemes Algorísmics (EA)
|
|
Crèdits: 6.0 (3.0 T 1.5 P 1.5 L)
| |
Departament:
LSI
|
Tipus d'assignatura
Optativa per la EI
Requisits de l'assignatura
|
IEA
- Pre-requisit per la EI
|
|
Objectius docents
L'objectiu de l'assignatura és aprofundir en el disseny i
avaluació dels algorismes. D'una banda la utilització de
l'estructura de dades més adient per a cada cas. En segon, les
diferentes maneres d'avaluar el cost d'un algorisme. Finalment, una
introducció als algorismes probabilístics com a eina de disseny
d'algorismes.
Programa
1. Fonaments Matemàtics.
- Manipulació de sumes i binomials
- Solució recurrències.
- Introducció a l'anàlisi Probabilístic.
2. Classificació.
- Quicksort, anàlisi mitjà.
- Classificació en temps lineal; Radix i bucket.
- Selecció.
3. Estuctures de dades.
- Taules de Hashing, Arbres de cerca, Arbres Vermells-Negres, Arbres
d'Inteval.
- Heaps.
- Estructures de dades per a conjunts disjunts.
4. Algorimes Probabilístics.
- Primalitat.
- Distància mínima.
Avaluació
Un examen alliberatori a mig trimestre i l'examen final.
Bibliografia
Bibliografia bàsica
- CORMEN, T.; LEISERSON, R.; RIVEST, R An Introduction to
Algorithms McGraw Hill, 1990
- Sedgewick, R. Algorithms
in C Addison-Wesley, 1996
Bibliografia complementària
- Diaz, Serna, Spirakis, Toran Paradigms
for fast parallel approximability Cambridge University
Press, 1997
|
fib.upc.edu