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 les assignatures "Fonaments de Programació I" i "Fonaments de Programació II" (anàlisi descendent, modularitat, pas de paràmetres i estructures de dades bàsiques).
- Facilitat per escriure codi amb un llenguatge de programació (recomanable 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. 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 complexos de forma eficient i elegant. Amb l'assoliment dels conceptes exposats a l'assignatura, l'estudiantat demostra conèixer i ser capaç de modelar diferents topologies d'estructures de dades així com els algorismes necessaris per accedir-hi i manipular-les considerant sempre l'impacte computacional que això suposa.
Els continguts de l'assignatura són els següents:
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. Teoria de la complexitat computacional
4.1 - Tesi de Cobham
4.2 - Classes de complexitat
4.3 - P vs NP
4.4 - Reduccions
5. Problemes combinatoris
5.1 - Força bruta
5.2 - Backtracking
5.3 - Branch and bound
5.4 - Greedy
6. Grafs
6.1 - Definició i conceptes bàsics
6.2 - Representació
6.3 - Recorreguts
6.4 - Ordenació topològica
6.5 - Arbre d'expansió mínim
6.6 - El camí més curt
7. Arbres
7.1 - Definició i conceptes bàsics
7.2 - Representació
7.3 - Recorreguts
7.4 - Arbres binaris de cerca
7.5 - Arbres AVL
8. Taules
8.1 - Definició i conceptes bàsics
8.2 - Representació
8.3 - Taules de hash
Durant l'assignatura, es faran servir les següents metodologies, per bloc de continguts:
Programació Avançada:
- 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.
Estructura de Dades:
- 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 bloc 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 millorar la nota del bloc. Cal aprovar l'examen i les pràctiques per separat.
El segon bloc s'avalua mitjançant una pràctica en grup (60%) i un examen individual (40%). Cal aprovar la pràctica i l'examen separat.
Es valorarà:
- En el codi de les pràctiques:
- 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.