Logo UAB
2022/2023

Disseny d’Algoritmes

Codi: 104359 Crèdits: 6
Titulació Tipus Curs Semestre
2503758 Enginyeria de Dades OB 2 2

Professor/a de contacte

Nom:
Jorge Bernal del Nozal
Correu electrònic:
jorge.bernal@uab.cat

Utilització d'idiomes a l'assignatura

Llengua vehicular majoritària:
català (cat)
Grup íntegre en anglès:
No
Grup íntegre en català:
Grup íntegre en espanyol:
No

Equip docent

Jorge Bernal del Nozal

Prerequisits

Tot i que no és obligatori, és molt aconsellable haver cursat les següents assignatures:

·         Fonaments de Programació

·         Programació Avançada

·         Estructures de Dades

·         Anàlisi de Grafs i prop d'Informació

·         Enginyeria l'Rendiment

Es considerarà que l'alumne ja ha adquirit prèviament els coneixements impartits en aquestes assignatures.

 

Objectius

Partint de la base que els alumnes tenen uns coneixements bàsics sobre programació i estructures de dades adquirits en assignatures anteriors, es pretén que l'alumne sigui capaç d'analitzar, dissenyar i implementar algoritmes basant-se en les tècniques de disseny d'algoritmes existents. Per complir amb aquest objectiu, l'alumne adquirirà els coneixements sobre:

·         Especificació formal de problemes. Com passar d'una descripció d'un problema a una especificació vàlida per al desenvolupament d'un algoritme que el resolgui.

·         Proves formals per validar programes. Disseny basat en contractes. Precondicions, postcondicions i invariants.

·         Paradigmes per al disseny d'algorismes. Algorismes de cerca, Greedy,  recursivitat, backtracking, branch & bound, programació dinàmica, algoritmes probabilístics, etc.

El desenvolupament d'un algoritme comença per formalitzar l'enunciat d'un problema. A partir d'aquest enunciat es dissenya un algoritme que solucioni el problema, però això no és suficient, també és important considerar quant trigarà l'algorisme en donar-nos la solució. Així que ens interessa a crear algoritmes el més ràpids possibles. D'aquesta manera podrem crear programes que solucionin problemes el més grans possibles en temps acceptables. Aquesta rapidesa s'aconsegueix dissenyant algoritmes que minimitzin el nombre d'operacions a realitzar per resoldre un problema i desenvolupant una implementació eficient de les operacions de l'algoritme. Això suposarà que en aquesta assignatura l'alumne adquirirà coneixements sobre algorísmica i implementació eficient d'algoritmes.

 

Competències

  • Avaluar de manera crítica el treball realitzat.
  • Dissenyar solucions algorítmiques eficients per a problemes computacionals, implementar-les en forma de desenvolupaments de programari robust, estructurat i fàcil de mantenir, i verificar-ne la validesa.
  • Que els estudiants tinguin la capacitat de reunir i interpretar dades rellevants (normalment dins de la seva àrea d'estudi) per emetre judicis que incloguin una reflexió sobre temes destacats d'índole social, científica o ètica.

Resultats d'aprenentatge

  1. Avaluar de manera crítica el treball realitzat.
  2. Decidir el mètode d'aprenentatge de dades més adequat segons les característiques de les dades que cal analitzar.
  3. Que els estudiants tinguin la capacitat de reunir i interpretar dades rellevants (normalment dins de la seva àrea d'estudi) per emetre judicis que incloguin una reflexió sobre temes destacats d'índole social, científica o ètica.

Continguts

El temari de l'assignatura serà:

  1. Tema 1. Repàs de conceptes bàsics (Pre-condicions, post-condicions, invariants)
  2. Tema 2. Complexitat computacional
  3. Tema 3. Algorismes de cerca. Taxonomia i estratègies
  4. Tema 4. Greedy
  5. Tema 5. Recursivitat
  6. Tema 6. Divideix i venceràs
  7. Tema 7. Backtracking.
  8. Tema 8. Branch & Bound.
  9. Tema 9. Programació dinàmica.
  10. Tema 10. Algorismes estocàstics

 

 

 

 

 

Metodologia

Tenint en compte que l'objectiu final de l'assignatura és que l'alumnat sigui capaç d'analitzar i dissenyar algoritmes de forma eficient segons un problema donat, el treball personal de l'alumnat ha de ser la part principal per obtenir els objectius d'aprenentatge, sempre acompanyat i guiat pel professorat. Per aquest motiu, les classes presencials seran altament pràctiques i se centraran en què l'alumnat consolidi els coneixements que són objectiu d'aprenentatge d'aquesta assignatura.

La metodologia general de l'assignatura es pot dividir en tres fases:

Preparació de la classe: l'objectiu d'aquesta fase és que l'alumnat pugui aprendre els conceptes que es treballaran en la sessió següent mitjançant diverses activitats ofertes pel professorat com pot ser el visionat de vídeos, la lectura de textos, etc.

Classe presencial: l'objectiu d'aquesta fase és la de consolidar els conceptes vistos i posar-los en valor dins del context de l'assignatura. El professorat vetllarà perquè l'alumnat aprofundeixi en aquests conceptes mitjançant exercicis (més o menys) guiats durant la sessió. Així la classe començarà amb una explicació resumida dels conceptes que l'alumne haurà estudiat en la preparació de la classe. Aquest resum donarà una visió general sobre els conceptes en estudi i donarà peu a que els alumnes puguin resoldre els dubtes que tinguin. Després s'explicarà el problema o treball pràctica a realitzar durant la segona part de la classe. Aquests problemes o pràctiques es realitzaran amb ordinador, ja que en molts casos suposaran implementar algoritmes.

Treball autònom: perquè l'alumnat prengui soltesa en la programació dels algoritmes vistos, aquest haurà de fer una part de la feina pel seu compte, ja siguin exercicis solts o dins d'un projecte.

La metodologia docent i l'avaluació proposades poden experimentar alguna modificació en funció de les restriccions a la presencialitat que imposin les autoritats sanitàries

 

Nota: es reservaran 15 minuts d'una classe, dins del calendari establert pel centre/titulació, per a la complementació per part de l'alumnat de les enquestes d'avaluació de l'actuació del professorat i d'avaluació de l'assignatura/mòdul.

Activitats formatives

Títol Hores ECTS Resultats d'aprenentatge
Tipus: Dirigides      
Classe de Teoría 22 0,88 2
Tipus: Supervisades      
Classe de problemes 14 0,56 1, 2
Classes de pràctiques 14 0,56 1, 2, 3
Tipus: Autònomes      
Estudi de la matèria impartida en teoria 40 1,6 2
Realització de problemes 25,5 1,02 1, 2, 3
Resoldre la práctica 25 1 1, 2, 3

Avaluació

Criteris i indicadors d'avaluació:

·         Comprensió dels conceptes teòrics de l'assignatura.

·         Implementació correcta i eficient d'algoritmes.

Activitats i instruments d'avaluació:

·         Nota Teoria: correspon a dos exàmens parcials de teoria sobre l'assignatura. S'han aprovar els exàmens parcials per eliminar matèria en el examen de recuperació.

·         Nota de problemes: Correspon a la nota obtinguda per una sèrie de problemes que haurà de lliurar a l'alumne. No hi ha recuperació per als lliuraments de problemes.

·         Nota seguiment del progrés d'aprenentatge: correspon a la nota obtinguda en les diferents activitats de seguiment de l'aprenentatge que es realitzaran durant el curs (qüestionaris en Caront, Kahoots) i que es duran a terme sempre durant les classes presencials. No hi ha recuperació per a aquestes activitats.

·         Nota Pràctiques: En aquest apartat hi ha una nota de grup i una individual:

o   Nota de grup: Correspon a la nota obtinguda als lliuraments per grups de la pràctica. Els lliuraments de pràctiques suspeses es pots recuperar en lliuraments posteriors.

o   Nota individual: És la puntuació obtinguda en l'examen de pràctiques. Hi haurà recuperació de l'examen de pràctiques.

La nota final de l'assignatura s'obté combinant l'avaluació d'aquestes quatre activitats de la següent manera:

A.  Nota Teoria

SI Nota examen primer parcial> = 5 i Nota examen segon parcial> = 5 LLAVORS

Nota Teoria= 0,5 * Nota examen primer parcial + 0,5 * Nota examen segon parcial

SINÓ Nota Teoria= MIN (Nota examen primer parcial, Nota examen segon parcial)

B.  Nota Problemes

Nota problemes = Mitjana dels problemes lliurats.

C.   Nota Seguiment

Nota seguiment = Nota acumulada recollida dels diferents sistemes d'avaluació presencial.

D.  Nota Pràctiques

SI Nota Individual> = 5 i Nota Grup> = 5 LLAVORS

Nota Pràctiques = 0,2 * Nota Individual + 0,8 * Nota Grup

SINÓ Nota Pràctiques = MIN (Nota Individual, nota Grup)

On:

·         Nota Individual = Examen de pràctiques.

·         Nota Grup = Mitjana ponderada dels lliuraments de pràctiques si totes estan aprovades, sinó el mínim de les notes dels lliuraments. En el cas de que la pràctica es faci de manera individual, no hi haurà examen de pràctiques pels alumnes que escollin aquesta opció.

·         Recuperació de pràctiques: En el cas d'haver suspès un lliurament de grup, es podrà recuperar en els següents lliuraments de la pràctica. La nota serà 0.75 * (max (nota recuperació, nota lliurament suspesa) Nota lliurament suspesa) + nota lliurament suspesa. En el cas de suspendre l'examen de pràctiques, l'alumne haurà de presentar a un examen de recuperació de pràctiques el mateix dia de l'examen de recuperació final.

 

Nota Final

Si Nota Teoria> = 5 i Nota Pràctiques> = 5 LLAVORS

Nota Final = 0,35 * Nota Teoria + 0,2 * Nota problemes + 0,1 * Nota seguiment + 0,35 * Nota Pràctiques

SINÓ Nota Final = MIN (Nota Teoria, Nota Pràctiques)

 

Condicions per aprovar l'assignatura:

Per aprovar l'assignatura s'ha d'haver aprovat (nota major o igual a 5):

·         Nota final

·         Nota teoria.

·         Nota pràctiques.

·         Notes lliuraments de pràctiques.

·         Exàmens.

Condicions per no avaluable:

·         No tenir cap part de l'assignatura suspesa i no complir les condicions per aprovar.

Condicions per al suspens:

·         No assolir una nota mitjana igual o superior a 5.

·         Suspendre alguna de les activitats d'avaluació de l'assignatura, tot i que la mitjana superi el 5. En aquest cas, la nota serà la nota mínima obtinguda d'alguna de les parts (exàmens o pràctiques).

Condicions per a la matrícula d'honor:

La matrícula d'honor es pot aconseguir amb una nota mitjana superior o igual a 9,0.

A causa de que hi ha un nombre limitat de matrícules de honor que es poden donar per grup, s'atorgaran per ordre d'nota de més a menys.

Pràctiques, treballs o exàmens copiats:

Sense perjudici d'altres mesures disciplinàries que s'estimin oportunes, i d'acord amb la normativa acadèmica vigent, les irregularitats comeses per un estudiant que puguin conduir a una variació de la qualificació es qualificaran amb un zero (0) . Les activitats d'avaluació qualificades d'aquesta forma i per aquest procediment no seran recuperables. Si és necessari superar qualsevol d'aquestes activitats d'avaluació per aprovar l'assignatura, aquesta assignatura quedarà suspesa directament, sense oportunitat de recuperar-la en el mateix curs. Aquestes irregularitats inclouen, entre d'altres:

- la còpia total o parcial d'una pràctica, informe, o qualsevol altra activitat d'avaluació;

- deixar copiar;

- presentar un treball de grup no fet íntegrament pels membres del grup;

- presentar com a propis materials elaborats per un tercer, encara que siguin traduccions o adaptacions, i en general treballs amb elements no originals i exclusiusde l'estudiant;

- tenir dispositius de comunicació (com telèfons mòbils, smart watches, etc.) accessibles durant les proves d'avaluació teoricopràctiques individuals (exàmens).

En cas que l'estudiant hagi comès irregularitats en un acte d'avaluació, la nota numèrica de l'expedient serà el valor menor entre 3.0 i la nota que li correspondria segons el mètode d'avaluació de l'assignatura (i per tant no serà possible l'aprovat per compensació).

Ras i curt: copiar, deixar copiar o plagiar en qualsevol de les activitats d'avaluació equival a un SUSPENS amb nota inferior a 3.0.

Publicació de notes, dates d'exàmens, etc:

Les dates d'avaluació continuada i lliurament de treballs es publicaran al campus virtual i poden estar subjectes a canvis de programació per motius d'adaptació a possibles incidències. Sempre s'informarà al campus virtual sobre aquests canvis ja que s'entén que és el mecanisme habitual d'intercanvi d'informació entre professor i estudiants.

Procediment de revisió de les qualificacions

Per a cada activitat d'avaluació, s'indicarà un lloc, data i hora d'revisió en la qual l'estudiant podrà revisar l'activitat amb el professor. En aquest context, es podran fer reclamacions sobre la nota de l'activitat, que seran avaluades pel professorat responsable de l'assignatura. Si l'estudiant no es presenta en aquesta revisió, no es revisarà posteriorment aquesta activitat.

 

Activitats d'avaluació

Títol Pes Hores ECTS Resultats d'aprenentatge
Avalació de pràctiques Veure activitts i instruments d'avaluació 2 0,08 1, 2, 3
Exam Final Veure activitats i instruments d'avaluació 2,5 0,1 2
Exam de pràctiques Veure activitats i instruments d'avaluació 1 0,04 1, 3
Primer parcial teoría Veure activitats i instruments d'avaluació 2 0,08 1, 2
Segon parcial teoría Veure activitats i instruments d'avaluació 2 0,08 1, 2

Bibliografia

·         Fonaments d'algorísmia, G Brassard P. Bratley. Prentice Hall.

·         Tècniques de Disseny d'Algorismes, Rosa Guerequeta i Antonio Vallecillo.

·         Tècniques de disseny d'algoritmes, F. Perales, M. Mascaró. Universitat de les Illes Balears

·         Karumanchi, Narasimha. "Algorithm Design Techniques: Recursion, Backtracking, Greedy, Divideix and Conquer, and Dynamic Programming." (2018).

·         Chun, Wesley. Core python programming. Vol. 1. Prentice Hall Professional, 2001.

Programari

Per fer les pràctiques es farà servir el llenguatge de progamació Python (versió 3.4 en endavant). No imposem cap restricció respecte del IDE que es vulgui fer servir (Anaconda, PyCharm, Visual Studio)