# Teoria Della Computazione
## Secondo semestre
### Vertex cover
**Input**:
- Grafo $G = (V, E)$, $V = \{v_1, v_2, \dots, v_n\}$, $E = \{e_1, e_2, \dots, e_m\}$, $E \subseteq V \times V$: $e_i = (v_i, v_j)$ $v_i, v_j \in V$.
- $k \leq n$.

**Output**:
- Yes/No: esiste $V' \subseteq V$ vertex cover di $G$ con $|V'| \leq k$? $V'$ è vertex cover di $G$ sse $V' \subseteq V \land \forall e = (v_i, v_j) \in E:v_i \in V' \lor v_j \in V'$

### Independent set
**Input**:
- Grafo $G = (V, E)$, $V = \{v_1, v_2, \dots, v_n\}$, $E = \{e_1, e_2, \dots, e_m\}$, $E \subseteq V \times V$: $e_i = (v_i, v_j)$ $v_i, v_j \in V$.
- $k \leq n$.

**Output**:
- Yes/No: esiste $V' \subseteq V$ independent set di $G$ con $|V'| \geq k$? $V'$ è independent set di $G$ sse $V' \subseteq V \land \forall e = (v_i, v_j) \in E:v_i \notin V' \lor v_j \notin V'$

**IND-SET** $\in$ **NP-complete**:
- **IND-SET** $\in$ **NP**: utilizzo di un certificato. Dati $G, k$ ed una soluzione $y = \{v_1, v_2, \dots, v_n\}$ posso verificare in tempo polinomiale se $y$ è un independent set di dimensione maggiore od uguale a $k$.
- Verifico che $|y| \geq k$.
- Itero sugli archi $(v_i, v_j) \in E$ e verifico che $v_i \notin y \lor v_j \notin y$.
- **3-SAT** $\leq_p$ **IND-SET**: devo trovare una funzione $f$ che dato un qualsiasi input di **3-sat** $\phi$, calcoli in tempo polinomiale $f(\phi) = (G, k)$ in modo che esista un assegnamento di letterali che verifica $\phi$ se e solo se esiste un independent set su $G$ con dimensione maggiore o uguale a $k$. Definiamo $f$ nel seguente modo: imponiamo $k$ uguale al numero delle formule di $\phi$ e costruiamo $G$ nel seguente modo:
- $G$ contiene 3 nodi per ogni clausola, uno per ogni letterale e collego le coppie di nodi della stessa clausola (formo un triangolo per ogni clausola).
- Collego tramite un arco ogni vertice che rappresenta il letterale generico $x$ ad ogni vertice che rappresenta il letterale $\bar{x}$.

Dimostriamo quindi che:
- Se $\exists I=$ **IND-SET** per $G$ con dimensione maggiore o uguale a $k$ allora $\phi$ è soddisfacibile: notiamo come $G$ sia composto da $k$ triangoli ognuno corrispondente ad una clausola di $\phi$, sapendo che $|I| \geq k$ e che $I$ risulta valido allora significa che avremo selezionato un nodo per ogni triangolo che corrisponde ad un letterale per ogni clausola. Abbiamo trovato quindi un insieme di $k$ letterali $X$, uno per ogni clausola vero, dobbiamo dunque dimostrare che non esistono $x_i, x_j \in X : x_j = \bar{x_i}$, per farlo basta notare come nel caso in cui $x_j = \bar{x_i}$ allora esiste un arco in $G$ che li collega ma a questo punto $I$ non sarebbe un independent set valido (**assurdo**).
- Se $\phi$ è soddisfaciile allora $\exists y=$ **IND-SET** per $G$ con dimensione maggiore o uguale a $k$: essendo $\phi$ soddsfacibile allora esiste un assegnamento delle variabili $A$ tale che per ogni clausola $c_i$ esiste almeno un letterale $l_{c_i}$ vero, dimostro che l'insieme dei nodi $I$ rappresentanti i letterali $l_{c_i}$ forma un independent set valido:
- Avendo $n$ clausole e scegliendo un nodo per clausola avrò che $|I|=n=k \rightarrow |I| \geq k$.
- Supponiamo che $V$ non rappresentasse un independent set valido significa che esiste almeno un arco $(v_i, v_j) \in E$ tale che $v_i \in I \land v_j \in I$, per costruzione del grafo notiamo che 2 nodi sono collegati se:
- I rispettivi letterali sono nella stessa clausola, ma scengliendo solo un letterale $l_{c_i}$ vero per clausola ciò non può essere verificato(**assurdo**).
- I rispettivi letterali sono uno la negazione dell'altro, ma essendo $A$ valido ciò non può essere verificato(**assurdo**).

### Set cover
Nella versione di ottimizzazione abbiamo:
**Input**:
- $U$ insieme universo formato da $n$ elementi.
- $S = \{S_1, S_2, \dots, S_m\} : S_i \subseteq U$.
- Funzione di costo $c:S \rightarrow Q^+$

**Output**:
- Insieme $X = \{S_{i1}, S_{i_2}, \dots, S_{ik}\}: \cup_{1 \leq j \leq k} S_{ij} = U$ e $\Sigma_{j = 1}^{k}c(S_{ij})$ è minimo. Nella versione con costo uniforme ($c(S_i) = 1 \forall i : 1 \leq i \leq m$) l'obiettivo diventa minimizzare $|X|$.

Nella versione di decisione con costo uniforme abbiamo:
**Input**:
- $U$ insieme universo formato da $n$ elementi.
- $S = \{S_1, S_2, \dots, S_m\} : S_i \subseteq U$.
- $k \in N$.

**Output**:
- Yes/No: Yes se $\exists X = \{S_{i1}, S_{i_2}, \dots, S_{ik}\}: \cup_{1 \leq j \leq k} S_{ij} = U$, no altrimenti.

**SET-COVER** $\in$ **NP-COMPLETE**
- **SET-COVER** $\in$ **NP**: utilizzo di un certificato. Dati $U, S, k$ ed una soluzione $X = \{S_{i1}, S_{i_2}, \dots, S_{ix}\}$ posso verificare in tempo polinomiale se $X$ è un set cover di dimensione $k$.
- Verifico che $|X| = k$.
- Verifico che per per ogni elemento $x \in U \exists S_j \in X: x \in S_j$
- **VERTEX COVER** $\leq_{p}$ **SET COVER**: devo trovare una funzione $f$ che dato un qualsiasi input di **VERTEX COVER** $G, k_1$, calcoli in tempo polinomiale $f(G, k) = (U, S, k_2)$ in modo che esista un vertex cover di dimensione $k_1$ per $G$ se e solo se esiste un set cover di dimensione $k_2$ su $U$. Definiamo $f$ nel seguente modo: innanzitutto poniamo $k_2 = k_1$ (per semplicità poi useremo $k$ per riferirci ad essi), facciamo corrispondere all'insieme universo $U$ l'insieme degli archi $E$ di $G$, e creiamo $n = |V|$ insiemi $S_i$, dove $S_i$ contiene tutti gli elementi rappresentati archi incidenti nel nodo $i$.

Dimostriamo quindi che:
- Se esiste un vertex cover di dimensione $k$ su $G$, ossia se esiste $V' \subseteq V \land \forall e = (v_i, v_j) \in E:v_i \in V' \lor v_j \in V'$ con $|V'| = k$ allora esiste un insieme $X = \{S_{i1}, S_{i_2}, \dots, S_{ik}\}: \cup_{1 \leq j \leq k} S_{ij} = U$. Scegliamo infatti l'insieme $X = \{S_{v_i} : v_i \in V'\}$, tale insieme ha cardinalità $k$ e sappiamo che $X = \cup_{1 \leq j \leq k} S_{ij} = U$ se non fosse così significherebbe che esiste un elemento $x \in U$ non contenuto in nessun elemento di $X$, ma ciò implica che esiste un arco (infatti gli elementi di **SET COVER** sono gli archi del grafo di **VERTEX COVER**) che non è incidente a nessuno nei nodi selezionati, ma essendo $V'$ un vertex cover rappresenta un **assurdo**.
- Se esiste un set cover $X = \{S_{i1}, S_{i_2}, \dots, S_{ik}\}: \cup_{1 \leq j \leq k} S_{ij} = U$ allora esiste un vertex cover di dimensione $k$: esiste $V' \subseteq V \land \forall e = (v_i, v_j) \in E:v_i \in V' \lor v_j \in V'$ con $|V'| = k$. Scegliamo come vertici di $V'$ i vertici che rappresentano gli insiemi di $X$, sappiamo dunque che $|V'| = |X| = k$, inoltre tali insiemi rappresentano un vertex conver, infatti se non fosse vero significa che esisterebbe un arco $e = (v_i, v_j)$ tale che $v_i \notin V' \land v_j \notin V'$, ma ciò implica che esiste un elemento $x \in U$ che non appartiene a nessun elemento di $X$, ma essendo $X$ un set cover rappresenta un **assurdo**.

### Algortimo $\epsilon$ approssimante per TSP

Dato un grafo $G=(V,E)$ completo, ed una funzione di costo $c: E \rightarrow Q$ supponiamo che esista un algoritmo $A(G, c)$ che sia $\epsilon$ approssimante per **TSP**, ossisa $A(G, c) \leq \epsilon \cdot opt(G, c)$, dimostriamo ora che tale algoritmo non può esistere a meno che $P=NP$. Infatti se $A$ esistesse sarebbe possibile risolvere il problema **Hamiltonian cycle** (HC) in tempo polinomiale, infatti sarebbe sufficiente tradurre una qualsiasi istanza $G = (V, E)$ di HC nelle relativa istanza $G' = (V', E', c)$ seguente modo(in tempo polinomiale):
- $V'=V$.
- $E' = V \times V$.
- $c(e) = 1 \forall e \in E, c(e) = |V| \cdot \epsilon + 1 \forall e \notin E$.

Possiamo ottenere in tempo polinomiale $x = A(G', c)$ ed avremo 2 casi:
- $x = |V|$ allora esiste un ciclo hamiltoniano di $V$ archi di costo 1 in $G'$ e di conseguenza un ciclo hamiltoniano in $G$.
- $x > |V|$ significa che è stato scelto almeno un arco di $E'$ non appartenente a $E$ e quindi $x > |V| \cdot \epsilon$ , ma sapendo che $A(G', c) \leq \epsilon \cdot opt(G', c)$ allora non esiste un ciclo hamiltoniano di $V$ archi di costo 1 (infatti in tal caso avrei che $opt(G', c) = V$ e quindi non sarebbe rispettata la relazione $A(G', c) < \epsilon \cdot opt(G', c) = \epsilon \cdot V$ ) e di conseguenza non esiste un ciclo hamiltoniano in $G$.

Potendo capire se esiste un ciclo hamiltoniano in $G$ in tempo polinomiale, ed essendo **HC** $\in$ **NP-complete** $A$ può esistere solo se $P = NP$.

### Algoritmo 2 approssimante per TSP metrico
Supponiamo che la funzione di costo $c: E \rightarrow Q$ rispetti le seguenti proprietà:
- $c(u, v) \geq 0 \forall (u, v) \in E$
- $c(v, v) = 0 \forall v \in V$.
- $c(u, v) \leq c(u, z) + c(z, v) \forall u,v,z \in V$.

Allora $c$ induce una simmetria e ci riferiamo a $TSP(G, c)$ come TSP metrico, in tal caso esiste un algoritmo $A$ 2 approssimanete, ossia $A(G, c) \leq 2 \cdot opt(G, c)$. Definiamo $A$ come segue.
1. Trovare l'albero di copertura minimo $T$ di $G$, può essere trovato in tempo polinomiale e sappiamo che $c(t) < opt(G, c)$ (se così non fosse allora basterebbe prendere il ciclo hamiltoniano di costo minimo e togliergli un arco per trovare un MST di costo minore).
2. Raddoppio ogni arco di $T$ trovando il grafo euleriano $E_g$ in tempo polinomiale. $c(E_g) = 2 \cdot c(T)$.
3. Trovo in tempo polinomiale un cammino euleriano $E_p$ in $E_g$ in tempo polinomiale (sappiamo che esiste un cammino euleriano in quanto ogni arco ha grado pari). $c(E_p) = c(E_g)$.
4. Scelgo un nodo casuale $v$ in $V$ e visito $E_p$ creando in tempo polinomiale un cammino hamiltoniano $H_c$ inserendo i nodi in tale ciclo in ordine della loro prima apparizione durante la visita. Sappiamo che per la disuguaglianza triangolare $c(H_c) \leq c(E_p) = c_(E_g) = 2 \cdot c(T)$.

Sapendo che $c(t) < opt(G, c)$ e che $c(H_c) \leq 2 \cdot c(T)$ allora $A(G, c) \leq 2 \cdot opt(G, c)$

Esempio pratico:
$G$:
$T$: 
$E_g$: 
$E_p$: 
$H_c$: 

### Complessità parametrica
Un problema **NP-HARD** può avere istanze che sono risolvibili in tempi ragionevoli se fissati dei parametri che caratterizzano l'istanza. Un problema decidibile $\pi$ si dice trattabile fissato il parametro $k$ se e solo esiste un algoritmo $A$, una costante $c$ ed una funzione computabile $f$ tale che per tutti gli input $<x,k>$ $A$ risolve $\pi$ con tempo di calcolo $f(k)|x|^c$ (polinomiale in $|x|$ ma potenzialmente esponenziale in $k$)).

### Vertex cover FPT
Dato il problema vertex-cover:
**input**: Grafo $G=(V,E)$, $k$
**output**: Esiste una copertura di dimensione minore o uguale a $k$ in $G$?

Il problema vertex-cover $(G,k)$ risulta risolvibile in tempo $O(2^k \cdot |V|)$: Costruisco un bounded search tree di profondità $k$ dove i vertici sono coperture candidate:
- Passo iniziale: data la radice $r$ di un albero ed un arco $e = (u, v) \in E$ creo due figli di $r$ uno contente $u$ e l'altro contenente $v$.
- Passo ricorsivo: sia $S$ l'insieme che etichetta un vertice, scelgo $e'=(u',v') \in E$ tale che $e'$ non risulta coperto da $S$, creo dunque due figli con etichette rispettivamente uguali a $S \cup \{u'\}$ e $S \cup \{v'\}$.

Se trovo un percorso di lunghezza uguale a $k$ da $r$ ad un nodo $S$ tale per cui $S$ copre tutti gli archi in $E$ allora ho trovato una copertura di $E$ di dimensione minore o uguale a $k$, se non esiste tale percorso allora non esiste nessuna copertura di $E$ di dimensione minore o ugale a $k$.

### Closest stringa FPT
**input**: una collezione di $k$ stringhe $s_1, \dots, s_k$ di lunghezza $l$ ed un intero $d$.
**output**: stringa $s$ tale che $d_h(s, s_i) \leq d \forall i: 1 \leq i \leq k$.

Tale problema è risolvibile in tempo $O((d + 1)^d \cdot |G|)$.
Per la disuguaglianza triangolare $d_h(s, s_i) + d_h(s, s_j) \geq d_h(s_i, s_j)$, quindi se $d_h(s_i, s_j) \geq 2d$ allora non esiste soluzione.
Costuriamo un albero di ricerca dove all'inizio $s = s_1$, se $s_1$ è una soluzione allora abbiamo finito altrimenti si cerca $s_j$ che dista da $s$ di al più $2d$ e almeno $d$ posizioni e scelgo $d+1$ figli che corrispondono alle posizioni che modifico in modo permanente.

## Ricerca con automa a stati finiti
#### Preprocessing del pattern $P$ in tempo $O(m\Sigma)$
Definizione della funzione $\delta : \{0, 1, \dots, m\} \times \Sigma \rightarrow \{0, 1, \dots, m\}$:
- $\delta(j, \sigma) = j + 1$ se $j < m \land P[j + 1] = \sigma$.
- $\delta(j, \sigma) = |B(P[1,j]\sigma)|$ altrimenti.

$\delta$ fornisce la transizione dallo stato $j$ allo stato $\delta(j, \sigma)$ attraverso il simbolo $\sigma$.
#### Scansione del testo $T$ per la ricerca in tempo $O(n)$
- Parti da uno stato iniziale $s_0 = 0$.
- Per ogni $q: 1 \leq q \leq n$ processa il simbolo $T[q]$ per passare dallo stato $s_{q-1}$ allo stato $s_q$: $s_q = \delta(s_{q - 1}, T[q])$.
- Se raggiugni lo stato $s_q = m$ allora esiste un'occorrenza di $P$ in $T$ che inizia all'indice $q - m + 1$.

## Definizione ricorsiva di bordo
- $B(\epsilon) = \epsilon$.
- $B(\sigma) = \epsilon$.
- $B(X\sigma) = \begin{cases} B(X)\sigma, & \mbox{if } X[B(X) + 1] = \sigma \\ B(B(X)\sigma) & altrimenti \end{cases}$

## KMP
#### Preprocessing del paattern $P$ in tempo $O(m)$
Calcolo della funzione di fallimento (prefix function) $\rho : \{0, 1, \dots, m\} \rightarrow \{-1, 0, 1, \dots, m - 1\}$
- $\rho(0) = -1$
- $\rho(j) = |B(P[1,j])|$ se $1 \leq j \leq m$


Usando la definizione ricorsiva di borde possiamo calcolare $\rho$ nel seguente modo:

r[0] = -1
r[1] = 0
for j = 2 to m do
    k = r[j - 1]
    while k >= 0 and p[k + 1] != p[j] then
        k = r[j]
    p[j] = k + 1
return r

#### Scansione del testo per la ricerca in tempo $O(N)$
La scansione del testo avviene tramite una finestra $W$ di confronto lunga $m$ che scorre lungo $T$ da sinistra a destra. Inizliamente la finestra viene posizionata in corrispondenza della posizione $i = 1$ di $T$. Assumendo che:
- $W$ si trova in posizione $i$ del testo.
- Il primo carattere di $P$ che genera un mismatch con $T$ è in posizione $j$ del pattern (mismatch in posizione i = j - 1 del testo).
- Per definizione, il valore $k = \rho(j - 1)$ rappresenta la lunghezza del bordo del prefisso $P[1,j-1]$, quindi:
- $P[1,k]$ ha un'occorrenza su $T$ che inizia in posizione $i$.
- $P[1,k]$ ha un'occorrenza su $T$ che inizia in posizione $p = i + j - k + 1$.
- Sposto quindi la finestra, il confronto riparte da:
- $i + j - 1 - k$ sul testo.
- $k + 1$ su $P$.
- Se $j = m$ allora trovo un'occorrenza di $P$ in $T$.

## Ricerca esatta con Baeza-Yates e Gonnet(BYG)
#### Preprocessing del pattern $P$ in tempo $O(|\Sigma| + m)$
Calcolo la parola $B_\sigma$ per ogni $\sigma \in \Sigma$: $B_\sigma = b_1b_2 \dots b_m$ tale che $b_j = 1 \iff P[j] = \sigma$. Per calcolare tali parole le inizializzo tutte a 0 e inizializzo una maschera $M$ formata da $m$ bit come seguee: $10000\dots$, eseguo poi una scansione di $P$ da sinistra verso destra ed ad ogni iterazione effettuo: $B_{P[j]} = M$ $OR$ $B_{P[j]}$ e $M = RSHIFT(M)$
#### Scansione del testo $T$ in tempo $O(N)$
Il testo viene scandito dalla prima all'ultima posizione, per ogni posizione $i$ del testo viene calcolata una parola $D_i$ di $m$ bit, ogni volta che $D_i$ ha il bit meno significativo uguale a 1 significa che esiste un'occorenza di $P$ in $T$ nella posizione $i-m+1$.
$D_i = d_1d_2\dots d_m$ tale che $d_j = D_i[j] = 1 \iff P[1, j] = suff(T[1, i])$. Abbiamo che $D_0 = 00 \dots 00$ e che $D_i[m] = 1 \iff$ ho un'occorenza di $P$ in $T$ che inizia il $i-m+1$.
Come calcolare $D_i$ a partire da $D_{i-1}$? per $j > 1$ allora $D_i[j] = D_{i - 1}[j - 1]$ $AND$ $B_{T[i]}[j]$, per $j=1$ allora $D_i[1] = 1$ $AND$ $B_{T[i]}[1]$. Ma allora posso riassumere dicendo che $D_i = RSHIFT1(D_{i - 1})$ $AND$ $B_{T[i]}$. La scansione del testo consiste dunque nel:
1. Inizializzare una maschera $M = 00 \dots 1$.
2. Inizializzare $D_0 = 00 \dots 0$.
3. Per ogni $i$ tra 1 e $n$ calcolo $D_i = RSHIFT1(D_{i - 1})$ $AND$ $B_{T[i]}$.
4. Ogni volta che $D_i$ $AND$ $M$ vale $00 \dots 01$ allora ho trovato l'occorrenza $i-m+1$.

## Ricerca approssimata con Wu e Manber
Dato un pattern $P$ ed un testo $T$, definiti su $\Sigma$ ed una soglia di errore $k$ diciamo che: $P$ ha un'occorrenza approssimata in $T$ in posizione $i$ se esiste una sottostringa $T[i - L + 1, i]$ che ha distanza di edit con $P$ minore o uguale a $k$.
#### Preprocessing del pattern $P$ in tempo $O(|\Sigma| + m)$
Stesso preprocessing del pattern mostrato nell'algoritmo BYG.
#### Scansione del testo $T$ in tempo $O(kn)$.
$k + 1$ iterazioni di scanzione del testo per $0 \leq h \leq k$, dove l'iterazione $h$ trova tutte le occorrenza del pattern con al più $h$ errori.
La generica iterazione $h$ calcola $h$ parole $D^h_i$ lunghe $m$ bit tali che $D^h_i[m] = 1 \iff$ $P$ ha un'occorenza che finisce in $i$ con al più $h$ errori. Con $h = 0$ trovo le occorrenze esatte (BYG). Con $h = k$ trovo le occorrenze approssimate. $D^h_i = d_1d_2\dots d_m$ tale che $d_j = D^h_i[j] = 1 \iff P[1, j] = suff_h(T[1, i])$.
- $D^0_0 = 00\dots0$
- $D^h_0[j] = 1 \forall j \leq h$
- $D^h_0[j] = 0 \forall j > h$
- Se $d_m = D^h_i[m] = 1$ ho un'occorrenza con al più $h$ errori che termina in $i$.

Algoritmo:
1. Iterazione $h = 0$, calcolo $D^0_i$ con BYG.
2. Per ogni iterazione $h > 0$ calcolo per ogni posizione $i$ del testo $D^h_i$.
3. Iterazione $h = k$, ogni volta che $D^k_i[m] = 1$ ho un'occorrenza approssimata di $P$ che finisce in posizione $i$

Calcoliamo per $h > 0, i > 0$
$D^{h}_i = \begin{cases} (RSHIFT1(D^h_{i-1}) AND B_{T[i]}) & or\\
RSHIFT1(D^{h - 1}_{i-1}) & or\\
D{^{h-1}_{i - 1}} & or \\
RSHIFT1(D^{h - 1}_{i}) \end{cases}$.
## Suffix Array
Dato un testo $T$ viene esteso con il simbolo **$** (considerato lessicograficamente minore di tutti gli altri simboli di $\Sigma$). Indichiamo con q-suffisso il suffisso $T[q,n]$. Il suffix array $S$ di un testo $T$ è un array di $n$ interi tale che $S[i]=q$ see solo se il q-suffisso è l-iesimo suffiso nell'ordinamento lessicografico di tutti i suffissi di $T$.
Per effettuare ricerca esatta con suffix array:
1. Preprocessing del testo $T$ per costruire il relativo suffix array.
2. Ricerca in tempo $O(mlogn)$ di un pattern $P$ di lunghezza $m$. (ricerca binaria).

## Burrows-Wheeler Transform
La BWT $B$ di un testo $T$ è la permutazione dei simboli di $T$ tale che $B[i]$ è l'ultimo simbolo della i-esima rotazione nell'ordinamento lessicografico delle rotazioni di $T$.
**Last First Mapping:** l'r-esimo simbolo $\sigma$ in $B$ e l'r-esimo simbolo $\sigma$ in $F$ sono lo stesso simbolo di $T$.
**Q-intervallo:**
1. Rispetto alla BWT: Intervallo $[b, e)$ di posizioni sulla BWT $B$ che contiene i simboli che procedono i suffissi che condividono la stringa $Q$ come prefisso.
2. Rispetto al Suffix Array: $[b, e)$ di posizioni sul SA $S$ che contiene gli indici dei suffissi che condividono la stringa $Q$ come prefisso.

**Backward extension:** estendere un Q-intervallo $[b, e)$ con il simbolo $\sigma$ ottenendo il $\sigma$Q-intervallo $[b', e')$

**Ricerca esatta con BWT:** $m$ operazioni di backward extension a partire dall'$\epsilon$-extension. L'ultima operazione trova il $P$-intervallo $[b, e)$, i valori di $S[b], S[b+1], \dots, S[e - 1]$ sono le occorrenze di $P$ in $T$. La generica iterazione estende il Q-intervallo per $Q=P[j+1, m]$ con $P[j]$ per ottenere il Q-intervallo $Q=P[j, m]$.
**FM-index:** Funzioni $C$ ed $Occ$:
1. $C: \Sigma \to \{0, 1, \dots, n\}$. $C(\sigma)$ corrisponde al numero di simboli della BWT minori di $\sigma$.
2. $Occ: \{1, 2, \dots, n + 1\} \times \Sigma \to \{0, 1, \dots, n\}$. $Occ(i, \sigma)$ corrisponde al numero di simboli $\sigma$ in $B[1, i - 1]$.

Possiamo dunque esprimere la LF function come $j = LF(i) = C(B[i]) + Occ(i, B[i]) + 1$
Ma allora per effettuare la backward extension possiamo, supponendo di estendere il Q-intervallo $[b, e)$ con il simbolo $\sigma$: $b' = C(\sigma) + Occ(b, \sigma) + 1$, $e' = C(\sigma) + Occ(e, \sigma) + 1$.
## Primo semestre
### Linguaggio formale

- Alfabeto finito $V = \{v_1, v_2, \dots, v_n\}$.
- Parola/Stringa: sequenza finita di simboli.
- Un linguaggio $L$ è un insieme di parole, $L$ non deve essere finito : $L = \{w | w = a^n, n \geq 1\}$.
- $L^*$: tutte le parole di $L$.
- $L^+$ tutte le parole di $L$ esclusa $\epsilon$.

### Problema:
- Insieme di parametri.
- Una soluzione.
- Regole che mettono in relazione input ed output.
- Istanza: uno specifico input.
- Diciamo che un algoritmo risolve un problema se produce l'output corretto per tutte le possibili istanza di tale problema.
- Diciamo che un algoritmo è efficiente se richiede un tempo di calcolo polinomiale rispetto alla dimensione dell'input.
- Ci sono 3 tipi di problemi:
- **Problemi di decisione**: ammette solo due risposte: "Sì" o "No".
- **Problemi di ricerca**: tra tutte le soluzioni corrette trovane una.
- **Problemi di ottimizzazione**: tra tutte le soluzioni ottime trovane una.

### Categorie di problemi in base al tempo:
- $P$: L'insieme dei problemi di decisioni che possono essere risolti da una macchina di Turing deterministica in tempo polinomiale.
- $NP$: L'insieme dei problemi di decisione che possono essere risolti da una macchina di Turing non deterministica in tempo polinomiale, oppure l'insieme dei problemi di decisione dove le istanze in input che hanno come risposta "Sì" sono verificabili in tempo polinomiale da una macchina di Turing deterministica.
- $NP-complete$: L'insieme dei problemi di decisione $P$ tali che:
- $P \in NP$
- $\forall P' \in NP$ $P' <_t P$
- $NP-hard$: L'insieme dei problemi di decisioni difficili almeno quanto il problema più difficile in $NP$, ossia l'insieme dei problemi di decisione $P$ tali che: $\forall P' \in NP$ $P' <_t P$.
- $EXPTIME$: l'insieme dei problemi di decisione che sono risolvibili da una macchina di turing deterministica in tempo esponenziale.

### Relezione tra $P$, $NP$, $NP-complete$, $NP-hard$:

### Problemi trattabili e intrattabili
- Un problema è definito **trattabile** se ammette una soluzione con tempo polinomiale.
- Un problema è definito **intrattabile** se non conosciamo un soluzione con tempo polinomiale.
- Un problema è definito **provably intractable** se esiste una dimostrazione che il problema non ammette soluzioni con tempo polinomiale.

### Categorie di linguaggi
- Rircorsivamente enumerabili, $RE$: $L \in RE$ se esiste una macchina di Turing $M$ tale che, data una stringa $x \in L$, $M(x)$ termina accettandando la stringa, se $x \notin L$ allora $M(x)$ potrebbe rifiutare $x$ oppure non terminare la propria esecuzione. In tal caso $L$ si dice parzialmente decidibile.
- Ricorsivi, $R$: $L \in R$ se esiste una macchina di Turing $M$ tale che, data una stringa $x \in L$, $M(x)$ termina accettando la stringa, se $x \notin L$ allora $M(x)$ termina rifiutando la stringa. In tal caso $L$ si dice decidicile.
- Se $L \in RE \land \bar{L} \in RE$ allora $L \in R$.

### Macchina di Turing deterministica:
- $S$: insieme finito di stati.
- $s_0$: stato iniziale.
- $\{Y, N, H\}$ insieme degli stati finali:
- $Y$ termina la computazione riconoscendo la stringa in input.
- $N$ termina la computazinoe rifiutando la stringa in input.
- $H$ termina la computazione producendo come output la stringa attualmente sul nastro.
- $\Sigma$: alfabeto finito dei simboli in input.
- Funzione di transizione $\delta :S \times \Sigma \to S$ $\cup \{Y, N, H\} \times \Sigma \times \{\leftarrow, \rightarrow, -\}$, ossia: trovandomi nello stato $s \in S$ e leggendo in input il carattere $\sigma \in \Sigma$ allora mi muoverò nello stato $s' \in S$ $\cup \{Y, N, H\}$, scrivendo sul nastro il simbolo $\sigma' \in \Sigma$ e la testa del nastro verrà eventualmente spostata a sinistra o destra.

La macchina di turning partirà nella configurazione iniziale, ossia nello stato $q_0$ e con la testa del nastro che legge il primo carattere della stringa in input. Ad ogni passo la macchina di Turing si trova in uno stato specifico e la testa sta leggendo uno specifico valore sul nastro infinito, in base allo stato attuale ed al simbolo letto utilizzando la funzione di transizione la macchina di Turing potrebbe cambiare stato, potrebbe cambiare il carattere sotto la testa del nastro per poi muovere la testa a sinistra o destra (oppure tenendola ferma). Quando la macchina si trova in uno stato finale si ferma. La stringa iniziale sul nastro rappresenta l'input mentre la stringa finale sul nastro rappresenta l'output.

**Configurazione di una macchina di Turing**: una tripla $(s, u, pos)$:
- $s \in S$: stato attuale.
- $u \in \Sigma^*$: stringa sul nastro
- $pos$: posizione della testa sul nastro.

**Macchine di Turing multinastro**: Nella macchina sono presenti più nastri infiniti, la macchina di Turing ha una testina per ogni nastro ed ad ogni passaggio legge tutti i valori sotto le testine ed in base allo stato in cui si trova, tramite la funzione di transizione, si muove in un nuovo stato cambiando il simbolo sotto ognuna delle testine per poi spostarle a destra o sinistra o lasciarle ferme.
*Teorema*: le macchine di Turing multinastro sono equipotenti alla macchine di Turing standard.

**Macchina di Turing universale**
La macchina di Turing universale $U$ prende come input 2 stringhe binarie: la codifica di una macchina di Turing $M$ (è possibile dimostrare che si può codificare in maniera univoca una qualsiasi macchina di Turing) ed un input $x$, e simula $M$ su $x$ ossia $U(M, x) = M(x)$.

### Tempi d'esecuzione di una macchina di Turing
- Una macchina di Turing $M$ su input $X$: $t_M(X) = min\{|B|$ $|$ $B$ è una computazione che accetta $X\}$.
- Una macchina di Turing $M$ ha tempi d'esecuzione $T_M(n) = max\{t_M(X) |$ $|X| = n\}$.
- $time(f(n))$: insieme dei problemi risolvibili con tempo $f(n)$. $P = \bigcup\limits_{k \geq 0} time(n^k)$

### Spazio utilizzato da una macchina di Turing
- Una macchina di Turing $M$ su input $X$ utilizza spazio pari al numero di celle di nasto utilizzate che indichiamo $s_M(X)$.
- Indichiamo la funzione di complessità spaziale di una macchina di Turing $M$ come $S_M(n) = max\{s_M(X)$ $|$ $|X| = n\}$
- $PSPACE$: insieme dei problemi risolvibili da una macchina di Turing deterministica in spazio polinomiale. $P \subseteq PSPACE$, **D-TSP**$\in PSPACE$.
- Teoremi:
- $S_M(n) \leq T_M(n) + n$.
- $S_M(n)$ finito non implica che $T_M(n)$ sia finito.
- Se abbiamo una macchina di Turing che lavora in tempo $T_M(n)$ infinito e spazio $S_M(n)$ finito allora possiamo costruire una macchina di Turing $M'$ equivalente che lavora in tempo $T_{M'}(n)$ finito e spazio $S_{M'}(n)$ finito: indicando con $S$ gli stati di $M$ e con $\Sigma$ l'alfabeto di $M$ allora possiamo dire che esistono solamente $|S| \times |\Sigma| ^{S_M(n)} \times S_M(n)$ possibili configurazioni. $M'$ dovrà dunque simulare $M$ ed in caso la simulazione superi le $|S| \times |\Sigma| ^{S_M(n)} \times S_M(n)$ configurazioni dovrà fermarsi rispondendo NO.
- Se un problema è risolvibile in memoria polinomiale allora è risolvibile in tempo esponenziale.

### Tesi di Turing-Church
Tutti i formalismi basati su computazione meccanica sono equipotenti
### Turing reduction
Permette di ridurre un problema $A$ ad un problema $B$ ($A <_T B$). $f:\Sigma_A^* \to \Sigma_B^*$ ossia permette di tradurre un qualsiasi input di $A$ in un input di $B$ addizionalmente:
- $f$ viene calcolata da una macchina di Turing deterministica in tempo polinomiale.
- $x \in L_A$ se e solo se $f(x) \in L_B$.

Per risolvere $A$ possiamo tradurre l'istanza di input $x$ nella relativa istanza di input per il problema $B$ $f(x)$, risolvere $B$ ed ottenere il relativo risultato per $A$.
- $L_2 \in P \land L_1 <_T L_2 \to L_1 \in P$.
- $L_1 \notin P \land L_1 <_T L_2 \to L_2 \notin P$.
- $<_T$ è riflessiva e transitiva.

### Macchina di Turing non deterministica
- $S$ insieme finito di stati.
- $s_0$: stato iniziale.
- $\{Y, N, H\}$ insieme degli stati finali:
- $Y$ termina la computazione riconoscendo la stringa in input.
- $N$ termina la computazinoe rifiutando la stringa in input.
- $H$ termina la computazione producendo come output la stringa attualmente sul nastro.
- $\Sigma$: alfabeto finito dei simboli in input.
- Relazione di transizione $\delta \subseteq (S \times \Sigma) \times (S \times \Sigma \times \{\leftarrow, \rightarrow, -\})$ ossia: trovandomi nello stato $s \in S$ e leggendo in input il carattere $\sigma \in \Sigma$ allora transiterò non deterministicamente una tripla $t = (s', \sigma', \{\leftarrow, \rightarrow, -\})$ tale che $(s, \sigma) \delta t$.

Caratteristiche di una macchina di Turing non deterministica $N$:
- $w \in \Sigma^*$ viene accettata se e solo se $\exists (s_0, x, 1) \to^{delta} (Y, x', p_F)$, ossia se esiste **almeno una** computazione (sequenza di configurazioni) che parte dallo stato finale e termina in $Y$.
- $w \in \Sigma^*$ viene rifiutata se per ogni possibile computazione $N(w) = LOOP \lor NO$.
- $N$ decide un linguaggio $L$ se:
- $\forall x \in L$, $x$ viene accettata da $N$.
- $\forall x \notin L$, $x$ tutte le computazioni $N(x) = NO$.
- $N$ decide un linguaggio $L$ in tempo $f(n)$ se:
- $N$ decide $L$.
- $\forall x \in L$ esiste una computazione $(s_0, x, 1) \to^{delta} (Y, x', p_F)$ che impiega meno di $f(n)$ passi.
- $\forall x \notin L$ tutte le computazioni impiegano meno di $f(n)$ passi.
- Le macchine di Turing non deterministiche sono equipotenti alle macchine di Turning deterministiche.
- Se esiste una macchina di Turing non deterministica $N$ che decide $L$ in tempo $f(n)$, allora esiste una macchina di Turing deterministica $M$ che decide $L$ in tempo $O(d^{f(n)})$, dove $d$ dipende da $N$ (d = numero massimo di rami di uscenti da $N$). Infatti è sufficiente effettuare una simulazione level by level con una DTM a 3 tapes:
- Il primo memorizza N.
- Il secondo memorizza la simulazione corrente.
- Il terzo memorizza le scelte fatte tramite un numero in base $d$.

### Dimostrare che un problema è $NP$ completo
Per dimostrare che un problema $p \in NP-complete$ devo dimostrare che:
- $p \in NP$.
- $\exists p' \in NP-complete$ $|$ $p' <_T p$.
Il primo problema ad essere stato inserito in $NP-Complete$ è **SAT**.
### Halting Problem:
Data una macchina di Turing $M$ ed un istanza di input $x$ stabilire se l'esecuzione $M(x)$ termina. Tale problema non è decidibile (quindi il linguaggio associato non è ricorsivo):
*Dimostrazione*: Definiamo il linguaggio $L_H = \{M, x | M(x) halts\}$, assumiamo inoltre di avere una macchina di Turing $M_H$ che decide $L_H$ ($M_H$ deve quindi terminare sempre). Costruiamo poi una macchina di Turing $D(M)$ nel seguente modo:
$D(M) = \begin{cases} Y & \mbox{if } M_H(M,M)=N\\LOOP & \mbox{if } M_H(M,M)=Y\end{cases}$
Consideriamo ora cosa succede se provo a computare $D(D)$, verrà computata $M_H(D,D)$ ed ho 2 casi:
- $M_H(D, D) = N$ (ossia $D$ non dovrebbe terminare con input $D$) allora per definizione di $D$: $D(D)=Y$ **Contraddizione**.
- $M_H(D, D) = Y$ (ossia $D$ dovrebbe terminare con input $D$) allora per definizione di $D$: $D(D) = LOOP$ **Contraddizione**.

Vediamo ora la decidibilità di $L_H$:

- $L_H \notin R$ in quanto non decidibile.
- $L_H \in RE$ è ricorsivamente enumerabile: Creiamo $M'(M, x) = \begin{cases} Y & \mbox{if } U(M,x)=Y\\Y & \mbox{if } U(M,x)=N\end{cases}$
- $\bar{L_H} \notin RE$, infatti se $\bar{L_H} \in RE \land L_H \in RE \to L_H \in R$ che sappiamo essere falso.

### Teorema di Savitch
$NSPACE(f(n)) \subseteq PSPACE(f(n)^2)$ ossia: se un problema $\pi$ può essere risolto da una macchina di Turing non deterministica con spazio $f(n)$ allora lo stesso problema può essere risolto da una macchina di Turing deterministica con spazion $f(n)^2$. Tale teorema implica che, essendo il quadrato di un polinomio un altro polinomio: $PSPACE = NPSPACE$. L'idea della dimostrazione di tale problema si basa sull'algoritmo **STCON** che permette, dato un grafo, di sapere se è possibile andare dal nodo $u$ al nodo $v$ utilizzando $O((logN)^2)$ memoria. Per farlo si procede ricorsivamente spezzando la funzione $f(u, v, k)$ in $f(u, i, k / 2) \land f(i, v, (k + 1) / 2)$ fino ai casi base con $k = 1 \lor k = 0$.
Supponiamo ora di avere un linguaggio $L \subset NSPACE(f(n))$, esiste una macchina di Turing $M$ che decide $L$ in spazion $f(n)$ creiamo ora un grafo $G_x^M$ i cui nodi sono le configurazioni di tale macchina di Turing sull'input $x$ ed esiste una arco da un nodo $a$ al nodo $b$ se e solo se è possibile andare dalla configurazione rappresentata dal nodo $a$ a quella rappresentata dal nodo $b$ in un singolo step di computazione. Partendo da $G_x^M$ (la cui dimensione è potenzialmente infinita) teniamo solo le configurazioni il cui spazio richiesto risulta essere $O(f(n))$, supponendo, senza perdita di generalità che l'alfabeto di $L$ sia binario, allora avremo un nuovo grafo $[G_x^M]$ contenente al più $2^{O(f(n))}$ nodi. Ma allora usando **STCON** con nodo iniziale = configurazione iniziale della macchina di Turing e nodo finale uno delle configurazioni in cui $M$ termina possiamo capire se $x \in L$ in memoria pari a $O(log(2^{O(f(n))})^2)$ = $O(f(n)^2)$.
### Problemi trattati.
**TSP:** Dato un grafo completo $G=(V,E)$, con archi pesati($W:E \to R^+$) trovare il ciclo di peso minore che passa per ogni vertice una sola volta.
**D-TSP:**
Dato un grafo completo $G=(V,E)$, con archi pesati($W:E \to R^+$) ed un valore $K$ stabilire se esiste un ciclo peso minore o uguale a $K$ che passa per ogni vertice una sola volta.
- **D-TSP** $\in NP-complete$

**Hamiltonian Cycle (HC):** dato un grafo non pesato $G = (V, E)$ stabilire se esiste un ciclo che visita tutti i nodi una sola volta per poi tornare al nodo iniziale.
Sicuramente **HC** $\in NP$, infatti possiamo risolverlo tramite una macchina di Turing non deterministica in tempo polinomiale.
Ridurre **HC** a **D-TSP**:
Parto da $G = (V, E)$ (non completo e non pesato) e lo trasformo in $G'= (V', E')$ tale che $V'=V$ ed $E'=\{(u, v, 0) \forall u, v \in V$ $|$ $(u, v) \in E\} \cup \{(u, v, 1) \forall u, v \in E$ $|$ $(u, v) \notin E\}$, la risposta di **HC** su $G$ corrisponde alla risposta di **D-TSP** con $K=0$ su $G'$.

**SAT:** Data una funzione booleana appartenente a CNF: $\phi = C_1 \land C_2 \land \dots \ C_m$ dove ogni clausola $C_i$ è la disgiunzione di un sottoinsieme delle variabili booleane $x_1, x_2, \dots, x_n$ stabilire se esiste una assegnamento delle variabili booleane $x_1, x_2, \dots, x_n$ che soddisfi tale formula. Ci chiediamo se **SAT** $\in NP-complete$:
- **SAT** $\in NP$? Tramite il concetto guess\check possiamo notare che, dato un possibile istanza dei valori di $x_1, x_2, \dots, x_n$ è possibile controllare che $\phi$ sia verificata in tempo polinomiale rispetto alla dimensione dell'input, quindi **SAT**$\in NP$.
- $\forall \pi \in NP, \pi <_T$ **SAT**? se $\pi \in NP$ allora $\exists N$ macchina di TUring non deterministica che risolve $\pi$ in tempo polinomiale $p(n)$ e tramite il teorema di Cook-Levin possiamo dire che: per ogni possibile input per $N$ possiamo costruire un espressione booleana che calcola se per quell'input specifico la macchina $N$ funziona correttamente e se si ferma rispondendo $YES$. Quindi tale espressione è soddisfatta se esiste un modo per la macchina di funzionare correttamente rispondendo $YES$ ma ciò equivale a chiedersi se può esistere una $NDTM$ che può risolvere tale problema ma essendo $\pi \in NP$ $N$ esiste per definizione. Tale simulazione può essere compiuta in $O(p(n)log(p(n)))$.

**3-SAT:** Data una funzione booleana appartenente a CNF: $\phi = C_1 \land C_2 \land \dots \ C_m$ dove ogni clausola $C_i$ è la disgiunzione di un sottoinsieme di cardinalità $3$ delle variabili booleane $x_1, x_2, \dots, x_n$ stabilire se esiste una assegnamento delle variabili booleane $x_1, x_2, \dots, x_n$ che soddisfi tale formula. Ci chiediamo se **SAT** $\in NP-complete$:
- **3-SAT**$\in NP$? Tramite il concetto guess\check possiamo notare che, dato un possibile istanza dei valori di $x_1, x_2, \dots, x_n$ è possibile controllare che $\phi$ sia verificata in tempo polinomiale rispetto alla dimensione dell'input, quindi **3-SAT**$\in NP$.
- $\forall \pi \in NP, \pi <_T$ **3-SAT**? Dimostro che **SAT** $<_T$ **3-SAT** e per la proprietà transitiva di $<_T$ allora $\forall \pi \in NP, \pi <_T$ **3-SAT**. Per farlo trovo un modo per codificare formule booleane di una cardinalità generica a CNF con clausole contenenti esattamente 3 variabili:
- $(x_1) \to (x_1 \lor a_1 \lor a_2) \land (x_1 \lor \bar{a_1} \lor a_2) \land (x_1 \lor a_1 \lor \bar{a_2}) \land (x_1 \lor \bar{a_1} \lor \bar{a_2})$.
- $(x_1 \lor x_2) \to (x_1 \lor x_2 \lor a_1) \land (x_1 \lor x_2 \lor \bar{a1})$
- $(x_1 \lor x_2 \lor x_3) \to (x_1 \lor x_2 \lor x_3)$
- $(x_1 \lor x_2 \lor x_3 \lor x_4) \to (x_1 \lor x_2 \lor a1) \land (x_3 \lor x_4 \lor \bar{a1})$
- $(x_1 \lor x_2 \lor \dots \lor x_n) \to (x_1 \lor x_2 \lor a_1) \land (x_3 \lor \bar{a_1} \lor a_2) \land (x_4 \lor \bar{a_2} \lor a_3) \dots (x_{n - 1} \lor x_{n}, \lor \bar{a_{n-2})}$

### LZ77