Grau en Enginyeria Informàtica

Estudia Enginyeria Informàtica a La Salle i seràs un professional capaç de treballar amb les últimes tecnologies i nous productes, dissenyant, implementant i mantenint sistemes informàtics per a qualsevol sector d'activitat econòmica

Programació avançada i estructura de dades

Descripció
L'assignatura té com a objectiu oferir una visió avançada de la programació d’algorismes, així com 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 de forma eficient i elegant. És important dominar l’anàlisi descendent, la modularitat, la gestió de memòria, les estructures de dades lineals, el pseudocodi, el llenguatge C, etcètera, treballats a l’assignatura “Metodologia i tecnologia de la programació”. Amb l’assoliment dels conceptes exposats a l’assignatura, l’alumne adquireix habilitats per proposar i discutir l’adequació de solucions a problemes complexos.
Tipus assignatura
Tercer - Obligatoria
Semestre
Anual
Curs
2
Crèdits
8.00

Professors Titulars

Professor/a
Coneixements previs

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.

Objectius

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.

Continguts

L’assignatura divideix els continguts en dues parts clarament diferenciades:

• Durant el primer semestre es treballa l’especificació, l’anàlisi, el disseny i la verificació formal d’algorismes. El disseny comprèn un enfoc per la resolució de problemes mitjançant tècniques recursives simples i múltiples. S’inclou també en aquesta part l’estudi i l’aplicació de tècniques orientades a la resolució de problemes que presenten un espai combinatori de solucions.

• El segon semestre es centra en l’estudi d’estructures de dades avançades lineals i no lineals i les seves aplicacions pràctiques.

Les tècniques que s’estudien 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.

Metodologia

Durant l’assignatura, 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 d’AC a classe i pràctiques avaluables.
o Self-paced learning, per a continguts que no s’avaluaran directament.
o Flipped-classroom, per a motivar l’autoaprenentatge i donar suport a l’alumne.

• 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.

Avaluació

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 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 l’examen semestral amb la nota d’avaluació continua, només en el cas de beneficiar a l’alumne i sempre que la nota de l’examen 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 d’avaluació continua i tindrà un pes del 30% de la nota corresponent. La resta vindrà d’exercicis 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 d’avaluació continua no beneficiarà l’alumne, 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 en parelles, havent d’aprovar 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 l’examen semestral

En cas que un alumne compleixi els requeriments especificats a continuació, pot convalidar l’examen final del primer semestre, obtenint la nota d’avaluació continuada com a nota de coneixements semestral. Concretament, cal que l’alumne:

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.

L’alumne és lliure de renunciar a la convalidació, optant a realitzar l’examen 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 s’apropi 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 d’aquest 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 l’alumne.

A criteri del professorat, es podran realitzar entrevistes del projecte a aquells alumnes o grups que es consideri necessari per assegurar que s’han adquirit els coneixements vistos durant el semestre. En cas de suspendre el projecte, es podrà recuperar a la convocatòria extraordinària, com s’indica al següent apartat.

Criteris avaluació
Bibliografia bàsica

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.

Material complementari