Problemi computazionali e algoritmi

In questa pagina 6

Problema computazionale

Definizione (problema computazionale). Un problema computazionale $\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, cioè che per ogni $i \in I$ esista almeno un $s \in S$ con $(i, s) \in \Pi$ . Le coppie stanno in $I \times S$ , quindi $\Pi \subseteq I \times S$ . Il simbolo $I \times S$ è il prodotto cartesiano dei due insiemi (vedi Operazioni tra insiemi): $\Pi$ ne è un sottoinsieme, cioè una relazione tra istanze e soluzioni. Se ogni istanza avesse una sola soluzione, $\Pi$ sarebbe il grafico di una funzione da $I$ a $S$ ; qui si ammette il caso più generale, con più soluzioni possibili per la stessa istanza.

Esempio. Per la somma di interi (gli insiemi numerici sono in Insiemi numerici (N, Z, Q, R)) l'istanza $(3,4)$ ha come soluzione $7$ , e $(1,9)$ e $(4,6)$ hanno la stessa soluzione $10$ .

Problema	$I$	$S$	$\Pi$
somma di interi	coppie $(x, y)$	$\mathbb{Z}$	$((x,y), s)$ con $s = x + y$
ordinamento (v. 1)	array di interi $A$	array ordinati $B$	$(A, B)$ con $B$ permutazione ordinata di $A$
ordinamento (v. 2)	array di interi $A$	permutazioni $P$	$(A, P)$ con $P$ che ordina $A$

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$ (una sequenza finita di passi elementari, come i cicli di calcolo di Fondamenti di Informatica) 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.

Definizione (macchina RAM). Il modello usato è la macchina RAM: i passi elementari sono assegnamento, operazioni logiche e aritmetiche, indicizzazione di array, restituzione di un valore da un metodo; ciascuno costa $\Theta(1)$ (la notazione è in Notazione asintotica: significa "un numero di operazioni limitato da una costante che non dipende dalla taglia dell'input"). Il modello rispecchia un vero elaboratore, in cui processore e memoria leggono o scrivono una cella con una sola istruzione e la memoria è indirizzabile per posizione; i casi in cui questa semplificazione non regge (accessi lenti fuori dalla cache) sono in Gerarchia di memoria e principio di località.

Esempio. A[i] <- A[i] + 1 è una indicizzazione, una addizione e un assegnamento: tre passi elementari, in tutto $\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

Definizione (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 pessimo).

Esempio. La taglia di un array di $n$ interi è $n$ ; quella di un grafo è la coppia $(n, m)$ di vertici e archi.

Strutture dati e ADT

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

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.
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 code. Il concetto di tipo di dato astratto è introdotto in Tipi di dato astratti; due implementazioni già viste in Fondamenti di Informatica sono Liste concatenate e Pila e coda.

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 (vedi Ricerca lineare e binaria): nel caso peggiore $x$ manca e si fanno $n$ confronti, uno per elemento, quindi $\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

Proprietà (ricerca binaria: invariante e complessità)

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 crescente tutti gli elementi in posizione $\le mid$ valgono al più $A[mid] < x$ , quindi $x$ può stare solo a destra di $mid$ e si pone $lo \leftarrow mid+1$ ; il caso $A[mid] > x$ è simmetrico. Al termine del ciclo ( $lo > hi$ ) l'intervallo è vuoto, quindi per l'invariante $x$ non c'è in $A$ e si restituisce $-1$ . Il metodo dell'invariante è spiegato in Dimostrazioni, induzione e invarianti.

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)$ .

Perché proprio $\lfloor \log_2 n \rfloor + 1$ . Sia $m = hi-lo+1$ il numero di posizioni ancora candidate. Se $x$ non è in $mid$ , l'elemento centrale è scartato e si tiene una delle due metà restanti, al più la più grande, che ha $\lfloor m/2 \rfloor$ elementi. Dopo $k$ iterazioni restano quindi al più $\lfloor n/2^k \rfloor$ candidati, e il ciclo termina quando ne restano $0$ . Vale $\lfloor n/2^k \rfloor = 0 \iff n/2^k < 1 \iff 2^k > n \iff k > \log_2 n$ (il logaritmo è l'inverso dell'esponenziale: Esponenziale e logaritmo). Il più piccolo intero $k$ con $k > \log_2 n$ è $\lfloor \log_2 n \rfloor + 1$ . Controllo: per $n=7$ è $\lfloor 2{,}81 \rfloor + 1 = 3$ , per $n=8$ è $3+1=4$ , per $n=100$ è $6+1=7$ (confermato simulando la ricerca su ogni possibile $x$ ).

Esempio. Su $A=[2,5,8,12,16,23,38]$ con $x=23$ la ricerca binaria restituisce l'indice $5$ dopo $2$ iterazioni; con $n=7$ ne servono al più $\lfloor\log_27\rfloor+1=3$ .

Traccia su $A = [2, 5, 8, 12, 16, 23, 38]$ , $x = 23$ :

iterazione	$lo$	$hi$	$mid=\lfloor (lo+hi)/2 \rfloor$	$A[mid]$	confronto con $x=23$	effetto
1	0	6	$\lfloor 6/2 \rfloor = 3$	12	$12 < 23$	$lo \leftarrow 4$
2	4	6	$\lfloor 10/2 \rfloor = 5$	23	uguale	restituisce $5$

Il grafico confronta il numero massimo di passi della ricerca lineare, $n$ , con il massimo $\lfloor \log_2 n \rfloor + 1$ della binaria: già a $n=100$ sono $100$ contro $7$ .

Grafico interattivo: Passi al caso pessimo: ricerca lineare, n, contro ricerca binaria, floor(log2 n)+1 iterazioni; a n = 100 sono 100 contro 7

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.

Versione ripasso

Problema $\Pi\subseteq I\times S$ : coppie (istanza, soluzione), con almeno una soluzione per ogni istanza (vedi Operazioni tra insiemi, Funzioni - definizione, dominio e grafico). Esempio: nella somma $(3,4)$ ha soluzione $7$ , mentre $(1,9)$ e $(4,6)$ hanno soluzione $10$ . Se un'istanza ha più soluzioni, l'algoritmo ne calcola una.
Algoritmo $A$ risolve $\Pi$ se, per ogni istanza $i$ , produce $s$ con $(i,s)\in\Pi$ . Modello di calcolo: la RAM, dove assegnamento, operazioni aritmetico-logiche, indicizzazione di array e return costano $\Theta(1)$ ciascuno (vedi Struttura di un elaboratore).
Pseudocodice: costrutti di alto livello (for, while, if, ricorsione); input e output si dichiarano sempre.
Taglia dell'istanza: lunghezza di un array, numero di nodi di un albero, $n$ ed $m$ per un grafo. La complessità si esprime in funzione della taglia (vedi Complessità in tempo e caso pessimo).
ADT e struttura dati: l'ADT specifica cosa fanno le operazioni; la struttura concreta fissa come e quindi il costo (vedi Liste, pile e code, Tipi di dato astratti).
Ricerca lineare in un array crescente: nel caso peggiore $n$ confronti, $\Theta(n)$ (vedi Ricerca lineare e binaria).
Ricerca binaria: lo <- 0; hi <- n-1; while lo <= hi: mid <- floor((lo+hi)/2); if A[mid] = x return mid; if A[mid] < x then lo <- mid+1 else hi <- mid-1; return -1.
Invariante: se $x$ è in $A$ , la sua posizione sta in $[lo,hi]$ . Vale all'inizio; si conserva perché l'ordine crescente esclude la metà scartata; a fine ciclo ( $lo>hi$ ) l'intervallo è vuoto, quindi $x$ non c'è (vedi Dimostrazioni, induzione e invarianti).
Costo: al più $\lfloor\log_2 n\rfloor+1$ iterazioni, perché dopo $k$ iterazioni restano al più $\lfloor n/2^k\rfloor$ candidati; quindi $O(\log n)$ . Per $n=7$ sono $3$ , per $n=100$ sono $7$ .
Traccia su $A=[2,5,8,12,16,23,38]$ , $x=23$ : $mid=3$ ( $A[3]=12<23$ , $lo\leftarrow4$ ), poi $mid=5$ con $A[5]=23$ : restituisce $5$ .
Errori tipici: confondere problema e algoritmo; non dichiarare input e output; $mid=(lo+hi)/2$ senza parte intera.