# Final 2022.02.17
###### tags: `Finales`

## Resumen

### Glosario/definiciones

### Trucos

### Errores comunes

## Resolución

### 1. (2.5 puntos) Sea $v = (v_1, v_2, ...,v_n)$ un vector de números enteros. Se quiere saber la mínima cantidad de números que hay que eliminar del vector para que cada número que permanezca sea múltiplo del anterior (excepto el primero). Por ejemplo, para los vectores $(-5, 5, 0), (0, 5, -5)$ y $(0, 5, -5, 2, 15, 15)$, los resultados deben ser respectivamente 0, 1 y 2.

> Tenian que mantener el orden relativo
> [name=Guido Rodriguez Celma]

#### a) Dar una función recursiva para calcular este valor. Justificar su correctitud. Ayuda: Dado un vector $v$ de números enteros y $k$ un número entero, considerar la función $f(v, k)$ que indica la mínima cantidad de números que hay que eliminar del vector $v$ para que cada número que permanezca sea múltiplo del anterior (excepto el primero), y además que $k$ sea múltiplo del último elemento que permanezca. Recordar que $0$ es múltiplo de todo entero.

$A = \{a_1, ..., a_n\}$

$min\_cant(A) = F(A, 0, 0)$

$F(A, i, j) =$
\begin{cases}
0 && \text{ si $i = |A|$} \\
\min(\\
& F(A, i + 1, j + 1) + 1, \\
& F(A, i + 1, j) \\
) && \text{ si $i = j$} \\
\min(\\
& F(A, i + 1, j) + 1, \\
& F(A, i + 1, i) \\
) && \text{si } A_i \mod A_j = 0 ∧ i ≠ j \\
F(A, i+1, j) + 1 && \text{si } A_i \mod A_j ≠ 0
\end{cases}

Funciona porque recorremos el arreglo desde el inicio hasta el final. En cada elemento, si es multiplo del anterior, me fijo si lo remuevo o no. Si no es múltiplo, solo puedo removerlo.

De esta forma tenemos en cuenta todas las maneras posibles de quedarse con un arreglo de múltiplos y nos quedamos con la mínima.

El caso del primer elemento se considera aparte. A este siempre lo vamos a poder incluir si queremos. También lo podemos remover, en cuyo caso el "primer elemento" de la secuencia pasaría a ser el siguiente elemento a su derecha.

Vamos sumando $1$ a la llamada recursiva cuando quitamos elementos y al terminar de recorrer sumamos 0, que no cambia el resultado por ser el elemento neutro de la suma.

#### b) Escribir un algoritmo de programación dinámica para resolver el problema.

# ejemplos del enunciado
A = [-5, 5, 0] # tiene que dar 0
B = [0, 5, -5] # tiene que dar 1
C = [0, 5, -5, 2, 15, 15] # tiene que dar 2

# ejemplos nuestros
Y = [0, 0, 1, 1, 1] # tiene que dar 2
Z = [3, 9, 2, 4, 8, 16] # tiene que dar 2

UNDEFINED = 99999
M = [[UNDEFINED for i in range(len(Z))] for j in range(len(Z))]



def F(A, i, j):
    if (i == len(A)):
        return 0

    if (M[i][j] != UNDEFINED):
        return M[i][j]

    # print(f"i: {i}, A[i]: {A[i]}, j: {j}, A[j]: {A[j]}")
    # print(f"A[i] % A[j]: {A[i]} % {A[j]}")

    if (i == j): # en la "primera posición" siempre puedo elegir sacarlo o dejarlo
        M[i][j] = min(1 + F(A, i+1, j+1), 
                          F(A, i+1, j))

    elif (A[i] % A[j] != 0):

        # print(f"voy sacar el {A[i]} de la posición {i}")

        M[i][j] = 1 + F(A, i+1, j)


    elif (A[i] % A[j] == 0):

        rama_sacar = 1 + F(A, i+1, j)
        rama_dejar = F(A, i+1, i)
        rama_min = min(rama_sacar, rama_dejar)

        M[i][j] = rama_min

        # if (rama_min == rama_sacar):
        #    print(f"voy sacar el {A[i]} de la posición {i}")

    return M[i][j]

#print(F(A, 0, 0))
#print(F(B, 0, 0))
#print(F(C, 0, 0))

#print(F(Y, 0, 0))
print(F(Z, 0, 0))

#### c) Calcular su complejidad.

Como tenemos $O(|A|²)$ llamados posibles para la función $F$ y cada uno cuesta $O(1)$, la complejidad es $O(A²)$.

### 2. (2.5 puntos) Para cada una de las siguientes afirmaciones determinar si es verdadera o falsa. En caso de que sea verdadera, demostrarla. En caso de ser falsa mostrar un contraejemplo. Sea $e$ una arista de un grafo conexo $G$:

#### a) Entonces vale que $e$ esta en todo AGM si y solo si $e$ es de peso mínimo.

Falso porque puede haber un grafo en el que la arista de mayor peso sea una arista puente. Esta arista va a pertenecer a todo AGM y sin embargo, no es de peso mínimo.

Otro contraejemplo puede ser un K3 con todos los pesos iguales: tenemos 3 AGMs posibles según cuál arista saquemos, todas son la de mínimo peso y sin embargo ninguna está en todos los AGM.

#### b) Entonces vale que $e$ esta en todo AGM si y solo si $e$ no pertenece a ningún ciclo.

Contraejemplo:

graph K3{
    u -- v [label=" 1 "];
    v -- w [label=" 10 "];
    w -- u [label=" 10 "];
}

La arista $uv$ pertenece a un ciclo y pertenece a todo AGM del K3 dado.

#### c) Entonces vale que $e$ esta en todo AGM si y solo si $e$ pertenece a un único ciclo.

Contraejemplo:

graph K2{
    v -- w;
}

$vw$ está en todo AGM de $K2$, sin embargo no está en ningún ciclo de K2.

### 3. (2.5 puntos) Se desean evaluar $t$ proyectos para seleccionar los mejores. Para esta tarea, se dispone de un banco de $r$ revisores, cada uno de los cuales ha elegido hasta $20$ proyectos que estaría dispuesto a evaluar. Cada proyecto puede ser examinado por hasta $5$ revisores distintos, y cada revisor puedo examinar hasta $10$ proyectos distintos. Además, un revisor sólo puede evaluar proyectos que él haya indicado que estaría dispuesto a examinar.

> Variación 2020: El 3 era de coloreo. (puede ser que lo este recordando mal asi que ojo) Habia que probar que si un grafo G tiene un unico coloreo optimo entonces, si tomas dos colores arbitrarios y miras el subgrafo de G asociado a quedarte con estos colores entonces este subgrafo es conexo.
> [name=Matias G P]

#### a) Proponer un modelo de flujo que permita determinar la máxima cantidad total de opiniones que es posible obtener por parte de los revisores. La entrada del problema es la cantidad $t$ de proyectos, la cantidad $r$ de revisores, y para cada revisor los proyectos que estaría dispuesto a examinar.


#### b) Dar una interpretación a cada unidad de flujo y cada restricción de capacidad.

* 1 unidad de flujo: 1 proyecto revisado por un revisor

* las restricciones de capacidad son las mencionadas en el enunciado

#### c) Indicar cómo se interpreta el flujo máximo del modelo.

El flujo máximo del modelo se interpreta como la máxima cantidad total de opiniones que es posible obtener por parte de los revisores.

#### d) Determinar la complejidad de resolver el modelo resultante con el algoritmo de Edmonds y Karp.

$O(m²n) = O((r + 20r + t)²(1 + r + t + 1)) =$
$= O((21r+t)²(r+t)) = O( (21²r² + 2*21rt + t²) (r+t) ) = O(r³ + t³)$

### 4. (2.5 puntos) Recordar que una clique de un grafo $G$ es un subgrafo completo maximal. Considerar los siguientes dos problemas de decisión:

#### a) Dado un grafo $G = (V, E)$ con $|V|$ par, ¿$G$ tiene una clique de al menos $|V|/2$ vértices?

#### b) Dado un grafo $G = (V, E)$, ¿$G$ tiene una clique con al menos $|V| - 3$ vértices?

¿A qué clase de complejidad pertenece cada uno de estos problemas? Justificar la respuesta (describiendo un algoritmo polinomial para el caso de que que el problema esté en P, y demostrándolo para el caso que el problema esté en NP-completo)

> Podían usar que Clique es NP-C
> [name=Guido Rodriguez Celma]

Para demostrar que están en NPC podemos usar el teorema de Cook-Levin. Entonces, tengo que probar que están NP y que un problema NPC conocido se puede reducir a ellos.

Veamos primero que están en NP:

* Podemos tomar como certificado el conjunto de vértices de la clique
* El verificador:
* Verifica que el tamaño del certificado sea el correcto
* Para cada para de vértices distintos del certificado, verifica que haya una arista en E(G) que los una

* Es fácil ver que esto se puede hacer en tiempo polinomial: El tamaño se verifica en $O(|V|)$ y lo segundo en $O(|V|² * |E|)$.

* $Clique ≤_p Π_a$