Algoritmi e strutture dati domande teoriche

[giacomovicinanza]

Salve a tutti. Questi sono gli ultimi esercizi che propongo sul forum. Ringrazio tutti coloro che mi hanno aiutato e mi scuso per avervi fatto perdere tempo XD

PRIMO QUESITO
"Indicare e commentare brevemente il tempo di esecuzione nel caso pessimo della ricerca
dell'elemento in un albero binario in cui in precedenza sono stati inseriti gli n-1 elementi:
1,2,3,4,5,...,n-3,n-2,n-1,n (cioè all'i-esimo inserimento è stato inserito l'elemento con il
valore i). Mostrare inoltre l'output di una visita pre-ordine in tale albero"

La ricerca binaria viene eseguita in tempo logaritmico nel peggiore dei casi, effettuando
confronti O(log n), dove n è il numero di elementi nell'array
Il tempo di esecuzione nel caso peggiore della ricerca è dovuto da O(log n) essendo dovuto
da alberi molto sbilanciati e profondi. Una visita in pre-ordine avviene in questo modo:
I. entro nel generico nodo n,ricevo dei parametri dalla procedura eseguita sul genitore
II. eseguo la computazione su n. mi avvalgo dei valori già computati sul genitore
III e IV. lancio la procedura sul figlio sinistro e destro. passo dei parametri alle
procedure eseguite sui figli
V. esco dal nodo n. restituisco un output alla procedura lanciata sul genitore

ordine di visita: n, n-1, n-2, n-3, ..., 5, 4, 3, 2, 1

SECONDO QUESITO
"Supponiamo che in una tabella hash a indirizzamento aperto siano stati
memorizzati n elementi e che la dimensione del bucket array sia m. Indicare
il tempo di esecuzione dell'algoritmo che stampa sullo standard output i valori
di tutti gli elementi presenti. Indicare, inoltre, il tempo di esecuzione
dell'operazione di ricerca nel caso ottimo"

tutti i record delle voci sono archiviati nell'array di bucket stesso. Quando è
necessario inserire una nuova voce, i bucket vengono esaminati, iniziando dallo
slot hash-to e procedendo in una sequenza di probe, fino a trovare uno slot
non occupato. Durante la ricerca di una voce, i bucket vengono scansionati nella
stessa sequenza, fino a quando non viene trovato il record di destinazione o viene
trovato uno slot dell'array inutilizzato, il che indica che tale chiave non è
presente nella tabella. Il nome "indirizzamento aperto" si riferisce al fatto che
la posizione ("indirizzo") dell'elemento non è determinata dal suo valore hash.
Il tempo di esecuzione nel caso ottimo è O(1). Infatti, dalla chiave si ottiene in
tempo costante la posizione del vettore nel quale è contenuta l’informazione da ricercare
'efficienza di una hash table dipende dalla frequenza delle collisioni che a sua volta
dipende dal rapporto fra
numero massimo di elementi e grandezza della tabella e dalle funzioni di hash utilizzate.

TERZO QUESITO
"Indicare il tempo di esecuzione dell'operazione di merge all'interno dell'algoritmo
Merge Sort quando le lunghezze delle due sequenze in input all'operazione di merge
sono n ed m"

Il vettore viene spezzato a metà ricorsivamente, fino ad arrivare a piccoli
blocchi di uno o due elementi. Successivamente tutti gli elementi, ordinati al
loro interno, sono fusi (merge) in un unico blocco grande (circa) il doppio.
Essendo le due sequenze hanno rispettivamente lunghezza n1 e n2:
• lo spazio necessario (oltre alle sequenze) è Θ(n1 + n2), per il vettore della sequenza;
• il numero di confronti eseguiti è Θ(n1 + n2) nel caso peggiore, e Θ(1) nel caso
migliore, quando una delle due sequenze contiene solo il valore minimo, quindi si
esaurisce immediatamente e l’altra sequenza viene copiata senza confronti;
• quando una delle due sequenze si esaurisce, non sono più necessari confronti, ma
bisogna comunque ricopiare tutti gli elementi dal vettore ad a (ordine generale del vettore), quindi il numero di
operazioni eseguite (tempo di calcolo) è Θ(n1 + n2) in ogni caso.

[apatriarca]

Quesito 1.
Prima di tutto ci sono $n$ elementi in $1, 2, 3, \ldots, n-1, n$. Un albero binario sbilanciato ha altezza nel caso peggiore uguale a $n$, non $\log n$. La spiegazione della visita pre-ordine mi sembra più confusa rispetto ad un altro post in cui l'avevi scritta, ma è corretta.

Quesito 2.
Non è stato fornito il tempo di esecuzione dell'algoritmo che stampa i valori di tutti gli elementi presenti. Hai scritto un sacco di informazioni nella tua risposta ma solo alcuni sono effettivamente rilevanti per la tua risposta.

Quesito 3.
Di nuovo molte informazioni sul merge sort che tuttavia non sono richieste. Ci sono alcune imprecisioni sulla parte importante alla risposta però:

• Nella tua risposta usi $n_1$ e $n_2$, ma nel quesito si usa $n$ ed $m$.
• Non mi è chiaro che cosa significa che una delle sequenze contiene solo il valore minimo e perché questo dovrebbe ridurre il confronto ad un numero costante. Direi che il caso migliore (che ha effettivamente un numero di confronti costante) si ha quando l'intervallo di valori delle due sequenze sono disgiunti e quindi una delle due sequenze precede l'altra nell'array finale. È tuttavia una ottimizzazione che non ho mai visto fare. Ho più spesso visto confrontare i valori fino a quando uno dei due array si esaurisce (e quindi il numero di confronti minimo in questo caso sarebbe uguale a $\min(n1, n2)$.

In linea generale l'impressione che dai è quella di avere imparato a memoria dei concetti che non hai necessariamente compreso. Credo sia poi sempre utile quando si parla di performance di qualcosa, scrivere lo pseudocodice di tale algoritmo. Ma non è detto che al tuo professore interessi.

[giacomovicinanza]

Per il secondo quesito:
Durante la ricerca di una voce, i bucket vengono scansionati nella
stessa sequenza, fino a quando non viene trovato il record di destinazione o viene
trovato uno slot dell'array inutilizzato, il che indica che tale chiave non è
presente nella tabella.
Il tempo di esecuzione nel caso ottimo è O(1). Infatti, dalla chiave si ottiene in
tempo costante la posizione del vettore nel quale è contenuta l’informazione da ricercare
La ricerca di un oggetto consiste nel visitare la sequenza di
scansione
hh(k, 0), h(k, 1), . . . , h(k, m − 1)i
a partire dall’inizio fino a che l’elemento cercato `e stato trovato
oppure una posizione libera `e stata trovata.
Data una tabella hash con fattore di carico $ alpha $ = n/m (n
numero di chiavi inserite, m dimensione della tabella), allora:
il tempo medio impiegato per una ricerca con successo è al massimo:
O(1 + $ alpha $)
Per il terzo quesito:
Essendo le due sequenze hanno rispettivamente lunghezza n e m:
• lo spazio necessario (oltre alle sequenze) è Θ(n + m), per il vettore della sequenza;
• il numero di confronti eseguiti è Θ(n + m) nel caso peggiore, e Θ(1) nel caso
migliore si ha quando l'intervallo di valori delle due sequenze sono disgiunti e quindi una delle due sequenze precede l'altra nell'array finale

[apatriarca]

La richiesta del secondo esercizio era di "Indicare il tempo di esecuzione dell'algoritmo che stampa sullo standard output i valori di TUTTI gli elementi presenti." Ho evidenziato io la parola TUTTI per mostrarti che non stai rispondendo alla richiesta dell'esercizio. Stai fornendo il tempo di esecuzione per trovare un singolo elemento, ma se devi stamparli tutti l'unico modo è quello di iterare su tutti i bucket e stampare il valore di quelli pieni. Quindi l'algoritmo itera su $m$ buckets e stampa $n$ elementi.

Sul terzo non ho nulla di nuovo da dire.

[giacomovicinanza]

Quindi il terzo è corretto?

[apatriarca]

L'operazione di merge ha senso anche all'esterno del merge sort o degli algoritmi di ordinamento. Considera per esempio il caso in cui hai due liste (ordinate) di eventi/appuntamenti (per esempio presi da due agende/calendari) e vuoi costruirne una sola. Oppure il caso in cui hai un database molto grosso suddiviso tra più macchine e vuoi ottenere un qualche risultato ordinato. Una soluzione consiste nell'ottenere un risultato ordinato su ogni macchina e poi fare un merge di tutti i risultati prima d'inviarli al client.

In linea di massima credo che la considerazione sullo spazio non faccia necessariamente parte dell'algoritmo di merge. L'algoritmo richiede sia possibile scrivere nella sequenza in uscita senza sovrascrivere quelle in ingresso. Negli esempi che ho fatto sopra si hanno sequenze completamente disgiunte per cui non è richiesto alcuno spazio aggiuntivo oltre a quello per le tre sequenze. Nel merge sort si vuole sovrascrivere lo spazio inizialmente occupato dalle due sequenze. Se si usano degli array questo non è ovviamente possibile (è invece possibile usando delle liste concatenate riordinando i nodi). Per questa ragione è necessario fare uso di memoria aggiuntiva uguale a \(\Theta(n)\). È infatti sufficiente copiare la prima sequenza su un array aggiuntivo perché la seconda non verrà sovrascritta dal merge (te lo lascio come esercizio capire perché).

La complessità temporale è uguale a \(\Theta(n + m)\) se il merge richiede la copia delle due sequenze e \(O(n + m)\) nel caso in cui avvenga in place. La copia delle due sequenze richiederà pur sempre un numero di operazioni lineare nelle sequenze d'ingresso per cui non c'è molto da discutere. Il confronto tra gli elementi delle due sequenze contribuirà solo nella variazione della costante. Se il merge avviene in place o facendo comunque uso di conoscenze su come sono scritte le sequenze d'ingresso è possibile fare meglio. Nel caso migliore per le liste concatenate doppie* (se le due sequenze sono disgiunte per cui una delle due precede totalmente l'altra) si potrebbe avere un tempo costante per il merge. Per gli array o liste concatenate semplici il meglio che si può fare è probabilmente di copiare solo la prima sequenza nella prima parte senza toccare la seconda sequenza. In questo caso si ha qualcosa come \(\Omega(n)\). Nota tuttavia che normalmente \(n \in \Theta(m)\) per cui alla fine in questo caso la complessità torna a essere \(\Theta(n + m)\)...

Ti consiglio di cercare di fare un po' più attenzione sulla notazione. \(O\), \(\Theta\) e \(\Omega\) non sono interscambiabili ma hanno ognuno un proprio significato (anche se spesso si usa solo \(O\) in modo forse un po' improprio). Detto questo non mi è chiaro lo scopo d'insistere con queste domande. Le domande all'esame saranno probabilmente diverse per cui è più importante comprendere i concetti e saperli usare in generale che imparare (a memoria?) delle risposte. I professori spesso lo capiscono se impari qualcosa a memoria...

* Deve essere possibile accedere in tempo costante all'ultimo elemento.