Se introduce el análisis matemático de los algoritmos y se presentan las herramientas para calcular su coste. Estas bases se utilizan para estudiar y analizar el diseño y las diferentes implementaciones de varios algoritmos y estructuras de datos fundamentales (pilas, colas, listas, colas de prioridad, árboles, árboles binarios de búsqueda, árboles equilibrados, tablas de hash y grafos) . Asimismo, se introducen las herramientas necesarias para poder implementar estas estructuras de datos y sus algoritmos asociados y se profundiza en la orientación a objetos y el uso de librerías externas.
Profesorado
Responsable
Jordi Cortadella Fortuny (
)
Otros
Jordi Petit Silvestre (
)
Jordi Puig Rabat (
)
Horas semanales
Teoría
3
Problemas
0
Laboratorio
2
Aprendizaje dirigido
0
Aprendizaje autónomo
7.5
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
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
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.
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.
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).
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).
Contenedores básicos.
Operaciones, usos e implementaciones de pilas, colas, colas de prioridades y listas.
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).
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.
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.
Cada semana se hacen dos horas de clase de teoría, una hora de problemas y dos horas de laboratorio.
El curso utiliza los lenguajes de programación C++ y Python.
Método de evaluación
La nota del curso se calcula en función de una nota obtenida de dos proyectos de laboratorio (NL), un examen parcial realizado sobre ordenador (NP), y un examen final que consta de dos pruebas: una sobre papel (NF1) y la otra sobre ordenador (NF2).
La nota final es el máximo de:
* 0.2 NL + 0.25 NP + 0.3 NF1 + 0.25 NF2
* 0.2 NL + 0.4 NF1 + 0.4 NF2
Reevaluación:
En el examen de reevaluación se podrán presentar sólo aquellos estudiantes que se hayan presentado los actos de evaluación y no hayan aprobado el curso. Para el examen de reevaluación se realizan dos pruebas similares al examen final: una sobre papel (R1) y la otra sobre ordenador (R2). En caso de no presentarse a alguna de las pruebas, se mantendrá la nota correspondiente del examen final (NF1 o NF2).
En caso de reevaluación, la nota final del curso se calcula como 0.2 NL + 0.4 R1 + 0.4 R2
Bibliografía
Básica:
Algorithmics and Programming II (lecture notes in English) -
Cortadella, Jordi; Petit, Jordi,
UPC, 2021.