Problemi computazionali e algoritmi

Problema computazionale

Un problema computazionaleSpecifica di cosa si vuole ottenere, indipendente dal modo di ottenerlo. $\Pi$ è un insieme di coppie $(i, s)$ con $i \in I$ (istanza, dominio delle istanze) e $s \in S$ (soluzione, dominio delle soluzioni). Si richiede che ogni istanza abbia almeno una soluzione: $\Pi \subseteq I \times S$.

Due osservazioni: una soluzione può servire a più istanze (la somma $10$ vale per $(1,9)$ e per $(4,6)$) e un'istanza può avere più soluzioni (nella v. 2 con chiavi ripetute, più permutazioni ordinano lo stesso array). In quel caso l'algoritmo ne calcola una.

Algoritmo e modello di calcolo

Un algoritmo $A$ risolve $\Pi$ se, ricevuta in input un'istanza $i \in I$, produce in output una soluzione $s$ con $(i, s) \in \Pi$: calcola una funzione che a ogni istanza associa una sua soluzione. I passi sono quelli elementari di un modello di calcolo.

Il modello usato è la macchina RAMRandom Access Machine: input, output, dati intermedi e programma stanno in memoria, e ogni accesso a una cella costa un passo. Non c'entra la memoria RAM del PC.: i passi elementari sono assegnamento, operazioni logiche e aritmetiche, indicizzazione di array, restituzione di un valore da un metodo; ciascuno costa $\Theta(1)$.

Gli algoritmi si scrivono in pseudocodice: costrutti di un linguaggio ad alto livello (for, while, if, ricorsione) mescolati a linguaggio naturale, senza dettagli di tipi o sintassi. Negli esami si richiede sempre di specificare input e output dell'algoritmo prima del corpo.

Taglia di un'istanza

La taglia è una funzione che associa a ogni istanza uno o più numeri che ne misurano la grandezza: la lunghezza di un array, il numero di nodi di un albero, il numero di vertici e archi di un grafo ($n$ ed $m$). La complessità si esprime in funzione della taglia (vedi Complessità in tempo e caso pessimoPerché lo studio sperimentale non basta; complessità al caso pessimo come massimo sul numero di operazioni tra le istanze di una data taglia; stima con limiti superiore e inferiore senza trovare l'istanza peggiore; esempi arrayMax, prefixAverages e InsertionSort; efficienza asintotica e limiti dell'analisi.Complessità in tempo e caso pessimo →).

Strutture dati e ADT

Un algoritmo organizza i dati in una struttura dati: collezione di oggetti con metodi per accedervi e modificarla. Due livelli:

1. ADT (tipo di dato astratto): specifica il tipo dei dati, le operazioni ammesse e i loro parametri, cioè cosa fa ogni operazione e non come. Si descrive con un'interfaccia.
2. Struttura dati concreta: l'implementazione dell'ADT (una classe in Java, un insieme di struct e funzioni in C), che fissa come agiscono le operazioni e quindi il loro costo. Vedi Liste, pile e codeRipasso degli ADT elementari: lista index-based (array) e position-based (lista doppiamente concatenata con sentinelle), pila LIFO, coda FIFO, deque, iteratori; interfacce, implementazioni e costi; array estendibile e coda circolare.Liste, pile e code →.

Esempio svolto: cercare in un array ordinato

Problema. $I$: coppie ($A$ array crescente di $n$ interi distinti, $x$ intero). $S$: un indice $i$ con $A[i] = x$, oppure $-1$ se $x$ non c'è.

Ricerca lineare. Scorre tutto l'array: nel caso peggiore $x$ manca e si fanno $n$ confronti, $\Theta(n)$.

Ricerca binaria. Si sfrutta l'ordine: si confronta $x$ con l'elemento centrale e si scarta metà dell'intervallo.

Algoritmo ricercaBinaria(A, n, x)
Input: array crescente A[0..n-1] di interi distinti, intero x
Output: indice di x in A, oppure -1
lo <- 0; hi <- n - 1
while lo <= hi do
    mid <- floor((lo + hi) / 2)
    if A[mid] = x then return mid
    if A[mid] < x then lo <- mid + 1
    else hi <- mid - 1
return -1

• Invariante: se $x$ è in $A$, allora la sua posizione sta in $[lo, hi]$. Vale all'inizio ($[0, n-1]$ è tutto l'array) e si conserva: se $A[mid] < x$, per l'ordine $x$ può stare solo a destra di $mid$.
• Complessità: l'intervallo dimezza a ogni iterazione, quindi ci sono al più $\lfloor \log_2 n \rfloor + 1$ iterazioni di costo costante: $O(\log n)$.

Traccia su $A = [2, 5, 8, 12, 16, 23, 38]$, $x = 23$: $lo=0, hi=6, mid=3$ ($12<23$) $\to lo=4$; $mid=5$, $A[5]=23$, restituisce $5$.

Errori comuni

• Confondere problema e algoritmo: il problema dice cosa, l'algoritmo come; per lo stesso problema esistono più algoritmi.
• Dimenticare di dichiarare input e output nello pseudocodice, o scegliere una taglia ambigua (per un grafo servono $n$ e $m$).
• Scrivere $mid = (lo + hi)/2$ senza la parte intera: gli indici devono essere interi.