Aquesta versió de la guia docent és provisional fins que no finalitzi el període d’edició de les guies del nou curs.

Logo UAB

Anàlisi i Disseny d'Algorismes

Codi: 102783 Crèdits: 6
2025/2026
Titulació Tipus Curs
Enginyeria Informàtica OB 3
Enginyeria Informàtica OT 4

Professor/a de contacte

Nom:
Francisco Javier Sánchez Pujadas
Correu electrònic:
javier.sanchez.pujadas@uab.cat

Equip docent

Pau Cano Ribe

Idiomes dels grups

Podeu consultar aquesta informació al final del document.


Prerequisits

No hi ha prerequisits formals però es recomana haver aprovat les assignatures de:

Primer curs del grau:  

  • Fonaments d’informàtica
  • Metodologia de la programació
  • Matemàtica discreta

Segon curs del grau: 

  • Laboratori de programació

Objectius

Aquesta assignatura és la continuació de les assignatures de programació vistes a primer i segon, com Fonaments d’informàtica, Metodologia de la programació i Laboratori de programació. 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 programa les implementacions d'aquests algorismes de la 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. 


Competències

    Enginyeria Informàtica
  • Adquirir hàbits de pensament.
  • Capacitat per a avaluar la complexitat computacional d'un problema, conèixer estratègies algorítmiques que puguin conduir a la seva resolució i recomendar, desenvolupar i implementar aquella que garanteixi el millor rendiment d'acord amb els requisits establerts.
  • Capacitat per concebre, desenvolupar i mantenir sistemes, serveis i aplicacions informàtiques emprant els mètodes de l'enginyeria del software com a instrument per a assegurar-ne la qualitat.
  • Capacitat per definir, avaluar i seleccionar plataformes de maquinari i programari per al desenvolupament i l'execució de sistemes, serveis i aplicacions informàtiques.
  • Treballar en equip.

Resultats d'aprenentatge

  1. Avaluar la complexitat dels algoritmes i identificar els seus punts dèbils.
  2. Conèixer els mecanismes de funcionament dels diferents paradigmes de programació.
  3. Desenvolupar el pensament científic.
  4. Desenvolupar la capacitat d'anàlisi, síntesi i prospectiva.
  5. Identificar i seleccionar estratègies algorítmiques adequades al problema.
  6. Seleccionar la millor tècnica de programació per a la resolució de problemes complexos.
  7. Treballar cooperativament.

Continguts

  • Tema 1. Precondicions, postcondicions i invariants
  • Tema 2. Recursivitat i complexitat Computacional
  • Tema 3. Divideix i venceràs
  • Tema 3. Backtracking
  • Tema 4. Branch & Bound
  • Tema 5. Programació Dinàmica
  • Tema 6. Greedy
  • Tema 7. Algorismes probabilístics
  • Tema 8. Anàlisi d'algorismes

Activitats formatives i Metodologia

Títol Hores ECTS Resultats d'aprenentatge
Tipus: Dirigides      
Classes presencials 50 2 1, 2, 4, 5, 6, 7
Tipus: Supervisades      
Reforç i seguiment en la resolució del projecte i els exercicis 4 0,16 1, 4, 5, 6
Seguiment en l'assimilació dels conceptes teòrics 4 0,16 1, 2, 4, 5, 6
Tipus: Autònomes      
Desenvolupament d'un projecte 36 1,44 1, 2, 3, 4, 5, 7
Elaboració d'informes pràctics 8 0,32 3, 4, 7
Preparació de parcials 12 0,48 1, 2, 4, 5, 6
Preparació prèvia a les classes 12 0,48 3, 4, 5, 6
Treball autònom 12 0,48 1, 2, 3, 4, 5, 6, 7

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 sessions de classe. Es dedicaran algunes hores de les sessions a plantejar la feina a fer i també a fer el seguiment del correcte desenvolupament, així com el plantejament de dubtes.

COMPETÈNCIES TRANSVERSALS: En aquesta assignatura es treballaran i avaluaran les següents competències transversals:

  • T01.02 - Desenvolupar la capacitat d'anàlisi, síntesi i prospectiva
  • T01.03 - Desenvolupar el pensament científic
  • T03.01 - Treballar cooperativament: es treballarà i avaluarà durant les classes presencials.

Nota: es reservaran 15 minuts d'una classe, dins del calendari establert pel centre/titulació, perquè els alumnes completin 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
Avaluació d'activitats desenvolupades a l'aula 10 1 0,04 1, 2, 3, 4, 5, 6, 7
Avaluació d'activitats desenvolupades fora de l'aula 20 1 0,04 1, 2, 3, 4, 5, 6, 7
Avaluació lluraments del projecte 30 2 0,08 1, 2, 3, 4, 5, 6, 7
Evaluación del examen del projecte 10 1 0,04 3, 4
Examen Final (recuperació) 30 3 0,12 1, 2, 3, 4, 5, 6
Primer Examen Parcial Teòric-Pràctic 15 2 0,08 1, 2, 3, 4, 5
Segon Examen Parcial Teòric-Pràctic 15 2 0,08 1, 2, 3, 4, 5, 6

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 exàmens)
  2. Exercicis Avaluables (EA)
  3. Projecte pràctic (P)

1. La primera part (PS) consisteix en la realització de dues proves parcials en les quals s'avaluarà l'alumnat de forma individual. La nota mínima per aprovar cada prova és de 5.

2. La segona part (EA) consistirà en l'entrega d'activitats 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 individual amb el lliurament d'un projecte i 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 5. La nota final d'aquesta part haurà de ser com a mínim un 5.

Les notes mínimes de 5 seran de 4 en el cas que els alumnes assisteixin a més del 50% de les classes.

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 setmana oficial d'exàmens.

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

P: En el cas de suspendre la prova escrita del projecte (cal haver-se presentat la primera vegada), es podrà recuperar el dia assignat a la setmana oficial d'exàmens. Els lliuraments parcials del projecte es poden recuperar en els següents lliuraments, amb una nota final del 80%  de la millora de la nota.

REVISIÓ DE QUALIFICACIONS

La revisió de les notes dels exàmens es farà el dia que indiqui el professorat després de cada examen.

La revisió de lliuraments es demanarà per e-mail i podrà ser presencial,  no presencial o per e-mail.

MATRÍCULA D'HONOR

Es donaran tantes matrícules com es puguin dins de la normativa de la universitat, sempre que la nota final obtinguda sigui com a mínim un 9. 

NO AVALUABLE

No haver presentat alguna part avaluable de l’assignatura.
Les parts no presentades de l’assignatura tenen nota 0.

CONVALIDACIÓ

No es convaliden projectes d'anys anteriors.

NOTA DE L'EXPEDIENT

Elements que s'avaluaran:

Exàmens:

  • Primer parcial de teoria.
  • Segon parcial de teoria.
  • Examen de pràctiques (verifica que s’ha treballat en la pràctica).
  • Examen de recuperació de teoria (els parcials eliminen matèria).
  • Examen de recuperació de pràctiques.

Problemes:

  • Problemes lliurats pels alumnes.

Pràctica:

  • Lliuraments de les pràctiques.

Nota Teoria: correspon a dos exàmens parcials de teoria sobre l'assignatura. S'han aprovar els exàmens parcials per eliminar matèria a l'examen de recuperació.
Nota de problemes: Corresponala 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 Pràctiques: En aquest apartat hi ha una nota dels lliuraments i una nota de l’examen de pràctiques:

  • Nota dels lliuraments: Correspon a la nota obtinguda als lliuraments de la pràctica. Els lliuraments de pràctiques suspesos es poden recuperar en lliuraments posteriors. El valor de la millora de la nota serà del 80%.
  • Nota examen de pràctiques: És la puntuació obtinguda en l'examen de pràctiques. Hi haurà recuperació de l'examen de pràctiques. L’examen de pràctiques es fa el mateix dia que l’examen del segon parcial i de l'examen de recuperació.

L’assistència a classe no és obligatòria però molt recomanable per aprovar l’assignatura.
Hi ha control d'assistència a classe automatitzat amb el servidor de correcció.
Assistència i avaluació de l’assignatura:
La nota mínima per poder fer mitjana serà de 4 (MinMitjana=4) si l’assistència a classe és superior al 50% de les classes. En cas contrari la nota mínima per fer mitjana serà de 5 (MinMitjana=5).
Aquesta nota mínima s’aplica a tots els exàmens, lliuraments de pràctiques i notes intermèdies de teoria i pràctiques.

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

Si Nota Teoria> = MinMitjana i Nota Pràctiques> = MinMitjana LLAVORS Nota Final = 0,4 * Nota Teoria + 0,2 * Nota problemes + 0,4 * Nota Pràctiques
SINÓ Nota Final = MIN (Nota Teoria, Nota Pràctiques)
SI Notaexamen primer parcial>=MinMitjana i Nota examen segon parcial>=MinMitjana 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)
Nota problemes = Mitjana dels problemes lliurats.
SI Nota examen de pràctiques >= MinMitjana i Nota lliuraments>= MinMitjana LLAVORS Nota Pràctiques = 0,2 * Nota examen de pràctiques + 0,8 * Nota lliuraments
SINÓ Nota Pràctiques = MIN(Nota examen de pràctiques, Nota lliuraments)
Nota Lliuraments = Mitjana ponderada dels lliuraments de pràctiques si totes superen MinMitjana, sinó el mínim de les notes dels lliuraments.

Les parts no presentades de l’assignatura tenen nota 0.

PLAGIS, CÒPIES, 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 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 delgrup;
-  presentar com a propis materials elaborats per un tercer, encara que siguin traduccions o adaptacions, ien 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ó teorico-pràctiques individuals (exàmens).

En resum: copiar, deixar copiar o plagiar en qualsevol de les activitats d'avaluació equival a un SUSPENS amb nota inferior a 3.5.

 

US D'INTEL·LIGÈNCIA ARTIFICIAL

Està permès un ús restringit de la IA. Normalment per resoldre dubtes i facilitar l'aprenentatge. Un ús de la IA que limiti l'aprenentatge de l'alumne es considerarà com plagi o copia. Perquè el professor pugui valorar l'ús il·lícit de la IA podrà demanar als alumnes que expliquin com han solucionat els problemes o pràctiques lliurades. No demostrar que es té els coneixements necessaris per fer la feina lliurada es considerà com plagi.

 

COMUNICACIÓ

Les dates d'avaluacions i lliuraments es publicaran al campus virtual  i poden estar subjectes a possibles 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 aquesta és la plataforma habitual d'intercanvi d'informació entre professors i estudiants. La plataforma de comunicació síncrona serà preferentment Teams.

 AVALUACIÓ ÚNICA

S'avaluarà igual que l'avaluació continuada. Però amb les següents diferències:

  • Les pràctiques i problemes es lliuraran el dia de l'examen de recuperació de l'assignatura. En aquest cas les pràctiques no tenen la possibilitat de recuperació, ja que l'alumne no pot corregir iveure la nota les vegades que vulgui abans del lliurament.
  • A causa del fet que no hi ha un seguiment del treball de l'alumne, serà obligatori fer un examen de validació de pràctiques, que és obligatori aprovar.
  • Els exàmens de teoria i pràctiques es faran el dia de l'examen de recuperació de l'assignatura.
  • En cas que sigui necessari, es convocarà els alumnes per fer els exàmens de recuperació de teoria i pràctiques.

 

 


Bibliografia

  • Brassard, G., Bratley, P., & Garcia-Bermejo, R. (1997). Fundamentos de algoritmia (Vol. 86). Madrid: Prentice Hall.
  • Guerequeta, R., & Vallecillo, A. (2019). Técnicas de diseño de algoritmos.
  • Villegas Jaramillo, & Guerrero Mendieta, L. E. (2016). 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
  • Eckel, B. (2021). Thinking in C++.
  • Stroustrup, B. (1993). C++ el lenguaje de Programación. Eddison Wesley/Díaz de Santos.

Web:

  • Algoritmo, https://es.wikipedia.org/wiki/Algoritmo
  • http://en.cppreference.com/w/
  • http://www.cplusplus.com/
  • Algoritmo voraz, https://es.wikipedia.org/wiki/Algoritmo_voraz

  • Recursión (ciencias de computación), https://es.wikipedia.org/wiki/Recursi%C3%B3n_(ciencias_de_computaci%C3%B3n)
  • Algoritmo divide y vencerás, https://es.wikipedia.org/wiki/Algoritmo_divide_y_vencer%C3%A1s
  • Vuelta atrás, https://es.wikipedia.org/wiki/Vuelta_atr%C3%A1s
  • Ramificación y poda, https://es.wikipedia.org/wiki/Ramificaci%C3%B3n_y_poda
  • Programación dinámica, https://es.wikipedia.org/wiki/Programaci%C3%B3n_din%C3%A1mica
  • Algoritmo probabilista, https://es.wikipedia.org/wiki/Algoritmo_probabilista
  • ¿Cuál es el algoritmo MÁS IMPORTANTE de la historia? https://www.youtube.com/watch?v=kflbmvCWdwk
  • La destacable historia detrás del algoritmo más importante de todos los tiempos https://www.youtube.com/watch?v=2Xkv-W9tOXU

Programari

Es programarà en C++ bàsic i s'utilitzarà Microsoft Visual Studio 2022 (llicència UAB). Per a la instal·lació de VS2022 s'utilitzaran les següents opcions:

•Microsoft Visual Studio Community 2022 o superior.
•Desktop development with C++ 
•C++ MFC latest v142
 
Els alumnes han de portar un ordinador portàtil amb Windows 10/11 per fer problemes i pràctiques a classe.

Grups i idiomes de l'assignatura

La informació proporcionada és provisional fins al 30 de novembre de 2025. 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

Nom Grup Idioma Semestre Torn
(PAUL) Pràctiques d'aula 440 Català primer quadrimestre matí-mixt
(PAUL) Pràctiques d'aula 441 Català primer quadrimestre matí-mixt