Logo UAB

Anàlisi i Disseny d'Algorismes

Codi: 102783 Crèdits: 6
2024/2025
Titulació Tipus Curs
2502441 Enginyeria Informàtica OB 3
2502441 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

Enrique Ruiz Amakrache

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


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ó grupal del projecte 30 2 0,08 1, 2, 3, 4, 5, 6, 7
Avaluació individual 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)
  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 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 4. 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.

NOTA DE L'EXPEDIENT, MATRÍCULA D'HONOR I NO AVALUABLE

En cas de no superar l'assignatura pel fet que alguna de les activitats d'avaluació no arriba a la nota mínima requerida, la nota numèrica de l'expedient serà la nota màxima entre els parcials suspesos, o en el seu defecte, la nota suspesa màxima. Amb les excepcions dels estudiants que:

1) no participin en cap de les activitats d'avaluació, que s'atorgarà la qualificació de "no avaluable" (qualsevol alumne que lliuri una pràctica o una avaluació programada tindrà nota),

2) hagin comès irregularitats en un acte d'avaluació, que s'atorgarà el valor menor entre 3.0 i la nota numèrica màxima abans citada (i per tant no serà possible l'aprovat per compensació). 

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.


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 l'avaluació individual 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% (i per tant mai superior a 8).

CONVALIDACIÓ

No es convaliden projectes d'anys anteriors.

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.

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

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
•Desktop development with C++ 
•C++ MFC latest v142
 
Els alumnes han de portar un ordinador portàtil amb Windows per fer problemes i pràctiques a classe.

Llista d'idiomes

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