La asignatura de Programación Avanzada y Estructura de Datos profundiza en el diseño de algoritmos para la resolución de problemas complejos y en el uso eficiente de estructuras de datos, reforzando la base de ciencias de la computación necesaria para la formación en ingeniería informática.
Mediante el uso de pseudocódigo se fomenta el razonamiento algorítmigo abstracto, mientras que conceptos como la complejidad computacional permiten que el estudiantado analice el rendimiento de distintas soluciones para justificar su adecuación a un contexto. Finalmente, la implementación práctica de estos algoritmos y estructuras permite al estudiantado seguir desarrollando algunas de las habilidades esenciales en el campo de la programación, como la capacidad de detectar y resolver errores o la capacidad de trabajar en equipo.
Por lo tanto, la asignatura construye sobre los fundamentos de programación y algorítmica establecidos en el primer curso y prepara al estudiantado para afrontar asignaturas finalistas del área de ciencias de la computación.
Profesores Titulares
Profesores Docentes
- Dominio de las técnicas de programación trabajadas en la asignatura "Metodología y Tecnología de la Programación" (análisis descendente, modularidad, paso de parámetros y estructuras de datos básicos).
- Facilidad para escribir código mediante un lenguaje de programación (preferiblemente C/Java).
- Capacidad para seguir y proponer razonamientos matemáticos.
La asignatura tiene como objetivo ofrecer una visión avanzada de la programación de algoritmos, así como de las estructuras de datos más usadas en la actualidad. El estudio de la eficiencia de los algoritmos y diversas técnicas y estructuras se trabajan en profundidad con el objetivo de resolver problemas de forma eficiente y elegante. Adquiriendo los conocimientos de la asignatura, el estudiantado desarrolla habilidades para proponer y discutir la adecuación de soluciones a problemas complejos.
Los contenidos de la asignatura por semestre son los siguientes:
Primer semestre:
1. Especificación de algoritmos
1.1 - Sintaxis
1.2 - Expresiones booleanas
1.3 - Quantificadores y operadores de rango
2. Eficiencia de algoritmos
2.1 - Eficiencia, rendimiento y complejidad
2.2 - Análisis asintótico
2.3 - Algoritmos de ordenación
3. Diseño recursivo
3.1 - Etapas del diseño recursivo
3.2 - Recursividad final y técnica de inmersión
3.3 - Ordenación recursiva
4. Programación dinámica
4.1 - Estrategia top-down
4.2 - Estrategia bottom-up
5. Teoría de la complejidad computacional
5.1 - Tesis de Cobham
5.2 - Clases de complejidad
5.3 - P vs NP
6. Problemas combinatorios
6.1 - Fuerza bruta
6.2 - Backtracking
6.3 - Branch and bound
6.4 - Greedy
Segundo semestre:
7. Grafos
7.1 - Definición y conceptos básicos
7.2 - Representación
7.3 - Recorridos
7.4 - Ordenación topológica
7.5 - Árbol de expansión mínimo
7.6 - El camino más corto
8. Árboles
8.1 - Definición y conceptos básicos
8.2 - Representación
8.3 - Recorridos
8.4 - Árboles binarios de búsqueda
8.5 - Árboles AVL
9. Árboles R
9.1 - Definición y conceptos básicos
9.2 - Representación
9.3 - Algoritmos básicos: Búsqueda, inserción, eliminación
9.4 - Optimización del kNN
10. Tablas
10.1 - Definición y conceptos básicos
10.2 - Representación
10.3 - Tablas de hash
Durante la asignatura, se usarán las siguientes metodologías, por semestre:
Primer semestre:
- Clases magistrales, para aquellos contenidos que lo requieran.
- Problemas y ejercicios a clase, para consolidar conocimientos.
- Ejercicios de EC en clase y prácticas evaluables.
- Self-paced learning, para contenidos que no se evaluarán directamente.
- Flipped-classroom, para motivar el autoaprendizaje y dar soporte al estudiantado.
Segundo semestre:
- Project-Based Learning, donde el estudiantado aprenderá a diseñar e implementar estructuras de datos.
- Clases magistrales intercaladas para introducir conceptos necesarios, complementados durante el PBL.
- Self-paced learning, para contenidos que no se puedan aplicar al proyecto.
El primer semestre se evalúa mediante un examen (50%) y dos prácticas (20% y 30%). También se realizan ejercicios de evaluación continua que, más allá de fomentar el seguimiento de la asignatura, pueden permitir a alumnos que los superen con buenos resultados convalidar el examen final mediante una entrevista. Es necesario aprobar el examen y las prácticas por separado.
El segundo semestre se evalúa mediante un proyecto en grupo y un examen de validación individual. En caso de superar el examen de validación, la nota del semestre será la del proyecto en grupo, ajustada a partir de mecanismos de evaluación individual. De lo contrario, la nota del semestre será la del examen.
Se valorará:
- En el código de las prácticas y proyectos:
- La corrección del diseño y la implementación de los algoritmos en relación a los requisitos.
- La eficiencia y rendimiento de los algoritmos, tanto en su diseño como en su implementación.
- La calidad del código y la facilidad de su validación.
- En las memorias de las prácticas y proyectos:
- La adecuación de la estructura del documento en relación a los requisitos.
- La idoneidad de las explicaciones conceptuales y de la justificación de las decisiones tomadas.
- La relevancia y corrección matemática del análisis de rendimiento, así como de las conclusiones que se extraen de él.
- En los exámenes:
- La capacidad de razonar una solución eficiente para un problema complejo que no se ha tratado anteriormente.
- La correcta aplicación de las técnicas contenidas en el temario, como el análisis asintótico o el diseño recursivo.
- La capazidad de sintetizar y visualizar el funcionamiento de algoritmos y estructuras contenidos en el temario.
- La justificación razonable de las respuestas proporcionadas.
Apuntes de la asignatura disponibles en el campus virtual.
Brass, P. (2008). Advanced Data Structures. Cambridge University Press.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to algorithms (4th Edition). MIT Press.
Sedgewick, R., Wayne, K. (2011). Algorithms (4th Edition). Addison-Wesley Professional.
Skiena, S. S. (2020). The algorithm design manual (3rd Edition). Springer.