Algoritmos y Estructuras de Datos

• Horas semanales
• Objetivos
• Contenidos
• Actividades
• Metodología docente
• Método de evaluación
• Bibliografía
• Web links
• Capacidades previas

Profesorado

Responsable

• Caroline König ( )

Horas semanales

Objetivos

1. Conocer las estructuras de datos clave utilizadas en la computación bioinformática.
   Competencias relacionadas: K3, K4, S7, S8, C6,
   Subcompetences:
   • Conocer problemas relevantes en la computación bioinformática que se resuelven apoyándose en estructuras de datos específicas.
2. Comprender el diseño y la implementación de estructuras de datos básicas para una gestión de datos eficiente en algoritmos avanzados.
   Competencias relacionadas: K3, K4, S7, S8, C6,
   Subcompetences:
   • Conocer, comprender, diseñar estructura de datos para implementar diccionarios.
   • Conocer, comprender, diseñar estructura de datos para implementar colas de prioridad.
   • Conocer, comprender, diseñar estructuras de datos para implementar árboles.
   • Conocer, comprender, diseñar estructura de datos para implementar pilas y colas.
3. Conocimiento sobre algoritmos que resuelvan problemas clásicos en grafos.
   Competencias relacionadas: K3, K4, S7, S8, C6,
   Subcompetences:
   • Conocer, diseñar, comparar e implementar algoritmos de camino más corto en grafos.
   • Conocer, diseñar, comparar e implementar algoritmos para ordenación topológica.
   • Conocer, diseñar, comparar e implementar algoritmos de recorrido de grafos.
4. Comprender, diseñar, comparar e implementar algoritmos de string matching.
   Competencias relacionadas: K3, K4, S7, S8, C6,
5. Conocer, diseñar e implementar algoritmos de búsqueda exhaustivos.
   Competencias relacionadas: K3, K4, S7, S8, C6,
   Subcompetences:
   • Comprender, diseñar e implementar algoritmos para explorar el espacio de búsqueda: Backtracking y Branch and Bound.
6. Analizar los límites de la computación a través del estudio de la completitud computacional.
   Competencias relacionadas: K3, K4, S7, S8, C6,
   Subcompetences:
   • Comprender el Teorema de Cook-Levin como base para demostrar la NP-completitud de problemas.
   • Reconocer y clasificar diversos problemas NP-completos, explorando sus dificultades y posibles aproximaciones algorítmicas para abordarlos.

Contenidos

1. Introducción a estructura de datos en bioinformatica
   Introducción a las estructuras de datos clave y descripción general de su aplicación en problemas bioinformáticos relevantes.
2. Algoritmos sobre arboles
   Estructura de datos para arboles. Arboles binarios de búsqueda. Arboles AVL.
3. Diccionarios
   Implementaciones basicas: tablas y listas. Implementaciones avanzadas: tablas de dispersiçón, arboles binarios de búsqueda.
4. Colas de prioridad
   Operaciones con colas de prioridad. Implementación con heaps. Heapsort
5. Algoritmes sobre strings
   Algoritmos exactos y aproximados de string matching
6. Algoritmos básicos de grafos
   Representaciones: Matriz de adjacencia, lista de adjacencia. Búsqueda en profundidad, Búsqueda por anchura. Algoritmo de Dijkstra y Bellman-Ford del camino más corto.
7. Algoritmos avanzados sobre grafos
   Ordenación topológica, Árboles de recubrimiento mínimo, Algoritmo de Kruskal, Algoritmo de Prim
8. Algoritmos de búsqueda exhaustiva
   Principios: espacio de soluciones, generación de subconjuntos, permutaciones. Backtracking y Branch and Bound.
9. Nociones de intratabilidad
   Clase P y NP. NP-completitud y reducabilidad.

Actividades

Actividad Acto evaluativo

Metodología docente

Método de evaluación

Bibliografía

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

Capacidades previas