Estructuras de Datos y Algoritmos

Créditos
6
Tipos
Obligatoria
Requisitos
Departamento
CS
Web
http://www.cs.upc.edu/~eda
Esta asignatura empieza introduciendo los conceptos de eficiencia y coste de un algoritmo y las herramientas matemáticas básicas para analizarlos. A continuación se utilizan estas herramientas para estudiar y analizar el diseño y las diferentes implementaciones de algoritmos y estructuras de datos clásicos y fundamentales.

Profesorado

Responsable

Otros

Horas semanales

Teoría
2
Problemas
1
Laboratorio
1
Aprendizaje dirigido
0.4
Aprendizaje autónomo
5.6

Competencias

Competencias Técnicas

Competencias técnicas comunes

  • CT2 - Utilizar de forma apropiada teorías, procedimientos y herramientas en el desarrollo profesional de la ingeniería informática en todos sus ámbitos (especificación, diseño, implementación, despliegue -implantación- y evaluación de productos) de manera que se demuestre la comprensión de los compromisos adoptados en las decisiones de diseño.
    • CT2.3 - Diseñar, desarrollar, seleccionar y evaluar aplicaciones, sistemas y servicios informáticos, y al mismo tiempo asegurar su fiabilidad, su seguridad y su calidad, conforme a principios éticos y a la legislación y la normativa vigente.
    • CT2.4 - Demostrar conocimiento y capacidad de aplicación de las herramientas necesarias para el almacenaje, el procesamiento y el acceso a los Sistemas de información, incluidos los basados en web.
  • CT4 - Demostrar conocimiento y capacidad de aplicación de los procedimientos algorítmicos básicos de las tecnologías informáticas para diseñar soluciones a problemas, analizando la idoneidad y la complejidad de los algoritmos
    • CT4.1 - Identificar las soluciones algorítmicas más adecuadas para resolver problemas de dificultad mediana.
    • CT4.2 - Razonar sobre la corrección y la eficiencia de una solución algorítmica.
    • CT4.3 - Demostrar conocimiento y capacidad de aplicación de los principios fundamentales y las técnicas básicas de los sistemas inteligentes y su aplicación práctica.
  • CT5 - Analizar, diseñar, construir y mantener aplicaciones de forma robusta, segura y eficiente, escogiendo el paradigma y los lenguajes de programación más adecuados.
    • CT5.1 - Escoger, combinar y explotar diferentes paradigmas de programación, en el momento de construir software, atendiendo a criterios como la facilidad de desarrollo, la eficiencia, la portabilidad y la mantenibilidad.
    • CT5.2 - Conocer, diseñar y utilizar de forma eficiente los tipos y las estructuras de datos más adecuados para la resolución de un problema.
    • CT5.3 - Diseñar, escribir, probar, depurar, documentar y mantener código en un lenguaje de alto nivel para resolver problemas de programación aplicando esquemas algorítmicos y usando estructuras de datos.
    • CT5.4 - Diseñar la arquitectura de los programas utilizando técnicas de orientación a objetos, de modularización y de especificación e implementación de tipos abstractos de datos.
    • CT5.5 - Usar las herramientas de un entorno de desarrollo de software para crear y desarrollar aplicaciones.
  • CT8 - Planificar, concebir, desplegar y dirigir proyectos, servicios y sistemas informáticos en todos los ámbitos, liderando su puesta en marcha, su mejora continua y valorando su impacto económico y social
    • CT8.6 - Demostrar comprensión de la importancia de la negociación, de los hábitos de trabajo efectivos, del liderazgo y de las habilidades de comunicación en todos los entornos de desarrollo de software.
    • CT8.7 - Controlar versiones y configuraciones del proyecto.

    • Competencias Transversales

    Uso solvente de los recursos de información

  • G6 [Avaluable] - Gestionar la adquisición, la estructuración, el análisis y la visualización de datos e información del ámbito de la ingeniería informática y valorar de forma crítica los resultados de esta gestión.
    • G6.2 - Después de identificar las partes diferentes de un documento académico y de organizar las referencias bibliográficas, diseñar y ejecutar una buena estrategia de búsqueda avanzada con recursos de información especializados, seleccionando la información pertinente teniendo en cuenta criterios de relevancia y calidad.

    • Objetivos

    1. Comprender las definiciones de las notaciones asintóticas O grande, Omega y Theta y su uso para caracterizar la eficiencia en tiempo y espacio de los algoritmos.
      Competencias relacionadas: CT4.2,
    2. Calcular la eficiencia de algoritmos iterativos aplicando las reglas de cálculo adecuadas.
      Competencias relacionadas: CT4.2,
    3. Describir la eficiencia de los algoritmos recursivos utilizando recurrencias y comprender y aplicar los teoremas maestros para resolverlas.
      Competencias relacionadas: CT4.2,
    4. Diseñar algoritmos para resolver problemas diversos de dificultad media con restricciones tanto de tiempo como de espacio.
      Competencias relacionadas: CT4.1, CT4.2,
    5. Comparar la eficiencia de distintos algoritmos para resolver un mismo problema y seleccionar el más adecuado.
      Competencias relacionadas: CT4.1, CT4.2,
    6. Conocer, explicar, diseñar, analizar, comparar e implementar algoritmos (como pueden ser mergesort, quicksort, Karatsuba y Strassen, entre otros) utilizando la técnica de dividir y vencer.
      Competencias relacionadas: CT4.1, CT4.2, CT5.3,
    7. Conocer, explicar, diseñar, analizar, comparar e implementar las principales estructuras de datos que se pueden utilizar para implementar diccionarios (tablas, tablas ordenadas, listas, listas ordenadas, tablas de dispersión, árboles binarios de búsqueda, árboles AVL).
      Competencias relacionadas: CT4.1, CT4.2, CT5.2, CT2.4,
    8. Conocer, explicar, diseñar, analizar, comparar e implementar las principales estructuras de datos que se pueden utilizar para implementar colas de prioridad (árboles, heaps).
      Competencias relacionadas: CT4.1, CT4.2, CT5.2, CT2.4,
    9. Conocer, explicar, diseñar, analizar, comparar e implementar algoritmos que resuelvan problemas clásicos en grafos como recorridos, ordenación topológica y caminos mínimos entre otros.
      Competencias relacionadas: CT4.1, CT4.2, CT5.2, CT2.4,
    10. Conocer, explicar, diseñar, analizar, comparar e implementar algoritmos de búsqueda exhaustiva utilizando la técnica de backtracking.
      Competencias relacionadas: CT4.1, CT4.2, CT2.4, CT4.3,
    11. Tomar conciencia de los límites de la computación: comprender las implicaciones de la pregunta "P = NP?", entender el enunciado del Teorema de Cook-Levin, reconocer e identificar varios problemas NP-completos clásicos.
      Competencias relacionadas: CT4.2,
    12. Completar y modificar implementaciones, en lenguaje de programación C++, de varios algoritmos para resolver problemas de dificultad media.
      Competencias relacionadas: CT4.2, CT5.2, CT5.1,
    13. Identificar y proponer soluciones para problemas de eficiencia de algoritmos y de programas escritos en lenguaje de programación C++.
      Competencias relacionadas: CT4.1, CT4.2, CT5.2, CT2.4, CT2.3,
    14. Analizar un juego estratégico para diseñar y programar un jugador eficaz, eficiente, colaborativo y competitivo que maximice las posibilidades de ganar el juego y que sea capaz de establecer alianzas y de coordinarse con otros jugadores
      Competencias relacionadas: CT8.6, CT8.7, CT4.1, CT4.2, CT5.2, CT5.4, CT5.5, G6.2, CT2.4, CT4.3, CT5.1, CT5.3, CT2.3,
    15. Ejecutar estrategias de búsqueda de información (referencias bibliográficas, artículos científicos, patentes, recursos web de calidad ...) para elaborar un documento que describa, para un problema dado, un algoritmo conocido que lo resuelva, estructurándolo correctamente, citando adecuadamente las fuentes utilizadas y haciendo un uso ético de la información recopilada.
      Competencias relacionadas: G6.2,
    16. Calcular el coste de un algoritmo en los casos peor, mejor y medio.
      Competencias relacionadas: CT4.2,

    Contenidos

    1. Análisis de Algoritmos
      Coste en tiempo y espacio. Caso peor, mejor y medio. Notación asintótica. Análisis del coste de algoritmos iterativos y recursivos.
    2. Divide y Vencerás
      Principios: partición en subproblemas, recombinación de soluciones. Ejemplos: mergesort, quicksort, algoritmo de Karatsuba para multiplicar números grandes, algoritmo de Strassen para multiplicar matrices.
    3. Diccionarios
      Operaciones de diccionarios y diccionarios ordenados. Implementaciones básicas: tablas y listas. Implementaciones avanzadas: tablas de dispersión, árboles binarios de búsqueda, árboles AVL.
    4. Colas con Prioridades
      Operaciones de colas con prioridades. Implementaciones con heaps. Heapsort.
    5. Grafos
      Representaciones: matrices de adyacencia, listas de adyacencia e implícita. Búsqueda en profundidad (DFS). Búsqueda en anchura (BFS). Ordenación topológica. Algoritmo de Dijkstra para caminos mínimos. Algoritmo de Prim para árboles de expansión mínimos.
    6. Generación y Búsqueda Exhaustiva
      Principios: espacio de soluciones, soluciones parciales, poda. Generación de subconjuntos y permutaciones. Ejemplos: mochila, viajante de comercio.
    7. Nociones de Intractabilidad
      Introducción básica a las clases P y NP, al Teorema de Cook-Levin, a las reducciones y a la NP-completitud.

    Actividades

    Actividad Acto evaluativo


    Análisis de Algoritmos

    Desarrollo del tema 1 de la asignatura.
    Objetivos: 1 2 3 5 4 16
    Contenidos:
    Teoría
    4h
    Problemas
    2h
    Laboratorio
    2h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    8h

    Dividir y Vencer

    Desarrollo del tema 2 de la asignatura.
    Objetivos: 3 5 4 6 12 13
    Contenidos:
    Teoría
    4h
    Problemas
    2h
    Laboratorio
    2h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    8h

    Diccionarios

    Desarrollo del tema 3 de la asignatura.
    Objetivos: 5 4 7 12 13
    Contenidos:
    Teoría
    3.5h
    Problemas
    2h
    Laboratorio
    2h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    8h

    Colas de Prioridades

    Desarrollo del tema 4 de la asignatura.
    Objetivos: 5 4 8 12 13
    Contenidos:
    Teoría
    1.5h
    Problemas
    2h
    Laboratorio
    1h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    4h

    Examen parcial de papel

    Se evalúan los objetivos correspondientes a los contenidos 1 y 2.
    Objetivos: 1 2 3 5 4 6 12
    Semana: 6 (Fuera de horario lectivo)
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Grafos

    Desarrollo del tema 5 de la asignatura.
    Objetivos: 5 4 9 12 13
    Contenidos:
    Teoría
    4h
    Problemas
    2h
    Laboratorio
    2h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    8h

    Presentación del Juego

    Familiarización con el Juego: primeras partidas, visualizaciones y depuración.
    Objetivos: 14
    Contenidos:
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    2h
    Aprendizaje autónomo
    0.5h

    Juego

    Se evalúan los objetivos correspondientes al objetivo específico 15. Se publicará un enunciado que consistirá en la descripción de un juego de estrategia. Los estudiantes deberán programar un jugador para este juego (es decir, implementar una estrategia para intentar ganar el juego). Se llevará a cabo una competición en la que los estudiantes competirán los unos contra los otros, de la que se obtendrá una clasificación. Para participar en esta competición, los jugadores de los estudiantes deberán superar un test de cualificación. La nota correspondiente a esta parte se calculará a partir de la posición en la clasificación de forma proporcional, garantizando que el campeón tenga un 10 y que todos los participantes que tengan un jugador cualificado tengan un nota mínima de 5. Los estudiantes que no hayan conseguido ningún jugador cualificado tendrán una nota de 0.
    Objetivos: 14
    Semana: 9 (Fuera de horario lectivo)
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Desarrollo del Juego

    Aprendizaje de las estrategias más apropiadas para el Juego. Resolución de dudas existentes a nivel grupal.
    Objetivos: 14
    Contenidos:
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    2h
    Aprendizaje autónomo
    2.5h

    Generación y Búsqueda Exhaustiva

    Desarrollo del tema 6 de la asignatura.
    Objetivos: 5 4 10 12 13
    Contenidos:
    Teoría
    4h
    Problemas
    2h
    Laboratorio
    4h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    8h

    Nociones de Intratabilidad y indecidibilidad

    Desarrollo del tema 7 de la asignatura.
    Objetivos: 11
    Contenidos:
    Teoría
    4h
    Problemas
    3h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    4h

    Gran Final del Juego

    Asistencia a la Gran Final del Juego. Aprendizaje de las estrategias utilizadas por los ganadores.
    Objetivos: 14
    Contenidos:
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    2h
    Aprendizaje autónomo
    1.5h

    Tutoriales Bibliotècnica-BRGF.

    Autoaprendizaje mediante tutoriales de la Bibliotécnica de la BRGF sobre: ​​la propiedad intelectual, el uso ético de la información y el uso de software de gestión de referencias bibliográficas.
    Objetivos: 15
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    2.5h

    Práctica de uso solvente de recursos de información.

    Se evalúan los objetivos correspondientes al objetivo específico 16. Se publicará un enunciado que consistirá en la descripción de un problema computacional y el nombre de un algoritmo que lo resuelve. Los estudiantes tendrán que buscar (en la biblioteca, en la web, ...) información sobre el problema y el algoritmo y elaborar un documento breve y bien estructurado que incluya correctamente las fuentes consultadas. El documento deberá entregarse el día del examen final. La competencia transversal se evaluará en base a este documento.
    Objetivos: 15
    Semana: 14 (Fuera de horario lectivo)
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Examen de ordenador

    Se evalúa la vertiente de laboratorio, es decir, de implementación, de los contenidos tratados hasta la fecha del examen. Frente al ordenador, los estudiantes reciben dos o tres problemas. Un problema se define con un enunciado, uno o más juegos de pruebas públicos y, quizá, cierto código ya implementado. Cuando un estudiante quiera entregar su solución para alguno de los problemas, la enviará a un juez automático que, en pocos segundos, le devolverá el veredicto sobre el comportamiento de su programa. El estudiante puede reenviar hasta 10 soluciones para el mismo problema. Los profesores corregirán el último envío realizado para cada problema.
    Objetivos: 7 8 9 10
    Semana: 15 (Fuera de horario lectivo)
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Examen final

    Se evalúa los objetivos correspondientes a los contenidos 1 a 7.
    Objetivos: 1 2 3 5 4 6 7 8 9 10 12 13 11
    Semana: 15 (Fuera de horario lectivo)
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Metodología docente

    El temario se expone de forma muy práctica, a través de la presentación de muchos ejemplos.

    Las clases de teoría introducen todos los conceptos y técnicas necesarios, los cuales se ponen en práctica en las clases de problemas y de laboratorio mediante una colección de problemas y ejercicios en un juez automático.

    Las dos horas de clases de teoría se hacen semanalmente. Las dos horas de clases de laboratorio se hacen quincenalmente. Las dos horas de clases de problemas se hacen quincenalmente.

    La programación del juego integra los conocimientos y las competencias de todo el curso.

    El curso utiliza el lenguaje de programación C++.

    Método de evaluación

    NPP = nota del examen parcial de papel (entre 0 y 10)
    NO = nota del examen ordenador (entre 0 y 10)
    NF = nota del examen final (entre 0 y 10)
    NJ = nota del juego (entre 0 y 10)

    NOTA = mín(10, màx (22.5%NPP + 22.5%NF + 45%NO + 20%NJ , 45%NF + 45%NO + 20%NJ))

    Bibliografía

    Básico

    Complementario

    Web links

    • MIT OpenCourseWare: és una publicació gratuïta dels materials dels cursos del Massachusets Institute of Technology (MIT) que mostra la majoria de temes que s'ensenyen en el MIT. Conté apunts, exercicis, exercicis resolts, exàmens i videos de classes. MIT OpenCourseWare: es una publicación gratuita de los materiales de los cursos del Massachusets Institute of Technology (MIT) que muestra la mayoría de temas que se enseñan en el MIT. Contiene apuntes, ejercicios, ejercicios resueltos, exámenes y vídeos de clases. 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
    • UVa Online Judge http://uva.onlinejudge.org/
    • Algorithms Courses on the WWW: és un llistat exhaustiu d'enllaços a portals web relacionats amb algorísmia i complexitat: cursos de diverses universitats, software, aplicacions gràfiques, pàgines personals d'investigadors coneguts, entre d'altres coses. Algorithms Courses on the WWW: es un listado exhaustivo de enlaces a portales web relacionados con la algoritmia y complejidad: cursos de varias universidades, software, aplicaciones gráficas, páginas personales de investigadores conocidos, entre otras cosas. Algorithms Courses on the WWW: it is an exhaustive listing of links to web sites related to algorithms and complexity: courses of several universities, software, graphic applications, personal pages of well-known researchers, among other things. http://www.cs.pitt.edu/~kirk/algorithmcourses/index.html
    • The Stony Brook Algorithm Repository: és un portal web amb una col·lecció d'implementacions de més de setanta algorismes fonamentals d'optimització combinatòria. The Stony Brook Algorithm Repository: es un portal web con una colección de implementaciones de más de setenta algoritmos fundamentales de optimitzación combinatoria. The Stony Brook Algorithm Repository: it is a web site with a collection of implementations of more than seventy fundamental algorithms of combinatorial optimitzation. http://www.cs.sunysb.edu/~algorith/
    • TopCoder http://www.topcoder.com
    • Transparències de K. Wayne per al curs "Algorithms and Data Structures" de la Princeton University https://www.cs.princeton.edu/courses/archive/fall12/cos226/lectures.php
    • Jutge https://www.jutge.org/

    Capacidades previas

    Se espera que los estudiantes estén familiarizados con las técnicas de programación imperativa basada en objetos:
    - paso de parámetros,
    - clases,
    - objetos,
    - métodos,
    - punteros,
    - memoria dinámica,
    - genericidad,
    - recursividad,
    - uso de clases estándar,
    - iteradores.

    También se espera que conozcan bien al menos un lenguaje imperativo orientado a objetos, preferentemente C++.

    Son también requisitos la capacidad crítica y la madurez matemática.