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 3: | Línea 3: | ||
El primer punto era de '''AGM''': | El primer punto era de '''AGM''': | ||
* 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'''. | |||
El segundo punto era de algoritmo de '''cancelación de ciclos''': | El segundo punto era de algoritmo de '''cancelación de ciclos''': | ||
* 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: | 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. | |||
Revisión del 19:45 15 sep 2022
Fue escrito, teníamos 3hs pero se podía estirar.
El primer punto era de AGM:
- 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.
El segundo punto era de algoritmo de cancelación de ciclos:
- 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.
