Descripció:
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.
És important dominar l'anàlisi descendent, la modularitat, la gestió de memòria, les estructures de dades lineals, el llenguatge C, i altres continguts treballats a l'assignatura "Metodologia i tecnologia de la programació".
Amb l'assoliment dels conceptes exposats a l'assignatura, l'estudiantat adquireix habilitats per proposar i discutir l'adequació de solucions a problemes complexos.
Tipus assignatura
Tercer - Obligatoria
Semestre
Primer
Curs
2
Crèdits
4.00
Professors Titulars
Professor/a
Professors Docents
Coneixements previs:
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.
Objectius:
Els Resultats d'Aprenentatge amb els que s'alinea aquesta assignatura són:
- Definir programes informàtics interactius a partir de dissenys lògics i estructurats.
- Desenvolupar programari software de manera estructurada i eficient amb el propòsit de desenvolupar un projecte interactiu.
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.
Continguts:
Els continguts generals de l'assignatura són els següents:
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
Metodologia:
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.
Avaluació:
L'assignatura 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
Criteris avaluació:
La nota final de l'assignatura es calcula a partir de la ponderació de les notes de coneixements i de pràctiques.
Nota_Final = 0.5 · Nota_Coneixements + 0.5 · Nota_Pràctiques
Cal treure un 5 o més de cadascuna de les parts per a aprovar l'assignatura. Altrament, la nota serà com a molt un 4.
Coneixements
Per a calcular la nota de coneixements es pondera la nota de l'examen final 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 = max( 0.4 · Nota_AC + 0.6 · Nota_Examen,Nota_Examen )
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, 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 es calcula ponderant les notes de les dues pràctiques que es 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 = 0.4 · Nota_Pràctica_1 + 0.6 · Nota_Pràctica_2
Entrevista per alliberar l'examen final
En cas que un/a estudiant compleixi els requisits especificats a continuació, pot optar a convalidar l'examen final. 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 final.
Bibliografia bàsica:
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.
Material complementari: