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
|