Algorismes i Estructures de Dades

• Hores setmanals
• Objectius
• Continguts
• Activitats
• Metodologia docent
• Mètode d'avaluació
• Bibliografia
• Web links
• Capacitats prèvies

Professorat

Responsable

• Caroline König ( )

Hores setmanals

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

Metodologia docent

Mètode d'avaluació

Bibliografia

Bàsica:

• Introduction to algorithms - Cormen, Thomas H; Leiserson, Charles Eric; Rivest, Ronald L; Stein, Clifford, The MIT Press, [2022]. ISBN: 9780262046305
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991005238379006711&context=L&vid=34CSUC_UPC:VU1
• Combinatorial algorithms : generation, enumeration and search - Kreher, Donald L; Stinson, Douglas R, CRC Press, cop. 1999. ISBN: 084933988X
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991001878419706711&context=L&vid=34CSUC_UPC:VU1
• Introduction to computation and programming using Python : with application to computational modeling and understanding data - Guttag, John V, 2021. ISBN: 9780262363433
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991005184779906711&context=L&vid=34CSUC_UPC:VU1

Complementaria:

• Algorithms unlocked - Cormen, Thomas H, The MIT Press , cop. 2013. ISBN: 0262518805
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004001129706711&context=L&vid=34CSUC_UPC:VU1
• Algorithms on trees and graphs : with python code - Valiente Feruglio, Gabriel, Springer , [2021]. ISBN: 9783030818845
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004916440606711&context=L&vid=34CSUC_UPC:VU1

Web links

• MIT OpenCourseWare: it is a free publication of the materials of the courses of the Massachusets Institute of Technology (MIT) that shows most of the topics that are taught in MIT. Contains notes, exercises, solved exercises, exams and videos of classes. http://ocw.mit.edu/courses/#electrical-engineering-and-computer-science
• Jutge https://jutge.org/
• Algorithms Courses on the WWW https://people.cs.pitt.edu/~kirk/algorithmcourses/index.html
• Lecture Notes K. Wayne of the course "Algorithms and Data Structures" from Princeton University https://www.cs.princeton.edu/courses/archive/fall12/cos226/lectures.php

Capacitats prèvies