Estructuras de Datos y Algoritmos

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

Profesorado

Responsable

• Albert Oliveras Llunell ( )

Otros

• Caroline König ( )
• Fernando Gastón Codony ( )
• Gabriel Valiente Feruglio ( )
• Ilario Bonacina ( )
• Jose Carmona Vargas ( )
• Salvador Roura Ferret ( )
• Santiago Marco Sola ( )

Horas semanales

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

Metodología docente

Método de evaluación

Bibliografía

Básica:

• Introduction to algorithms - Cormen, T.H. [et al.], MIT Press, 2022. ISBN: 9780262046305
  
• Fundamentos de algoritmia - Brassard, G.; Bratley, P, Prentice Hall, 1997. ISBN: 848966000X
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991001484479706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Data structures and algorithm analysis in C++ - Weiss, M.A, Pearson, 2014. ISBN: 0273769383
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004000539706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Combinatorial algorithms: generation, enumeration and search - Kreher, D.L.; Stinson, D.R, CRC Press, 1999. ISBN: 084933988X
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991001878419706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Computers and intractability: a guide to the theory of NP-Completeness - Garey, M.R.; Johnson, D.S, W.H. Freeman, 1979. ISBN: 0716710447
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991000087999706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• The C++ programming language - Stroustrup, B, Addison-Wesley, 2013. ISBN: 9780321563842
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004038849706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Foundations of algorithms - Neapolitan, R.E, Jones and Bartlett Learning, 2015. ISBN: 9781284049190
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004097269706711&context=L&vid=34CSUC_UPC:VU1&lang=ca

Complementaria:

• Introduction to algorithms: a creative approach - Manber, U, Addison-Wesley , 1989. ISBN: 0201120372
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991000704999706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Algorithmics: the spirit of computing - Harel, D.; Feldman, Y, Springer , 2012. ISBN: 9783642441356
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004154489706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Algorithms - Dasgupta, S.; Papadimitriou, C.; Vazirani, U, Mc Graw Hill Higher Education , 2008. ISBN: 9780073523408
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991003202339706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Algorithms - Sedgewick, R; Wayne, K, Addison-Wesley , 2011. ISBN: 9780321573513
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004156419706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Algorithms in C++ (Vol. 2) - Sedgewick, Robert; Wyk, Christopher J. Van, Addison-Wesley , 1998-2002. ISBN: 9780201361186
  http://cataleg.upc.edu/record=b1211994~S1*cat

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