Diferencia entre revisiones de «Final del 19/02/15 (Algoritmos III)»

De Cuba-Wiki
mSin resumen de edición
Sin resumen de edición
 
Línea 41: Línea 41:


== Ejercicio 2 ==
== Ejercicio 2 ==
''G=''(''V,X'') es Hamiltoniano entonces para todo <math>S \in V, S \neq \empty</math>  
''G=''(''V,X'') es Hamiltoniano entonces para todo <math>S \in V, S \neq \emptyset</math>  


<math> W(G-S) \leq |S|</math> (''W''(''G'') es la cantidad de componentes conexas de ''G'')
<math>W(G-S) \leq |S|</math> (''W''(''G'') es la cantidad de componentes conexas de ''G'')


a) Dar un ejemplo de que el teorema no es una condición suficiente para asegurar que el grafo es hamiltoniano.
a) Dar un ejemplo de que el teorema no es una condición suficiente para asegurar que el grafo es hamiltoniano.

Revisión actual - 15:07 4 ago 2017

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

Preguntas sobre complejidad

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).

Luego pregunto sobre los ejercicios estos que eran de un final del 2010

Ejercicio Complejidad Oral

a) ¿Qué se puede decir de sabiendo que existe una reducción polinomial de a y que ?

b) ¿Qué se puede decir de sabiendo que existe una reducción polinomial de a Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Pi_2} y que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Pi_2 \in NP}  ?

c) ¿Qué se puede decir de Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Pi_1} sabiendo que existe una reducción polinomial de Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Pi_1} a Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Pi_2} y que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Pi_2 \in NP-Completo }  ?

d) ¿Qué se puede decir de Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Pi_2} sabiendo que existe una reducción polinomial de Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Pi_1} a Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Pi_2} y que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Pi_1 \in NP-Completo}  ?

e) ¿Qué se puede decir de Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Pi_2} sabiendo que existe una reducción polinomial de Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Pi_1} a Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Pi_2} y que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Pi_1 \in NP-Completo} y Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Pi_2 \in NP} ?

Preguntas sobre flujo

Qué es un flujo válido y decir cuál es el valor del flujo en una red que tenía dibujada con un flujo. Dar una iteración de la red residual de Ford Fulkerson (tenía dibujada una red con un flujo y había que armar la red residual, te hace un camino de aumento ahí y hay que mostrar entonces como se mejora el flujo en la red). A qué clase de complejidad pertenece. (P)

Circuitos Hamiltonianos

Qué tipo de problemas son. (NP)

Matching Maximo

Qué tipo de problemas son. (P) Porque se sabe que es P . Teorema Matching Maximo <=> no hay camino en aumento.

Ejercicio 1

a) Si el camino entre i y j tiene más de un camino mínimo ¿Cual elige Floyd?.

b) Adaptarlo para que calcule los caminos mas cortos tal que no pasen por un conjunto de nodos dado.

Ejercicio 2

G=(V,X) es Hamiltoniano entonces para todo Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle S \in V, S \neq \emptyset}

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle W(G-S) \leq |S|} (W(G) es la cantidad de componentes conexas de G)

a) Dar un ejemplo de que el teorema no es una condición suficiente para asegurar que el grafo es hamiltoniano.

b) Mostrar, usando el teorema, que el grafo de la figura no es hamiltoniano.


Archivo:Grafo.png
Grafo ej. 2