Enginyeria en Informàtica (3371)
Estructures de Dades i de la Informació I(12413)
Descripció
L'assignatura introdueix la importancia d'un bon disseny de les estructures de dades d'una aplicació, a partir de donar una visió general de les estructures més comunes així com de l'abstracció necessària per separar la representació de les dades, la seva implementació i el seu ús.
Objectius
L'alumne haurà d'ésser capaç d'especificar, dissenyar, implementar
i avaluar estructures de dades i saber identificar els algorismes
més adients sobre aquestes estructures. És a dir, es pretén que
l'alumne s'apropi per primer cop a la figura del dissenyador
analista, més que no d'un programador.
No obstant, també es pretén proporcionar a l'alumne més
experiència en el camp de la programació mitjançant la realització
de pràctiques i un projecte final.
Temari
1. Especificació algebràica i concepte de Tipus Abstracte de Dades (TAD)
1. Llenguatge abstracte d'especificació de TAD's
2. Parametrització de TAD's
2. Estructures Lineals: Especificació i Implementació
1. TAD pila
2. TAD cua
3. TAD llista
3. Estructures associatives (o funcionals)
1. TAD taula associativa
2. Implementació: Taules de Dispersió (hashing)
4. Arbres
1. TAD Arbres Binaris
2. TAD Arbres Binaris de Cerca (ordenats)
3. Altres tipus d'arbres: AVL i Cua de prioritat
5. Disseny d'estructures de dades
Organització
L'assignatura s'estructura en sessions teòriques (3'5 h. setmanals, distribuïdes en dues sessions; una de 2 h i una altra de 1'5 h.) i sessions pràctiques (1 sessió setmanal de 2h.).
Pràctiques
Les pràctiques de l'assignatura reforcen els continguts teòrics
presentats a les sessions teòriques.
A les sessions pràctiques s'implementen alguns dels Tipus
Abstractes de Dades (TAD) presentats i s'estudien les diferents
alternatives d'implementació per cadascún d'ells. A la pràctica
final, a mode de compendi, s'utilitza algun dels TAD's implementats
durant el curs per a la realització d'una pràctica final més
complerta.
Mètode d'avaluació
Nota Final = [Teoria · 0,6 + Pràctiques · 0,4] on cada part ha
d'estar aprovada.
Teoria: La teoria s'avaluarà mitjançant un examen al final
del trimestre que contindrà una part d'Examen Test (50%) i una part
de qüestions (50%).
Pràctiques: Es faran un total de 9 pràctiques, 8 de les
quals seran setmanals i cadascuna comptarà un 10% de la nota de
pràctiques, i una pràctica final que suposarà el 20% restant de la
nota.
Observacions
L'alumne ha d'haver cursat, prèviament, l'assignatura de Programació I i cursar en paral·lel Programació II (12410).
Bibliografia
Bibliografia bàsica
* AHO, A.V. i d'altres. Data Structures and Algorithms.
Addison-Wesley, 1983.
* PEÑA, R. Diseño de programas. Prentice Hall, 2a Edició,
1999.
* WEISS, M. Data Structures and Algorithm Analysis in C.
Benjamin Cummings, 1993.
* FRANCH GUTIÉRREZ, X. Estructuras de datos. Especificación,
diseño e implementación. Edicions UPC, 1994.
* AMSBURY, W. Data Structures, from arrays to priority queues. Wadsworth, 1985.
* CORMEN, LEISERSON, RIVEST. Introduction to Algorithms. MIT Press, 1990.
* FLAMIG, B. Practical Data Structures in C++. Wiley and Sons, 1993.
* FRAKES, B.; BAEZA-YATES, R. Information Retrieval: Data Structures and Algorithms. Prentice Hall, 1992.
* HOROWITZ, E.; SAHNI, S. Fundamentals of Data Structures. Computer Science Press, 1983.
* KORSH, J.; GARRET, L. Data Structures, Algorythms and Program Style Using C. PWS Kent Publishing, 1988
* MORET, SHAPIRO: Algorithms from P to NP. Benjamin Cummings, 1991.
* PLUM, T. Reliable Data Structures in C. Plum Hall, 1985
* WIRTH, N. Algorithms + Data Structures = Programs. Prentice Hall, 1980.