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 Inteligencia Artificial.
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 que requieran conocimientos del área de ciencias de la computación.
Profesores Titulares
Profesores Docentes
- Dominio de las técnicas de programación trabajadas en las asignaturas "Fundamentos de Programación I" y "Fundamentos de Programación II" (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 (recomendable 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. 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 demuestra conocer y ser capaz de modelar diferentes topologías de estructuras de datos así como los algoritmos necesarios para su acceso y manipulación considerando siempre el impacto computacional que ello requiere.
Los contenidos de la asignatura son los siguientes:
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. Teoría de la complejidad computacional
4.1 - Tesis de Cobham
4.2 - Clases de complejidad
4.3 - P vs NP
4.4 - Reducciones
5. Problemas combinatorios
5.1 - Fuerza bruta
5.2 - Backtracking
5.3 - Branch and bound
5.4 - Greedy
6. Grafos
6.1 - Definición y conceptos básicos
6.2 - Representación
6.3 - Recorridos
6.4 - Ordenación topológica
6.5 - Árbol de expansión mínimo
6.6 - El camino más corto
7. Árboles
7.1 - Definición y conceptos básicos
7.2 - Representación
7.3 - Recorridos
7.4 - Árboles binarios de búsqueda
7.5 - Árboles AVL
8. Tablas
8.1 - Definición y conceptos básicos
8.2 - Representación
8.3 - Tablas de hash
Durante la asignatura, se usarán las siguientes metodologías, por bloque:
Programación Avanzada:
- 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.
Estructura de Datos:
- 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 bloque 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 mejorar la nota del bloque. Es necesario aprobar el examen y las prácticas por separado.
El segundo bloque se evalúa mediante un proyecto en grupo (60%) y un examen individual (40%).
Se valorará:
- En el código de las prácticas:
- 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:
- 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.