Universitat de Girona

Programa de l'assignatura

Curs 2004-05

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.- Introducció [3 h] 1.1.- Classes i objectes
1.2.- Abstracció de dades
1.3.- Herència i Polimorfisme
1.4.- Genericitat
1.5.- Patrons de disseny


2.- Gestió dinàmica de memòria [3 h] 2.1.- Introducció
2.2.- Refèrencies i gestió de la memòria
2.3.- Estructures enllacades
2.4.- Algoritmes sobre estructures encadenades
2.5.- Altres implementacions
2.6.- Exemples i exercicis


3.- Contenidors I: seqüencies i arbres [8 h] 3.1.- Piles
3.2.- Cues
3.3.- Llistes amb punt d'interés i iteradors
3.4.- Arbres binaris
3.5.- Arbres n-aris
3.6.- Montícles i cues de prioritat
3.7.- Exemples i exercicis


4.- Contenidors II: diccionaris de dades [10 h] 4.1.- Concepte
4.2.- Tipologia: conjunts, taules de consulta o edfs
4.3.- Estructures no ordenades
4.4.- Estructures lineals ordenades.
4.5.- Arbres de cerca: variants
4.6.- Tècniques de dispersió


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


6.- Disseny [4 h] 6.1.- Introducció
6.2.- Disseny d'estructures complexes.
6.3.- Patrons de disseny: Iterator, Visitor, Composite,…

 
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ó:
Examen 70%
Laboratori 25%
Problemes 5%
 
Informació addicional  

Sessions de laboratori:
0. Sistema operatiu UNIX.
1. Introducció al llenguatge C++.
2. Estructures dinàmiques de la informació.
3. Sequències i arbres binaris.
4. Diccionaris de dades.
 
Llengua de les classes  

Català