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

De Cuba-Wiki
Sin resumen de edición
Sin resumen de edición
Línea 1: Línea 1:
Fue escrito, teníamos 3hs pero se podía estirar.
Fue escrito, teníamos 3hs pero se podía estirar.


El primer punto era de '''AGM''':
Desarrollar una explicación del problema '''AGM''' que contenga los siguientes puntos:


* Definir el problema de '''AGM'''(que datos toma y que resultados se esperan).
* Definir el problema de '''AGM'''(que datos toma y que resultados se esperan).
Línea 11: Línea 11:
* Mencionar un ejemplo práctico de un problema que se resuelva con '''AGM'''.
* Mencionar un ejemplo práctico de un problema que se resuelva con '''AGM'''.


El segundo punto era de algoritmo de '''cancelación de ciclos''':
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 el problema de '''Camino de costo mínimo''' (que datos toma y que resultados se esperan).

Revisión del 19:46 15 sep 2022

Fue escrito, teníamos 3hs pero se podía estirar.

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

  • Definir el problema de AGM(que datos toma y que resultados se esperan).
  • Explicar Prim dar su pseudocódigo y demostrar que es correcto y dar su complejidad.
  • Explicar como 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 que 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 que implica en la práctica que un problema de decisión sea np-completo.