Final del 06/03/15 (Algoritmos III)

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

El final fue parte oral y parte ejercicios.

Parte Oral[editar]

Qué es NP. Qué significa que un problema sea NP. Qué es un problema P. Qué signifca que un problema sea NP-C, cómo se verifica esto. Ejemplos de problemas NP-C, también me empezó a nombrar problemas y preguntaba a qué clase pertenecían (por ejemplo coloreo de vertices, circuito euleriano, hamiltoniano, etc). Para que me sirve saber si un problema es NP. Que algoritmos de camino minimo existen y sus complejidades. Que es programación dinámica.

Ejercicio Escritos[editar]

Ejercicio 1[editar]

1) Sea (V, ) y (V, ) arboles, demostrar que para todo existe un tal que (V, - e + f) y (V, - f + e) son arboles

Ejercicio 2[editar]

Sean y dos matching maximales de G, demostrar que .

Ejercicio 3[editar]

no me acuerdo

Ejercicio 4[editar]

Dado que clique es np completo sobre un grafo G. si a G lo modificamos de las siguientes maneras, sigue siendo NP completo el problema de clique?

  • G es bipartito
  • G es planar
  • G es conexo