Problemi computazionali - istanze, soluzioni, correttezza e complessità

In questa pagina 3

Il capitolo fissa il linguaggio con cui tutta la materia descrive un algoritmo: che cosa deve fare (il problema), che cosa fa (l'algoritmo), se lo fa bene (correttezza) e quanto costa (complessità). Sono richiami più formali di Problemi computazionali e algoritmi, Complessità in tempo e caso pessimo e Notazione asintotica di Dati e Algoritmi, che si danno per noti.

Algoritmo e problema computazionale

Definizione (algoritmo). Un algoritmo è una procedura computazionale finita e deterministica, specificata come sequenza di passi elementari (istruzioni) di un dato modello computazionale, che trasforma un ingresso in una e una sola uscita. Dal punto di vista insiemistico un algoritmo è una funzione $A : \mathcal{I} \to \mathcal{O}$ dall'insieme degli ingressi a quello delle uscite. La particolare funzione realizzata è descritta dalla sequenza finita di istruzioni.

Il modello computazionale è l'astrazione di un calcolatore e del suo insieme di istruzioni (nel corso: la RAM con pseudocodice, come in Dati e Algoritmi).

Definizione (problema computazionale). Un problema computazionale è una specifica astratta della relazione tra un insieme di istanze $I$ e un insieme di soluzioni $S$ : $\Pi \subseteq I \times S, \qquad \Pi = \{(i_1, s_1), (i_2, s_2), \dots\}.$ Si scrive anche $i \,\Pi\, s$ per $(i, s) \in \Pi$ . La relazione deve essere:

totale: ogni istanza ha almeno una soluzione, $\forall i \in I,\ \exists s \in S : (i,s) \in \Pi$ ;

non necessariamente univoca: possono esistere $s_1 \neq s_2$ con $i \,\Pi\, s_1$ e $i \,\Pi\, s_2$ .

Il problema è un oggetto logico (una relazione), indipendente dal modo di risolverlo. L'algoritmo ne è una funzione: quando l'istanza ha più soluzioni, l'algoritmo ne sceglie una sola.

Definizione (algoritmo che risolve un problema). Un algoritmo $A_\Pi : \mathcal{I} \to \mathcal{O}$ risolve $\Pi$ se $\mathcal{I} = I$ , $\mathcal{O} = S$ e $\forall i \in I : \quad A_\Pi(i) = s \ \Longrightarrow\ i \,\Pi\, s.$

Osservazione (codifica). Identificare ingressi e uscite dell'algoritmo con istanze e soluzioni astratte è una semplificazione: $\mathcal{I}$ e $\mathcal{O}$ sono in realtà codifiche di $I$ e $S$ compatibili con il modello di calcolo (per $I = \mathbb{N}$ si può prendere l'insieme delle stringhe binarie). La distinzione si richiama solo quando serve, per esempio per la taglia di un intero (più sotto).

Esempi di problemi

Somma di due interi. $I = \mathbb{Z} \times \mathbb{Z}$ , $S = \mathbb{Z}$ , $\Pi = \{((a,b), c) : c = a + b\}$ . Qui la relazione è una funzione (ogni istanza ha una sola soluzione).

Raggiungibilità in un grafo diretto. Un grafo diretto è $G = (V, E)$ con $V \subseteq \mathbb{N}$ finito ed $E \subseteq V \times V$ . Un cammino è una sequenza $\pi = \langle v_1, \dots, v_k\rangle$ , $k \ge 1$ , con $(v_j, v_{j+1}) \in E$ per $1 \le j < k$ ; esiste anche il cammino degenere $\langle v_1 \rangle$ , senza archi. Il problema chiede un cammino da $u$ a $v$ , se esiste:

$I = \{\langle G, u, v\rangle : u, v \in V\}$ ;
$S = \{\langle v_1, \dots, v_k\rangle : k \ge 1\} \cup \{\epsilon\}$ , dove $\epsilon$ è la sequenza vuota e significa "non esiste";
$\Pi$ contiene $(\langle G,u,v\rangle, \pi)$ se $\pi$ è un cammino da $u$ a $v$ , e $(\langle G,u,v\rangle, \epsilon)$ se nessun cammino esiste.

Qui la relazione non è univoca: tra $u$ e $v$ ci possono essere più cammini, e tutti sono soluzioni valide.

Ordinamento di sequenze di interi. La stella di Kleene $A^\star$ di un insieme $A$ è l'insieme di tutte le sequenze finite, vuota compresa, di elementi di $A$ ; $\varepsilon = \langle\rangle$ ha lunghezza $0$ . Allora $I = S = \mathbb{Z}^\star$ e $\langle x_1,\dots,x_n\rangle \,\Pi\, \langle y_1,\dots,y_m\rangle \iff \begin{cases} (1)\ n = m \\ (2)\ y_1 \le y_2 \le \dots \le y_n \\ (3)\ \exists\, \varphi : \{1..n\} \to \{1..n\}\ \text{biunivoca},\ y_i = x_{\varphi(i)}. \end{cases}$ I vincoli (1) e (2) dicono che la soluzione è una sequenza ordinata della stessa lunghezza, il (3) che è una permutazione degli elementi dell'istanza. Qui $S$ contiene anche sequenze non ordinate: non è richiesto che ogni elemento di $S$ sia in relazione con qualche istanza. Si potrebbe restringere $S$ alle sole sequenze ordinate, $S' = \{\langle y_1..y_n\rangle : y_1 \le \dots \le y_n\}$ , e il vincolo (2) diventerebbe implicito.

Radici quadrate di un numero complesso non nullo (domanda tipica di prima parte). L'istanza è un numero complesso $z \ne 0$ : $I = \mathbb{C} - \{0\}$ . Ogni $z \ne 0$ ha due radici quadrate distinte, $w$ e $-w$ , entrambe diverse da zero. Se la soluzione è la coppia delle due radici, $S = (\mathbb{C} - \{0\}) \times (\mathbb{C} - \{0\}) = (\mathbb{C} - \{0\})^2$ , e $\Pi = \{(z, (w, -w)) : w^2 = z\} \subseteq I \times S.$ Le soluzioni effettivamente usate stanno nel sottoinsieme $S' = \{(w, -w) : w \ne 0\} \subset S$ . Anche qui $\Pi$ non è univoca: per $z = -1$ sono soluzioni sia $(i, -i)$ sia $(-i, i)$ , perché la coppia è ordinata. Le altre alternative del test non vanno: $S = \mathbb{C} - \{0\}$ conterrebbe una sola radice (è il problema "trova una radice"), $I = (\mathbb{C}-\{0\})^2$ avrebbe coppie in ingresso, e $\mathbb{C}^+$ non descrive i numeri complessi non nulli.

Analisi di un algoritmo

Di ogni algoritmo si studiano correttezza e complessità (in tempo e a volte in spazio, cioè la memoria necessaria).

Definizione (correttezza). Provare che $A_\Pi$ è corretto per $\Pi$ significa dimostrare $\forall i \in I : A_\Pi(i) = s \ \Longrightarrow\ i \,\Pi\, s.$ Informalmente: la funzione di ingresso e uscita realizzata dall'algoritmo è coerente con la specifica.

Lo strumento principale è l'induzione: sulla taglia per gli algoritmi ricorsivi (Divide and conquer - proprietà di sottostruttura e albero delle chiamate), sugli invarianti per quelli iterativi (Dimostrazioni, induzione e invarianti).

Definizione (modello di costo). Un modello di costo associa a ogni istruzione del modello computazionale un costo non negativo $c_{\text{istr}} \in \mathbb{R}^+ \cup \{0\}$ . Il costo dell'esecuzione di $A_\Pi$ sull'istanza $i$ è $t_{A_\Pi, i} = \sum_{\text{istruzioni eseguite da } A_\Pi(i)} c_{\text{istr}}.$

Nel corso si usano costi unitari o nulli: essendo interessati all'ordine di grandezza, si ignorano le costanti e si conta solo il tipo di istruzione che si ritiene dominante. La scelta va fatta con giudizio, perché da lei dipende se l'analisi è significativa:

aritmetica su interi in binario: le operazioni elementari tra bit;
aritmetica su matrici di numeri complessi: le operazioni aritmetiche tra numeri complessi;
ordinamento: il confronto tra due chiavi.

I conteggi esatti che si incontrano nel corso (per esempio $n - 1$ confronti per il massimo di $n$ elementi) valgono nel modello in cui si è dichiarato quale istruzione costa $1$ e quali costano $0$ .

Definizione (taglia). La taglia di un'istanza, $\lvert i\rvert \in \mathbb{N}$ , è una misura intera non negativa ragionevolmente rappresentativa della grandezza della codifica dell'istanza.

Non è una definizione rigorosa: la taglia si sceglie volta per volta.

Due interi $z_1, z_2$ : il numero totale di bit per rappresentarli.
Sequenza di $n$ interi da ordinare: $n$ .
Due matrici quadrate $n \times n$ : indifferentemente $n$ oppure $n^2$ (numero di elementi di una matrice), perché entrambe descrivono bene la grandezza.

Si pone $I_n = \{i \in I : \lvert i\rvert = n\}$ . Poiché $t_{A,i}$ varia da un'istanza all'altra, lo si riassume con una funzione $T_A : \mathbb{N} \to \mathbb{R}^+ \cup \{0\}$ della sola taglia:

Definizione (tre complessità).

Caso peggiore: $T_A(n) = \sup_{i \in I_n} t_{A,i}$ .

Caso migliore: $T_A(n) = \inf_{i \in I_n} t_{A,i}$ .

Caso medio: $T_A(n) = \mathbb{E}[t_{A,i}]$ , media rispetto a una distribuzione fissata su $I_n$ .

Il caso peggiore è conservativo (limita il costo di qualsiasi esecuzione di taglia $n$ ) ed è quello usato di default nel corso. Il caso migliore di solito dice poco; il caso medio è molto difficile da stimare in teoria ma può essere prezioso in pratica.

Esempio (ricerca lineare). Cerco $x$ scandendo un array di $n = 10$ elementi distinti, costo unitario per ogni confronto $A[k] = x$ :

python

def lineare(A, x):
    confronti = 0
    for v in A:
        confronti += 1
        if v == x:
            break
    return confronti

A = list(range(10))
print(lineare(A, 0))                                  # caso migliore: 1
print(lineare(A, -1))                                 # caso peggiore (assente): 10
print(sum(lineare(A, x) for x in A) / len(A))         # medio, x presente e uniforme: 5.5

Caso migliore $1$ (l'elemento è il primo), caso peggiore $n$ (l'elemento è l'ultimo o manca), caso medio $(n+1)/2$ se $x$ è in posizione uniforme: $\frac{1}{n}\sum_{k=1}^{n} k = \frac{n+1}{2} = 5{,}5$ .

Esempio (la taglia di un intero conta). Per decidere se un intero $m$ è primo, la divisione per tentativi esegue circa $\sqrt{m}$ divisioni (per $m = 1\,000\,003$ , che è primo, ne servono $999$ ). Se come taglia si prende $m$ stesso, il costo è $\sqrt{m}$ ; ma la taglia della codifica binaria è $b = \lceil\log_2 m\rceil$ bit, e in funzione di $b$ il costo è $\approx 2^{b/2}$ : esponenziale nella taglia. Un algoritmo che sembra radice quadrata è dunque esponenziale rispetto alla grandezza dell'ingresso. Lo stesso accade quando $n$ è il numero da calcolare e non la lunghezza di una sequenza: lo si ritrova nel conteggio del calcolo memoizzato di una ricorrenza in Esercizio - funzione g(n) definita per ricorrenza, calcolo memoizzato e formula chiusa (compito del 19 giugno 2024, es. 2).

Sommario: che cosa specificare

Per analizzare correttamente un algoritmo $A_\Pi$ bisogna sempre dire:

quali sono le istruzioni a costo unitario;
che cosa si intende per taglia $\lvert i\rvert$ ;
quale complessità si studia (per default: tempo, caso peggiore).

Il passo seguente è ottenere $T(n)$ per gli algoritmi ricorsivi, cioè scrivere e risolvere una ricorrenza: Divide and conquer - proprietà di sottostruttura e albero delle chiamate.

Domande d'esame

Sia $\Pi$ il problema dell'estrazione delle radici quadrate di un numero complesso non nullo. Si definiscano $I$ e $S$ . Risposta: $I = \mathbb{C} - \{0\}$ , $S = (\mathbb{C}-\{0\})^2$ (la coppia delle due radici, ciascuna non nulla); $\Pi \subseteq I \times S'$ con $S' = \{(w,-w)\}$ . Vedi Esercizio - domande di prima parte su problemi computazionali, ricorrenze e conteggi (simulazioni d'esame).
Un problema computazionale è una funzione? Che relazione c'è con l'algoritmo? Risposta: no, è una relazione totale e non necessariamente univoca; l'algoritmo è una funzione che a ogni istanza associa una sola delle sue soluzioni.
Che cosa si deve specificare prima di dichiarare "l'algoritmo costa $T(n)$ "? Risposta: istruzioni a costo unitario, taglia dell'istanza e tipo di complessità (caso peggiore, migliore o medio).

Versione ripasso

Algoritmo = funzione $A:\mathcal I\to\mathcal O$ , finita e deterministica; problema $\Pi\subseteq I\times S$ : relazione totale ( $\forall i\,\exists s$ ) e non necessariamente univoca. $A_\Pi$ risolve $\Pi$ se $\mathcal I=I$ , $\mathcal O=S$ e $A_\Pi(i)=s\Rightarrow i\,\Pi\,s$ : da una relazione estrae una funzione. $\mathcal I,\mathcal O$ sono codifiche di $I,S$ .
Esempi: somma ( $I=\mathbb Z^2$ , $S=\mathbb Z$ , funzione); raggiungibilità (cammino da $u$ a $v$ oppure $\epsilon$ , non univoca); ordinamento ( $I=S=\mathbb Z^\star$ , vincoli: stessa lunghezza, ordinata, permutazione); radici quadrate di $z\ne0$ : $I=\mathbb C-\{0\}$ , $S=(\mathbb C-\{0\})^2$ , $S'=\{(w,-w)\}$ , non univoca perché la coppia è ordinata.
Correttezza: $\forall i\in I: A_\Pi(i)=s\Rightarrow i\,\Pi\,s$ ; per induzione (ricorsivi) o con invarianti (iterativi), vedi Dimostrazioni, induzione e invarianti.
Costo: $t_{A,i}=\sum c_{\text{istr}}$ con costi $0$ o $1$ sulle istruzioni dominanti (confronti per ordinare, operazioni complesse per matrici complesse, bit per interi). Taglia $\lvert i\rvert$ scelta con giudizio ( $n$ per sequenze, $n$ o $n^2$ per matrici, numero di bit per interi).
Casi: peggiore $\sup_{i\in I_n}t_{A,i}$ (default), migliore $\inf$ , medio $\mathbb E$ . Ricerca lineare su $n$ elementi: $1$ , $n$ , $\frac{n+1}2$ .
Taglia di un intero: divisione per tentativi $\approx\sqrt m=2^{b/2}$ divisioni con $b$ bit: esponenziale nella taglia.
Sommario: specificare istruzioni a costo unitario, taglia, tipo di complessità.
Errori tipici: dire che $\Pi$ è una funzione; scegliere $S=\mathbb C-\{0\}$ per le due radici; contare tutte le istruzioni invece delle dominanti; confondere il valore $m$ con la taglia $\log_2 m$ in bit.
Raggiungibilità: $I=\{\langle G,u,v\rangle\}$ , $S$ = sequenze di nodi $\cup\{\epsilon\}$ ; $\Pi$ contiene $(\langle G,u,v\rangle,\pi)$ per ogni cammino $\pi$ da $u$ a $v$ (anche il cammino degenere $\langle v_1\rangle$ ) e $(\langle G,u,v\rangle,\epsilon)$ se non ce ne sono: più cammini, quindi relazione non univoca.
Ordinamento: $I=S=\mathbb Z^\star$ (stella di Kleene); $\langle x_1..x_n\rangle\,\Pi\,\langle y_1..y_m\rangle\iff n=m,\ y_1\le\dots\le y_n,\ \exists\varphi$ biunivoca con $y_i=x_{\varphi(i)}$ . Non serve che ogni elemento di $S$ sia in relazione con un'istanza; in alternativa $S'$ = sole sequenze ordinate e il vincolo $y_1\le\dots\le y_n$ diventa implicito.
Costo e taglia, scelte tipiche: interi in binario $\to$ operazioni su bit, taglia = bit; matrici complesse $\to$ operazioni su complessi, taglia $n$ o $n^2$ ; ordinamento $\to$ confronti, taglia $n$ . Le complessità si leggono come funzioni $T:\mathbb N\to\mathbb R^+\cup\{0\}$ con ordine di grandezza in Notazione asintotica e Complessità in tempo e caso pessimo.
Ricerca lineare ( $n=10$ , costo = confronti): migliore $1$ , peggiore $10$ (assente), medio $5{,}5=\frac{n+1}2$ .
Domande tipiche: definire $I$ ed $S$ per le radici quadrate (quarta alternativa, risposta in Esercizio - domande di prima parte su problemi computazionali, ricorrenze e conteggi (simulazioni d'esame)); dire che cosa specificare per analizzare un algoritmo (istruzioni a costo unitario, taglia, tipo di complessità).