Logo UAB
2022/2023

Tècniques de Disseny d’Algoritmes

Codi: 104393 Crèdits: 6
Titulació Tipus Curs Semestre
2503740 Matemàtica Computacional i Analítica de Dades OB 2 1

Professor/a de contacte

Nom:
Javier Sánchez Sánchez Pujadas
Correu electrònic:
javier.sanchez.pujadas@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

Prerequisits

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

  • Iniciació a la Programació
  • Algorismia i Combinatòria en grafs. mètodes Heurístics
  • Programació Orientada a Objectes

Es considerarà que l'alumne ja ha adquirit 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, es pretén que l'alumne sigui capaç de analitza, 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.
  • 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 en donar-nos la solució. Així que ens interessa 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 i amb criteris qualitat el treball realitzat.
  • Dissenyar, desenvolupar i avaluar solucions algorísmiques eficients per a problemes computacionals d'acord amb els requisits establerts.
  • Que els estudiants hagin demostrat que comprenen i tenen coneixements en una àrea d'estudi que parteix de la base de l'educació secundària general, i se sol trobar a un nivell que, si bé es basa en llibres de text avançats, inclou també alguns aspectes que impliquen coneixements procedents de l'avantguarda d'aquell camp d'estudi.
  • Que els estudiants hagin desenvolupat aquelles habilitats d'aprenentatge necessàries per emprendre estudis posteriors amb un alt grau d'autonomia.
  • Que els estudiants sàpiguen aplicar els coneixements propis a la seva feina o vocació d'una manera professional i tinguin les competències que se solen demostrar per mitjà de l'elaboració i la defensa d'arguments i la resolució de problemes dins de la seva àrea d'estudi.
  • Utilitzar eficaçment la bibliografia i els recursos electrònics per obtenir informació.

Resultats d'aprenentatge

  1. Avaluar de manera crítica i amb criteris de qualitat el treball desenvolupat.
  2. Avaluar i analitzar la complexitat computacional de les solucions algorítmiques per poder desenvolupar i implementar aquella que garanteixi el millor rendiment.
  3. Implementar solucions recursives a problemes de programació.
  4. Que els estudiants hagin demostrat que comprenen i tenen coneixements en una àrea d'estudi que parteix de la base de l'educació secundària general, i se sol trobar a un nivell que, si bé es basa en llibres de text avançats, inclou també alguns aspectes que impliquen coneixements procedents de l'avantguarda d'aquell camp d'estudi.
  5. Que els estudiants hagin desenvolupat aquelles habilitats d'aprenentatge necessàries per emprendre estudis posteriors amb un alt grau d'autonomia.
  6. Que els estudiants sàpiguen aplicar els coneixements propis a la seva feina o vocació d'una manera professional i tinguin les competències que se solen demostrar per mitjà de l'elaboració i la defensa d'arguments i la resolució de problemes dins de la seva àrea d'estudi.
  7. Seleccionar i utilitzar les estratègies de programació apropiades per a la resolució d'un problema donat.
  8. Utilitzar eficaçment la bibliografia i els recursos electrònics per obtenir informació.

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.

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

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. Es 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.

 

Adaptació de la metodologia a docència no presencial 

La docència no presencial suposarà donar més importància al treball autònom de l’alumne i implica un canvi metodològic on s’aplicarà la classe invertida. Considerant aquet concepte és planificarà la docència setmanal com uns vídeos/pdfs amb la matèria teòrica de la setmana. De les 4h de docència presencial es faran 2h de classe online. En aquestes classes es resoldran problemes i s’avançarà en el desenvolupament de la pràctica. Al final de la setmana es tindrà que fer un lliurament de problemeso pràctiquesperquè el professor pugui comprovar el seguiment de l’assignatura per part de l’alumnat.

Preparació de la classe: Cada setmana començarà amb el estudi o revisió del material que publicarà el professor al campus virtual. Normalment aquet material serà una presentació feta amb powerpoint i un vídeo on es comentaran les pàgines de la presentació com si fos una típica classe magistral de teoria. En aquet material s’explicaran conceptes teòrics, es faran exemples de resolució de problemes i es proposaran problemes per les classes online i per lliurar. L’alumne haurà de estudiar aquet material abans de les classes online.

Classe online: El professor farà una petita introducció al problema/pràctica que es tractarà duran la classe. A partir d’aquet moment s’ha d’establir un diàleg on els alumnes expressaran els dubtes que tinguin i proposaran com solucionar el problema/pràctica. El professor guiarà als alumnes fins arribar a solucionar el problema a partir de les propostes dels alumnes. En cas que sigui possible s’implementaran a classe les propostes de solució dels alumnes/professor. La participació a classe es puntuarà i servirà per millorar la nota de la assignatura.

Treball autònom: El treball autònom serà igual que en la metodologia presencial.

 

Material necessari per la docència no presencial

Per les classes online com per les consultes s’utilitzarà la aplicació Microsoft Teams que ha d’estar instal·lada a l’ordinador de l’alumne. Aquet ordinador ha de tenir càmera i micròfon per facilitar la interacció a les classes i 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è l'alumnat empleni 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      
Classes presencials (teoria, problemes i pràctiques) 50 2 1, 2, 3, 4, 5, 6, 7, 8
Tipus: Supervisades      
Reforç i seguiment en la resolució dels projectes 4 0,16 1, 2, 3, 4, 5, 6, 7, 8
Seguiment en l'assimilació dels conceptes teòrics 4 0,16 1, 2, 3, 4, 5, 6, 7, 8
Tipus: Autònomes      
Elaboració informes pràctics 8 0,32 1, 2, 3, 4, 5, 6, 7, 8
Preparació examens parcials 12 0,48 1, 2, 3, 4, 5, 6, 7, 8
Preparació prèvia a les classes 48 1,92 1, 2, 3, 4, 5, 6, 7, 8
Treball autònom 12 0,48 1, 2, 3, 4, 5, 6, 7, 8

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 l'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 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 pots reucuperar 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> = 5 i Nota Pràctiques> = 5 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 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)

Nota problemes = Mitjana ponderada dels problemes lliurats.

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)

 

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.

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

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.

Condicions per al suspens:

No assolir una nota mitjana superior o igual 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 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 perun 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 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
Avaluació grupal del projecte Veure descripció evaluació 2 0,08 1, 2, 3, 4, 5, 6, 7, 8
Avaluació individual del projecte Veure descripció evaluació 1 0,04 1, 2, 3, 4, 5, 6, 7, 8
Entrega d'exercicis Veure descripció evaluació 1 0,04 1, 2, 3, 4, 5, 6, 7, 8
Examen Final (recuperació) Veure descripció evaluació 4 0,16 1, 2, 3, 4, 5, 6, 7, 8
Primer Examen Parcial Teòric-Pràctic Veure descripció evaluació 2 0,08 1, 2, 3, 4, 5, 6, 7, 8
Segon Examen Parcial Teòric-Pràctic Veure descripció evaluació 2 0,08 1, 2, 3, 4, 5, 6, 7, 8

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 2019 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.