L'assignatura de Tècniques Avançades de Programació aprofundeix en el disseny d'algorismes per a la resolució de problemes complexos, reforçant la base de ciències de la computació necessària per a la formació en enginyeria.
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 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 que requereixin coneixements 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. L'estudi de l'eficiència dels algorismes i de diverses tècniques de disseny 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 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. 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
Durant l'assignatura, es faran servir les següents metodologies:
- 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.
L'assignatura 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.
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:
- 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.