Estructuras de Datos y Algoritmos

Usted está aquí

Créditos
6
Tipos
Obligatoria
Requisitos
  • Prerrequisito: PRO2
  • Prerrequisito: PRO1
Departamento
CS
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.

Profesores

Responsable

  • Enric Rodriguez Carbonell ( )

Otros

  • Albert Oliveras Llunell ( )
  • Antoni Lozano Bojados ( )
  • Conrado Martínez Parra ( )
  • Jordi Delgado Pin ( )
  • Pilar Nivela Alos ( )
  • Salvador Roura Ferret ( )

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 - 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.
    Related competences: CT4.2,
  2. Calcular la eficiencia de algoritmos iterativos aplicando las reglas de cálculo adecuadas.
    Related competences: CT4.2,
  3. Describir la eficiencia de los algoritmos recursivos utilizando recurrencias y comprender y aplicar los teoremas maestros para resolverlas.
    Related competences: CT4.2,
  4. Diseñar algoritmos para resolver problemas diversos de dificultad media con restricciones tanto de tiempo como de espacio.
    Related competences: CT4.1, CT4.2,
  5. Comparar la eficiencia de distintos algoritmos para resolver un mismo problema y seleccionar el más adecuado.
    Related competences: 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.
    Related competences: 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).
    Related competences: 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).
    Related competences: 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.
    Related competences: 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.
    Related competences: 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.
    Related competences: CT4.2,
  12. Completar y modificar implementaciones, en lenguaje de programación C++, de varios algoritmos para resolver problemas de dificultad media.
    Related competences: 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++.
    Related competences: 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
    Related competences: 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.
    Related competences: G6.2,
  16. Calcular el coste de un algoritmo en los casos peor, mejor y medio.
    Related competences: 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
4h
Problemas
2h
Laboratorio
2h
Aprendizaje dirigido
0h
Aprendizaje autónomo
8h

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)
Tipo: examen de teoría
Teoría
0h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
2h
Aprendizaje autónomo
4h

Colas de Prioridades

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

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

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)
Tipo: entrega
Teoría
0h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
8h

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
2h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
4h

Examen parcial 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: 12 (Fuera de horario lectivo)
Tipo: examen de laboratorio
Teoría
0h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
2h
Aprendizaje autónomo
4h

Teoría
4h
Problemas
2h
Laboratorio
2h
Aprendizaje dirigido
0h
Aprendizaje autónomo
4.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)
Tipo: entrega
Teoría
0h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
3h

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)
Tipo: examen final
Teoría
0h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
3h
Aprendizaje autónomo
10h

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)
NPO = nota del examen parcial de 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 (30%NPP + 30%NPO + 30%NF + 20%NJ , 30%NPO + 60%NF + 20%NJ))

Bibliografía

Básica:

Complementaria:

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
  • Jutge https://www.jutge.org/
  • UVa Online Judge http://uva.onlinejudge.org/
  • 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
  • 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/

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.