# Final 2021.09.16
###### tags: `Finales`

* Resolución de Lebron: https://t.me/c/1461330951/3408

## Resumen

### Glosario/definiciones

### Trucos

* En dinámica muy probablemente necesites 2 índices (y te queda una matriz)

## Resolución

### 1)



S = [0, 15, 40, 50, 60]
# S = [0, 25, 30, 55, 70]

M = [["UNDEFINED" for _ in range(len(S))] for i in range(len(S))]


def f(pos_actual, pos_anterior):
    print(f"anterior: {S[pos_anterior]}, actual: {S[pos_actual]},")

    if M[pos_actual][pos_anterior] != "UNDEFINED":
        return M[pos_actual][pos_anterior]

    if pos_actual == len(S) - 1:
        M[pos_actual][pos_anterior] = cumplen_la_condicion(pos_actual, pos_anterior)

    if pos_actual >= 1 and cumplen_la_condicion(pos_actual, pos_anterior):
        M[pos_actual][pos_anterior] = f(pos_actual + 1, pos_actual) or f(pos_actual + 1, pos_anterior)

    if pos_actual >= 1 and not cumplen_la_condicion(pos_actual, pos_anterior):
        M[pos_actual][pos_anterior] = f(pos_actual + 1, pos_anterior)

    return M[pos_actual][pos_anterior]

def cumplen_la_condicion(pos_actual, pos_anterior):
    return 15 <= S[pos_actual] - S[pos_anterior] <= 25

print(f(1, 0))

# imprimo la matriz
for i in M:
  for j in i:
    print(j, end=' ')
  print()

El algoritmo evalua todos los subconjuntos posibles y devuelve verdadero si y solo sí hay uno que cumple la condición.

La implementación usa 2 índices para recorrer el conjunto de números. En uno tenemos la posición actual y en otro la anterior.

La misma empieza en las posiciones 0 y 1. Se fija si los elementos en esas ubicaciones cumplen con la condición.

* Si no la cumplen, sabe que el elemento actual debe ser removido para llegar a una solución válida. Se continúa la recursión quitando al actual.

* Si cumplen la condición, se debe chequear los 2 casos posibles:
* Continuar manteniendo al elemento actual
* Continuar quitando al elemento actual

Cuando se llega a las últimas 2 posiciones, se chequea si estos elementos cumplen la condición. El resultado da True si estos también la cumplen. De lo contrario, el resultado será False.

Complejidad: $O(|S|²)$

Tenemos |S|² estados posibles, y cada estado se calcula 1 vez en $O(1)$. Ya que la siguiente vez que se necesite, se utilizará el resultado memoizado.

### 2)

INFINITO = float('inf')

V = {'A', 'B', 'C', 'D', 'E', 'F'}
E = {(('A', 'D'), 2), (('A', 'B'), 3), (('A', 'C'), 1), (('D', 'E'), 1), (('C', 'E'), 2), (('C', 'F'), 2)}

def dame_w_distancia_minima(S, π):
    π_ordenado = dict(sorted(π.items(), key=lambda item: item[1]))
    for w in π_ordenado:
        if w not in S:
            return w

def vecinos_sin_camino_minimo_calculado(w, S):
    result = set()
    for e in E:
        if e[0][0] == w and e[0][1] not in S:
            result.add(e[0][1])
        if e[0][1] == w and e[0][0] not in S:
            result.add(e[0][0])
    return result

def distancia(v, w):
    for e in E:
        if e[0] == (v, w) or e[0] == (w, v):
            return e[1]

    # no hace falta pero por las dudas
    print('warning: devolviendo distancia de no adyacentes')
    return INFINITO


def hay_eje_entre(v, w):
    for e in E:
        if e[0] == (v, w) or e[0] == (w, v):
            return True

    return False

print(dijkstra('A'))

#### (a) Explique cómo modificar el algoritmo de Dijkstra para contar el numero de diferentes caminos mínimos de $v$ a $w$

def dijkstra(origen):
    S = set()
    π = {}
    pred = {}
    cant = {}

    for v in V:
        π[v] = INFINITO
        pred[v] = INFINITO
        cant[v] = 1

    π[origen] = 0
    pred[origen] = 0

    while S != V:
        w = dame_w_distancia_minima(S, π)
        S.add(w)

        for v in vecinos_sin_camino_minimo_calculado(w, S):
            distancia_candidata = π[w] + distancia(v, w)
            if distancia_candidata == π[v]:
                cant[v] += 1
            if distancia_candidata < π[v]:
                π[v] = distancia_candidata
                pred[v] = w

    return (π, pred, cant)

#### (b) Explique como modificar el algoritmo de Dijkstra de modo tal que si hay mas de un camino mínimo de $v$ a $w$, se elija el camino con el menor numero de aristas

def dijkstra(origen):
    S = set()
    π = {}
    pred = {}
    cant_caminos = {}
    cant_aristas = {}

    for v in V:
        π[v] = INFINITO
        pred[v] = INFINITO
        cant_caminos[v] = 1
        cant_aristas[v] = 0


    π[origen] = 0
    pred[origen] = 0

    while S != V:
        w = dame_w_distancia_minima(S, π)
        S.add(w)

        for v in vecinos_sin_camino_minimo_calculado(w, S):
            distancia_candidata = π[w] + distancia(v, w)
            if distancia_candidata == π[v]:
                cant_caminos[v] += 1
                if cant_aristas[w] + 1 < cant_aristas[v]:
                    pred[v] = w
                    cant_aristas[v] += cant_aristas[w] + 1

            if distancia_candidata < π[v]:
                π[v] = distancia_candidata
                pred[v] = w
                cant_aristas[v] += cant_aristas[w] + 1


    return (π, pred, cant_caminos, cant_aristas)

### 3) Un grafo $G$ es coloreable en forma única si todo coloreo con $χ(G)$ colores induce la misma particion de los vertices. Mostrar que si $G$ es coloreable en forma ́unica el subgrafo inducido por dos conjuntos cualesquiera de la particion inducida por los $χ(G)$-coloreos es un subgrafo conexo

### 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:

> Voy a usar X en esto para referirme a \Pi.

##### i. $Π$ es $NP-hard$ pero no $NPC$.

> i) Falso. X es NP-completo. Si hay una reducción polinomial de TSP a X, entonces X es al menos tán difícil como TSP, luego X está en NP-Hard. Si hay una reducción polinomial de X a TSP, entonces como se puede resolver TSP en una máquina de Turing no-determinista en tiempo polinomial, se puede resolver X en una máquina de Turing no-determinista en tiempo polinomial, y luego X está en NP. Como está en NP, y está en NP-Hard, está en NP-complete.

##### ii. $Π$ es $NP$ pero no $NPC$.

> ii) Falso, por el mismo motivo.

##### iii. $Π$ es $NPC$.

> iii) Cierto, por el mismo motivo.

##### iv. $Π$ no es $NP-hard$ ni $NPC$.

> iv) Falso, por el mismo motivo.

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

> v) No se sabe. Si P = NP, entonces al X estar en NP, X estaría en P. Si P != NP, entonces hay problemas en NP que son más difíciles que cualquier cosa en P, y como X está en NP-hard, es igual o más dificil que ellos, y luego X no está en P.

> [name=Lebron] [time=Sun, Dec 22, 2021 5:25 AM]

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