Ultimo aggiornamento: 2022-02-26
Consideriamo il problema seguente: è dato un array di interi v[] di lunghezza \(n \geq 1\). Tra tutti i sottovettori v[i..j] con \(0 \leq i \leq j < n\) vogliamo determinare quello la cui somma dei valori sia massima possibile. Con la notazione v[i..j] indichiamo la porzione di v compresa tra gli indici \(i\) e \(j\), estremi inclusi.
Esistono diverse soluzioni. In questo esercizio ne vengono proposte due: la prima è basata sulla “forza bruta” e consiste nel considerare tutte le combinazioni valide di \(i,j\) e per ciascuna calcolare il valore della somma del sottovettore v[i..j]. L’algoritmo che si ottiene ha costo costo asintotico \(\Theta(n^3)\).
La seconda soluzione agisce sempre per “forza bruta”, ma in modo leggermente più intelligente. Infatti, se abbiamo calcolato la somma \(s_{i,j}\) del contenuto del sottovettore v[i..j], allora la somma \(s_{i, j+1}\) del contenuto del sottovettore v[i..j+1] sarà
\[ s_{i, j+1} = s_{i,j} + v[j+1] \]
In altre parole, non serve ricalcolare le somme da zero: possiamo estendere i sottovettori aggiungendo un elemento, e riutilizzare la somma della porzione già esaminata per velocizzare il calcolo della nuova somma. L’algoritmo ha costo asintotico \(\Theta(n^2)\); si faccia riferimento al codice per i dettagli.
La funzione main() legge la lunghezza \(n\) come parametro sulla riga di comando, inizializza un array di lunghezza \(n\) e ne calcola il sottovettore di somma massima usando entrambi gli algoritmi. Vengono quindi stampati i valori delle somme (devono essere uguali) e i tempi di esecuzione in secondi.
Si lanci il programma con vari valori di \(n\) (es., da \(n=1000\) e \(n=5000\) con passi di \(500\), oppure altri valori più bassi che non richiedano troppo tempo sulla propria macchina) segnando i tempi di esecuzione, Si compili una tabella come quella che segue (i tempi sono puramente indicativi):
| \(n\) | Tempo |
|---|---|
| 1000 | 0.37 |
| 1500 | 1.26 |
| 2000 | 2.98 |
| 2500 | 5.77 |
| 3000 | 10.04 |
| … | … |
Per risultati più precisi è opportuno ripetere ciascuna misura più volte (es., 5 volte) e calcolare la media dei tempi. Rappresentare graficamente i tempi di esecuzione in funzione di \(n\) per verificare che crescano come \(n^3\) e \(n^2\), rispettivamente. Per realizzare i grafici si può usare un foglio di calcolo (Excel, Libreoffice Calc o equivalenti).
Usando i dati misurati, estrapolare i valori necessari a completare la tabella seguente:
| Tempo necessario per risolvere un problema di dimensione | Algoritmo \(\Theta(n^3)\) | Algoritmo \(\Theta(n^2)\) |
|---|---|---|
| \(n=1000\) | \(t=\ldots\) | \(t=\ldots\) |
| \(n=10000\) | \(t=\ldots\) | \(t=\ldots\) |
| \(n=100000\) | \(t=\ldots\) | \(t=\ldots\) |
Non bisogna misurare i tempi di esecuzione, dato che comunque con \(n=10000\) o \(n=100000\) l’algoritmo \(\Theta(n^3)\) richiederebbe troppo tempo. Si chiede invece di estrapolare i risultati ragionando come segue. Sia \(T(n)\) il tempo misurato (in secondi) richiesto dal programma \(\Theta(n^3)\) per risolvere un problema di dimensione \(n\). Possiamo scrivere che, asintoticamente, \(T(n)\) sia proporzionale a \(n^3\) con una certa costante \(\alpha\), cioè:
\[ T(n) \approx \alpha n^3 \]
Misurando \(T(n)\) per un valore “piccolo” di \(n\), ad esempio \(n=5000\) (qualunque altro valore va bene, purché non troppo piccolo), possiamo stimare \(\alpha\) come
\[ \alpha \approx \frac{T(5000)}{5000^3} \]
(Anche qui la misura dovrebbe essere ripetuta un certo numero di volte per ottenere una stima accurata). Una volta stimato \(\alpha\) siamo in grado di stimare \(T(n)\) per ogni \(n\) come:
\[ T(n) \approx \alpha n^3 = \frac{T(5000)}{5000^3} \times n^3 \]
Attenzione: il valore \(\alpha\) sarà diverso tra i due algoritmi, quindi occorre misurarlo separatamente per ciascuno dei due.
Supponiamo ora di avere un certo tempo a disposizione, e chiediamoci qual è la dimensione massima del problema risolvibile da ciascuno dei due algoritmi nel tempo assegnato.
Possiamo usare la formula empirica appena derivata. Considerando l’algoritmo \(\Theta(n^3)\), sia \(\alpha\) la costante moltiplicativa determinata sopra. Da
\[ T(n) \approx \alpha n^3 \]
possiamo derivare \(n\) dato \(T(n)\) risolvendo l’equazione in funzione di \(n\):
\[ n \approx \left( \frac{T(n)}{\alpha} \right)^{1/3} \]
Nel caso dell’algoritmo \(\Theta(n^2)\) si ragiona in modo analogo. Si compili la Tabella 3 con i valori stimati.
| Dimensione problema risolvibile in tempo \(T(n)\) | Algoritmo \(\Theta(n^3)\) | Algoritmo \(\Theta(n^2)\) |
|---|---|---|
| 1 secondo | \(n=\ldots\) | \(n=\ldots\) |
| 1 ora | \(n=\ldots\) | \(n=\ldots\) |
| 1 giorno | \(n=\ldots\) | \(n=\ldots\) |