L'assignatura de Programació Avançada i Estructura de Dades aprofundeix en el disseny d'algorismes per a la resolució de problemes complexos i en l'ús eficient d'estructures de dades, reforçant la base de ciències de la computació necessària per a la formació en enginyeria informàtica.
Mitjançant l'ús de pseudocodi es fomenta el raonament algorítmic abstracte, mentre que conceptes com la complexitat computacional permeten a l'estudiantat analitzar el rendiment de diferents solucions per a justificar-ne l'adequació a un context. Finalment, la implementació pràctica d'aquests algorismes i estructures permet a l'estudiantat seguir desenvolupant algunes de les habilitats essencials en el camp de la programació, com la capacitat de detectar i resoldre errors o la capacitat de treballar en equip.
Així doncs, l'assignatura construeix sobre els fonaments de programació i algorísmica establerts en el primer curs i prepara l'estudiantat per a afrontar assignatures finalistes de l'àmbit de ciències de la computació.
Professors Titulars
Professors Docents
- Domini de les tècniques de programació treballades a l'assignatura "Metodologia i Tecnologia de la Programació" (anàlisi descendent, modularitat, pas de paràmetres i estructures de dades bàsiques).
- Facilitat per escriure codi amb un llenguatge de programació (preferiblement C/Java).
- Capacitat per seguir i proposar raonaments matemàtics.
L'assignatura té com a objectiu oferir una visió avançada de la programació d'algorismes, així com d'algunes de les estructures de dades més utilitzades en l'actualitat. L'estudi de l'eficiència dels algorismes i de diverses tècniques i estructures es treballen en profunditat amb l'objectiu de resoldre problemes de forma eficient i elegant. Amb l'assoliment dels conceptes exposats a l'assignatura, l'estudiantat adquireix habilitats per proposar i discutir l'adequació de solucions a problemes complexos.
Els continguts de l'assignatura per semestre són els següents:
Primer semestre:
1. Especificació d'algorismes
1.1 - Sintaxi
1.2 - Expressions booleanes
1.3 - Quantificadors i operadors de rang
2. Eficiència d'algorismes
2.1 - Eficiència, rendiment i complexitat
2.2 - Anàlisi asimptòtica
2.3 - Algorismes d'ordenació
3. Disseny recursiu
3.1 - Etapes del disseny recursiu
3.2 - Recursivitat final i tècnica d'immersió
3.3 - Ordenació recursiva
4. Programació dinàmica
4.1 - Estratègia top-down
4.2 - Estratègia bottom-up
5. Teoria de la complexitat computacional
5.1 - Tesi de Cobham
5.2 - Classes de complexitat
5.3 - P vs NP
6. Problemes combinatoris
6.1 - Força bruta
6.2 - Backtracking
6.3 - Branch and bound
6.4 - Greedy
Segon semestre:
7. Grafs
7.1 - Definició i conceptes bàsics
7.2 - Representació
7.3 - Recorreguts
7.4 - Ordenació topològica
7.5 - Arbre d'expansió mínim
7.6 - El camí més curt
8. Arbres
8.1 - Definició i conceptes bàsics
8.2 - Representació
8.3 - Recorreguts
8.4 - Arbres binaris de cerca
8.5 - Arbres AVL
9. Arbres R
9.1 - Definició i conceptes bàsics
9.2 - Representació
9.3 - Algorismes bàsics: Cerca, inserció, eliminació
9.4 - Optimització del kNN
10. Taules
10.1 - Definició i conceptes bàsics
10.2 - Representació
10.3 - Taules de hash
Durant l'assignatura, es faran servir les següents metodologies, per semestre:
Primer semestre:
- Classes magistrals, per a aquells continguts que ho requereixin.
- Problemes i exercicis a classe, per a consolidar coneixements.
- Exercicis d'AC a classe i pràctiques avaluables.
- Self-paced learning, per a continguts que no s'avaluaran directament.
- Flipped-classroom, per a motivar l'autoaprenentatge i donar suport a l'estudiantat.
Segon semestre:
- Project-Based Learning, on l'estudiantat aprendrà a dissenyar i implementar estructures de dades.
- Classes magistrals intercalades per introduir els conceptes necessaris, complementats durant el PBL.
- Self-paced learning, per a continguts que no es puguin aplicar al projecte.
El primer semestre s'avalua mitjançant un examen (50%) i dues pràctiques (20% i 30%). També s'hi realitzen exercicis d'avaluació continua que, més enllà de fomentar el seguiment de l'assignatura, poden permetre a alumnes que els superin amb bons resultats convalidar l'examen final mitjançant una entrevista. Cal aprovar l'examen i les pràctiques per separat.
El segon semestre s'avalua mitjançant un projecte en grup i un examen de validació individual. En cas d'aprovar l'examen de validació, la nota del semestre serà la del projecte en grup, ajustada a partir de mecanismes d'avaluació individual. Altrament, la nota del semestre serà la de l'examen.
Es valorarà:
- En el codi de les pràctiques i projectes:
- La correctesa del disseny i la implementació dels algorismes en relació als requisits.
- L'eficiència i rendiment dels algorismes, tant en el seu disseny com en la seva implementació.
- La qualitat del codi i la facilitat de validació.
- En les memòries de les pràctiques i projectes:
- L'adequació de l'estructura del document en relació als requisits.
- La idoneïtat de les explicacions conceptuals i de la justificació de les decisions preses.
- La rellevància i correctesa matemàtica de l'anàlisi de rendiment, així com de les justificacions que se n'extreuen.
- En els exàmens:
- La capacitat de raonar una solució eficient per a un problema complex que no s'ha vist anteriorment.
- La correcta aplicació de les tècniques contingudes al temari, com l'anàlisi asimptòtic o el disseny recursiu.
- La capacitat de sintetitzar i visualitzar el funcionament d'algorismes i estructures continguts al temari.
- La justificació raonable de les respostes proporcionades.
Apunts de l'assignatura disponibles al campus virtual.
Brass, P. (2008). Advanced Data Structures. Cambridge University Press.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to algorithms (4th Edition). MIT Press.
Sedgewick, R., Wayne, K. (2011). Algorithms (4th Edition). Addison-Wesley Professional.
Skiena, S. S. (2020). The algorithm design manual (3rd Edition). Springer.