Universitat de Girona

Programa de l'assignatura

Curs 2003-04

3105II0004 INTRODUCCIÓ A LES ESTRUCTURES DE DADES


Objectius  

- Aprendre a gestionar la memòria interna de la màquina creant i alliberant els objectes adequadament.
- Estudiar les principals estructures de dades de memòria interna.
- Conèixer els algoritmes de manipulació d’estructures de dades de memòria interna.
- Saber dissenyar estructures de dades complexes.
 
Prerrequisits  

Recomanats: Metodologia i tecnologia de la programació
 
Contingut (Programa)  

1.- Classes [3 h] 1.1.- Classes i abstracció de dades
1.2.- Herència i Polimorfisme
1.3.- Genericitat
1.4.- Patrons de disseny

2.- Gestió dinàmica de memòria [3 h] 2.1.- Introducció
2.2.- Refèrencies
2.3.- Estructures enllacades

3.- Contenidors I: seqüencies i arbres [8 h] 3.1.- Piles
3.2.- Cues
3.3.- Llistes amb punt d'interés
3.4.- Arbres binaris

4.- Contenidors II: diccionaris de dades [10 h] 4.1.- Concepte
4.2.- Tipologia (conjunts, taules de consulta o edfs)
4.3.- Tècniques d'implementació (lineals, dispersió, arbres de cerca, arbres AVL)

5.- Contenidors III: estructures complexes [2 h] 5.1.- Grafs (concepte, representació)
5.2.- Relacions (concepte, representació)

6.- Disseny [4 h] 6.1.- Exemples de disseny
 
Bibliografia  



BIBLOGRAFIA BÀSICA:
- Franch, X.:ESTRUCTURA DE DADES, Edicions U.P.C., 1993
- Preiss, B.R.: DATA STRUCTURES AND ALGORITMS, John Wiley and Sons, 1999
- Stroustrup, B.: EL LENGUAJE DE PROGRAMACIÓN C++, Addison-Wesley, 2001 (versió original del 2000).

BIBLOGRAFIA COMPLEMENTARIA:
- Aho, A.V.; Hopcroft, J.E.; Ullman, J.D.: ESTRUCTURA DE DATOS Y ALGORITMOS, Addison-Wesley Iberoamericana, 1988.
- Coffin, S.: UNIX. Manual de referencia, McGraw-Hill, 1992.
- Gamma, E.; Helm, R.; Johnson, R.; Vlissides, J.: DESIGN PATTERNS, Addison-Wesley, 1995 (versió traduida del 2003)
- Horowitz, E.; Sahni, S.; Mehta, D.: FUNDAMENTALS OF DATA STRUCTURES IN C++, Computer Science Press, 1995.
- Martin, J.: DATA TYPES AND DATA STRUCTURES, Prentice-Hall, 1986.
- Musser, D.R.; Derge, G.J.; Saini, A.:STL TUTORIAL AND REFERENCE GUIDE, Addison-Wesley, 2001
- Weiss, M.A.: ESTRUCTURAS DE DATOS EN JAVA, Addison-Wesley, 2000 (versió original de 1998)
- Wirth, N.: ALGORITMOS Y ESTRUCTURAS DE DATOS, Prentice-Hall Hispanoamericana, 1987
 
Mètodes docents  

En aquesta assignatura es realitzen en tres tipus de sessions: teoria (3 crèdits), problemes (1’5 crèdits) i pràctiques (1,5 crèdits).
 
Tipus d'exàmens i avaluacions  

Qualificació:
Treballs pràctics 70%
Laboratori 30%
 
Informació addicional  

0. Sistema operatiu UNIX. (1 sessió)
1. Introducció al llenguatge C++. (3 sessions)
2. Estructures dinàmiques de la informació. (3 sessions)
3. Sequències i arbres binaris. (3 sessions)
4. Diccionaris de dades (3 sessions)
5. Pràctica final (1 sessio)
 
Llengua de les classes  

Català