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

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. Comprendre, dissenyar, comparar i implementar algoritmes de string matching.
      Competències relacionades: K3, K4, S7, S8, C6,
    5. 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.
    6. 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 sobre strings
      Algorisme exacte i aproximat de tipus string matching.
    6. 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.
    7. Algorismes sobre grafos avançats
      Ordenació topològica, Arbres de recobriment mínim, Algorisme de Kruskal, Algorisme de Prim
    8. Algorismes de cerca exhaustiva
      Principis: espai de solucions, generació de subconjunts i permutacions. Backtracking i Branch and Bound.
    9. 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

    Algorismes sobre strings


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

    Examen parcial


    Objectius: 2 4 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
    2h
    Problemes
    1h
    Laboratori
    2h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    6h

    Algorismes de cerca exhaustiva


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

    Nocions d'intractabilitat


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

    Examen final


    Objectius: 2 5 3 6 4 1
    Setmana: 18 (Fora d'horari lectiu)
    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)
    AC= activitats d'avaluació continuada (problemes)
    EJ= exercicis de programació en el jutge

    NOTA = 10.0%AC + 10.0%EJ+ 35.0%EP + 45.0%EF

    La nota de la reavaluació substitueix la nota del examen parcial i final.

    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, punters, memòria dinàmica, 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.