Algoritmos y Estructuras de Datos

Créditos
6
Tipos
Obligatoria
Requisitos
Esta asignatura no tiene requisitos , pero tiene capacidades previas
Departamento
CS
Mail
caroline.leonore.konig@upc.edu
Esta asignatura se centra en estructuras de datos y algoritmos para el análisis eficiente de datos en problemas bioinformaticos. La materia abarca árboles, diccionarios, grafos y colas de prioridad, y explica los algoritmos relacionados con estas estructuras de datos, así como algoritmos eficientes para explorar espacios de búsqueda complejos. El curso introduce la teoría de la intractabilidad computacional y sus respectivas clases.

Profesorado

Responsable

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

Horas semanales

Teoría
2
Problemas
1
Laboratorio
1
Aprendizaje dirigido
0
Aprendizaje autónomo
6

Competencias

Resultados de aprendizaje

Conocimientos

  • K3 - Identificar los fundamentos matemáticos, las teorías informáticas, los esquemas algorítmicos y los principios de organización de la información aplicables al modelado de sistemas biológicos y a la resolución eficiente de problemas bioinformáticos mediante el diseño de herramientas computacionales.
  • K4 - Integrar los conceptos ofrecidos por los lenguajes de programación de mayor uso en el ámbito de las Ciencias de la Vida para modelar y optimizar estructuras de datos y construir algoritmos eficientes, relacionándolos entre sí y con sus casos de aplicación.

    • Habilidades

  • S7 - Implementar métodos de programación y análisis de datos orientados a partir de la elaboración de hipótesis de trabajo, dentro del área de estudio.
  • S8 - Enfrentarse a la toma de decisiones, y defenderlas con argumentos, en la resolución de problemas de las áreas de biología, así como, dentro de los ámbitos adecuados, las ciencias de la salud, las ciencias de la computación y las ciencias experimentales.

    • Competencias

  • C6 - Detectar deficiencias en el propio conocimiento y superarlas mediante la reflexión crítica y la elección de la mejor actuación para ampliar este conocimiento.

    • 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. 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.
    5. 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. 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.
    6. Algoritmos avanzados sobre grafos
      Ordenación topológica, Árboles de recubrimiento mínimo, Algoritmo de Kruskal, Algoritmo de Prim
    7. Algoritmos de búsqueda exhaustiva
      Principios: espacio de soluciones, generación de subconjuntos, permutaciones. Backtracking y Branch and Bound.
    8. Nociones de intratabilidad
      Clase P y NP. NP-completitud y reducabilidad.

    Actividades

    Actividad Acto evaluativo


    Introducción a las estructuras de datos en la computación bioinformática


    Objetivos: 1
    Teoría
    2h
    Problemas
    0h
    Laboratorio
    2h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    4h

    Algoritmos sobre arboles


    Objetivos: 2
    Teoría
    4h
    Problemas
    2h
    Laboratorio
    2h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    10h

    Diccionarios


    Objetivos: 2
    Teoría
    2h
    Problemas
    0h
    Laboratorio
    2h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    4h

    Cola de Prioridad


    Objetivos: 2
    Teoría
    2h
    Problemas
    2h
    Laboratorio
    1h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    6h

    Examen parcial


    Objetivos: 2 1
    Semana: 8 (Fuera de horario lectivo)
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Algoritmos basicos sobre grafos


    Objetivos: 3
    Teoría
    4h
    Problemas
    2h
    Laboratorio
    2h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    10h

    Algoritmos avanzados sobre grafos


    Objetivos: 3
    Teoría
    5h
    Problemas
    3h
    Laboratorio
    4h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    16h

    Algoritmos de búsqueda exhaustiva


    Objetivos: 4
    Teoría
    4h
    Problemas
    2h
    Laboratorio
    2h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    10h

    Nociones de intractabilidad


    Objetivos: 5
    Teoría
    2h
    Problemas
    4h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    10h

    Examen final


    Objetivos: 2 4 3 5 1
    Semana: 18 (Fuera de horario lectivo)
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Prueba de programación

    Prueba de programación practica con la plataforma Jutge sobre los algoritmos explicados en el curso.
    Objetivos: 2 4 3
    Semana: 18
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Metodología docente

    Las clases teóricas presentan conceptos y técnicas fundamentales, que luego se aplican en sesiones de resolución de problemas y laboratorio mediante una colección de ejercicios evaluados por un juez automático.

    Las sesiones teóricas se realizan semanalmente durante dos horas, mientras que las clases de laboratorio y resolución de problemas tienen lugar cada dos semanas, también con una duración de dos horas cada una.

    El curso se basa en la programación con Python.

    Método de evaluación

    EP = nota del examen parcial (entre 0 y 10)
    EF = nota del examen final (entre 0 y 10)
    AA= actividades autonomas de aprendizaje (entre 0 y 10)

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

    Es obligatoria la presentación del alumno en el examen final y en la prueba de programación para tener derecho a participar en el examen de revaluación.

    La nota de la revaluación podrá ser como máximo un 8,0.

    En caso de que el profesorado lo considere conveniente, se podrá realizar una prueba oral para validar la autoría de cualquiera de las pruebas de evaluación.

    Bibliografía

    Básico

    Complementario

    Web links

    Capacidades previas

    Se requiere que los estudiantes tengan una base en programación imperativa orientada a objetos, incluyendo el paso de parámetros, clases, objetos, métodos, recursividad e iteradores. También deben conocer Python y tener nociones básicas de cálculo de eficiencia de algoritmos, incluyendo la notación asintótica y el análisis de coste en tiempo y espacio.