Diferencia entre revisiones de «Final del 14/09/22 (AED3)»
De Cuba-Wiki
Sin resumen de edición |
m (→Desarrollar una introducción a la teoría de NP-completitud, que contenga los siguientes puntos:) |
||
| (No se muestran 3 ediciones intermedias de 2 usuarios) | |||
| Línea 1: | Línea 1: | ||
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'''( | * 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 '''Prim''', dar su pseudocódigo y demostrar que es correcto y dar su complejidad. | ||
* Explicar | * Explicar cómo se compara con '''Kruskal''', dar el pseudocódigo. | ||
* 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'''. | ||
==== 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). | ||
* Definir | * Definir qué es una red residual. | ||
* Dar el pseudocódigo. | * Dar el pseudocódigo. | ||
| Línea 21: | Línea 21: | ||
* Demostrar que el algoritmo es correcto y dar su complejidad. | * 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, | * 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. | ||
| Línea 29: | Línea 29: | ||
* mostrar una reducción de un problema np-completo a otro np-completo. | * mostrar una reducción de un problema np-completo a otro np-completo. | ||
* Explicar | * Explicar qué implica en la práctica que un problema de decisión sea np-completo. | ||
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.
