Diferencia entre revisiones de «Final del 11/06/19 (Algoritmos III)»
De Cuba-Wiki
(Página creada con «Final escrito: 1) Describir el problema de árbol generador mínimo y los algoritmos que lo resuelven. Demostrar correctitud de alguno de ellos. 2) Definir los problemas d…») |
Sin resumen de edición |
||
| Línea 2: | Línea 2: | ||
1) Describir el problema de árbol generador mínimo y los algoritmos que lo resuelven. Demostrar correctitud de alguno de ellos. | 1) Describir el problema de árbol generador mínimo y los algoritmos que lo resuelven. Demostrar correctitud de alguno de ellos. | ||
2) Definir los problemas de recubrimiento por vértices y aristas y enunciar y demostrar las diferentes relaciones con matching máximo y conjunto independiente. Decir a qué clase de complejidad computacional (P o NP-completo) pertenece cada uno de ellos. | 2) Definir los problemas de recubrimiento por vértices y aristas y enunciar y demostrar las diferentes relaciones con matching máximo y conjunto independiente. Decir a qué clase de complejidad computacional (P o NP-completo) pertenece cada uno de ellos. | ||
Revisión actual - 00:16 15 sep 2019
Final escrito:
1) Describir el problema de árbol generador mínimo y los algoritmos que lo resuelven. Demostrar correctitud de alguno de ellos.
2) Definir los problemas de recubrimiento por vértices y aristas y enunciar y demostrar las diferentes relaciones con matching máximo y conjunto independiente. Decir a qué clase de complejidad computacional (P o NP-completo) pertenece cada uno de ellos.
