Diferencia entre revisiones de «Final del 06/03/15 (Algoritmos III)»

De Cuba-Wiki
(Página creada con «El final fue parte oral y parte ejercicios. == Parte Oral == Qué es NP. Qué significa que un problema sea NP. Qué es un problema P. Qué signifca que un problema sea...»)
 
mSin resumen de edición
 
(No se muestran 3 ediciones intermedias de otro usuario)
Línea 1: Línea 1:
{{Back|Algoritmos y Estructuras de Datos III}}
El final fue parte oral y parte ejercicios.
El final fue parte oral y parte ejercicios.


Línea 14: Línea 15:


== Ejercicio 1 ==
== Ejercicio 1 ==
1) Sea (V, <math>T_1</math>) y (V, <math>T_2</math>) arboles, demostrar que para todo <math> v \in T_1</math> existe un <math> f \in T_2</math> tal que (V, <math>T_1</math> - e + f) y (V, <math>T_2</math> - f + e) son arboles
1) Sea (V, <math>T_1</math>) y (V, <math>T_2</math>) arboles, demostrar que para todo <math> e \in T_1</math> existe un <math> f \in T_2</math> tal que (V, <math>T_1</math> - e + f) y (V, <math>T_2</math> - f + e) son arboles


== Ejercicio 2 ==
== Ejercicio 2 ==


no me acuerdo
Sean <math>M1</math> y <math>M2</math> dos matching maximales de G, demostrar que <math>|M1|\leq 2|M2|</math>.


== Ejercicio 3 ==
== Ejercicio 3 ==

Revisión actual - 23:51 27 jul 2015

Plantilla:Back El final fue parte oral y parte ejercicios.

Parte Oral

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

Ejercicio 1

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

Sean y dos matching maximales de G, demostrar que .

Ejercicio 3

no me acuerdo

Ejercicio 4

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
Obtenido de «https://www.cubawiki.com.ar/index.php?title=Final_del_06/03/15_(Algoritmos_III)&oldid=10016»