Tècniques de Disseny d’Algoritmes
Codi: 104393 Crèdits: 6| Titulació | Tipus | Curs |
|---|---|---|
| 2503740 Matemàtica Computacional i Analítica de Dades | OB | 2 |
Professor/a de contacte
- Nom:
- Aura Hernandez Sabate
- Correu electrònic:
- aura.hernandez@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
- CM28 (Competència) Dissenyar solucions algorísmiques eficients a problemes computacionals d'acord amb els requisits establerts.
- CM29 (Competència) Avaluar la complexitat computacional de les solucions algorísmiques per a poder desenvolupar i implementar la que garanteixi el millor rendiment.
- KM23 (Coneixement) Identificar les estratègies de programació adequades per a la resolució d'un problema determinat.
- KM23 (Coneixement) Identificar les estratègies de programació adequades per a la resolució d'un problema determinat.
- SM24 (Habilitat) Implementar solucions recursives a problemes de programació.
- SM26 (Habilitat) Aplicar els principis fonamentals i les tècniques bàsiques de la programació paral·lela, concurrent i distribuïda.
- 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ó, 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ó grupal del projecte | Veure descripció avaluació | 2 | 0,08 | CM28, SM24, SM26 |
| Avaluació individual del projecte | Veure descripció avaluació | 1 | 0,04 | CM28, CM29 |
| Entrega d'exercicis | Veure descripció avaluació | 1 | 0,04 | CM28, CM29, KM23, SM24, SM26 |
| Examen Final (recuperació) | Veure descripció avaluació | 4 | 0,16 | CM28, CM29, KM23, SM24, SM26 |
| Primer Examen Parcial Teòric-Pràctic | Veure descripció avaluació | 2 | 0,08 | CM28, CM29, KM23, SM24, SM26 |
| Segon Examen Parcial Teòric-Pràctic | Veure descripció avaluació | 2 | 0,08 | CM28, CM29, KM23, SM24, SM26 |
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:
- 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 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.
Llista d'idiomes
| Nom | Grup | Idioma | Semestre | Torn |
|---|---|---|---|---|
| (PLAB) Pràctiques de laboratori | 1 | Català | primer quadrimestre | matí-mixt |
| (TE) Teoria | 1 | Català | primer quadrimestre | matí-mixt |