# Final 2021.08.11

* Enunciado: https://www.cubawiki.com.ar/images/4/4b/Final_del_11-08-21_(Algoritmos_III).pdf

###### tags: `Finales`

## Resumen

### Glosario/definiciones

* TSP: https://en.wikipedia.org/wiki/Travelling_salesman_problem NPC

### Trucos

* Para demostrar/refutar las implicaciones, intentar el contrarrecíproco: $p => q <=> ¬q => ¬p$

### Errores comunes

* No saber la complejidad de problemas conocidos (por ejemplo, TSP)

## Resolución

### 1: Sea $M ∈ N^{m×n}$ una matriz de números naturales. Se desea obtener un camino que empiece en la casilla superior izquierda ($[1, 1]$), termine en la casilla inferior derecha ($[m, n]$), y tal que minimice la suma de los valores de las casillas por las que pasa. En cada casilla $[i, j]$ hay dos movimientos posibles: ir hacia abajo (a la casilla $[i + 1, j]$), o ir hacia la derecha (a la casilla $[i, j + 1]$).

#### a) Función

$F(i, j) =$
\begin{cases}
M_{m,n} & \text{si $(i,j) = (m, n)$} \\
M_{i, j} + min(F(i, j+1), F(i+1, j))& \text{si $i < m ∧ j < n$} \\
M_{i, j} + F(i+1, j)& \text{si $i < m ∧ j = n$} \\
M_{i, j} + F(i, j+1)& \text{si $i = m ∧ j < n$}
\end{cases}

Empezamos desde F(0,0), la primer posición del tablero.

En el caso general, sumamos el valor de la posición actual y tomamos el mínimo entre los dos subcaminos posibles: si bajamos o si vamos a la derecha.

Cuando estamos en los bordes, hay solo una dirección posible por la que podemos continuar, por lo que el llamado recursivo en este caso es uno solo.

Terminamos al llegar a la posición objetivo (m, n), devolviendo el valor de esta posición (caso base).

#### b) Algoritmo

Memo = [M][N]

def f(i, j):

    if Memo[i][j] != UNDEFINED
        return Memo[i][j]

    if (i, j) == (m, n):
        Memo[i][j] = M[m][n]
    
    if i < m and j < n:
        Memo[i][j] = M[i][j] + min(f(i, j+1), f(i+1, j))
    
    if i < m and j == n:
        Memo[i][j] = M[i][j] + f(i+1, j)
    
    if i == m and j < n:
        Memo[i][j] = M[i][j] + f(i, j+1)
    
    return Memo[i][j]

def reconstruir_camino():
    i, j = 0, 0
    camino = [(i, j)]
    
    while ((i, j) != (m, n)):
        valor_derecha = inf if (j+1 == n) else Memo[i][j+1]
        valor_abajo   = inf if (i+1 == m) else Memo[i+1][j]
        
        if (valor_derecha < valor_abajo):
            j = j+1
        else:
            i = i+1
        camino.append((i, j))

    return camino

f(0, 0)
return reconstruir_camino()

#### c) Complejidad

$O(mn)$ estados posibles
cada uno calculado en $O(1)$
$\text{reconstruir_camino}$ cuesta $O(m+n)$
costo total: $O(m.n)+O(m+n) = O(m.n)$

### 2: Sea $G$ un grafo conexo con pesos asociados a sus aristas. Sean $v$ y $w$ dos vértices distintos de $G$. Decimos que un camino entre $v$ y $w$ es min-max si minimiza el peso de la arista mas pesada del camino (sobre el conjunto de todos los caminos entre v y w que haya en G). Sea $T$ un árbol generador mínimo de $G$, y sea $P$ el unico camino entre $v$ y $w$ que hay en $T$. Demostrar que $P$ es un camino min-max entre $v$ y $w$. Es decir, demostrar que para todo camino $P′$ entre $v$ y $w$ que haya en $G$, el peso de la arista más pesada de $P$ es menor o igual que el peso de la arista mas pesada de $P′$.

#### Telegram

> Sean u, v arbitrarios. Tomá un camino entre u y v en T. Sacale su arista mas pesada e. Ahora tenés dos componentes conexas, A y B. Agarra en G cualquier camino minimax P entre u y v, y asumi que su arista mas pesada es menos pesada que e. Hay una arista e' de P que cruza de A a B. Agrega e', conectando A y B. Esto te da un AGM de menor peso. Absurdo. Luego no existe tal camino P con tal arista e'.

> e es la arista de mayor peso en el único camino en T entre u y v. Llamá si querés Q a ese camino. Si llamamos w(P) al mayor peso entre todas las aristas de P, w(P) >= w(e') porque e' es una arista en P, y como asumimos que w(e) > w(P), sabemos w(e) > w(e'), y al usar e' para conectar A y B, que eran las componentes conexas en las que partimos a T cuando le sacamos e, nos queda un AGM con peso w(T) - w(e) + w(e') < w(T), lo cual no puede pasar. Luego lo que asumimos, w(e) > w(P), es falso. Luego para todo camino P entre u y v en G, w(P) >= w(e) = w(Q), que es lo que queríamos demostrar. Estaba en el celu, disculpá los typos.

> [name=Lebron] [time=Sun, Feb 18, 2022 11:36 PM] [Fuente](https://t.me/c/1461330951/4180)

### 3: Dada una red N = (V, E), con funcion de capacidad c: E → Z≥0, fuente s y sumidero t. Decidir si cada una de las siguientes afirmaciones es Verdadera o Falsa. Justificar.

Recordar que un arco e est ́a saturado por el flujo f si f (e) = c(e).

a) Para cualquier flujo m ́aximo entero f y arco e no saturado por f , si se incrementa c(e) en
uno, el valor del flujo m ́aximo de N se incrementa.

b) Para cualquier flujo m ́aximo entero f y arco e no saturado por f , si se incrementa c(e) en
uno, el valor del flujo m ́aximo de N nunca se incrementa.

c) Para cualquier flujo m ́aximo entero f y arco e saturado por f , si se incrementa c(e) en uno,
el valor del flujo m ́aximo de N se incrementa.

d) Para cualquier camino P desde s a t en N , si la capacidad de cada arco en P se incrementa
en uno, entonces el valor de flujo m ́aximo de N aumenta.

e) Para cualquier camino P desde s a t en N , si la capacidad de cada arco en P se incrementa
en uno, entonces el valor de flujo m ́aximo de N aumenta como m ́aximo en uno.

### 4: Justificar todas las respuestas.

#### (a) Dado un problema de decisión $Π$, si mostramos una reduccion polinomial de $Π$ a $TSP$ y otra de $TSP$ a $Π$, decidir si cada una de las siguientes sentencias se desprenden de estos hechos:

##### i. $Π$ es NP-difícil pero no NP-completo.

Falso.

Como podemos reducir $Π$ a TSP, sabemos que TSP es igual o más difícil que $Π$. Y como también sabemos que TSP se puede reducir a $Π$, entonces $Π$ es igual o más difícil que TSP. Por ende, $Π$ tiene que ser igual de difícil que TSP, el cual sabemos que pertenece a NPC

##### ii. $Π$ es NP pero no NP-completo.

Falso: es NP (certificado trivial usando la transformación y que TSP es NP) y también NPC (porque es NP-hard por poder reducirse TSP a él y TSP ser NPC).

##### iii. $Π$ es NP-completo.

Verdadero: TSP es NP-completo. Al poder reducirse el uno al otro, sabemos que son igual de difíciles.

##### iv. $Π$ no es NP-difícil ni NP-completo.

Falso: Ver punto anterior (NPC implica NP-difícil).

##### v. $Π$ esta en P.

Falso: P no está en NPC.

#### (b) Decidir si cada una de las siguientes sentencias es verdadera o falsa:

##### i. Un problema $Π ∈ NP$ es NP-completo si puede ser reducido a $SAT$ en tiempo polinomial.

Falso.

Para ser NPC, tiene que ser NP y NP-hard. Que $Π$ pueda ser reducido a SAT no implica que $Π$ pertenezca a NP-hard.

Si la reducción fuera al revés, de SAT a $Π$, podríamos afirmar que pertenece a NPC por el teorema de Cook-Levin.

##### ii. Un problema $Π ∈ NP$ es NP-completo si $SAT$ puede ser reducido a ́el en tiempo polinomial.

Verdadero: Ver inciso anterior.

##### iii. Si $NP = coNP$ entonces $P = NP$.

Falso: que todo problema cuyas instancias positivas puedan ser certificadas polinomialmente, cumpla que sus instancias negativas también puedan serlo y viceversa, no implica que existan algoritmos polinomiales para resolverlos.

##### iv. Si $NP ≠ coNP$ entonces $P ≠ NP$.

Afirmación equivalente a su contrarrecíproca: $P = NP => NP = coNP$

Verdadero: Si $P = NP$, significa que para todo problema $NP$ existe un algoritmo polinomial que lo resuelve. De esta forma, podemos certificar instancias (tanto negativas como positivas) en tiempo polinomial usando el certificado trivial (la instancia) y el algoritmo polinomial que lo resuelve como verificador.