Enginyeria Tè;cnica en Informàtica de Sistemes (3372)

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.

Organització

L'assignatura s'estructura en sessions teòriques (3'5 h. setmanals, distribuïdes en dues sessions; una de 1'5 h. i una altra de 2 h.) i sessions pràctiques (1 sessió setmanal de 2h.).

Temari

Tema 1. Especificació algebràica i concepte deTipus abstracte de dades (TAD)

1. Llenguatge abstracte d'especificació de TAD's
2. Parametrització de TAD's

Tema 2. Estructures Lineals: Especificació i Implementació

1. TAD pila
2. TAD cua
3. TAD llista

Tema 3. Estructures associatives (o funcionals)

1. TAD taula associativa
2. Implementació: Taules de Dispersió (hashing)

Tema 4. Arbres

1. TAD Arbres Binaris
2. TAD Arbres Binaris de Cerca (ordenats)
3. Altres tipus d'arbres: AVL i Cua de prioritat

Tema 5. Disseny d'estructures de dades

Pràctiques

Les pràctiques de l'assignatura reforcen els continguts teòrics presentats a les sessions teòriques. A més a més, pretèn donar una visió més àmplia del llenguatge de Programació C, presentat a l'assigantura de Programació 1. 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,7 + Prac · 0,3 * Teoria = Examen · 0,9 + Entrega Exercicis · 0,1 o Examen = Teoria (test) · 0,4 + Problemes · 0,6 o Entrega Exercicis = Control Parcial · 0,5 + Entrega Problemes · 0,5 * Prac = Entregues Parcials + Entrega Final

Observacions

L'alumne ha d'haver cursat, prèviament, alguna assignatura de programació bàsica. És convenient cursar alhora l'assignatura 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.

Bibliografia complementària
FRANCH. X. Estructures de Dades. Especificació, disseny i implementació. Tercera Edició, 1995
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.