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 (
)
Pau Fernandez Duran (
)
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 final de la asignatura tiene en cuenta los siguientes actos de evaluación:
* P1: proyecto de programación individual a entregar a mediados de curso
* P2: proyecto de programación en pareja a entregar a final de curso
* PL: examen parcial de laboratorio (con ordenador)
* FL: examen final de laboratorio (con ordenador)
* FT: examen final de teoría (con papel)
La nota de proyectos se calcula como: P = (P1 + P2)/2
La nota de exámenes se calcula como: X = max (0.3 PL + 0.4 FT + 0.3 FL, 0.5 FT + 0.5 FL)
La nota final N se calcula como:
* N = max(0.3 P + 0.7 X, 0.15 P + 0.85 X), si X >= 4
* N = 0.15 P + 0.85 X, si X < 4
Bibliografía
Básica:
Algorithmics and Programming II (lecture notes in English) -
Cortadella, Jordi; Petit, Jordi,
UPC, 2021.