La asignatura tiene como objetivo ofrecer una visión avanzada de la programación de algoritmos. El estudio de la eficiencia de los algoritmos y diversas técnicas de diseño se trabajan en profundidad con el objetivo de resolver problemas de forma eficiente y elegante.
Es importante dominar el análisis descendiente, la modularidad, la gestión de la memoria, las estructuras de datos lineales, el lenguaje C, y otros contenidos trabajados en la asignatura de "Metodología y tecnología de la programación".
Adquiriendo los conocimientos de la asignatura, el estudiantado desarrolla habilidades para proponer y discutir la adecuación de soluciones a problemas complejos.
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. (Recomendable C/Java).
Capacidad para seguir y proponer razonamientos matemáticos.
Los Resultados de Aprendizaje de esta asignatura son:
- Definir programas informáticos interactivos a partir de diseños lógicos y estructurados.
- Desarrollar programario software de manera estructurada y eficiente con el propósito de crear un proyecto interactivo.
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.
- 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.
Los contenidos generales de la asignatura son los siguientes:
1. Especificación de algoritmos
2. Eficiencia de algoritmos
3. Diseño recursivo
4. Programación dinámica
5. Teoría de la complejidad computacional
6. Problemas combinatorios
Durante la asignatura, se usarán las siguientes metodologías, por 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.
La asignatura se evalúa mediante un examen y dos prácticas. 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.
La nota de la asignatura se calcula a partir de la ponderación de las notas de conocimientos y prácticas.
Nota_Final = 0.5 · Nota_Conocimientos + 0.5 · Nota_Prácticas
Es necesario aprobar ambas partes (con un 5) para aprobar la asignatura. De lo contrario, la nota final no superará el 4.
Conocimientos
Para calcular esta nota se pondera la nota del examen final 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 = max( 0.4 · Nota_EC + 0.6 · Nota_Examen,Nota_Examen )
Uno de los ejercicios de evaluación continua se entregará la semana del punto de control, substituyendo dicho examen.
En caso de suspender la parte de conocimientos, 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á en este caso.
Prácticas
La nota de prácticas 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 = 0.4 · Nota_Práctica_1 + 0.6 · Nota_Práctica_2
Entrevista de convalidación del examen semestral
En caso de que un/a estudiante cumpla los requisitos especificados a continuación, puede optar a convalidar el examen final de la asignatura. Para ello, el/la estudiante debe:
- Aprobar todas las ECs, obteniendo una media ponderada superior o igual a 7.
- Aprobar la Práctica 1 y presentar la Práctica 2, ambas en la primera convocatoria (sobre 10).
- Asistir de forma continuada a clase.
Los contenidos de la entrevista de convalidación, así como la forma de solicitarla, se comunicarán cuando se acerque el final del primer semestre.
El equipo de la asignatura propondrá una nota de convalidación a partir del resultado de la entrevista y las notas de EC. El/la estudiante es libre de renunciar a la convalidación, escogiendo entonces realizar el examen final.
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.