# Final 2021.07.20

https://www.cubawiki.com.ar/images/9/9c/Final_del_20-07-21_(Algoritmos_III).pdf

###### tags: `Finales`

## Resumen

### Glosario/definiciones

### Trucos

### Errores comunes

## Resolución

### 1


INFINITO = float('inf')
S = [-1.5, -1, 2]

def goloso():
    result = []
    # (asumo que S esta ordenado, si no, lo ordeno)
    anterior = -INFINITO
    for elem in S:
        if anterior < elem:
            anterior = elem+1
            result.append((elem, anterior))

    return result

print(goloso())

El algoritmo recorre linealmente el conjunto, haciendo intervalos cerrados a partir de cada número y tratando de abarcar la mayor cantidad de números posibles. Si el número siguiente ya fue abarcado, lo saltea (para minimizar la cardinalidad).

La complejidad es la de ordenar el arreglo (si no lo estuviera previamente) (mergesort $O(n\log n)$) sumada a la de recorrer el conjunto una vez: $O(n)$ (la máxima entre ambas: la de ordenar, sino solo el recorrido lineal pues todas las operaciones son $O(1)$.).

### 2: Un corte de aristas de $G$ es un conjunto de aristas tal que al borrarlas aumenta la cantidad de componentes conexas de $G$. Dado $G = (V, X)$ un grafo conexo, probar que un subgrafo $H$ de $G$ es subgrafo de $G′ = (V, X ∖ X_T)$ para algún $T = (V, X_T)$ árbol generador de $G$ si, y sólo si, $H$ no contiene un corte de aristas de $G$.

Hipótesis: G conexo

#### $\Rightarrow$)

Suponemos $H$ subgrafo de $G′ = (V, X ∖ X_T)$ para algún $T$ AG de $G$.

Todo AG tiene que tener por lo menos a 1 arista del corte (sino no sería conexo y no sería AG).

Entonces $T$ tiene al menos a 1 arista del corte.

Entonces a $X∖X_T$ le falta al menos 1 arista del corte.

Por lo tanto $H$ nunca va a tener al corte entero (porque le falta al menos 1 arista).

#### $\Leftarrow$)

Sabemos que $H$ (subgrafo de $G$) **no** contiene un corte de aristas de $G$.

Qvq, $H$ es subgrafo de $G'$ (el "anti-AG").

Es decir, queremos ver que H es "menor" o igual a G\E(T) (con menos vértices y/o aristas).

$H$ subgrafo de $G => V(H) \subseteq V(G) \land E(H) \subseteq E(G)$

Además, todo AG tiene que tener por lo menos a 1 arista del corte (sino no sería conexo y no sería AG).

#### Lebron (por el absurdo)

Sea $G = (V, E)$ un grafo. Sea $T = (V, X)$ un AG de $G$. Sea $H \subseteq G$ un tal $H ⊆ (V, E - X)$.

Asumo que existe $E' ⊆ E(H) ⊆ E - X$ un corte por aristas de $G$ en $H$.

Sea $G' = (V, E - E')$.

Luego $G'$ no es conexo, por ser $E'$ un corte por aristas de $G$. Como $E' ⊆ E - X$, entonces $X ∩ E' = ∅$.

Luego $X ⊆ E - E'$. Luego $T = (V, X)$ es un grafo conexo, subgrafo de $G' = (V, E - E')$, que no es conexo.

Absurdo.

Luego lo que asumí, la existencia de tal corte E', no puede suceder.

### 3 Flujo

### 4 

#### a)

Falso

En principio, esta afirmación no se desprende del hecho de que SUBSET-SUM esté en $NPC$ y COMPOSITE en $NP$. Para que esa reducción sea cierta, habría que demostrarla (o sea, mostrar que existe una función que transforma instancias de SUBSET-SUM en instancias de COMPOSITE de forma tal que una de ellas es positiva si y solo si la otra también lo es).

La afirmación que sí se desprende es la opuesta: que COMPOSITE puede ser reducido polinomialmente a SUBSET-SUM. Ya que, SUBSET-SUM, al estar en NP-hard, significa que todo problema en NP puede ser reducido al él.

#### b)

Verdadero

Si hubiera un algoritmo polinomial para SUBSET-SUM, podríamos resolver cualquier problema en NP reduciéndolo primero a SUBSET-SUM y luego usando el algoritmo polinomial que resuelve este último.

#### c)

Verdadero

Razonamiento análogo al punto anterior: Para resolver cualquier instancia de COMPOSITE en tiempo polinomial, podemos primero transformarla a una instancia de SUBSET-SUM en tiempo polimial (porque COMPOSITE es NP y SUBSET-SUM es NP-hard) y luego resolverla con el hipotético algoritmo $O(n³\log t)$ con el que contamos.

#### d)

Falso.

Que haya un algoritmo polinomial para un problema $NP$ en particular (en este caso, COMPOSITE), no significa que también haya algoritmos polinomiales para los demás problemas en $NP$.

#### e)

La afirmación es equivalente a su contrarrecíproca:

Si algún problema en $NP$ puede ser resuelto en tiempo polinomial, entonces $P = NP$.

Es un generalización de la afirmación anterior que ya vimos que es falsa.

En particular, todos los problemas $P$ están en $NP$. Entonces la premisa ya era cierta. Pero no sabemos si $P = NP$, entonces la afirmación es falsa.