Algorísmia

• Professorat
• Hores setmanals
• Competències
• Objectius
• Continguts
• Activitats
• Metodologia docent
• Mètode d'avaluació
• Bibliografia
• Capacitats prèvies

Professorat

Responsable

• Maria Jose Serna Iglesias ( )

Altres

• Amalia Duch Brown ( )
• Conrado Martínez Parra ( )
• Maria Josep Blesa Aguilera ( )
• Santiago Marco Sola ( )

Hores setmanals

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 [Avaluable] - 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.
   Competències relacionades: 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ó
   Competències relacionades: 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
   Competències relacionades: 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.
   Competències relacionades: 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
   Competències relacionades: CT1.2C, CCO2.5, 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
   Competències relacionades: 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
   Competències relacionades: 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
   Competències relacionades: CT4.1, CT4.2, CT5.2, CT5.4, CCO3.1, CCO3.2, G7.3, CT5.3,

Continguts

1. Conceptes Algorísmics Bàsics
   Anàlisi del cas pitjor. Notació asimptòtica. Dividir per conquerir. Anàlisi d'algorismes recursius. Ordenació lineal. 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'algú dels algorismes i/o estructures de dades seguents (o d'altres). Programació lineal. Monticles de Fibonaccci. Hashing. Filtres de Bloom. Blockchain. Estructures de dades mètriques. Map Reduce. Grafs aleatoris. PageRank.

Activitats

Activitat Acte avaluatiu

Metodologia docent

Mètode d'avaluació

Bibliografia

Bàsica:

• Algorithm design - Kleinberg, J.; Tardos, E, Pearson, 2014. ISBN: 9781292023946
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004001669706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Algorithms - Dasgupta, S.; Papadimitriou, C.; Vazirani, U, McGraw-Hill, 2008. ISBN: 9780073523408
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991003202339706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• The Nature of computation - Moore, C.; Mertens, S, Oxford University press, 2011. ISBN: 9780199233212
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991003877749706711&context=L&vid=34CSUC_UPC:VU1&lang=ca

Complementaria:

• Fundamentals of algorithmics - Brassard, G.; Bratley, P, Prentice-Hall International , 1996. ISBN: 013073487X
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991001368999706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• The algorithm design manual - Skiena, S, Springer , 2008. ISBN: 9781848000698
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991003493029706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Handbook of data structures and applications - Mehta, D.P.; Sahni, S. (eds.), Chapman & Hall/CRC , 2005. ISBN: 1584884355
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991002955369706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• LaTeX: a document preparation system: user's guide and reference manual - Lamport, L, Addison-Wesley , 1994. ISBN: 0201529831
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991001080769706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Randomized Algorithms - Motwani, R.; Raghavan, P, Cambridge University Press , 1995. ISBN: 0521474655
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991001320239706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Probability and computing: randomized algorithms and probabilistic analysis - Mitzenmacher, M.; Upfal, E, Cambridge University Press , 2005. ISBN: 0521835402
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991002835539706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Networks, crowds, and markets: reasoning about a highly connected world - Easley, D.; Kleinberg, J, Cambridge University Press , 2010. ISBN: 9780521195331
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991003784319706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Introduction to algorithms - Cormen, T.H [et al.], MIT Press , 2022. ISBN: 9780262046305
  
• Algorithms - Sedgewick, R.; Wayne, K, Addison-Wesley , 2011. ISBN: 9780321573513
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004156419706711&context=L&vid=34CSUC_UPC:VU1&lang=ca

Capacitats prèvies