Análisis y diseño
de algoritmos

Algorítmica
Algorithmics

• Presentación de la asignatura: 2025, 2024

• Introducción al análisis y diseño de algoritmos

Caso práctico

• Big Data

Problema

• Asignaciones estables

Análisis de la eficiencia

• La eficiencia de los algoritmos

• La eficiencia de los algoritmos paralelos 

Ejercicios y problemas

• Relación de ejercicios 

• Ejercicio resuelto: Bucles anidados

• Ejercicio resuelto: Recurrencia "divide y vencerás"

Divide y vencerás

• Algoritmos "divide y vencerás"

Algoritmos de ordenación

• Algoritmos de ordenación

• Implementación en Java de algoritmos de ordenación

• Implementación en Python de algoritmos de ordenación

• Algoritmos paralelos de ordenación

Caso práctico

• Optimización de carteras de inversión con HRP [Hierarchical Risk Parity]

Ejercicios y problemas

• Relación de ejercicios y problemas

• Problema resuelto: Par más cercano.

• Problema resuelto: Comparación de preferencias.

Algoritmos greedy

• Algoritmos greedy

• Algoritmos greedy sobre grafos

Caso práctico

• Inversión basada en momentos

Ejercicios y problemas

• Relación de ejercicios y problemas

Exploración de grafos

• Recorridos sobre grafos

• Resolución en Java de problemas de recorridos sobre grafos (solución orientada a objetos usando el patrón de diseño "visitante" [visitor], que permite separar el problema concreto que se resuelve del recorrido del grafo), p.ej. componentes conexas u ordenación topológica de un grafo.

• Backtracking (vuelta atrás)

• Resolución de sudokus en Java usando backtracking

• Branch & Bound (ramificación y poda)

• Árboles de juegos

Caso práctico

• Estudios de eventos

Ejercicios y problemas

• Relación de ejercicios y problemas

• Resolución en Python de problemas de branch & bound

Programación dinámica

• Programación dinámica

• Implementación en Java de algoritmos de caminos mínimos

Aplicaciones

• Alineación de secuencias

• Implementación en Java de algoritmos de alineación de secuencias

• Extra: Otras aplicaciones de la programación dinámica

• Extra: Curva braquistócrona en Python (cuaderno Jupyter, ejecutable con Google Colab)

Caso práctico

• Entrenamiento de redes neuronales [deep learning]

Ejercicios y problemas

• Relación de ejercicios y problemas

• Problema resuelto: Arbitraje en el mercado de divisas

• Implementación en Java: Ciclos negativos y arbitraje de divisas

Exámenes

• Ejercicios y problemas de exámenes de años anteriores

Apéndice: Computabilidad & Complejidad Computacional

Ejercicios y problemas

• El problema de la parada

• Máquinas de Turing

• Reducciones

• Problemas NP-completos

• Clases de complejidad