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

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. 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


    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

    Algoritmos sobre strings


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

    Examen parcial


    Objetivos: 2 4 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
    2h
    Problemas
    1h
    Laboratorio
    2h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    6h

    Algoritmos de búsqueda exhaustiva


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

    Nociones de intractabilidad


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

    Examen final


    Objetivos: 2 5 3 6 4 1
    Semana: 18 (Fuera de horario lectivo)
    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 i 10)
    EF = nota del examen final (entre 0 i 10)
    AC= activitades de evalucacicón continuada (problemas)
    EJ= ejercicios de programación (jutge)

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

    La nota del examen de reevaluación sustituye la nota del examen parcial y del examen final.

    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, punteros, memoria dinámica, 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.