Anàlisi d'Estructura de Dades (AED)
(http://www-lsi.upc.edu/~conrado/docencia/aed)
| Professors Responsables: |
CONRADO MARTINEZ PARRA (conrado lsi.upc.edu)
|
|
Crèdits: 4.5 (3.0 T 1.5 P 0.0 L)
| |
Departament:
LSI
|
Tipus d'assignatura
Optativa per la EI
Requisits de l'assignatura
|
EA
- Pre-requisit per la EI
|
|
Objectius docents
Podem resumir en dos els objectius generals de l'assignatura
1. Estructures de dades: Proporcionar a l'estudiant un ampli ventall de
coneixements sobre estructures de dades avançades com ara els
self-adjusting trees, les skip list o red-black trees.
Capacitar l'estudiant per a que utilitzi o desenvolupi tècniques
eficients d'implementació de tipus abstractes. Capacitar l'estudiant per
a que desenvolupi extensions de les estructures de dades avançades,
proporcionant noves funcionalitats a les mateixes.
2. Tècniques d'Anàlisi: Donar a conèixer a
l'estudiant diverses tècniques d'anàlisi i que aquest aprengui a
aplicar-les. Concienciar l'estudiant de les avantatges derivades de la
utilització d'implementacions eficients i de l'anàlisi de les
implementacions que puguin desenvolupar. Entre les tècniques
d'anàlisi que s'estudien en el curs es troben les de cost en cas
mitjà, cost amortitzat, anàlisi probabilístic,...
Així mateix, es pretèn refermar les tècniques
d'anàlisi del cas pitjor, que l'estudiant ja coneix. Entre els aspectes
pràctics, pararem atenció a la realització d'experiments
rigorosos per a la mesura de l'eficiència i contrast amb les prediccions
teòriques.
El temari d'Anàlisi d'Estructures de Dades s'estructura en 3 temes
relativament extensos, amb la finalitat d'aconseguir els objectius
abans esmentats.
Programa
1. Anàlisi en cas pitjor (Durada: aprox 8h)
1.1. Repàs de conceptes bàsics.
1.2. Heaps i heapsort.
1.3. Àrbres red-black.
2. Anàlisi probabilístic (Durada: aprox 18h)
2.1. Conceptes bàsics. Distribucions de probabilitat. Eines de
l'anàlisi de cas mitjà.
2.2. Àrbres binaris de cerca.
2.3. Àrbres digitals de cerca, tries i Patricia.
2.4. Hashing.
2.5. Skip lists. Randomized BSTs.
3. Anàlisi amortizat (Durada: aprox 18h)
3.1. Conceptes bàsics. Anàlisi distribucional. Anàlisi competitiu.
3.2 Estructures de dades òptimes.
3.3. Llistes lineals autoorganitzatives.
3.5. Splay trees.
3.6. Altres exemples.
Avaluació
L'assignatura consta de vàries proves tant teòriques com
pràctiques. Cada convocatòria consta, d'una prova teòrica
(40% de la nota final) i una pràctica obligatòria (30% de la nota
final). A més d'aquestes proves, l'alumne pot realitzar, amb
caràcter voluntari, exercicis addicionals de tipus teòric i de
tipus pràctic que es proposaran. Aquestes proves d'evaluació
continuada contribueixen al 30% restant de la nota final
Bibliografia
Bibliografia bàsica
- AHO, A.V.; HOPCROFF, J.E.; and ULLMAN, J.D The Design and Analysis of
computer Algorithms Addison-Wesley, 1974
- CORMEN, T.H.; LEISERSON, C.E.; and RIVEST, R.L Introduction to
Algorithms The MIT Press, Cambridge, MA, 1990
- KNUTH, D.E The Art of Computer Programming: Sorting and Searching
(vol. 3) Addison-Wesley, 1973
Bibliografia complementària
- GONNET, G.H. and BAEZA-YATES, R. Handbook of Algorithms and Data Structures(2nd edition) Addison-Wesley, 1991
- MAHMOUD, H.M Evolution of Random Search Trees Wiley Interscience, 1992
- MEHLHORN, K Data Structures and Algorithms: Sorting and Searching
(vol. 1) Springer-Velarg, 1984
- SEDGEWICK, R Algorithms Addison-Wesley, 2nd edit, 1988
- TARJAN, R.E Data Structures and Network Algorithms Society for
Industrial and Applied Mathematics, 1983
- VAN LEEUWEN, J Handbook of Theoretical Computer Science
(vol. A) North-Holland, 1990
-
PUGH, W Skip lists: a probabilistic alternative to balanced
trees Communications of the ACM, 33, 668-676, 1990
-
SLEATOR, D.D. and TARJAN, R.E. Amortized efficiency of list
uptade and paging rules Communications of the ACM, 28, 202-208, 1985
-
SLEATOR, D.D. and TARJAN, R.E Self-adjusting binary search trees
Journal of the ACM, 32, 652-686, 1985
|
