Algorísmia

Crèdits
6
Departament
CS
Tipus
Obligatòria d'especialitat (Computació)
Requisits
  • Corequisit: PROP
  • Prerequisit: EDA
  • Precorequisit: PE
L'algorísmia estudia els algorismes, les seves propietats i la seva eficiència. L'algorísmia té com a objectiu el desenvolupament de mètodes i tècniques per al disseny d'algorismes i estructures de dades (EDs) eficients i el seu anàlisi, així com el desenvolupament d'algorismes i EDs que resolguin problemes concrets. Després d'un breu repàs de conceptes i tècniques algorísmiques bàsiques ja conegudes, s'estudien noves tècniques de disseny algorísmic com ara el mètode golafre (greedy method), la programació dinàmica, els fluxos sobre xarxes, la programació lineal i l'aleatorització. Cadascuna de les tècniques de disseny i anàlisi estudiades s'il•lustra amb exemples concrets, molts dels quals són algorismes i EDs de gran transcedència pràctica com ara l'algorisme de Dijkstra per al càlcul de camins mínims en un graf, l'algorisme de càlcul de la distància d'edició entre dos strings, el test de primalitat de Rabin o l'algorisme de Ford-Fulkerson per trobar el fluxe òptim sobre una xarxa.
Web: http://www.cs.upc.edu/~mjserna/docencia/grauA/alg-GEI.html
Mail:

Professors

Responsable

  • Maria Jose Serna Iglesias ( )

Altres

  • Josep Diaz Cort ( )
  • M. Jose Blesa Aguilera ( )
  • Maria Del Carme Alvarez Faura ( )

Hores setmanals

Teoria
2
Problemes
2
Laboratori
0
Aprenentatge dirigit
0.4
Aprenentatge autònom
5.6

Competències

Competències Tècniques

Competències tècniques comunes

  • CT1 - Demostrar coneixement i comprensió de fets essencials, conceptes, principis i teories relatives a la informàtica i a les seves disciplines de referència.
    • CT1.2C - Interpretar, seleccionar i valorar conceptes, teories, usos i desenvolupaments tecnològics relacionats amb la informàtica i la seva aplicació a partir dels fonaments matemàtics, estadístics i físics necessaris. CEFB3. Capacitat per a comprendre i dominar els conceptes bàsics de matemàtica discreta, lògica, algorísmica i complexitat computacional, i la seva aplicació per al tractament automàtic de la informació mitjançant sistemes computacionals i la seva aplicació per a la resolució de problemes propis de l'enginyeria.
  • CT4 - Demostrar coneixement i capacitat d'aplicació dels procediments algorísmics bàsics de les tecnologies informàtiques per a dissenyar solucions a problemes, analitzant la idoneïtat i la complexitat dels algorismes
    • CT4.1 - Identificar les solucions algorísmiques més adequades per a resoldre problemes de dificultat mitjana.
    • CT4.2 - Raonar sobre la correcció i l'eficiència d'una solució algorísmica.
  • CT5 - Analitzar, dissenyar, construir i mantenir aplicacions de forma robusta, segura i eficient, triant el paradigma i els llenguatges de programació més adequats.
    • CT5.2 - Conèixer, dissenyar i utilitzar de forma eficient els tipus i les estructures de dades més adients per a la resolució d'un problema.
    • CT5.3 - Dissenyar, escriure, provar, depurar, documentar i mantenir codi en un llenguatge d'alt nivell per a resoldre problemes de programació aplicant esquemes algorísmics i utilitzant estructures de dades.
    • CT5.4 - Dissenyar l'arquitectura dels programes utilitzant tècniques d'orientació a objectes, de modularització i d'especificació i implementació de tipus abstractes de dades.

Competències Transversals

Aprenentatge autònom

  • G7 - Detectar carències en el coneixement propi i superar-les mitjançant la reflexió crítica i l'elecció de la millor actuació per ampliar aquest coneixement. Capacitat per a l'aprenentatge de nous mètodes i tecnologies, i versatilitat per a adaptar-se a noves situacions.
    • G7.3 - Aprenentatge autònom: capacitat de planificació i organització del treball personal. Aplicar els coneixements adquirits a la realització d'una tasca en funció de la pertinença i de la importància, decidir la manera de dur-la a terme i el temps que se li ha de dedicar, i seleccionar les fonts d'informació més adients. Identificar la importància d'establir i mantenir contactes amb els companys d'estudis, amb el professorat i amb els professionals (networking). Identificar fòrums d'informació sobre enginyeria TIC, els seus avenços i el seu impacte en la societat (IEEE, associacions, etc.).

Competències Tècniques de cada especialitat

Especialitat computació

  • CCO1 - Tenir un coneixement profund dels principis fonamentals i dels models de la computació i saber-los aplicar per a interpretar, seleccionar, valorar, modelar i crear nous conceptes, teories, usos i desenvolupaments tecnològics, relacionats amb la informàtica.
    • CCO1.1 - Avaluar la complexitat computacional d'un problema, conèixer estratègies algorísmiques que puguin dur a la seva resolució, i recomanar, desenvolupar i implementar la que garanteixi el millor rendiment d'acord amb els requisits establerts.
  • CCO2 - Desenvolupar de forma efectiva i eficient els algorismes i el software apropiats per a resoldre problemes complexos de computació.
    • CCO2.5 - Implementar software de cerca d'informació (information retrieval).
  • CCO3 - Desenvolupar les solucions informàtiques que, considerant l'entorn d'execució i l'arquitectura del computador sobre el qual s'executen, aconsegueixin el millor rendiment.
    • CCO3.1 - Implementar codi crític seguint criteris de temps d'execució, eficiència i seguretat.
    • CCO3.2 - Programar considerant l'arquitectura hardware, tant en asemblador com en alt nivell.

Objectius

  1. Conèixer l'esquema dels algorismes golafres, identificar quan es pot aplicar i com, conèixer les tècniques més habituals per a demostrar la seva correctesa i familiaritzar-se amb alguns algorismes golafres fonamentals, p.e., els algorismes de Dijkstra, de Kruskal i de Prim.
    Related competences: CT1.2C, CCO1.1, CT4.1, CT4.2, CT5.2, G7.3,
  2. Conèixer l'esquema de programació dinàmica, identificar quan es pot aplicar i com i familiaritzar-se amb alguns algorismes de programació dinàmica fonamentals, p.e., l'algorisme de Floyd o el càlcul de la distància d'edició
    Related competences: CT1.2C, CCO1.1, CT4.1, CT4.2, CT5.2, G7.3,
  3. Conèixer el problema bàsic de càlcul de fluxos òptims sobre xarxes, familiaritzar-se amb un algorisme bàsic (Ford-Fulkerson), entendre el teorema de maxflow-mincut, reconèixer quan un problema es pot formular en termes d'un problema de fluxos
    Related competences: CT1.2C, CCO1.1, CT4.1, CT4.2, G7.3,
  4. Comprendre la importància de l'aleatorització en el disseny d'algorismes i estructures de dades, familiaritzar-se amb algunes tècniques elementals d'anàlisi probabilístic necessàries per estudiar l'eficiència dels algorismes al.leatoritzats i familiaritzar-se amb alguns exemples clàssics com ara quicksort aleatoritzat, les skip lists, el test de primalitat de Rabin o l'algorisme de cerca de patrons de Karp-Rabin
    Related competences: CT1.2C, CCO1.1, CT4.1, CT4.2, G7.3,
  5. Conèixer alguns problemes computacionals específics que sorgeixen en àmbits tant dispars com la cerca en bases de dades documentals, bases de dades proteíniques i genòmiques, sistemes de informació geogràfica, recuperació d'informació basada en el contingut, compressió de dades, etc. i conèixer algunes estructures de dades avançades per a donar resposta a aquestes necessitats
    Related competences: CCO2.5, CT1.2C, CCO1.1, CT4.1, CT4.2, CT5.2, CCO3.1, G7.3,
  6. Familiaritzar-se amb l'ús dels principis de disseny algorísmic pel disseny d'estructures de dades i conèixer algunes tècniques essencials per a obtenir implementacions d'aquestes que garanteixin la màxima eficiència i treguin partit de les caracterísitques específiques del hardware que ha de suportar aquestes estructures de dades
    Related competences: CT1.2C, CCO1.1, CT4.1, CT4.2, CT5.2, CCO3.1, CCO3.2, G7.3,
  7. Desenvolupar els hàbits, actituds i habilitats necessàries per a poder estudiar, de manera independent o en equip, un tema específic, fent-ne ús de les fonts d'informació disponibles (bibliografia, Web, ...) i aconseguir el nivell de coneixement i compresió del tema suficient com per a poder explicar-ho a tercers, escrivint un resum i preparant un material audiovisual complementari
    Related competences: G7.3,
  8. Conèixer i comprendre alguns principis bàsics pel disseny d'experiments computacionals i aprendre tècniques bàsiques de recollida de dades, validació i anàlisi estadístic de les dades recollides i com treure'n conclusions; reconèixer la necessitat, la utilitat i les limitacions dels estudis experimentals en el disseny i implementació d'algorismes i estructures de dades
    Related competences: CT5.3, CT4.1, CT4.2, CT5.2, CT5.4, CCO3.1, CCO3.2, G7.3,

Continguts

  1. Conceptes Algorísmics Bàsics
    Anàlisi del cas pitjor. Notació asimptòtica. Dividir per conquerir. Anàlisi d'algorismes recursius. Hashing. Algoritmes per Grafs. Aleatorització.
  2. Algorismes Golafres
    Esquema dels algorismes golafres. Planificació de tasques. Algorismes de Bellman-Ford i Johnson per als camins mínims. Algorismes de Kruskal i Prim per a arbres d'expansió mínims. Particions (Union-find). Codis de Huffman.
  3. Programació Dinàmica
    Principi d'optimalitat. Memoització. Algorisme de Floyd-Warshall per a camins mínims. Problema del viatjant de comerç. Problema de la motxilla. Altres examples.
  4. Fluxos sobre Xarxes
    Conceptes bàsics. Teorema del maxflow-mincut. Algorisme de Ford-Fulkerson. Aplicacions: matching i camins sense arestes en comú. Dualitat.
  5. Estructures de Dades i Algorismes Avançats
    Es farà una selecció d'alguna de les estructures de dades seguents o d'altres juntament amb els algoritmes associats. Monticles de Fibonaccci. Cuckoo hashing. Filtres de Bloom. Blockchain. Estructures de dades mètriques. Map Reduce. Grafs aleatoris.

Activitats

Conceptes Algorísmics Bàsics

Recordar conceptes fonamentals apresos a les assignatures prèvies, i familiaritzar-se amb la terminologia i notació que es farà servir al llarg del curs. Aprendre altes técniques algorítmiques bàsiques.
Teoria
6
Problemes
6
Laboratori
0
Aprenentatge dirigit
0
Aprenentatge autònom
10
  • Aprenentatge autònom: - Estudi de la teoria i problemes vistos a classe - Resolució dels exercicis proposats amb antelació

Continguts:

Algorismes Golafres

Atendre les classes de teoria i problemes ón es desenvolupa el tema i fer els exercicis proposats pel professor per fer a casa o a classe
Teoria
4
Problemes
4
Laboratori
0
Aprenentatge dirigit
0
Aprenentatge autònom
6
  • Aprenentatge autònom: - Estudi de la teoria i problemes vistos a classe - Resolució dels exercicis proposats amb antelació
Objectius: 1
Continguts:

Programació Dinàmica

Atendre les classes de teoria i problemes ón es desenvolupa el tema i fer els exercicis proposats pel professor per fer a casa o a classe
Teoria
4
Problemes
6
Laboratori
0
Aprenentatge dirigit
0
Aprenentatge autònom
10
  • Aprenentatge autònom: - Estudi de la teoria i problemes vistos a classe - Resolució dels exercicis proposats amb antelació
Objectius: 2
Continguts:

Fluxos sobre Xarxes

Atendre les classes de teoria i problemes ón es desenvolupa el tema i fer els exercicis proposats pel professor per fer a casa o a classe
Teoria
8
Problemes
8
Laboratori
0
Aprenentatge dirigit
0
Aprenentatge autònom
10
  • Aprenentatge autònom: - Estudi de la teoria i problemes vistos a classe - Resolució dels exercicis proposats amb antelació
Objectius: 3
Continguts:

Estructures de Dades Avançades

Atendre les classes de teoria i problemes ón es desenvolupa el tema i fer els exercicis proposats pel professor per fer a casa o a classe
Teoria
8
Problemes
6
Laboratori
0
Aprenentatge dirigit
0
Aprenentatge autònom
7
  • Aprenentatge autònom: - Estudi de la teoria i problemes vistos a classe - Resolució dels exercicis proposats amb antelació
Objectius: 5 6
Continguts:

Resolució de problemes

L'objectiu és la resolució dels problemes proposats pel professor, amb caràcter individual. Es disposarà de com a mínim 4 dies entre la data en la qual el enunciat s'assigna i la classe de problemes en la que s'ha de fer la presentació i una setmana més per entregar per escrit la resolució del problema. Al llarg del curs es preveuen la assignació de dos o tres problemes a cada estudiant.
Teoria
0
Problemes
0
Laboratori
0
Aprenentatge dirigit
3
Aprenentatge autònom
11
  • Aprenentatge dirigit: Reunions entre el professor i els estudiants per a donar instruccions generals sobre els exercicis, aclariments de dubtes, fer el seguiment de l'activitat, etc.
Objectius: 1 2 3 4 5 6 8
Continguts:

Metodologia docent

Les classes de teoria són d'estil magistral, amb exposició teòrica per part del professor, intercalades amb nombrosos exemples. S'espera que els estudiants participin activament amb les seves preguntes i comentaris al llarg d'aquestes classes. Cada setmana es faran dos hores de teoria i dos hores de problemes. A les classes de problemes es discutiran les solucions proposades pels estudiants d'exercicis plantejats pel professor amb antelació (enunciats més complexos, amb els quals l'estudiant ha pogut treballar durant una setmana, autònomament) o d'exercicis curts plantejats durant la pròpia classe per a ser treballats en equips de dos estudiants o individualment. Ocasionalment, els estudiants podran ser requerits a exposar les seves solucions a la resta dels companys.

Complementant l'estudi personal i la resolució d'exercicis pràctics en paper, al llarg del curs es proposaran exercicis de programació, en els quals l'estudiant haurà de dissenyar i codificar programes en C++ que resolguin els problemes plantejats, p.e. implementar dos algorismes que resolen un mateix problema i portar a terme llevar un experiment computacional que permeti comparar la eficiència dels dos algorismes, i a la vegada, comparar aquesta eficiència amb les prediccions de l'anàlisi teòrica. Cada estudiant haurà de realitzar un seguit d'exercicis de programació de manera individual i un altre en equip (equips de dos persones). Aquest darrer exercici servirà per a avaluar la competència de aprenentatge autònom, doncs requereix l'estudi d'un tema concret, relacionat amb els que es veuen al llarg del curs, però no exposat a classe de teoria.

Mètode d'avaluació

La nota final (NF) es calcula a partir de la nota de la resolució de problemes d'algorismia (E), dels exercicis de programació (P), la nota de la prova final escrita (F) i la nota del treball associat a l'aprenentatge autònom (A) segons la fòrmula

NF = 0.6 F + 0.1 E + 0.1 P + 0.2 A

El profesorat avaluarà el grau d'adquisició de la competència d'aprenentatge autònom a partir de la nota obtinguda en un exercici de programació que implica un treball d'aprenentage autònom per part dels estudiants. La nota A s'avaluarà en una escala numèrica de 0 a 10.

La nota qualitativa de la competència transversal es determina a partir de la nota numèrica A obtinguda per l'alumne per trams: [0,5) => D, [5,6.5) => C, [6.5,8.5) => B, [8.5,10] => A

Bibliografia

Bàsica:

Complementaria:

Capacitats prèvies

- Familiaritat amb les tècniques bàsiques de programació i el llenguatge de programació C++: iteracions, alternatives, funcions recursives,
pas de paràmetres, punters, referències, memòria dinàmica, classes, objectes, mètodes, ...

- Coneixement de conceptes algorísmics bàsics: eficiència d'algorismes, notació asimptòtica, grafs, recorreguts de grafs, estructures de dades (llistes, arbres de cerca, hash, heaps, ...)

- Coneixements bàsics de matemàtica discreta, àlgebra lineal i càlcul

- Coneixements bàsics de teoria de probabilitat i estadística

- Coneixements bàsics d'arquitectura de computadors i de la jerarquia de memòria