Problems & Algorithms

Problemi e Algoritmi

Problemi Computazionali

Collezione di domande (istanze-ingressi) per cui sia stabilito un criterio astratto per riconoscere le risposte (uscite) corrette

Es
- Massimo comune divisore
- moltiplicazione fra due interi
- fattorizzazione
- ordinamento
- percorso ottimo in un grafo

Un Problema é una Relazione Binaria \(R = {(istanza,risposta) : istanza, risposta soddisfano…}\) Il dominio della relazione é l’insieme delle domande possibili R é univoca se ogni istanza ammette una sola risposta

Algoritmi

Metodo meccanico per risolvere un Problema Computazionale

Procedura
- produce un output qualsiasi da input
Algoritmo
- procedura che termina per ogni ingressa ammissibile

Un algoritmo é detto deterministico se sullo stesso input fornisce sempre lo stesso output

ad ogni algoritmo deterministico possiamo associare una finzione input-output

Un algoritmo risolve R, ossia é corretto rispetto ad R, se la sua funzione A associa una risposta ad ogni istanza di R

Un programma implementa piú algoritmi, inoltre implementa opportune strutture dati

Peak Finding

Input: vettore A[0…n-1] interi positivi Output: un intero 0<= p <n t.c. A[p-1]<=A[p]>=A[p+1] dove A[-1]=A[n]=-inf

Peak(A)
for(i=0;i<length(A);i++)
    if(A[i]>=A[i-1] && A[i]>=A[i+1])
        return i
end for

Left Peak Finding

Nel caso migliore p=0 é un picco Nel caso peggiore p=n-1 confronti

Max Peak Finding

MAX-PEAK(A)
r = 0
i = 1
while(i<n-1)
    if A[i] > A[r]
        r <- i
    i <- i+1
end while
return r

Fa sempre lo stesso numero di confronti, sempre n-1

Analisi

Teorema picco Si trovano segmenti sempre piú corti su cui vale il teorema a partire da un q centrale.

Divide et Impera

PEAK-DI(A,i,j)
p<-(i+j)/2
if A[p-1]<=A[p]>=A[p+1] then
    return p
else
    if A[p-1]>A[p] then
        return PEAK-DI(A,i,p-1)
    else
        return PEAK-DI(A,p+1,j)
    endif
endif

PEAK-FIND-DI(A,n)
return PEAK-DI(A,0,n-1)

\(T(n)=\begin{cases} 1 & n=1 \\ T(\frac{n}{2})+1 & n>1 \end{cases}\) \(T(n)=T(\frac{n}{2^k})+k\) per \(1\le k \le \log_{2}n\) \(T(n)=1+\log_{2}n\)

Insolubilitá e Intrattabilitá

non tutti i problemi hanno una soluzione algoritmica (problema della terminazione)
intrattabile é un problema che ha una soluzione algoritmica ma il cui sforzo computazionale é troppo grande

Correttezza

Totale e Parziale

Specifica

Precondizioni
Postcondizioni
- criterio che stabilisce come deve essere fatto l’output

Ricorsione

Un problema si presta alla ricorsione quando la soluzione con un certo input ha una relazione semplice con la soluzione del problema con uno o piú input diminuiti

HANOI(n,sorgente,destinazione,appoggio)
PRE:
- n>0
- base degli n dischi in alto ha diametro piú piccolo del disco piú in alto sia di destinazione che di appoggio
POST:
- torre di n dischi piú in alto su sorgente é spostata su destinazione

if n-1 then
    sposta un disco da sorgente a destinazione
else
    HANOI(n-1, sorgente, appoggio, destinazione)
    sposta un disco da sorgente a destinazione
    HANOI(n-1, appoggio, destinazione, sorgente)
endif

DIV-REC(a,b)
- Pre: a >= 0, b > 0
- Post: q,r t.c. a == bq + r && 0 <= r < b
if a < b then
    q,r <- 0,a
else
    q',r <- DIV-REC(a-b,b)
    q <- q'+1
end if
return q,r

Schema dell’induzione semplice
1. Caso base P(1)
2. Passo induttivo P(m+1), P(m) é l’ipotesi induttiva
3. 1. e 2. implicano che \(\forall n \ge 1, P(n)\)

Schema dell’induzione completa
1. Caso base
2. Passo induttivo
3. Conclusione

Iterazione

Divisione Interativa:

DIV_IT(a,b)
while r >= b do
    r <- r-b
    q <- q+1
end while
return r,q

Si utilizzano le invarianti per la dimostrazione di correttezza

sempre vera:
- inizializzazione
- mantenimento
  - vale prima del ciclo -> vale anche dopo il corpo del ciclo

Va scelto in modo che sia utile per la dimostrazione di correttezza

Terminazione

T2 temporal prover

la non terminazione puó essere semplicemente causata da un errore logico
non terminazione implicita nel problema
- problema \(3n+1\)
  - Congettura di Collatz

É difficile dimostrare la terminazione se i parametri non decrescono in tutti i casi Spesso gli algoritmi diminuiscono la dimensione dei parametri, l’ampiezza dell’intervallo

Problema del Ordinamento - Sorting

Binary Search

aka Ricerca Dicotomica

dimezza la dimensione del problema ad ogni passo

BinSearch-Ric(x,A,i,j)
- Pre: A[i...j] ordinato
- Post: true se x appartiene A[i...j]
if i>j then
    return false
else
    m <- floor((i+j)/2)
    if x == A[m] then
        return true
    else
        if x<A[m] then
            return BinSearch-Ric(x,A,i,m-1)
        else
            return BinSearch-Ric(x,A,m+1,j)
        end if
    end if
end if

Casi

best: \(1\)
worst: \(log_2 n\)

Insertion Sort

per ordinare A[1...n]:

la parte A[1...i-1] giá ordinato
si puó inserire l’elemento A[i] nella parte ordinata tramite scambi
- se A[i] > A[i-1] -> A[1...i] é ordinato e ci si ferma; altrimenti si scambia A[i] con A[i-1]
- se A[i-1] > A[i-2] -> A[1...i] é ordinato; altrimenti si scambia A[i-1] e A[i-2]
- …

Si parte inserendo A[2] poi si prosegue fino a n

Insertion-Sort(A)
for i<-2 to length(A) do
    j<-i
    while j>1 and A[j-1]>A[j] do
        scambia A[j-1] con A[j]
        j<-j-1
    end while
end for
return A

Terminazione

assicurata dalla limitatezza dei cicli for e while

Correttezza

2 cicli -> 2 invarianti
1. A[1...i-1] é ordinato
  - corretto se il ciclo interno é corretto
2. A[1...j-1] e A[j...i] sono ordinati && A[1...j-1] \le A[j+1...i]
All’uscita dell’algoritmo abbiamo i uguale a n+1 che implica che tutto il vettore A[1...n] é ordinato

Complessitá

dipende da n e dalla distribuzione all’interno del vettore assegnamo un costo ad ogni riga dell’algoritmo e lo moltiplichiamo alle volte per cui é eseguito
1. for - n
2. <- - n-1
3. while - \(\sum_{i}^{n}{t_i-1}\)
  1. 1 nel caso migliore
  2. i nel caso peggiore
4. scambio - \(\sum_{i}^{n}{t_i-1}\)
Worst: \(an^2 + bn + c\) Nel caso peggiore Insert-Sort ha complessitá temporale quadratica Best: \(dn + e\) Nel caso migliore Insert-Sort ha complessitá temporale lineare

Selection Sort

Assumiamo che la parte sx del vettore sia giá ordinata e che contenga elementi <= di questa parte a dx

cerchiamo l’elemento minimo della parte dx e lo spostiamo in ultima posizione a sx (diminuendo la dimensione del problema)

Selection-Sort(A)
for i <- 1 to length(A)-1 do
    j <- i+1
    k <- i
    while j < length(A)+1 do
        if A[j] < A[k] do
            k <- j
        end if
        j <- j+1
    end while
    scambia A[i] e A[k]
end for
return A

Terminazione

Implicata dalla terminazione dei cicli

Correttezza

2 Invarianti
1. A[1...i-1] ordinato e A[i...n] <= A[1...i-1]
2. A[k] ≤ A[i...j-1]

Complessitá

Sia nel caso migliore che nel caso peggiore, Complessitá temporale quadratica

Alberi di Decisione

le foglie dell’albero devono essere tutte le possibili pormutazioni degli elementi del vettore

\(n!\)
per costruire un albero con un numero tale di foglie sono necessari almeno \(\log_2 n!\) livelli
Usando la formula di Stirling per approssimare \(n!\)
- \(n \log_2 n\)

Che cresce molto piú lentamente di una funzione quadratica

ció implica che esistano algoritmi molto piú efficienti di quelli quadratici visti

Complessitá di un algoritmo

Risorse utilizzate dall’algoritmo

tempo
spazio
hardware
- sempre piú importante con piú core e thread di esecuzione

Noi trattiamo la complessitá temporale

per stimare la grandezza massima dell’ingresso(input) di un esecuzione ragionevole
per confrontare l’efficienza di piú algoritmi
analisi asintotica

Il tempo di calcolo é una funzione rispetto all’input Gli approcci differiscono solo di una costante moltiplicativa (che puó essere quindi ignorata ai fini dell’analisi) sotto certe condizioni:

secondi di esecuzioni
numero di operazioni elementari
numero di volte una specifica operazione viene eseguita
- piú semplice

Una volta stabiliti i numeri di esecuzioni si passa all’analisi del caso migliore e del caso peggiore, si riconducono a polinomi

La dimensione dell’ingresso é una misura della sua rappresentazione

\(\mid m \mid \log_2 (m)+1\)
\(\mid A[0…n-1] \mid nc\)
- \(c\) numero bit del generico elemento di \(A\)
  - \(c = 1\) perché le costanti moltiplicative non contano dal punto di vista dell’analisi asintotica

Fissato la dimensione esistano algoritmi per cui \(T\) puó cambiare rispetto alla forma dell’input Distinguiamo i casi: migliore e peggiore

\(T_{peggiore}(n) \text{max}\{T()x\}: \mid x\mid n\)
\(T_{migliore}(n) \text{min}\{T()x\}: \mid x \mid n\)

Dobbiamo confrontare tra loro funzioni che hanno infiniti valori

si trascura il numero finito di casi, conviene scegliere la funzione che cresce piú lentamente all’infinito
- se non ci interessano questi casi, se abbiamo informazioni in piú allora vanno analizzati anche questi casi

Quanto contano le costanti?

con un computer molto piú veloce la dimensione massima trattabile cambia in maniera trascurabile
la funzione che cresce meno velocemente é comunque piú importante di una costante moltiplicativa per il calcolo della complessitá
inoltre la stima delle costanti é molto difficile nella pratica

O-grande

Definito da P. Bachman, 1892. \(f(n) \in O(g(n)) \iff \exists c > 0, n_0 \forall n > n_0 \mid f(n) \le cg(n)\) Un \(f(n)\) é O-grande di \(g(n)\) se e solo se \(f(n)\) cresce al piú come \(g(n)\) dopo un numero finito di casi \(n_0\) e eventuali costanti moltiplicative \(c\). Permette di specificare limiti superiori non stretti.

\(O(1)\)
- insieme delle funzioni superiormente limitate
  - la dimensione dell’input non ha impatto sul lavoro dell’algoritmo

Se \(p(n)\) é un polinomio di grado \(k\) allora \(p(k) \in O(n^k)\)

Definizione equivalente \(f(n) \in O(g(n)) \iff lim_{n \to \infty}\frac{f(n)}{g(n)}\) e \(0 \le lim_{n \to \infty} \frac{f(n)}{g(n)} < \infty\)

Teorema Utile \(\lim_{ n \to \infty}\frac{f(n)}{g(n)} = 0 \iff f(n) \in O(g(n)) \land g(n) \notin O(f(n))\)

NB
- nei polinomi ció che conta é il termine di grado piú alto: il grado del polinomio
- nei logaritmi non conta la base per O-grande
  - \(O(\log_a n) = O(\log_b n) \text{ con } a,b >1\)
Inclusioni
- \(O(1) \subset O(\log n)\)
- \(O(\log n) \subset O(n)\)
- \(O(n) \subset O(n \log n)\)
- \(O(n^p) \subset O(2^n)\)
- \(O(2^n) \subset O(3^n)\)

Il tempo di calcolo sufficiente alla risoluzione del problema é il suo confine superiore

confine superiore alla complessitá di un problema

Il tempo di calcolo necessario alla risoluzione del problema

confine inferiore alla complessitá del problema, per i tempi di calcolo di tutti gli algoritmi che risolvono il problema
banali
- dimensione del input
- dimensione del output
- eventi contabili

Omega

\(\Omega\) limite asintotico inferiore \(f(n) \in \Omega(g(n)) \iff \exists c > 0, n_0 \forall n > n_0 \mid cg(n) \le f(n)\) \(0< lim_{n \to \infty} \frac{f(n)}{g(n)} \le \infty\)

Teta

Θ limite asintotico sia inferiore sia superiore \(f(n) \in \Theta(g(n)) \iff \exists c_1 > 0,c_2 >0, n_0 \forall n > n_0 \mid c_1 g(n) \le f(n) \le c_2 g(n)\) \(f(n) \in \Theta(g(n)) \iff f(n) \in O(g(n)) \land f(n) \in \Omega (g(n))\) \(0< lim_{n \to \infty} \frac{f(n)}{g(n)} < \infty\)

o-piccolo

\(f(n) \in (g(n)) \iff \forall c > 0 \exists n_0 \forall n > n_0 \mid f(n) \le cg(n)\) \(f(n)\) é un infinitesimo di \(g(n)\)

Somma-17

Somma-17(V)
- Pre: V é un vettore che contiene numeri positivi
- Post: True se ci sono due numeri a,b t.c. a+b=17, False altrimenti

boolean b = False
for i=0 to length(V)-1
  for j=i+1 to length(V)-1
    if V[i] + V[j] == 17
      b = True
    end-if
  end-for
end-for
return b

\(O(n^2)\) per il numero di volte che viene eseguito l’if nel caso peggiore \(\Omega(n)\) per la dimensione dei dati

Soluzione di complessitá lineare

Somma-17-Lineare(V)

bool C[18]
int i, j
for i=0 to 17
  C[i] = False
end-for
for i=0 to length(V)-1
  if V[i] <= 17
    C[V[i]] = True
end-for
for i=0,j=17; i<j && !(C[i] && C[j]) do
  i++
  j--
end-for
return i < j

\(T_{Somma-17-Lineare}(n) \in O(18+n+9+1) \in O(n)\) Questo implica che l’algoritmo é ottimo in quanto \(\Omega(n)\) é confine inferiore del problema.

Minimo

\(cn + d \le T(n) \le an+b\)

contenuto tra funzioni lineari
- al piú lineare

Relazioni di Ricorrenza

La funzione tempo di un algoritmo ricorsivo é a sua volta ricorsiva: é detta Relazione di ricorrenza

Calcolo ricorsivo del fattoriale

\(T(n) = c \text{ se } n=0\) \(T(n) = T(n-1)+d \text{ altrimenti}\)

int min_ric(int a[], int i){
  if (i = length(a))
      return a[i];
  else
      return min(a[i], min_ric(a, i+1));
}

Nel caso dell’algoritmo della torre di Hanoi ci si riconduce ad una sommatoria di progressione geometrica. \(T(n)=c^n b + \frac{c^n - 1}{c - 1}d\) \(T(n) \subset \Theta(c^n)\)

Quick Sort

Sceglie un perno e riorganizza il vettore per avere elementi minori di \(q\) prima di questo e maggiori dopo. Ogni passo se necessario va partizionato il vettore.

int partition(int a[],int s, int n){
  int i=s;
  int j = n-1;
  while(i<=j){
    if(a[i] <= a[0])
      i++;
    else if(a[j] > a[1])
      j--;
    else {
      int temp = a[i];
      a[i] = a[j];
      a[j] = temp;
    }
  }
  int temp = a[j];
  a[j] = a[s];
  a[s] = temp;
  return j;
}

void quick_sort(int a[]){
  int n = length(a)-1;
  if(n>0){
    int p = partition(a,0,n);
    if(p>2)
      quick_sort(a,0,n);
    if(p<n-1)
      quick_sort(a,p+1,n);
  }
}

Per dimostrarne la correttezza va utilizzata l’induzione completa, non semplice.

in quanto la dimensione delle due chiamate ricorsive operano su dimensioni ignote minori di n elementi

Uno volta dimostrata la correttezza di partizione la dimostrazione é banale

Complessitá

Il partizionamento esamina una volta ogni elemento: é lineare \(T_p(n)=an\) Identifichiamo le situazioni estreme della ricorsione di quicksort
1. due partizioni con lo stesso numero degli elementi
2. una contiene tutti gli elementi e una é vuota
3. da luogo ad una relazione di ricorrenza
  - \(T(n) = c\) con \(n=1\)
  - \(T(n)= T(n-1)+T_p(n)+b\) altriment

Relazioni Lineari a Partizione costante

Teorema master per relazioni lineari in termini \(O()\), con \(a\) che rappresenta il numero di chiamate ricorsive. h: quanto diminuisce la dimensione del problema a: numero delle chiamate ricorsive b e c: quanto tempo impiegano le parti non ricorsive

\(a=1\): \(T(n)\subset O(n^{b+1})\)
\(a\ge 2\): \(T(n)\subset O(a^n n^b)\)

Il risultato dá meno informazioni rispetto alla sostituzione o l’iterazione, che dá informazioni rispetto a \(\Theta()\). Puó anche non fornire il limite piú stretto possibile.

Divide et Impera - Relazioni lineari a partizione bilanciata

Teorema \(T(n) = d \text{ se }n=1\) \(T(n) = aT(n/b)+cn^\beta \text{ se } n=1\) allora: posto \(\alpha = \log a / \log b\) \(\alpha > \beta\): \(T(n) \subset O(n^\alpha)\) \(\alpha = \beta\): \(T(n) \subset O(n^\alpha \log n)\) \(\alpha < \beta\): \(T(n) \subset O(n^\beta)\)

Minimo e Massimo

Merge Sort

Fondere array ordinati impiega molto meno tempo

int merge(int b[],int c[]){
  if (b == NULL)
    return c;
  else if(c == NULL)
    return b;
  else if(b[1] <= c[1])
    return {b[1],merge(b[2...length(b)],c)};
  else
    return {c[1],merge(b,c[2...length(b)])};
}

int merge_sort(int a[], int i, int n){
  if(n-i == 1)
    return a;
  else{
    int k = (n-i)/2;
    int b[] = merge_sort(a, 1, k);
    int c[] = merge_sort(a, k+1, n);
    return merge(b,c);
  }
}

Complessitá

\(T(n)=2T(n/2)+n\) \(T(n)=\log_2 n \cdot n \text{ . } cn \in \Theta(n \log n)\) L’algoritmo é ottimo.

Quick Sort: caso medio

Il caso peggiore é noto (quadratico), il caso migliore sará come il Merge Sort \(O(n \log n)\)

Si dimostra che é ottimo con \(O(n \log n)\)

Programmazione Dinamica

Si basano come i Divide et Impera sulla scomposizione ricorsiva di un problema in sottoproblemi per poi ricomporli

DI efficiente se i sottopreblemi sono indipendenti, altrimenti puó fare lo stesso lavoro piú di una volta
DI puó essere molto inefficiente se i sottoproblemi non sono indipendenti tra loro

Al contrario PD puó semplificare molto il problema.

Il problema deve possedere due proprietá

sottostruttura della soluzione
- la soluzione del sottoproblema e' un sottoinsieme del problema
sottoproblemi ripetuti
- una soluzione deve essere riutilizzabile in un altro sottoproblema
- annotazione dei risultati piu' semplici
  - Memoization
- per efficienza di memoria si sviluppa un approccio Bottom-up

Prima si sviluppa una soluzione iterativa, poi la si migliora con le tecniche della PD

Successione di Fibonacci

\(f_0 = 0 \text{, } f_1=1\) \(f_n = f_{n-2} + f_{n-1} \text{ per } n>1\)

Fib(n)
if n <= 2 then
  f = 1
else
  f = Fib(n-1) + Fib(n-2)
endif
return f

La relazione di ricorrenza del numero di nodi \(N_n\) nell’albero delle chiamate é simile a quella della sequenza di Fibonacci \(f_n\). Cambia per un +1. La formula di Binet permette il calcolo del ennesimo Fibonacci. \(N_n \subset \Omega(\phi^n)\) Quindi ha crescita esponenziale, almeno.

Molto lento perché é richiesto il calcolo della stessa cosa ripetutamente

perció implementiamo la memoization: approccio Top-down
- lo spazio utilizzato per migliorare l’algoritmo cosí é \(\Theta(n)\)

L’albero ha uno sviluppa lineare verso sinistra, anche il tempo sará \(\Theta(n)\)

Fib-BottomUp(n)
if n <= 2 then
  return 1
else
  Fib[1] = 1, Fib[2] = 1
  for i=3 to n do
    Fib[i] = Fib[i-1]+Fib[i-2]
  end-for
endif
return Fib[n]

Tempo e spazio sono \(\Theta(n)\)

L’array puó essere eliminato, servono solo gli ultimi due numeri

Fib-Iter(n)
if n <= 2 then
  return 1
else
  FibA = 1, FibB = 1
  for i=3 to n do
    tmp = FibA+FibB
    FibB = FibA
    FibA = tmp
  end-for
endif
return FibA

Il tempo di calcolo é sempre \(\Theta(n)\) ma lo spazio ora é \(\Theta(1)\)

Massima Sottosequenza Comune - LCS

Longest Common Subsequence es: Trattando Stringhe di DNA Non si intendono elementi necessariamente successivi

CS = sotto-sequenza / common-subsequence

Z é LCS se

Z cs X && Z cs Y && Z ha lunghezza massima

Proprietá della sottostruttura

mettere in relazione \(LCS(X,Y)\) con la soluzioni che coinvolgono prefissi di \(X\) e \(Y\)
definiamo \(k,m,n\) come lunghezze di \(Z,X.Y\)
due casi
- \(x_m = y_n\)
  - se \(Z\) é \(LCS(X,Y)\) allora \(z_k\) sará \(x_m\)
    - allora \(Z_{k-1}\) é \(LCS(X_{m-1},Y_{n-1})\)
- \(x_m \neq y_n\)
  - se \(Z\) é \(LCS(X,Y)\) allora \(z_k\) puó essere \(x_m\) o \(y_n\) o qualsiasi altro
    - sicuramente \(x_m\) o \(y_n\) non serve per formare \(Z\), anche entrambi
    - allora \(Z_{k-1}\) é \(LCS(X_{m-1},Y_{n})\) o \(LCS(X_{m},Y_{n-1})\) o entrambi

Teorema

se \(i=0 || j=0\)
- < >
se \(x_i = y_j\)
- \(LCS(X_{i-1}, Y_{j-1}) + x_i\) dove \(+\) indica la concatenazione
se \(x_i \neq y_j\)
- longest(\(LCS(X_{i-1},Y)\), \(LCS(X,Y_{j-1})\))

Il Tempo di calcolo di questa procedura ricorsiva é esponenziale: \(T(k)=2T(k-1)+1 \in \Theta(2^k) = \Theta(2^{m+n})\)

Si costruiscono due tabelle basate sullo schema ricorsivo \(c[0..m, 0..n]\) e \(b[1..m, 1..n]\)

Algoritmo Bottom-up

permette di ottimizzare riempiendo una tabella \(m \cdot n\) \(T(k) \in \Theta(m \cdot n)\)

Dan's Brain