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.
Los Resultados de Aprendizaje de esta asignatura son:
- El alumno o alumna será capaz identificar la teoría, conceptos y métodos de la programación y las estructuras de datos para resolver un determinado problema.
- El alumno o alumna podrá resolver un problema mediante el diseño y la implementación de un algoritmo eficiente utilizando estructuras de datos adecuadas.
Para alcanzar estos resultados, la asignatura se divide en dos bloques de contenido: Programación Avanzada y Estructura de Datos.
Al finalizar el curso, el alumno debe ser capaz de:
- Justificar la necesidad de la especificación formal de algoritmos.
- Realizar la especificación formal de un algoritmo en términos de pre y post-condiciones.
- Implementar un algoritmo sin ambigüedades a partir de la especificación del mismo.
- Evaluar la eficiencia de un algoritmo a través del cálculo del coste.
- Diseñar un algoritmo recursivo.
- Explicar los principales mecanismos de derivación formal y verificación formal de algoritmos recursivos simples y llevarlo a la práctica en problemas.
- Reconocer distintas clases de complejidad computacional como P o NP, así como reducciones entre problemas de diferentes clases.
- Escoger los métodos de resolución de problemas combinatorios más adecuados en cada situación.
- Implementar los métodos de Backtracking, Branch & Bound y Greedy adaptados a cada problema en concreto y buscando su máxima eficiencia y eficacia.
- Diseñar e implementar la estructura de datos más adecuada para una determinada aplicación, dados unos requisitos de eficiencia temporal y espacial.
- Implementar grafos y aplicar algoritmos para resolver problemas como el camino mínimo.
- Implementar los árboles binarios y AVL. Implementar también los distintos recorridos posibles.
- Implementar tablas de hash.
1. Introducción a los grafos: Árboles, caminos y ciclos
2. Grafos Eulerianos y Hamiltonianos
3. Digrafos
4. Álgebra lineal de matrices de adyacencia e incidencia
5. Algoritmos de búsqueda y recorridos
6. Costes computacionales
Durante la asignatura, se usarán las siguientes metodologías, por bloque de contenidos:
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 y dos prácticas. También se realizan ejercicios de evaluación continua que pueden mejorar la nota del bloque.
El segundo bloque se evalúa mediante un proyecto en grupo y un examen individual.
Aunque la asignatura sea semestral, esta se estructura en dos bloques que requieren ser aprobados con una nota igual o superior a 5. Si no se aprueban ambos bloques, la asignatura queda suspendida con una nota máxima de 4.
Nota_Final = 0.5 · Nota_B1 + 0.5 · Nota_B2
Bloque 1 - Programación Avanzada:
La nota del primer bloque se calcula a partir de la ponderación de las notas de conocimientos y prácticas.
Nota_B1 = 0.4 · Nota_Conocimientos_B1 + 0.6 · Nota_Practicas_B1
Es necesario obtener una calificación de 5 o superior en cada una de las partes para aprobar el bloque. Si no, la nota del bloque será de un máximo de 4.
Conocimientos
Para calcular esta nota se pondera la nota del examen de punto de control con la nota de evaluación continua,
únicamente en caso de beneficiar al/la estudiante y siempre que la nota del examen sea superior o igual a 5.
Nota_Conocimientos_B1 = max( 0.4 · Nota_AC_B1 + 0.6 · Nota_Examen_B1,Nota_Examen_B1 )
En caso de suspender la parte de conocimientos del primer semestre, se realizará un examen de recuperación en la
convocatoria extraordinaria de julio, siendo 5 el mínimo para aprobar. La nota de evaluación continua no aplicará.
Prácticas
La nota de prácticas del primer bloque se calcula ponderando las notas de las dos prácticas que se realizan, teniendo
que aprobar ambas por separado, con una nota igual o superior a 5. En caso contrario, la nota de prácticas será como
mucho de 4.
Nota_Prácticas_B1 = 0.5 · Nota_Práctica_1 + 0.5 · Nota_Práctica_2
Bloc 2 - Estructura de Datos:
El segundo bloque se basa en la metodología Project-Based Learning (PBL), por lo que solo habrá una práctica y un examen final. Es necesario aprobar ambos elementos por separado con una nota igual o superior a 5. En caso contrario, la nota del segundo bloque será como mucho de 4.
Nota_B2 = 0.4 · Nota_Examen_B2 + 0.6 · Nota_Práctica_3
Resumen y recuperaciones:
En resumen, la nota de la asignatura la determinan principalmente 5 actividades de evaluación, cada una con las siguientes ponderaciones:
Práctica 1: 15%
Práctica 2: 15%
Práctica 3: 30%
Examen Bloc 1: 20% (punto de control, si se aprueba en convocatoria ordinaria la nota puede mejorarse por AC)
Examen Bloc 2: 20% (final)
Cada una de estas actividades podrá ser recuperada en convocatoria extraordinaria de julio según las fechas que aparecen en el plan docente de la asignatura o el calendario correspondiente.
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.