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: 2020-2021

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

 

   -

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

   -

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

   -

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 arbres

2.1. Tornada enrere (backtracking), cerca, ramificació, poda

3. Algorismes sobre grafs

4. Algorismes greedy

5. Programació dinàmica

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 prèviament realitzada, i el laboratori a una classe de problemes en què l’estudiant ha de resoldre davant de l’ordinador i de manera individual els problemes proposats pel 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 problemes 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 següents escenàris:

En el model esperat de docència mixta:

L’assignatura es distribueix en un bloc d’una hora i mitja a la setmana presencials corresponents a classes teòrico-pràctiques per a un total de 15 sessions al llarg de l’any en les quel’estudiant i el professor treballen de forma conjunta en la resolució de problemes a la pissarra i també a l’ordinador. En aquestes classes es dedica un cert temps a la resolució de dubtes dels conceptes teòrics explicats a teoria. Un altre hora i mitja no presencial assíncrona es dedica a classes de laboratori en les que l’estudiant ha de resoldre les pràctiques que li ha proposat el professorat, davant de l’ordinador i de manera individual. I finalment una hora no presencial principalment síncrona en la que els professors expliquen els conceptes teòrics a partir de casos que l’estudiant es pot trobar al món rea

En cas de docència virtual obligada per la situació sanitària

Els rangs horaris es mantenen i la docència teòrico-pràctica es realitzarà principalment en format no-presencial síncron, podent variar el repartiment de l’alumnat en grups.

En cas de docència presencial:

Els rangs horaris es mantenen però totes les classes es fan en modalitat presencial, podent variar el repartiment de l’alumnat en grups.

 

 

Avaluació acreditativa dels aprenentatges

 

L’avaluació continuada es basa en exàmens (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 de teoria. —Es fa un examen proves de coneixement (PC) al llarg del curs i un examen final (EF) amb una part pràctica i una part teòrica. Depenent de la situació sanitària les proves és realitzaran en modalitat presencial o no-presencial

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. Depenent de la situació sanitària les proves és realitzaran en modalitat presencial o no-presencial

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