Edición de «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, evaluació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.