Algorísmia

Crèdits
6
Tipus
Obligatòria d'especialitat (Computació)
Requisits
Departament
CS;BSC;ENTEL
Web
http://www.cs.upc.edu/~mjserna/docencia/grauA/alg-GEI.html
Mail
alg@cs.upc.edu
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.

Professorat

Responsable

Altres

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.

    • 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,

    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


    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.
    • Aprenentatge autònom: - Estudi de la teoria i problemes vistos a classe - Resolució dels exercicis proposats amb antelació

    Continguts:
    Teoria
    4h
    Problemes
    4h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    10h

    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
    • Aprenentatge autònom: - Estudi de la teoria i problemes vistos a classe - Resolució dels exercicis proposats amb antelació
    Objectius: 1
    Continguts:
    Teoria
    6h
    Problemes
    6h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    16h

    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
    • Aprenentatge autònom: - Estudi de la teoria i problemes vistos a classe - Resolució dels exercicis proposats amb antelació
    Objectius: 2
    Continguts:
    Teoria
    8h
    Problemes
    9h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    15h

    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
    • Aprenentatge autònom: - Estudi de la teoria i problemes vistos a classe - Resolució dels exercicis proposats amb antelació
    Objectius: 3
    Continguts:
    Teoria
    8h
    Problemes
    8h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    15h

    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
    • Aprenentatge autònom: - Estudi de la teoria i problemes vistos a classe - Resolució dels exercicis proposats amb antelació
    Objectius: 5 6
    Continguts:
    Teoria
    1h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    4h

    Examen parcial

    Examen parcial fora d'hores de classe. Cobrint la primera part del temari i el tema assignat com treball d'aprenentatge autònom
    Objectius: 1 2 5 6 7
    Setmana: 8 (Fora d'horari lectiu)
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Examen Final Examen Final

    Examen final sobre tota la materia del curs
    Objectius: 1 2 3 4 5 7
    Setmana: 15 (Fora d'horari lectiu)
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Estudi d'un tema fora dels continguts del curs

    A principi de curs es plantejarà un tema d'estudi aquest tema formarà part del temari de l'examen parcial.

    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    10h

    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 dues hores de teoria i dues 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 mateixa classe per a ser treballats en equips de dos-quatre estudiants o individualment. Els estudiants podran ser requerits a exposar les seves solucions a la resta dels companys. Al llarg del curs caldrà lliurar la solució escrita de 3-4 dels problemes plantejats i corregir algunes de les solucions lliurades per altres estudiants.


    Per tal de poder avaluar la competència de aprenentatge autònom, es requereix l'estudi d'un tema concret, relacionat amb els que es veuen al llarg del curs, però no exposat a classe de teoria. Aquest tema es proposarà al començament del curs i s'avaluarà dintre de l'examen parcial.

    Mètode d'avaluació

    La nota final es calcula a partir de la nota de la resolució de problemes algorísmics (A); la nota associada als lliuraments i correccions de problemes (E); la de les proves escrites: parcial (M), matèria corresponent a les 6-7 primeres setmanes del curs i el tema associat a l'aprenentatge autònom, i l'examen final (F), tota la matèria.

    La nota final es calcula com: 0.75 max(0.5 M + 0.5 F, F) + 0.15 E + 0.1 A

    El professorat avaluarà el grau d'adquisició de la competència d'aprenentatge autònom a partir de la nota obtinguda en una de les preguntes del parcial, que contribuirà amb 1 punt a la nota del parcial. La nota qualitativa de la competència transversal es determina a partir de la nota numèrica obtinguda per l'alumne per trams: [0,0.25) => D, [0.25,0.5) => C, [0.5,0.75) => B, [0.75,1] => A

    Bibliografia

    Bàsic

    Complementari

    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