Final del 14/09/22 (AED3)

El final fue escrito; eran 3hs para resolverlo pero se podía estirar. Había que resolver las siguientes secciones:

Desarrollar una explicación del problema AGM que contenga los siguientes puntos:

• Definir el problema de AGM(qué datos toma y qué resultados se esperan).

• Explicar Prim, dar su pseudocódigo y demostrar que es correcto y dar su complejidad.

• Explicar cómo se compara con Kruskal, dar el pseudocódigo.

• Mencionar un ejemplo práctico de un problema que se resuelva con AGM.

Desarrollar una explicación del algoritmo de cancelación de ciclos que contenga los siguientes puntos:

• Definir el problema de Camino de costo mínimo (que datos toma y que resultados se esperan).

• Definir qué es una red residual.

• Dar el pseudocódigo.

• Demostrar que el algoritmo es correcto y dar su complejidad.

Desarrollar una introducción a la teoría de NP-completitud, que contenga los siguientes puntos:

• Explicar las versiones de problema de localización, optimización, decisión y evaluación.

• definir las clases de problemas p, np, np-completo para problemas de decisión.

• mostrar una reducción de un problema np-completo a otro np-completo.

• Explicar qué implica en la práctica que un problema de decisión sea np-completo.