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ó. (Recomanable C/Java).
Capacitat per seguir i proposar raonaments matemàtics.
Els Resultats d'Aprenentatge d'aquesta assignatura són:
- Ús d'un entorn real de programació.
- Treball en equip en l'anàlisi, disseny i implementació de software.
- Definició de l'estructura modular i de dades per dur a terme les aplicacions informàtiques.
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.
- 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, AVL i R-trees. Implementar també els diversos recorreguts possibles.
- Implementar taules de hash.
Els continguts generals per semestre són els següents:
Primer semestre:
1. Especificació d'algorismes
2. Eficiència d'algorismes
3. Disseny recursiu
4. Programació dinàmica
5. Teoria de la complexitat computacional
6. Problemes combinatoris
Segon semestre:
7. Grafs
8. Arbres
9. Arbres R
10. Taules
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 i dues pràctiques. 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.
El segon semestre s'avalua mitjançant un projecte en grup i un examen de validació individual.
L'assignatura és anual, pel que la nota final es calcula a partir de les notes dels dos semestres, sempre que ambdues siguin superiors o iguals a 5. Si no s'aproven els dos semestres, l'assignatura queda suspesa amb una nota màxima de 4.
Nota_Final = 0.5 · Nota_S1 + 0.5 · Nota_S2
Primer semestre:
La nota del primer semestre es calcula a partir de la ponderació de les notes de coneixements i de pràctiques.
Nota_S1 = 0.5 · Nota_Coneixements_S1 + 0.5 · Nota_Pràctiques_S1
Cal treure un 5 o més de cadascuna de les parts per a aprovar el semestre. Altrament, la nota del semestre serà com a molt un 4.
Coneixements
Per a calcular la nota de coneixements del primer semestre es pondera la nota de l'examen semestral 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_S1 = max( 0.4 · Nota_AC_S1 + 0.6 · Nota_Examen_S1,Nota_Examen_S1 )
Un dels exercicis d'avaluació contínua s'entregarà la setmana de punt de control, i substituirà l'examen corresponent.
En cas de suspendre la part de coneixements del primer semestre, 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 semestre 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_S1 = 0.4 · Nota_Pràctica_1 + 0.6 · Nota_Pràctica_2
Entrevista per alliberar l'examen semestral
En cas que un/a estudiant compleixi els requisits especificats a continuació, pot optar a convalidar l'examen final del primer semestre. Cal que l'estudiant:
- Aprovi totes les ACs, obtenint una mitjana superior o igual a 7.
- Aprovi la Pràctica 1 i entregui la Pràctica 2, ambdues en la primera convocatòria (sobre 10).
- Assisteixi de forma continuada a classe.
Els continguts de l'entrevista de convalidació, juntament amb la forma de demanar-la, es comunicaran quan s'apropi el final del primer semestre.
L'equip de l'assignatura proposarà una nota de convalidació a partir del resultat de l'entrevista i les notes d'AC. L'estudiant és lliure de renunciar a la convalidació, escollint realitzar l'examen del primer semestre.
Segon semestre:
El segon semestre es basa en la metodologia Project-Based Learning (PBL), pel que la nota final d'aquest es calcularà a partir de la del projecte.
El projecte està dividit en quatre fases, cadascuna corresponent a un bloc de continguts. Cada fase començarà amb la publicació de l'enunciat corresponent i acabarà amb dues activitats d'avaluació: Un checkpoint en forma de reunió amb l'equip de l'assignatura per validar l'estat del projecte, així com un qüestionari d'autoavaluació P2P. Amb aquests dos elements es calcularà una nota orientativa per cada fase.
Tot i així, l'avaluació definitiva es realitzarà al final del semestre, i consistirà en dues entregues diferents: Codi i memòria. La nota del projecte ponderarà aquests dos elements, però cada integrant del grup obtindrà una nota individual resultant de multiplicar-la per dos factors entre 0.5 i 1.5: Mentoria i P2P.
Nota_Projecte_S2 = 0.6 · Nota_Codi +0.4 · Nota_Memòria
Nota_S2 = Nota_Projecte_S2 · Factor_Mentoria · Factor_P2P
El factor de mentoria el determinarà l'equip de l'assignatura segons el seguiment en les sessions pràctiques, així com els resultats dels checkpoints. En cas que el grup no es presenti o no demostri haver treballat en dos o més checkpoints, la nota del projecte serà de NP i caldrà recuperar el semestre.
El factor de P2P es calcularà a partir dels quatre qüestionaris d'autoavaluació. En cas de no respondre un dels qüestionaris, el factor es calcularà a partir dels altres tres. En cas de no respondre'n dos o més, la nota del projecte serà de NP i caldrà recuperar el semestre.
Per aprovar el codi cal que totes les fases compleixin els requisits mínims de forma independent. En cas contrari, la nota corresponent serà com a molt de 4.
Cal aprovar el codi i la memòria per separat amb una nota de 5 o més. En cas contrari, la nota del projecte serà com a molt de 4 i no s'aplicaran factors individuals a cap membre del grup.
Examen de validació de coneixements
Per validar que tot i treballar en grup s'han adquirit els coneixements del semestre, tot/a estudiant que entregui el projecte haurà de presentar-se a un examen de validació.
Si s'aprova amb un 5 o més, aquest examen no tindrà efecte sobre la nota final. En cas contrari la substituirà, havent de recuperar el semestre.
Recuperació
En cas de suspendre el projecte (incloent no presentar-lo o suspendre l'examen de validació), es realitzarà un examen de recuperació a la convocatòria extraordinària de juliol, on cal treure un 5 o més per aprovar.
De forma excepcional, en funció del seguiment i l'estat del projecte es pot permetre una entrega de recuperació (sobre 8) a aquells grups que estiguin a prop d'aprovar. L'equip de l'assignatura té la potestat de permetre re-entregar el projecte només a una part del grup, havent-se de presentar la resta de membres a l'examen de recuperació.
La re-entrega i l'examen de recuperació són mecanismes mútuament excloents. En cas que un/a estudiant pugui re-entregar i decideixi presentar-se a l'examen aquesta serà la nota que prevaldrà.
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.