Diferencia entre revisiones de «Final del 06/08/18 (Algoritmos III)»

De Cuba-Wiki
(Página creada con «Final escrito de Paula Zabala. = Enunciados = == Ejercicio 1 == Sea <math>G=(V,X)</math> un grafo. Probar que si <math>d(v) \geq d, \forall v \in V </math> para algún <m...»)
 
mSin resumen de edición
 
(No se muestra una edición intermedia del mismo usuario)
Línea 4: Línea 4:


== Ejercicio 1 ==
== Ejercicio 1 ==
Sea <math>G=(V,X)</math> un grafo. Probar que si <math>d(v) \geq d, \forall v \in V </math> para algún <math>d >0 \implies</math> existe un circuito simple de longitud al menos <math>d+1</math> en <math>G</math>.
Sea <math>G=(V,X)</math> un grafo. Probar que si <math>d(v) \geq d, \forall v \in V </math> para algún <math>d > 0 \implies</math> existe un circuito simple de longitud al menos <math>d+1</math> en <math>G</math>.


== Ejercicio 2 ==
== Ejercicio 2 ==
Dados <math>G=(V,X)</math> un digrafo con pesos en sus aristas, <math>s \in V</math> y <math>k</math> un entero positivo, se quiere hallar los <math>k</math> vértices más cercanos a <math>s</math> con un algoritmo cuya complejidad sea <math>O(nk)</math>.
Dados <math> G=(V,X)</math> un digrafo con pesos en sus aristas, <math>s \in V</math> y <math>k</math> un entero positivo, se quiere hallar los <math>k</math> vértices más cercanos a <math>s</math> con un algoritmo cuya complejidad sea <math>O(nk)</math>.


a) ¿Se puede modificar fácilmente el algoritmo de Dijkstra para resolver esto? En caso afirmativo, explicar cómo; en caso negativo, justificar por qué no.
a) ¿Se puede modificar fácilmente el algoritmo de Dijkstra para resolver esto? En caso afirmativo, explicar cómo; en caso negativo, justificar por qué no.

Revisión actual - 16:16 24 oct 2018

Final escrito de Paula Zabala.

Enunciados

Ejercicio 1

Sea 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 G=(V,X)} un grafo. Probar que si 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 d(v) \geq d, \forall v \in V } para algún 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 d > 0 \implies} existe un circuito simple de longitud al menos 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 d+1} en 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 G} .

Ejercicio 2

Dados 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 G=(V,X)} un digrafo con pesos en sus aristas, 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} 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 k} un entero positivo, se quiere hallar los 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 k} vértices más cercanos 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 s} con un algoritmo cuya complejidad sea 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 O(nk)} .

a) ¿Se puede modificar fácilmente el algoritmo de Dijkstra para resolver esto? En caso afirmativo, explicar cómo; en caso negativo, justificar por qué no.

b) ¿Se puede modificar fácilmente el algoritmo de Bellman-Ford para resolver esto? En caso afirmativo, explicar cómo; en caso negativo, justificar por qué no.

Ejercicio 3

Dado 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 G=(V,X)} un grafo con una función de peso definida sobre sus aristas, 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 l: X \rightarrow \Re } . Probar 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 \exists e \in X} tal 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 l(e) < l(e'), \forall e' \in X \backslash \{e\}} (es decir, hay una arista de peso menor estricto a todas las otras) 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 \implies e} pertenece a todo árbol generador mínimo 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 G} .

Ejercicio 4

Un grafo 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 G} es coloreable en forma única si todo coloreo con 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 \chi(G)} colores induce la misma partición de los vértices. Probar que si 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 G} es coloreable de forma única, entonces el subgrafo inducido por dos conjuntos cualesquiera de la partición inducida por los 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 \chi(G)} colores es un subgrafo conexo.

Ejercicio 5

Decidir si las siguientes afirmaciones son verdaderas o falsas. Justificar.

  • a) Si todos los arcos de una red tienen diferentes capacidades, la red tiene un único corte mínimo.
  • b) Si se multiplican las capacidades de todos los arcos por 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 \lambda > 0} , el o los cortes mínimos no cambian.
  • c) Si se multiplican las capacidades de todos los arcos por 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 \lambda > 0} , el valor del o de los cortes mínimos no cambia
  • d) Si se suma a las capacidades de todos los arcos 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 \lambda > 0} , el o los cortes mínimos no cambia.
  • e) Si se suma a las capacidades de todos los arcos 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 \lambda > 0} , el valor del o de los cortes mínimo no cambia.

Ejercicio 6

  • a) ¿Cuándo un problema pertenece a la clase P?
  • b) ¿Cuándo un problema pertenece a la clase NP?
  • c) ¿Cuándo un problema pertenece a la clase NP-C?
  • d) ¿Qué es una reducción polinomial de un problema de decisión 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 uno 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} ?
  • e) Demostrar que el problema de conjunto independiente máximo (en su versión de decisión) pertenece a la clase NP.
  • f) En la práctica, ¿cómo se demuestra que un problema pertenece a la clase NP-C? Justificar.
  • g) Enunciar 5 problemas estudiados en la materia que sean P y 5 que sean NP-C.

Notas

En el ejercicio 1, aclaró en el momento del examen que supongamos una cota 'conveniente' para 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 d} , para evitar contraejemplos raros (por ejemplo, en un grafo compuesto por dos 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 K_{2}} separados, todos los vértices tienen grado mayor o igual a 1, pero no hay circuitos de longitud 2) que arruinaran la demostración.