Logo

Disseny D'algoritmes

Codi: 104359
Crèdits: 6
2026/2027
Titulació Tipus Curs
Enginyeria de Dades OB 2

Professor/a de contacte

Nom :
Gemma Sanchez Albaladejo
Correu electrònic :
gemma.sanchez@uab.cat

Equip docent

Pau Cano Ribe

Idiomes dels grups

Podeu consultar aquesta informació al final del document.

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 cerca d'Informació

·         Enginyeria del Rendiment

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

 

Objectius

Partint de la base que l’estudiant ja té uns coneixements bàsics sobre programació, aquesta assignatura està centrada a introduir diferents estils i paradigmes de disseny d'algorismes. L'objectiu principal és que els estudiants desenvolupin habilitats en el disseny i anàlisi d'algorismes per a poder resoldre problemes del món real de manera efectiva i eficient d'acord amb els requisits establerts per un client potencial.

Per això s'espera que en acabar el curs l’estudiant sabrà:

  • Especificar formalment problemes i programes, i verificar-los.
  • Utilitzar proves formals per validar programes i invariants per dissenyar basant-se en contractes.
  • Calcular la complexitat algorísmica i computacional d’un algorisme.

Per altra banda, coneixerà i sabrà triar a cada moment diferents estils i paradigmes de disseny d’algorismes com:

  • Recursivitat
  • Backtracking
  • Programació dinàmica
  • Algorismes probabilístics
  • Etc.

L'algorísmica pretén trobar la forma més ràpida de solucionar problemes i això té dos vessants. La primera, i més importat, és trobar algorismes amb la mínima complexitat, o sigui que facin el mínim nombre d'operacions possible. La segona, correspon a programar les implementacions d'aquests algorismes de forma que l'execució sigui tan ràpida com sigui possible. Per tant, els objectius inclouen conèixer les tècniques de desenvolupament d'algorismes i la implementació de programes ràpids.

Resultats d'aprenentatge

  1. 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.
  2. Avaluar de manera crítica el treball realitzat.
  3. Decidir el mètode d'aprenentatge de dades més adequat segons les característiques de les dades que cal analitzar.

Continguts

El temari de l'assignatura serà:



  • Tema 1. Repàs de conceptes bàsics (Pre-condicions, post-condicions, invariants, Complexitat computacional)

  • Tema 2. Algorismes de cerca. Taxonomia i estratègies

  • Tema 3. Greedy

  • Tema 4. Divideix i venceràs

  • Tema 5. Backtracking

  • Tema 6. Branch & Bound

  • Tema 7. Programació dinàmica

  • Tema 8. Algorismes estocàstics


 


 


 


 


 

Activitats formatives i Metodologia

Títol Hores ECTS Resultats d'aprenentatge
Reforç i seguiment en la resolució del projecte i els exercicis 4 0,16 1, 2, 3
Preparació de parcials 12 0,48 1, 2, 3
Preparació prèvia a les classes 12 0,48 2, 3
Desenvolupament d'un projecte 44 1,76 1, 2, 3
Treball autònom 12 0,48 1, 2, 3
Seguiment en l'assimilació dels conceptes teòrics 4 0,16 1, 2, 3
Classes presencials 50 2 1, 2, 3

Tenint en compte que l'objectiu final de l'assignatura és que l'alumnat desenvolupi habilitats per analitzar i dissenyar algorismes de forma eficient segons un problema donat, el treball de l'alumnat és l'eix central del seu aprenentatge, acompanyat i guiat pel professorat. Per aquest motiu, les sessions dirigides seran altament pràctiques i es centraran en que l'alumnat consolidi els coneixements que són objectiu d'aprenentatge

d'aquesta assignatura.


La metodologia general de l'assignatura està dividida en tres fases:


Preparació de la sessió: l'objectiu d'aquesta fase és que l'alumnat pugui aprendre els conceptes que es treballaran a la/les sessió(ns) següent(s) 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ó.

Treball autònom: per tal que l'alumnat agafi desimboltura en la programació dels algorismes vistos aquest haurà de fer una part del treball pel seu compte amb

  1. exercicis solts que s'entregaran per ser avaluats
  2. dins d'un projecte de programació que s'anirà realitzant al llarg de tot el curs.

Projecte de programació: Dins del treball autònom demanat a l'alumnat, caldrà realitzar un projecte de programació que s'anirà desenvolupant al llarg de tot el curs, a mida que es vagi avançant en el temari. Cada part del projecte estarà relacionada amb un dels temes previstos i s'aniran plantejant dins de les sessionsde classe. Es dedicaran algunes hores de les sessions a plantejar lafeina a fer i també a fer el seguiment del correcte desenvolupament, així com el plantejament de dubtes.



Nota: es reservaran 15 minuts d'una classe, dins del calendari establert pel centre/titulació, perquè l'alumnat completi les enquestes d'avaluació de l'actuació del professorat i d'avaluació de l'assignatura.

Avaluació

Activitats d'avaluació continuada

Títol Pes Hores ECTS Resultats d'aprenentatge
Primer parcial teoria 20 2 0,08 1, 2, 3
Examen Final (recuperació) 40 3 0,12 1, 2, 3
Avaluació d'activitats desenvolupades a l'aula 5 1 0,04 1, 2, 3
Segon parcial teoria 20 2 0,08 1, 2, 3
Avaluació individual del projecte 10 1 0,04 2
Avaluació d'activitats desenvolupades fora de l'aula 10 1 0,04 3
Avaluació grupal del projecte 35 2 0,08 1, 2, 3

Aquesta assignatura no preveu el sistema d’avaluació única.


S'avaluaran tres tipus d'activitats de manera independent i la suma ponderada d'elles donarà la nota final. Aquestes tres activitats són:

  1. Proves de síntesi (PS)
  2. Exercicis Avaluables (EA)
  3. Projecte pràctic (P)


1. La primera part (PS) consisteix en la realització de dues proves parcials en les que s'avaluarà l'alumnat de forma individual. La nota mínima per aprovar cada prova és de 4, però la mitjana de les dues haurà d'arribar al 5.

2. La segona part (EA) consistirà en l'entrega d'activitats individuals al llarg de tot el curs. Aquestes activitats poden ser en forma d'exercicis, qüestionaris, informes, etc i es poden plantejar dins de les sessions de classe o poden ser proposades com a deures per fer a casa. La nota final sortirà de la suma ponderada de les entregues fixades que es demanin.

3. La tercera part (P) s'avaluarà de manera grupal (amb el lliurament d'un projecte) i individual (amb l'avaluació d'una prova escrita). La nota final s'obtindrà de la suma ponderada de la nota grupal i la individual. El projecte consta de diferents entregues al llarg del curs, les notes de les quals conformaran la nota grupal. La nota mínima per aprovar el projecte és de 5, mentre que l'examen individual cal aprovar-lo amb una nota mínima de 3.5. La nota final d'aquesta part haurà de ser com a mínim un 5.

Per aprovar l'assignatura és necessari que l'avaluació de cadascuna de les parts superi el mínim exigit i que l'avaluació total superi els 5 punts.


RECUPERACIÓ


PS: En el cas de suspendre o no presentar-se a alguna de les proves individuals es podran recuperar el dia assignat a la recuperació de l'assignatura.

EA: Aquesta part no tindrà la possibilitat de recuperar-se.

P: En el cas de suspendre l'avaluació individual del projecte (cal haver-se presentat la primera vegada), es podrà recuperar el dia assignat a la recuperació de l'assignatura. Els lliuraments parcials del projecte es poden recuperar en els següents lliuraments, amb una nota final del 80% (i per tant mai superior a 8).


CONVALIDACIÓ

No es convaliden projectes d'anys anteriors.


MH: Es donaran tantes matrícules com es puguin dins de la normativa de la universitat, començant per les notes més altes i sempre i quan la nota mínima sigui un 9.


NO AVALUABLE: Es considerarà no avaluable (NA) a l'alumnat que no fa com a mínim el 30% dels exercicis Avaluables (EA) i no fa cap de les proves de síntesi (PS) ni el lliurament del 30% dels projectes (P)


SUSPESOS: Si el càlcul de la nota final és igual o superior a 5 però no s’arriba al mínim exigit en alguna de les activitats d’avaluació, la nota final serà suspès i es posarà un 4.5 a la nota de l'expedient de l'alumnat que estigui en aquesta situació.Si es suspen degut a que s'han comès irregularitats (veure apartat PLAGIS, COPIES, ETC)


PLAGIS, COPIES, ETC:

Sense perjudici d'altres mesures disciplinàries que s'estimin oportunes, i d'acord amb la normativa acadèmica vigent, les irregularitats comeses per l'alumnat 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 exclusius de l'estudiant.
  • Tenir dispositius de comunicació (com telèfons mòbils, smart watches, etc.) accessibles durant les proves d'avaluació teòric-pràctiques individuals (exàmens).
  • L'ús de models d'IA/LLM en qualsevol activitat avaluativa.

En aquests casos, la nota numèrica de l'expedient serà el valor menor entre 3.0 i la mitjana ponderada de les notes (i per tant no serà possible l'aprovat per compensació). En l'avaluació dels lliuraments de problemes i pràctiques s’utilitzaran eines de detecció de còpia del codi del programa.



COMUNICACIÓ

Les dates d'avaluacions i lliuraments es publicaran al gestor documental campus virtual (https://cv.uab.cat/) i poden estar subjectes a possibles canvis de programació per motius d'adaptació a possibles incidències. Sempre s'informarà al Caronte sobre aquests canvis ja que s'entén que aquesta és la plataforma habitual d'intercanvi d'informació entre professors i estudiants.


REVISIONS: Per a cada activitat d’avaluació, s’indicarà un lloc, data i hora de revisió en la que l'estudiant podrà revisar l’activitat amb el professor. Algunes d'aquestes revisions es podran fer també mitjançant el campus virtual en l'entorn de prova pilot de revisió d'exàmens. En aquest context, es podran fer reclamacions sobre la nota de l’activitat, que seran avaluades pel professorat responsable de l’assignatura. A l'alumnat que no es presenti a aquesta revisió, no se li revisarà posteriorment aquesta activitat.


PROTOCOL DE SOL·LICITUT DE REPROGRAMACIÓ D'ACTIVITATS D'AVALUACIÓ:

En cas que un estudiant no pugui assistir a una prova parcial o a l’avaluació individual de seguiment del projecte per una causa degudament justificada i reconeguda per la titulació, no es programarà una prova alternativa abans de la recuperació. En aquests casos, l’estudiant realitzarà directament la prova de recuperació corresponent. Només en el cas que tampoc pugui acreditar l’assoliment dels resultats d’aprenentatge mitjançant aquesta prova, l’equip docent valorarà la realització d’una activitat d’avaluació específica addicional. Les incidències justificades que impedeixin la realització de lliuraments de problemes o del projecte seran analitzades individualment per l’equip docent, que determinarà les mesures compensatòries que corresponguin en funció de les circumstàncies de cada cas. En cas d’incidències tècniques generals que afectin la plataforma de lliurament i impedeixin o dificultin significativament la presentació dels treballs, els delegats o delegades del curs hauran de comunicar la incidència a tot l’equip docent tan aviat com sigui possible. Un cop verificada la incidència, s’establirà una ampliació extraordinària del termini de lliurament proporcional al temps durant el qual el servei hagi estat afectat.


ÚS DE LA IA. Ús restringit: Per a aquesta assignatura, es permet l'ús de tecnologies d'Intel·ligència Artificial (IA) exclusivament en tasques de suport, com la cerca bibliogràfica o d’informació, la correcció de textos o les traduccions, la generació de petits codis d'inicialització de classes o alguns processos simples de recorregut d'estructures simples com els vectors. Qualsevol treball que inclogui fragments generats amb IA en qualsevol altra tasca serà considerat una falta d'honestedat acadèmica i comportarà un 0 en la nota de l'activitat, podent comportar sancions majors en casos de gravetat. Per aquesta raò l'estudiant haurà d'identificar clarament quines parts han estat generades amb aquesta tecnologia, especificar les eines emprades i incloure una reflexió crítica sobre com aquestes han influït en el procés i el resultat final de l’activitat.


Bibliografia

  • Fundamentos de Algorítmia, G Brassard P. Bratley. Prentice Hall.
  • Análisis y diseño de algoritmos : un enfoque práctico, Eduardo Villegas Jaramillo, Luz Enith Guerrero Mendieta. (Primera edición.). Disponible en línia
  • Técnicas de Diseño de Algoritmos, Rosa Guerequeta y Antonio Vallecillo.
  • Técnicas de diseño de algoritmos, F. Perales, M. Mascaró. Universitat de les Illes Balears
  • Karumanchi, Narasimha. \"Algorithm Design Techniques: Recursion, Backtracking, Greedy, Divide and Conquer, and Dynamic Programming.\" (2018).
  • Chun, Wesley. Core python programming. Vol. 1. Prentice Hall Professional, 2001.

Programari

Es programarà en llenguatge de programació Python (versió 3.4 en endavant). No imposem cap restricció respecte del IDE que es vulgui fer servir (Anaconda, PyCharm, Visual Studio)

Grups i idiomes de l'assignatura

La informació proporcionada és provisional fins al 30 de novembre. A partir d'aquesta data, podreu consultar l'idioma de cada grup a través d'aquest enllaç. Per accedir a la informació, caldrà introduir el CODI de l'assignatura

Tipus de docència Grup Idioma Semestre Torn
(PAUL) Pràctiques d'aula 81 Català/Castellà segon quadrimestre matí-mixt
(PAUL) Pràctiques d'aula 82 Català/Castellà segon quadrimestre matí-mixt