Algorismes i Estructures de Dades

Crèdits
6
Tipus
Obligatòria
Requisits
Aquesta assignatura no té requisits , però té capacitats prèvies
Departament
CS
Mail
caroline.leonore.konig@upc.edu
Aquesta assignatura se centra en estructures de dades i algorismes per a l'anàlisi eficient de dades en problemes bioinformàtics. La matèria cobreix arbres, diccionaris, grafs i cues de prioritat, i explica els algorismes relacionats amb aquestes estructures de dades, així com algorismes eficients per explorar espais de cerca complexos. El curs introdueix la teoria de la intractabilitat computacional i les seves respectives classes.

Professorat

Responsable

  • Caroline König (caroline.leonore.konig@upc.edu)

Hores setmanals

Teoria
2
Problemes
1
Laboratori
1
Aprenentatge dirigit
0
Aprenentatge autònom
6

Competències

Resultats d'aprenentatge

Coneixements

  • K3 - Identificar els fonaments matemàtics, les teories informàtiques, els esquemes algorísmics i els principis d'organització de la informació aplicables al modelat de sistemes biològics i a la resolució eficient de problemes bioinformàtics mitjançant el disseny d'eines computacionals.
  • K4 - Integrar els conceptes oferts pels llenguatges de programació de major ús en l'àmbit de les Ciències de la Vida per a modelar i optimitzar estructures de dades i construir algorismes eficients, relacionant-los entre sí i amb els seus casos d'aplicació.

    • Habilitats

  • S7 - Implementar mètodes de programació i anàlisi de dades a partir de l'elaboració d'hipòtesis de treball, dins de l'àrea d'estudi.
  • S8 - Enfrontar-se a la presa de decisions, i defensar-les amb arguments, en la resolució de problemes de les àrees de biologia, així com, dins dels àmbits adequats, les ciències de la salut, les ciències de la computació i les ciències experimentals.

    • Competències

  • C6 - Detectar deficiències en el propi coneixement i superar-les mitjançant la reflexió crítica i l'elecció de la millor actuació per a ampliar aquest coneixement.

    • Objectius

    1. Conèixer les principals estructures de dades utilitzades en la bioinformàtica.
      Competències relacionades: K3, K4, S7, S8, C6,
      Subcompetences
      • Conèixer problemes rellevants en computació bioinformàtica que es resolen basant-se en estructures de dades específiques.
    2. Comprendre el disseny i la implementació d'estructures de dades bàsiques per a una gestió eficient de dades en algoritmes avançats.
      Competències relacionades: K3, K4, S7, S8, C6,
      Subcompetences
      • Conèixer, comprendre, dissenyar estructura de dades per implementar diccionaris.
      • Conèixer, comprendre, dissenyar estructura de dades per implementar cues de prioridad.
      • Conèixer, comprendre, dissenyar estructuras de dades per a implementar arbres.
      • Conèixer, comprendre, dissenyar estructura de dades per implementar piles i cues.
    3. Coneixements sobre algorismes que resolguin problemes clàssics en grafs.
      Competències relacionades: K3, K4, S7, S8, C6,
      Subcompetences
      • Conèixer, dissenyar, comparar i implementar algoritmes de camí més curt en grafs.
      • Conèixer, dissenyar, comparar i implementar algoritmes d'ordenació topològica.
      • Conèixer, dissenyar, comparar i implementar algoritmes de recorregut de grafs.
    4. Conèixer, dissenyar i implementar algoritmes de cerca exhaustius.
      Competències relacionades: K3, K4, S7, S8, C6,
      Subcompetences
      • Comprendre, dissenyar i implementar algoritmes per explorar l'espai de cerca: Backtracking i Branch and Bound.
    5. Analitzar els límits de la computació a través de l'estudi de la completesa computacional. C
      Competències relacionades: K3, K4, S7, S8, C6,
      Subcompetences
      • Comprendre el Teorema de Cook-Levin com a base per demostrar la NP-completesa de problemes.
      • Reconèixer i classificar diversos problemes NP-complets, explorant les seves dificultats i les possibles aproximacions algorítmiques per abordar-los.

    Continguts

    1. Introducció a estructures de dades en bioinformatica
      Introducció a les estructures de dades clau i visió general de la seva aplicació en problemes bioinformàtics rellevants.
    2. Algorismes sobre arbres
      Estructura de dades per arbres. Arbres binaris de cerca. Arbres AVL.
    3. Diccionaris
      Implementacions bàsiques: taules and llistes. Implementacions advancades: taules de dispersió, arbores de cerca binaria
    4. Cues de prioritat
      Operacions amb cuas de prioritat. Implementació amb heaps. Heapsort.
    5. Algorismes bàsics de grafs
      Representacions: Matriu d'adjacència, llista d'adjacència. Cerca en profunditat, cerca en amplada. Algorisme de Dijkstra i Bellman-Ford del cami més curt.
    6. Algorismes sobre grafos avançats
      Ordenació topològica, Arbres de recobriment mínim, Algorisme de Kruskal, Algorisme de Prim
    7. Algorismes de cerca exhaustiva
      Principis: espai de solucions, generació de subconjunts i permutacions. Backtracking i Branch and Bound.
    8. Nocions d'intractabliitat
      Classe P i NP. NP-completesa y reducabilitat.

    Activitats

    Activitat Acte avaluatiu


    Introducció a les estructures de dades en la computació bioinformàtica


    Objectius: 1
    Teoria
    2h
    Problemes
    0h
    Laboratori
    2h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    4h

    Algorismes sobre arbes


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

    Diccionaris


    Objectius: 2
    Teoria
    2h
    Problemes
    0h
    Laboratori
    2h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    4h

    Cua de prioritata


    Objectius: 2
    Teoria
    2h
    Problemes
    2h
    Laboratori
    1h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    6h

    Examen parcial


    Objectius: 2 1
    Setmana: 8 (Fora d'horari lectiu)
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Algorismes bàsics sobre grafos


    Objectius: 3
    Teoria
    4h
    Problemes
    2h
    Laboratori
    2h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    10h

    Algorismes avançats sobre grafs


    Objectius: 3
    Teoria
    5h
    Problemes
    3h
    Laboratori
    4h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    16h

    Algorismes de cerca exhaustiva


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

    Nocions d'intractabilitat


    Objectius: 5
    Teoria
    2h
    Problemes
    4h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    10h

    Examen final


    Objectius: 2 4 3 5 1
    Setmana: 18 (Fora d'horari lectiu)
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Prova de programació

    Prova de programació practica amb la plataforma Jutge sobre els algoritmes vist al curs.
    Objectius: 2 4 3
    Setmana: 18
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Metodologia docent

    Les classes de teoria presenten els conceptes i tècniques fonamentals, que es treballen de manera pràctica a les sessions de problemes i laboratori mitjançant una col·lecció d'exercicis resolts en un jutge automàtic.

    La teoria es desenvolupa en sessions setmanals de dues hores, mentre que les classes de laboratori i problemes es realitzen cada quinze dies, també amb una durada de dues hores cadascuna.

    El curs es basa en la programació amb Python.

    Mètode d'avaluació

    EP = nota de l'examen parcial (entre 0 i 10)
    EF = nota de l'examen final (entre 0 i 10)
    PP= prova de programació (entre 0 i 10)
    AA= activitats autonòms d'aprenentatge (entre 0 i 10)

    NOTA = 30%EP + 40%EF + 20%PP + 10% AA

    És obligatòria la presentació de l'alumne a l'examen final i a la prova de programació per tenir dret a participar en l'examen de reavaluació.

    La nota de la reavaluació pot ser com a màxim un 8,0.

    En cas que el professorat ho consideri convenient, es podrà fer una prova oral per validar l'autoria de qualsevol de les proves d'avaluació.

    Bibliografia

    Bàsic

    Complementari

    Web links

    Capacitats prèvies

    Es requereix que els estudiants tinguin una base en programació imperativa orientada a objectes, incloent-hi el pas de paràmetres, classes, objectes, mètodes, recursivitat i iteradors. També han de conèixer Python i tenir nocions bàsiques de càlcul d'eficiència d'algorismes, incloent la notació asimptòtica i l'anàlisi de cost en temps i espai.