Algoritmia y Programación II

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

Profesorado

Responsable

• Jordi Cortadella Fortuny ( )

Otros

• Jordi Petit Silvestre ( )
• Pau Fernandez Duran ( )

Horas semanales

Competencias

Competencias Técnicas

Competencias técnicas

• CE2 - Ser capaz de programar soluciones a problemas de ingeniería: Diseñar soluciones algorítmicas eficientes a un problema computacional dado, implementarlas en forma de Programa robusto, estructurado y mantenible, y comprobar la validez de la solución.

Competencias Transversales

Transversales

• CT4 - Trabajo en equipo. Ser capaz de trabajar como miembro de un equipo interdisciplinar, ya sea como un miembro más o realizando tareas de dirección, con la finalidad de contribuir a desarrollar proyectos con pragmatismo y sentido de la responsabilidad, asumiendo compromisos teniendo en cuenta los recursos disponibles.
• CT5 [Avaluable] - Uso solvente de los recursos de información. Gestionar la adquisición, la estructuración, el análisis y la visualización de datos e información en el ámbito de especialidad y valorar de forma crítica los resultados de dicha gestión.
• CT6 - Aprendizaje autónomo. 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 dicho conocimiento.
• CT7 - Tercera lengua. Conocer una tercera lengua, preferentemente el inglés, con un nivel adecuado oral y escrito y en consonancia con las necesidades que tendrán los titulados y tituladas.

Básicas

• CB5 - Que los estudiantes hayan desarrollado aquellas habilidades de aprendizaje necesarias para emprender estudios posteriores con un alto grado de autonomía

Competencias Técnicas Genéricas

Genéricas

• CG1 - Concebir sistemas computacionales que integren datos de procedencias y formas muy diversas, creen con ellos modelos matemáticos, razonen sobre dichos modelos y actúen en consecuencia, aprendiendo de la experiencia.
• CG2 - Elegir y aplicar los métodos y técnicas más adecuados a un problema definido por datos que representen un reto por su volumen, velocidad, variedad o heterogeneidad, incluidos métodos informáticos, matemáticos, estadísticos y de procesado de la señal.
• CG5 - Poder recurrir a conocimientos fundamentales y metodologías de trabajo sólidas adquiridos durante los estudios para adaptarse a los nuevos escenarios tecnológicos del futuro.

Objetivos

1. Ser capaz de diseñar, analizar, implementar algoritmos que resuelvan problemas utilizando técnicas algorítmicas y de programación.
   Competencias relacionadas: CB5, CT4, CT5, CT6, CT7, CE2, CG1, CG2, CG5,

Contenidos

1. Tipos Abstractos de Datos.
   Especificación e implementación. Abstracción, descomposición funcional y por datos, ocultación y encapsulación de la información. Lenguajes orientados a objetos: clases y objetos, métodos privados y públicos, constructores y destructores. Genericidad. Ejemplos: punto, rectángulo, números racionales.
2. 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. Ejemplos: ordenación por inserción y selección, subsecuencia de suma máxima, envolvente convexa.
3. Dividir y vencer.
   Principios: partición en subproblemas, recombinación de soluciones. Teorema Master. Ejemplos: búsqueda binaria, ordenación por fusión, ordenación y selección rápidas, cálculo de los dos puntos más cercanos en un plano. Transformada rápida de Fourier (FFT).
4. Gestión de memoria.
   Representación de los datos en memoria. Punteros y referencias. Gestión dinámica de memoria (clase vector). Estructura de la memoria de un programa (código, pila, heap).
5. Contenedores básicos.
   Operaciones, usos e implementaciones de pilas, colas, colas de prioridades y listas.
6. Grafos.
   Representaciones: matrices de adyacencia, listas de adyacencia y representación implícita. Búsqueda en profundidad (DFS). Búsqueda en anchura (BFS). Ordenación topológica. Algoritmos por caminos mínimos (Dijsktra, Bellman-Ford). Algoritmos para árboles de expansión mínimos (Prim y Kruskal). Algoritmos para flujos máximos (Ford-Fulkerson).
7. Conjuntos y diccionarios.
   Árboles y su representación. Árboles binarios y recorridos (pre-orden, post-orden, in-orden y por niveles). Árboles de búsqueda binarios y árboles balanceados: operaciones e implementación. Tablas de dispersión.

Actividades

Actividad Acto evaluativo

Metodología docente

Método de evaluación

Bibliografía

Básica:

• Algorithmics and Programming II (lecture notes in English) - Cortadella, Jordi; Petit, Jordi, UPC, 2021.
  
• Data structures and algorithm analysis in C++ - Weiss, Mark Allen, Pearson, 2014. ISBN: 9780273769385
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004000539706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Algorithms - Dasgupta, Sanjoy.; Papadimitriou, Christos; Vazirani, Umesh, Mc Graw Hill Higher Education, 2008. ISBN: 9780073523408
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991003202339706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Introduction to algorithms - Cormen, T.H. [et al.], MIT Press, 2022. ISBN: 9780262046305
  
• Fundamentos de algoritmia - Brassard, Gilles.; Bratley, Paul, Prentice Hall, 1997. ISBN: 9788489660007
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991001484479706711&context=L&vid=34CSUC_UPC:VU1&lang=ca

Complementaria:

• Introduction to algorithms: a creative approach - Manber, Udi, Addison-Wesley , 1989. ISBN: 9780201120370
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991000704999706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Algorithms in C++ - Sedgewick, Robert, Addison-Wesley , 1998-2002. ISBN: 9780201350883
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991002417629706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Algorithms illuminated. Part 1: The Basics - Roughgarden, Tim, Soundlikeyourself Publishing , 2017-2020. ISBN: 9780999282908
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004186919706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Algorithms illuminated. Part 2: Graph Algorithms and Data Structures - Roughgarden, Tim, Soundlikeyourself Publishing , 2017-2020. ISBN: 9780999282922
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004186919706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Algorithms illuminated. Part 3: Greedy Algorithms and Dynamic Programming - Roughgarden, Tim, Soundlikeyourself Publishing , 2017-2020. ISBN: 9780999282946
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004186919706711&context=L&vid=34CSUC_UPC:VU1&lang=ca

Web links

• Pàgina principal del curs. http://www.cs.upc.edu/~jordicf/Teaching/AP2
• Jutge.org https://jutge.org

Capacidades previas