Any acadèmic

Logo UAB

Tècniques de Disseny d'Algoritmes

Codi: 104393 Crèdits: 6
2025/2026
Titulació Tipus Curs
Matemàtica Computacional i Analítica de Dades OB 2

Professor/a de contacte

Nom:
Enrique Ruiz Amakrache
Correu electrònic:
enrique.ruiz@uab.cat

Idiomes dels grups

Podeu consultar aquesta informació al final del document.


Prerequisits

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

  • Iniciació a la Programació
  • Algorísmia i Combinatòria en grafs.
  • Programació Orientada a Objectes

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

 

Material:

Ordinador amb Windows 10 o posterior i processador amb codi màquina x64 (intel/amd)


Objectius

Partint de la base que l'alumnat té uns coneixements bàsics sobre programació i estructures de dades, es pretén que l'estudiant 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'estudiant 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.
  • Anàlisi de complexitat.
  • Paradigmes per al disseny d'algorismes. 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, cal considerar quant trigarà l'algorisme a donar-nos la solució. Així que ens interessa crear algoritmes tan ràpids com sigui possible. D'aquesta manera podrem crear programes que solucionin problemes els 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.


Resultats d'aprenentatge

  1. CM28 (Competència) Dissenyar solucions algorísmiques eficients a problemes computacionals d'acord amb els requisits establerts.
  2. CM29 (Competència) Avaluar la complexitat computacional de les solucions algorísmiques per a poder desenvolupar i implementar la que garanteixi el millor rendiment.
  3. KM23 (Coneixement) Identificar les estratègies de programació adequades per a la resolució d'un problema determinat.
  4. SM24 (Habilitat) Implementar solucions recursives a problemes de programació.
  5. SM26 (Habilitat) Aplicar els principis fonamentals i les tècniques bàsiques de la programació paral·lela, concurrent i distribuïda.

Continguts

El temari de l'assignatura serà:

  • Especificació formal d'algoritmes
  • Complexitat Algorísmica
  • Algorismes Greedy
  • Recursivitat
  • Divideix i venceràs
  • Backtracking
  • Branch & bound
  • Programació dinàmica
  • Algorismes Probabilístics

Activitats formatives i Metodologia

Títol Hores ECTS Resultats d'aprenentatge
Tipus: Dirigides      
Classes presencials (teoria, problemes i pràctiques) 50 2
Tipus: Supervisades      
Reforç i seguiment en la resolució dels projectes 4 0,16
Seguiment en l'assimilació dels conceptes teòrics 4 0,16
Tipus: Autònomes      
Elaboració informes pràctics 8 0,32
Preparació examens parcials 12 0,48
Preparació prèvia a les classes 48 1,92
Treball autònom 12 0,48

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 de l'alumnat és l'eix central del seu aprenentatge, acompanyat i guiat pel professorat. Per aquest motiu, les classes presencials seran altament pràctiques i se centraran en el fet que 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 que els alumnes puguin resoldre els dubtes que tinguin. Després s'explicarà el problema o treball pràctic a fer 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.

Per fer més dinàmic l'aprenentatge basat en problemes i pràctiques, es realitzarà un ús intensiu de correctors automàtics, sempre que sigui possible. Així, per a cada problema o pràctica que hagi de lliurar l'alumne, se li proporcionarà un corrector automàtic que li permetrà provar immediatament el programa que estigui desenvolupant. Així, l'alumne sabrà si ha resolt el problema o encara hi ha algun error que ha de solucionar. A més, per posar èmfasi en la implementació òptima d'algoritmes, l'alumne podrà comparar els temps d'execució de la seva solució amb la proporcionada pel professor. Així, es vol gamificar els treballs pràctics, marcant com a objectiu i premiant superar la solució del professor.
Per a la realització dels problemes i pràctiques s'utilitzarà el llenguatge de programació C ++ a nivell bàsic. Se selecciona aquest llenguatge per ser el llenguatge d'alt nivell que obté el màxim rendiment dels processadors actuals, per això, és especialment apropiat per a la implementació òptima d'algoritmes.

 

Material necessari per a la docència no presencial

Per les consultes en línia s’utilitzarà l'aplicació Microsoft Teams que ha d’estar instal·lada a l’ordinador de l’alumne. Aquest ordinador ha de tenir càmera i micròfon per facilitar la interacció a les consultes. Per programar s’utilitzarà Visual Studio C++ i el sistema operatiu Microsoft Windows.

 

 

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ó grupal del projecte Veure descripció avaluació 2 0,08 CM28, KM23, SM24, SM26
Avaluació individual del projecte Veure descripció avaluació 1 0,04 CM29
Entrega d'exercicis Veure descripció avaluació 1 0,04 CM28, CM29, KM23, SM24, SM26
Examen Final (recuperació) Veure descripció avaluació 4 0,16
Primer Examen Parcial Teòric-Pràctic Veure descripció avaluació 2 0,08 CM29
Segon Examen Parcial Teòric-Pràctic Veure descripció avaluació 2 0,08 CM29

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 d'aprovar els exàmens parcials per eliminar matèria en l'examen de recuperació.
  • Nota de problemes: Correspon a la nota obtinguda per una sèrie de problemes que haurà de lliurar a l'estudiant. No hi ha recuperació per als lliuraments de problemes.
  • Nota Pràctiques: En aquest apartat hi ha una nota de grup i una individual:
    • Nota de grup: Correspon a la nota obtinguda als lliuraments per grups de la pràctica. Els lliuraments de pràctiques suspeses es poden recuperar en lliuraments posteriors.
    • 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 tres activitats de la següent manera:

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

Nota Final = 0,4 * Nota Teoria + 0,2 * Nota problemes + 0,4 * Nota Pràctiques

SI NO Nota Final = MIN (Nota Teoria, Nota Pràctiques)

 

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

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

SI NO Nota Teoria = MIN (Nota examen primer parcial, Nota examen segon parcial)

 

Nota problemes = Mitjana ponderada dels problemes lliurats.

 

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

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

SI NO Nota Pràctiques = MIN (Nota Individual, Nota Grup)

 

Nota Individual = Examen de pràctiques

Nota Grup = Mitjana ponderada dels lliuraments de pràctiques si totes estan aprovades, si no el mínim de les notes dels lliuraments.

 

Convalidació de pràctiques: No es convaliden pràctiques d'anys anteriors.

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.8 * (max (nota recuperació, nota lliurament) Nota lliurament) + nota lliurament. En el cas de suspendre l'examen de pràctiques, l'estudiant s'haurà de presentar a un examen de recuperació de pràctiques el mateix dia de l'examen de recuperació final.

Condicions per aprovar l'assignatura:

Per aprovar l'assignatura s'ha d'haver aprovat:

Nota final >=5
Nota teoria >=4
Nota pràctica>=4
Notes lliuraments de pràctiques >=4
Exàmens >=4
 

 

Condicions per no avaluable:

No tenir cap part de l'assignatura suspesa.

Condicions per al suspens:

  1. No assolir una nota mitjana superior o igual a 5.
  2. 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 entre totes 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 que hi ha un nombre limitat de matrícules d'honor que es poden donar per grup, s'atorgaran per ordre de 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 exclusius de 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ó).

En resum: 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 de revisió en la qual l'estudiant podrà revisar l'activitat amb l'equip docent. 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.

 

Avaluació única:

Es farà igual que l'avaluació normal, però en aquest cas es presentaran tots els treballs el dia de l'examen final de l'assignatura. Per tant, consta de:

  • Examen del primer parcial de teoria.
  • Examen del segon parcial de teoria.
  • Examen de pràctiques.
  • Lliuraments de problemes (no recuperables).
  • Lliuraments de pràctiques (no recuperables).

Bibliografia

Fundamentos de Algorítmia, G Brassard P. Bratley. Prentice Hall.

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

Thinking in C++ 2nd Edition by Bruce Eckel Volume 1 y Volume 2.

(http://www.mindview.net/Books/TICPP/ThinkingInCPP2e.html)

El lenguaje de programación C++, Bjarne Stroustrup

http://en.cppreference.com/w/

http://www.cplusplus.com/

 


Programari

La pràctica es fa amb ordinador amb Windows 10. S'utilitza el compilador Visual Studio 2022 per compilar programes en C ++. A més s'utilitza un projecte per a la pràctica que és una aplicació gràfica i correctors automàtics que es proporcionen des del campus virtual.


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
(PLAB) Pràctiques de laboratori 1 Català/Espanyol primer quadrimestre matí-mixt
(TE) Teoria 1 Català/Espanyol primer quadrimestre matí-mixt