Estructura de Dades i Algorismes (EDA)
(http://www.fib.upc.edu/~eda)
| Professors Responsables: |
SALVADOR ROURA FERRET (roura lsi.upc.edu)
|
|
Crèdits: 9.0 (4.5 T 3.0 P 1.5 L)
| |
Departament:
LSI
|
Tipus d'assignatura
Obligatoria de primer cicle per la EI
Obligatoria per la ETIG ,ETIS
Requisits de l'assignatura
|
PM
- Pre-requisit per la EI , ETIG , ETIS
|
|
Objectius docents
Proporcionar a l'alumne la capacitat d'especificar, dissenyar, implementar i avaluar estructures de dades i
l'habilitat d'identificar els algoritmes més adients sobre aquestes estructures. Igualment, es pretén
proporcionar a l'alumne més experiència en el camp de la programació mitjançant la realització de pràctiques.
Programa
1. Conceptes bàsics de Tipus Abstractes de Dades
Repàs del concepte de TAD. Especificació de TADs. Correctesa
dels programes que usen un TAD i correctesa de la seva
implementació. Classes i objectes. Relació amb els TADs.
2. Anàlisi de l'eficiència d'algorismes
Mesures del cost en espai i temps d'algorismes.
Cost en cas pitjor i mitjà.
Regles de càlcul de l'eficiència d'algorismes iteratius
i recursius.
Notacions assimptòtiques
3. Estructures lineals
Repàs del concepte de seqüència. Piles i cues.
Llistes. Implementació en vector i enllaçada
d'estructures lineals. Aplicacions. Ordenació de llistes
per fusió (mergesort).
4. Arbres
Repàs del concepte d'arbre. Arbres generals. Arbres binaris.
Aplicacions. Recorreguts en preordre, postordre, inordre
i per nivells. Implementació d'arbres amb vector d'apuntadors
als fills. Implementació d'arbres amb apuntadors
primogènit/següent-germà.
5. Taules associatives
Especificació del TAD "taula associativa". Variants. Aplicacions.
Tècniques d'implementació senzilles: llistes, llistes ordenades, bitvector.
Tècniques d'implementació avançades: arbres binaris de cerca,
arbres binaris de cerca balancejats, taules de dispersió (hash),
tries.
6. Cues de prioritat
Especificació del TAD "cua de prioritat". Aplicacions.
Implementació mitjançant heaps. Heapsort.
7. Particions
Especificació del TAD "partició". Aplicacions. Implementació
mitjançant mfsets.
8. Grafs
Repàs del concepte de graf i nomenclatura. Especificació.
Implementació amb matrius i llistes d'adjacència.
Recorregut en profunditat i en amplada de grafs. Aplicacions.
Algorisme de Dijkstra per als camins mínims. Algorisme de
Kruskal per a l'arbre d'expansió mínim.
Avaluació
la nota final es calcula amb
F = 0.7 T + 0.3 Pract
T = max(E, 0.7 E + 0.3 Parc),
siguent E la nota del examen final, Parc la nota del examen parcial i Pract la nota de practicas.
Bibliografia
Bibliografia bàsica
- M.A. Weiss Data Structures and Algorithm Analysis in C++ (2nd edition) Addison-Wesley, 1999
- A.V. Aho, J.D. Ullman Foundations of Computer Science (C edition) W.H. Freeman & Co., 1995
- B. Stroustrup The C++ Programming Language (3rd edition) Addison-Wesley, 1997
Informació complementària
CLASSES DE LABORATORI
S'ha de dur a terme 1 pràctica en parelles
durant el quadrimestre.
|
