Teoría de Algoritmos - Curso Buchwald

Cursada el segundo cuatrimestre de 2025. Pagina de la cátedra.

Temario

• Inducción matemática
• División y Conquista (avanzada)
• Algoritmos Greedy
• Búsqueda exhaustiva
• Backtracking
• Programación Dinámica
• Programación Lineal
• Redes de Flujo
  • Ford–Fulkerson
  • Edmonds–Karp
• Reducciones y Clases de Complejidad
  • P
  • NP
  • NP-completo
  • NP-difícil
  • P vs NP
  • PSPACE
• Aproximaciones y Algoritmos Randomizados
  • Heurísticas
  • Análisis de complejidad
  • Estructuras aleatorizadas
• Gramáticas y Lenguajes Formales
  • Clasificación de Chomsky
  • Correspondencia gramática–lenguaje
• Autómatas
  • Determinísticos
  • No determinísticos
  • Correspondencia lenguaje–autómata
• Máquinas de Turing
  • Computabilidad
  • Problemas decidibles
  • Problemas indecidibles

Trabajo Práctico 1

• Modelado de un problema de planificación y optimización.
• Algoritmos Greedy (diseño y criterio de selección).
• Demostración de optimalidad del algoritmo.
• Análisis de complejidad temporal.
• Casos de prueba y validación experimental.
• Medición de tiempos y verificación empírica con gráficos.

Trabajo Práctico 2

• Modelado de un problema de optimización secuencial con decisiones en el tiempo.
• Programación Dinámica para maximización de resultados.
• Definición de estados, subproblemas y ecuación de recurrencia.
• Construcción de la solución óptima y reconstrucción de decisiones.
• Análisis de complejidad temporal y espacial.
• Análisis de correctitud y optimalidad del enfoque dinámico.
• Casos de prueba y validación de optimalidad.
• Medición de tiempos y verificación empírica con gráficos.

Trabajo Práctico 3

• Modelado de un problema de partición en k grupos con función objetivo cuadrática.
• Formulación en versión de decisión y de optimización.
• Pertenencia a NP y demostración de NP-completo mediante reducción.
• Diseño de algoritmo exacto por Backtracking.
• Estrategias de poda y verificación de correctitud.
• Modelado mediante Programación Lineal Entera (formulación exacta y variante aproximada).
• Algoritmos de aproximación y heurísticas greedy de balanceo de cargas.
• Análisis de calidad de aproximación (relación entre solución aproximada y óptima).
• Comparación empírica entre métodos exactos y aproximados.
• Medición de tiempos y análisis de escalabilidad.