Disseny d'Algoritmes
Codi: 104359 Crèdits: 6| Titulació | Tipus | Curs | Semestre |
|---|---|---|---|
| 2503758 Enginyeria de Dades | OB | 2 | 2 |
Professor/a de contacte
- Nom:
- Aura Hernandez Sabate
- Correu electrònic:
- aura.hernandez@uab.cat
Idiomes dels grups
Podeu accedir-hi des d'aquest enllaç. Per consultar l'idioma us caldrà introduir el CODI de l'assignatura. Tingueu en compte que la informació és provisional fins a 30 de novembre de 2023.
Equip docent
- Enrique Ruiz Amakrache
Prerequisits
Tot i que no és obligatori, és molt aconsellable haver cursat les següents assignatures:
· Fonaments de Programació
· Programació Avançada
· Estructures de Dades
· Anàlisi de Grafs i cerca d'Informació
· Enginyeria del Rendiment
Es considerarà que l'estudiant ja ha adquirit prèviament els coneixements impartits en aquestes assignatures.
Objectius
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
- Avaluar de manera crítica el treball realitzat.
- Dissenyar solucions algorítmiques eficients per a problemes computacionals, implementar-les en forma de desenvolupaments de programari robust, estructurat i fàcil de mantenir, i verificar-ne la validesa.
- Que els estudiants tinguin la capacitat de reunir i interpretar dades rellevants (normalment dins de la seva àrea d'estudi) per emetre judicis que incloguin una reflexió sobre temes destacats d'índole social, científica o ètica.
Resultats d'aprenentatge
- Avaluar de manera crítica el treball realitzat.
- Decidir el mètode d'aprenentatge de dades més adequat segons les característiques de les dades que cal analitzar.
- Que els estudiants tinguin la capacitat de reunir i interpretar dades rellevants (normalment dins de la seva àrea d'estudi) per emetre judicis que incloguin una reflexió sobre temes destacats d'índole social, científica o ètica.
Continguts
El temari de l'assignatura serà:
- Tema 1. Repàs de conceptes bàsics (Pre-condicions, post-condicions, invariants, Complexitat computacional)
- Tema 2. Algorismes de cerca. Taxonomia i estratègies
- Tema 3. Greedy
- Tema 4. Divideix i venceràs
- Tema 5. Backtracking
- Tema 6. Branch & Bound
- Tema 7. Programació dinàmica
- Tema 8. Algorismes estocàstics
Metodologia
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
- exercicis solts que s'entregaran per ser avaluats
- 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 sessionsde classe. Es dedicaran algunes hores de les sessions a plantejar lafeina a fer i també a fer el seguiment del
correcte desenvolupament, així com el plantejament de dubtes.
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.
Activitats formatives
| Títol | Hores | ECTS | Resultats d'aprenentatge |
|---|---|---|---|
| Tipus: Dirigides | |||
| Classes presencials | 50 | 2 | 2 |
| Tipus: Supervisades | |||
| Reforç i seguiment en la resolució del projecte i els exercicis | 4 | 0,16 | 1, 2 |
| Seguiment en l'assimilació dels conceptes teòrics | 4 | 0,16 | 1, 2, 3 |
| Tipus: Autònomes | |||
| Desenvolupament d'un projecte | 44 | 1,76 | 1, 2, 3 |
| Preparació de parcials | 12 | 0,48 | 1, 2 |
| Preparació prèvia a les classes | 12 | 0,48 | 1, 2, 3 |
| Treball autònom | 12 | 0,48 | 1, 2 |
Avaluació
Aquesta assignatura no preveu el sistema d’avaluació única.
S'avaluaran tres tipus d'activitats de manera independent i la suma ponderada d'elles donarà la nota final. Aquestes tres activitats són:
- Proves de síntesi (PS)
- Exercicis Avaluables (EA)
- 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 3.5. 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 degut a 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 suspesamàxima. Amb les excepcions de l'alumnat que:
1) no participi en cap de les activitats d'avaluació, que s'atorgarà la qualificació de "no avaluable" (qualsevol estudiant que lliuri una pràctica o una avaluació programada tindrà nota),
2) hagi 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 i quan 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 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ó 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 gestor documental Caronte (https://caronte.uab.cat/) i poden estar subjectes a possibles canvis de programació per motius d'adaptació a possibles incidències. Sempre s'informarà al Caronte sobre aquests canvis ja que s'entén que aquesta és la plataforma habitual d'intercanvi d'informació entre professors i estudiants.
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 |
| Avaluació d'activitats desenvolupades fora de l'aula | 20 | 1 | 0,04 | 1, 2, 3 |
| Avaluació grupal del projecte | 30 | 2 | 0,08 | 1, 2, 3 |
| Avaluació individual del projecte | 10 | 1 | 0,04 | 1, 3 |
| Examen Final (recuperació) | 30 | 3 | 0,12 | 1, 2 |
| Primer parcial teoria | 15 | 2 | 0,08 | 1, 2 |
| Segon parcial teoria | 15 | 2 | 0,08 | 1, 2 |
Bibliografia
- Fundamentos de Algorítmia, G Brassard P. Bratley. Prentice Hall.
- 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
- 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
- Karumanchi, Narasimha. "Algorithm Design Techniques: Recursion, Backtracking, Greedy, Divide and Conquer, and Dynamic Programming." (2018).
- Chun, Wesley. Core python programming. Vol. 1. Prentice Hall Professional, 2001.
Programari
Es programarà en llenguatge de programació Python (versió 3.4 en endavant). No imposem cap restricció respecte del IDE que es vulgui fer servir (Anaconda, PyCharm, Visual Studio)