Diferencia entre revisiones de «Final del 14/09/22 (AED3)»

De Cuba-Wiki
Sin resumen de edición
 
Línea 23: Línea 23:
==== Desarrollar una introducción a la teoría de '''NP-completitud''', que contenga los siguientes puntos: ====
==== 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.
* 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.
* definir las clases de problemas p, np, np-completo para problemas de decisión.

Revisión actual - 03:00 6 ene 2023

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.