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.
Els Resultats d'Aprenentatge d'aquesta assignatura són:
- L'alumne o alumna serà capaç d'identificar la teoria, els conceptes i els mètodes de la programació i les estructures de dades per resoldre un determinat problema.
- L'alumne o alumna podrà resoldre un problema mitjançant el disseny i la implementació d'un algorisme eficient utilitzant estructures de dades adequades.
Per a assolir aquests resultats, l'assignatura es divideix en dos blocs de contingut: Programació Avançada i Estructura de Dades.
En acabar el curs, l'alumne ha de ser capaç de:
- Justificar la necessitat de l'especificació formal dels algorismes.
- Realitzar l'especificació formal d'un algorisme en termes de pre i post-condicions.
- Implementar un algorisme sense ambigüetats a partir de l'especificació del mateix.
- Avaluar l'eficiència d'un algorisme a través del càlcul del cost.
- Dissenyar un algorisme recursiu.
- Explicar els principals mecanismes de derivació formal i demostració formal d'algorismes recursius simples i de dur-ho a la pràctica en problemes.
- Reconèixer diferents classes de complexitat computacional com P o NP, així com reduccions entre problemes de diferents classes.
- Escollir els mètodes de resolució de problemes combinatoris més adients en cada situació.
- Implementar els mètodes de Backtracking, Branch & Bound i Greedy adaptats a cada problema en concret i buscant-ne la màxima eficiència i eficàcia.
- Dissenyar i implementar l'estructura de dades més adequada per una determinada aplicació, donats uns requisits d'eficiència temporal i espaial.
- Implementar grafs i aplicar-hi algorismes per a resoldre problemes com el camí mínim.
- Implementar els arbres binaris i AVL. Implementar també els diversos recorreguts possibles.
- Implementar taules de hash.
Els continguts generals de l'assignatura són els següents:
1. Especificació d'algorismes
2. Eficiència d'algorismes
3. Disseny recursiu
4. Complexitat computacional
5. Optimització combinatòria
6. Grafs
7. Arbres
8. Taules
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 i dues pràctiques. També s'hi realitzen exercicis d'avaluació continua que poden millorar la nota del bloc.
El segon bloc s'avalua mitjançant un projecte en grup i un examen individual.
Tot i que l'assignatura és semestral, aquesta s'estructura en dos blocs que cal aprovar per separat amb una nota igual o superior a 5. Si no s'aproven els dos blocs, l'assignatura queda suspesa amb una nota màxima de 4.
Nota_Final = 0.5 · Nota_B1 + 0.5 · Nota_B2
Bloc 1 - Programació Avançada:
La nota del primer bloc es calcula a partir de la ponderació de les notes de coneixements i de pràctiques.
Nota_B1 = 0.4 · Nota_Coneixements_B1 + 0.6 · Nota_Pràctiques_B1
Cal treure un 5 o més de cadascuna de les parts per a aprovar el bloc. Altrament, la nota del bloc serà com a molt un 4.
Coneixements
Per a calcular la nota de coneixements del primer bloc es pondera la nota de l'examen de punt de control amb la nota d'avaluació contínua, només en el cas de beneficiar a l'estudiant i sempre que la nota de l'examen sigui superior a 5.
Nota_Coneixements_B1 = max( 0.4 · Nota_AC_B1 + 0.6 · Nota_Examen_B1,Nota_Examen_B1 )
En cas de suspendre la part de coneixements del primer bloc, es realitzarà un examen de recuperació a la convocatòria extraordinària de juliol, on la nota d'avaluació contínua no beneficiarà l'estudiant, i on cal treure un 5 o més per aprovar.
Pràctiques
La nota de pràctiques del primer bloc es calcula ponderant les notes de les dues pràctiques que s'hi realitzen, havent d'aprovar cadascuna per separat amb nota igual o superior a 5. Altrament, la nota de pràctiques serà com a molt de 4.
Nota_Pràctiques_B1 = 0.5 · Nota_Pràctica_1 + 0.5 · Nota_Pràctica_2
Bloc 2 - Estructura de Dades:
El segon bloc es basa en la metodologia Project-Based Learning (PBL), pel que només hi haurà una pràctica i un examen final. Cal aprovar cadascun d'aquests elements per separat amb una nota igual o superior a 5. Altrament, la nota del bloc serà com a molt de 4.
Nota_B2 = 0.4 · Nota_Examen_B2 + 0.6 · Nota_Pràctica_3
Resum i recuperacions:
En resum, la nota de l'assignatura la determinen principalment 5 activitats d'avaluació, cadascuna amb les següents ponderacions:
Pràctica 1: 15%
Pràctica 2: 15%
Pràctica 3: 30%
Examen Bloc 1: 20% (punt de control, si s'aprova en convocatòria ordinària la nota pot ser millorada per AC)
Examen Bloc 2: 20% (final)
Cadascuna d'aquestes activitats es podrà recuperar en convocatòria extraordinària de juliol segons les dates que apareixen al pla docent de l'assignatura o al calendari corresponent.
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.