Pla docent de l'assignatura

 

 

Tanca imatge de maquetació

 

Imprimeix

 

Dades generals

 

Nom de l'assignatura: Algorísmica Avançada

Codi de l'assignatura: 364300

Curs acadèmic: 2021-2022

Coordinació: Santiago Segui Mesquida

Departament: Departament de Matemàtiques i Informàtica

crèdits: 6

Programa únic: S

 

 

Hores estimades de dedicació

Hores totals 150

 

Activitats presencials i/o no presencials

52,5

 

-  Teoria

Presencial

 

22,5

 

-  Exercicis pràctics

Presencial

 

15

 

-  Pràctiques de laboratori

Presencial

 

15

Treball tutelat/dirigit

47,5

Aprenentatge autònom

50

 

 

Competències que es desenvolupen

 

   -

6T-TRANSV. Capacitat abstractiva: crear i utilitzar models que reflecteixin situacions reals.

   -

4T-TRANSV. Capacitat de fer raonaments crítics i lògics.

   -

6FC - FORMACIÓ COMUNA. Coneixement i aplicació dels procediments algorísmics bàsics de les tecnologies informàtiques per dissenyar solucions a problemes, analitzant la idoneïtat i complexitat dels algorismes proposats.

Objectius d'aprenentatge

 

Referits a coneixements

— Conèixer les tècniques algorísmiques avançades que permeten abordar el desenvolupament de programes correctes i eficients per resoldre problemes computacionalment no trivials.

— Conèixer les tècniques avançades d’anàlisi d’algorismes que permeten avaluar la complexitat computacional d’un algorisme.

 

 

Blocs temàtics

 

1. Introducció a l’algorísmica avançada

1.1. Algorismes exhaustius, aproximats, recursió, complexitat

2. Algorismes sobre grafs

2.1. Representació, DFS, BFS, components connexes

2.2. Dijkstra, Bellman-Ford, ordre topològic

2.3. Ford-Fulkerson, Max-flow min-cut

3. Algorismes greedy

3.1. Minimum spanning tree; Kruskal; Prim

4. Programació dinàmica

4.1. Knapsack; Floyd-Warshall; etc.

5. Algoritmes enumeratius

5.1. Backtracking

5.2. Ramificació i poda

6. Complexitat, problemes P i NP

 

 

Metodologia i activitats formatives

 

L’assignatura es distribueix en tres blocs principals: teoria, problemes i laboratori. La teoria correspon a les classes magistrals, els problemes corresponen a exercicis relacionats amb la teoria feta prèviament, i el laboratori a una classe de problemes en què l’estudiant ha de resoldre davant de l’ordinador i de manera individual els que ha plantejat el professorat. Prèviament, els ha d’haver treballat de manera autònoma.

Durant la docència presencial s’incideix especialment en els aspectes següents:

— Ús, durant les classes magistrals, de casos reals que exemplifiquin la relació entre els conceptes teòrics i els problemes que l’estudiant es pot trobar en el món real.

— Ús, durant les sessions de resolució de problemes, de casos que permetin a l’estudiant fer anàlisis tant teòriques com empíriques.

— En la part de laboratori, implementar de manera eficient el codi associat als continguts de les classes de teoria i exercicis i relacionats amb problemes algorísmics avançats.

 

Donada la situació sanitària, la docència magistral es pot veure modificada per un dels escenaris següents:

Quan l’ocupació sigui del 50 %

Els alumnes rebran docència presencial una setmana i per Internet la següent

Quan l’ocupació sigui del 100 %

L’estructura horària serà la mateixa, però amb la totalitat d’alumnes en modalitat presencial.

 

En la mesura que sigui possible s’incorporarà la perspectiva de gènere en el desenvolupament de l’assignatura.

 

 

Avaluació acreditativa dels aprenentatges

 

L’avaluació continuada es basa en exàmens presencials (tant de teoria com de pràctiques) i en el lliurament de problemes resolts a l’ordinador (associats als enunciats de les sessions de pràctiques).

Proves presencials de teoria. Es fa un examen parcial (EP) al llarg del curs i un examen final (EF) amb una part pràctica i una part teòrica. 

Cada prova individual de teoria ha d’obtenir una nota mínima de 4 punts sobre 10 per tal de fer mitjana; en cas contrari, proves de teoria amb nota inferior a 4 s’hauran de recuperar el dia de recuperació d’examen (vegeu Reavaluació). Les proves de teoria es fan sense apunts. La nota final de les proves presencials de teoria (PT) és la mitjana de les dues proves de teoria en cas de complir els requisits de nota mínima especificats.

Proves de pràctiques. Durant el curs, l’estudiant ha de fer dues proves davant de l’ordinador sobre les pràctiques. 

En tots els casos, el professorat ha d’avaluar la prova amb una nota de 0 (nota mínima) a 10 (nota màxima). Cada prova individual de pràctiques ha d’obtenir una nota mínima de 4 punts sobre 10 per tal de fer mitjana; en cas contrari, proves de pràctiques amb nota inferior a 4 s’hauran de recuperar el dia de recuperació d’examen (vegeu Reavaluació). En les proves presencials de pràctiques, tant davant de l’ordinador, com en paper en el cas de la recuperació, els alumnes poden portar apunts impresos. La nota final de les proves de pràctiques (PP) és la mitjana de les dues proves de pràctiques en cas de complir els requisits de nota mínima especificats.

Lliurament de pràctiques. El professorat proposa un seguit de problemes de pràctiques que l’alumnat ha de lliurar al Campus Virtual de l’assignatura dins del període que s’assenyali. Els lliuraments han d’incloure el Notebook amb codi Python comentat, amb la solució als problemes proposats i les respectives anàlisis d’eficiència. Cada lliurament de pràctiques s’avaluarà amb una nota que pot anar de 0 (nota mínima) a 10 (nota màxima). Si l’estudiant no lliura els problemes dins del període assenyalat, obté un 0. La nota final dels lliuraments de pràctiques (LP) és la mitjana de tots els lliuraments.

Segons aquest esquema, i si es compleixen les notes mínimes especificades, per poder estimar la nota final de l’assignatura, l’estudiant ha de complir la condició següent:

PT>= 4,0, PP >= 4,0, i LP >= 4,0.

En aquest cas, la nota final es calcula segons la fórmula següent:

Nota_Final = 1/3 * PT + 1/3 * PP + 1/3 * LP 

Per aprovar l’assignatura s’ha de complir que Nota_Final >= 5. En cas contrari, l’estudiant no aprova segons el model d’avaluació continuada i ha de fer un examen final únic anomenat Reavaluació (vegeu Reavaluació) —sempre que la nota obtinguda com a nota final sigui com a mínim un 3,5—, i que consta d’una part teòrica escrita i una prova pràctica davant de l’ordinador.

Reavaluació

Finalment, tots aquells alumnes que obtinguin una Nota_Final >= 3,5 tenen dret a una reavaluació. La nota final de l’assignatura és llavors la nota de la reavaluació.

 

Avaluació única

L’avaluació única consisteix en un examen final únic que consta d’una part teòrica (EP) i una prova pràctica (LP) davant de l’ordinador. Tant la part teòrica EP com la part pràctica LP s’avaluaran amb una nota que pot anar de 0 (nota mínima) a 10 (nota màxima).

L’estudiant que es vulgui acollir a l’avaluació única ho ha de sol·licitar a la Secretaria de la Facultat dins dels terminis establerts cada curs acadèmic.

 

Reavaluació

Finalment, tots aquells alumnes que obtinguin una Nota_Final >= 3,5 tenen dret a una reavaluació. La nota final de l’assignatura és llavors la nota de la reavaluació.

En aquest cas, la nota s’avalua de la manera següent:

Nota_Final = 0,5 * EP + 0,5 * LP

Per aprovar l’assignatura s’ha de complir que EP >= 4,0, LP >= 4,0, i Nota_Final >= 5. En cas contrari, l’estudiant no aprova segons el model d’avaluació única i ha de fer un examen final únic anomenat reavaluació (vegeu Reavaluació) —sempre que la nota obtinguda com a nota final sigui com a mínim un 2,5—, que consta d’una part teòrica escrita i d’una prova pràctica davant de l’ordinador.

Reavaluació

Els alumnes no presentats tenen dret a un procés de reavaluació.

Qualsevol intent de frau comporta l’aplicació de la normativa acadèmica general de la UB i l’inici d’un procés disciplinari.