Professors Titulars
Professors Docents
Domini de les tècniques de programació treballades a Metodologia i Tecnologia de la Programació (anàlisi descendent, modularitat, pas de paràmetres i estructures de dades bàsiques).
Conèixer bé el llenguatge que s´utilitzarà per realitzar els exercicis (Pseudocodi/C/Java).
Capacitat per seguir i proposar raonaments matemàtics.
Resultats d´aprenentatge
- Ús d´un entorn real de programació
- Treball en equip en l´análisis, 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:
- Avaluar l´eficiència d´un algorisme a través del càlcul del cost.
- Dissenyar un algorisme recursiu.
- Transformar un algorisme recursiu a iteratiu.
- Justificar la necessitat de l´especificació formal dels algorismes.
- Explicar els principals mecanismes de derivació formal i demostració formal d´algorismes recursius simples i de dur-ho a la pràctica en problemes.
- Fer l´especificació d´una funció en termes de pre i post-condicions.
- Implementar un algorisme sense ambigüetats a partir de l´especificació del mateix.
- 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 eficiencia i eficacia.
- Especificar formalment qualsevol Tipus Abstracte de Dades usant especificació algebraica.
- Implementar un Tipus Abstracte de Dades a partir de la seva especificació algebraica.
- Dissenyar i implementar l´estructura de dades més adequada per una determinada aplicació, donats uns requisits d´eficiència temporal i espaial.
- Implementar els arbres binaris, n-aris, avl, 2-3, B i heaps. Implementar també els diversos recorreguts possibles.
- Implementar les taules vistes a l´assignatura.
- Implementar les variants dels diferents grafs. Implementar la cerca del camí mínim.
Lassignatura divideix els continguts en dues parts clarament diferenciades:
Durant el primer semestre es treballa lespecificació, lanàlisi, el disseny i la verificació formal dalgorismes. El disseny comprèn un enfoc per la resolució de problemes mitjançant tècniques recursives simples i múltiples. Sinclou també en aquesta part lestudi i laplicació de tècniques orientades a la resolució de problemes que presenten un espai combinatori de solucions.
El segon semestre es centra en lestudi destructures de dades avançades lineals i no lineals i les seves aplicacions pràctiques.
Les tècniques que sestudien inclouen coneixements teòrics i pràctics, habilitats, experiències i sentit crític, totes elles fonamentades en teories i tècniques sòlides, comprovades i ben establertes.
Durant lassignatura, es faran servir les següents metodologies, per semestre:
Primer Semestre:
o Classes magistrals, per a aquells continguts que ho requereixin.
o Problemes i exercicis a classe, per a consolidar coneixements.
o Exercicis dAC a classe i pràctiques avaluables.
o Self-paced learning, per a continguts que no savaluaran directament.
o Flipped-classroom, per a motivar lautoaprenentatge i donar suport a lalumne.
Segon Semestre:
o Project-Based Learning, on els alumnes aprendran a dissenyar i implementar estructures de dades.
o Classes magistrals intercalades per introduir els conceptes necessaris, complementats durant el PBL.
o Self-paced learning, per a continguts que no es puguin aplicar al projecte.
Lassignatura é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 saproven els dos semestres, lassignatura queda suspesa amb un 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à de 4.
Coneixements
Per a calcular la nota de coneixements del primer semestre es pondera la nota de lexamen semestral amb la nota davaluació continua, només en el cas de beneficiar a lalumne i sempre que la nota de lexamen sigui superior a 3,5.
Nota_Coneixements_S1 = max( 0.6 · Nota_AC_S1 + 0.4 · Nota_Examen_S1,Nota_Examen_S1 )
En aquest primer semestre, el punt de control comptarà com a nota davaluació continua i tindrà un pes del 30% de la nota corresponent. La resta vindrà dexercicis realitzats a classe.
En cas de suspendre la part de coneixements del primer semestre, es realitzarà un examen de recuperació al Juliol, on la nota davaluació continua no beneficiarà lalumne, 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 shi realitzen en parelles, havent daprovar cadascuna per separat amb nota igual o superior a 5. Altrament, la nota de pràctiques serà un 4.
Nota_Pràctiques_S1 = 0.4 · Nota_Pràctica_1 + 0.6 · Nota_Pràctica_2
Alliberar lexamen semestral
En cas que un alumne compleixi els requeriments especificats a continuació, pot convalidar lexamen final del primer semestre, obtenint la nota davaluació continuada com a nota de coneixements semestral. Concretament, cal que lalumne:
Es presenti a totes les ACs, incloent el punt de control, obtenint una mitjana ponderada superior o igual a 7.
Entregui les dues pràctiques del primer semestre.
Assisteixi de forma continuada a classe i mostri interès.
Lalumne és lliure de renunciar a la convalidació, optant a realitzar lexamen del primer semestre, ja sigui en convocatòria ordinària o extraordinària.
Els mecanismes concrets de convalidació, juntament amb la forma de demanar-la, es comunicaran amb temps quan sapropi el final del primer semestre.
Segon semestre:
El segon semestre es basa gairebé totalment en la metodologia Project-Based Learning (PBL), pel que la nota final daquest serà la nota del projecte, que cal que sigui superior o igual a 5 per aprovar:
Nota_S2 = Nota_Projecte_S2
El punt de control del segon semestre consistirà en un exercici opcional que només podrà bonificar la nota de lalumne.
A criteri del professorat, es podran realitzar entrevistes del projecte a aquells alumnes o grups que es consideri necessari per assegurar que shan adquirit els coneixements vistos durant el semestre. En cas de suspendre el projecte, es podrà recuperar a la convocatòria extraordinària, com sindica al següent apartat.
Brass, P. (2008). Advanced Data Structures. Cambridge University Press.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2014). Introduction to algorithms (3rd Edition). MIT Press.
Sedgewick, R., Wayne, K. (2011). Algorithms (4th Edition). Addison-Wesley Professional.
Skiena, S. S. (2012). The algorithm design manual (2nd Edition). Springer.