Appunti Algoritmi E Strutture Dati

Visita In Ampiezza

Partendo dall'algoritmo di visita generica e rappresentando l'insieme dei nodi aperti S mediante il tipo di dato Coda, otteniamo la visita in ampiezza. In questo algoritmo i nodi vengono visti per livelli: visito per prima la radice, poi i figli della radice, poi i figli dei figli e così via.

S = { A }

S non è vuoto, quindi estraggo u = A (primo della lista)

Prendo i figli del nodo, quindi S = {B C D}

S non è vuoto, quindi prendo il primo aggiunto u = B, e quindi S = { C D }

Accodo tutti i figli di B, quindi S = { C D E F G }

Continuo così fino a quando non ho visitato tutti i nodi del primo livello.

Avrò quindi, S = {E F G H I L M N O} e partendo da E, che è il primo aggiunto, li visito tutti. Non avranno figli, quindi li vado chiudendo fino ad ottenere S = { } finendo.

I nodi vengono visitati livello per livello. È una modifica dell'algoritmo di visita generico, solo

che S è una coda. Sapendo che S è una coda, ogni volta che inserisco un elemento lo accodo, quindi quando prendo un elemento prendo quello che è nella coda da più tempo. Esempio: Albero Blu S = {A} U = A allora S = {} Visito A S = {B C D} (Prima B, poi C, poi D. Il primo ad uscire sarà B) U = B allora S = {C D} Visito B S = {C D E F G} E così a continuare da C verso sx, accodando i nuovi figli. Strutture Dati Pagina 15 E così a continuare da C verso sx, accodando i nuovi figli. Strutture Dati Pagina 16 Ordinamento domenica 19 aprile 2020 15:55 Dato un insieme voglio ordinarlo. Vogliamo ordinare gli elementi perché la ricerca su insiemi ordinati ha costo O(log n). L'operazione rilevante è il confronto tra gli elementi, e non verranno usati operatori logici. Ci sono due tipi di ordinamento: Ordinamento In Loco: Se l'array ordinato è lo stesso dell'array in input. Ordinamento Non In Loco: Se per ordinare ho bisogno di un altro array.quindi instanzio un altro array che conterrà gli elementi dell'array in input ordinati. L'ideale sarebbe ordinare gli elementi in tempo lineare (Grafico Blu) però non è possibile perché avremo un costo O(n) solo per accedere agli elementi, e per ordinare ho bisogno di fare dei confronti tra tutte le possibili coppie. Facendo ciò il costo diventa O(n^2) (Grafico Rosso). O(n^2) è il costo di un algoritmo che confronta tutte le possibili coppie, e il costo O(n) lo avremo solo in un algoritmo che scandisce gli elementi. Un algoritmo con di ordinamento ottimale è un algoritmo che ha costo O(n^2logn) (Grafico Verde) che è maggiore di n ma di molto minore di n^2. O(n logn) è anche il minimo costo che possiamo ottenere da un algoritmo di ordinamento. Qualsiasi algoritmo di ordinamento ha costo Ω(n logn) cioè che ho sicuramente bisogno di almeno nlogn confronti. Albero Delle Decisioni: Dati un generico algoritmo A che

ordina usando dei confronti e un valore n che rappresenta il numero di elementi da ordinare, definiamo un albero, detto albero di decisione che illustra le diverse sequenze di confronti che A potrebbe fare su gli n elementi. Ogni nodo ha i due elementi del confronto, e ogni cammino descrive la sequenza di confronti ed il loro esito per l'esecuzione dell'algoritmo su un determinato insieme. Questo tipo di albero è un albero binario perché il confronto può avere solo due esiti. Se un nodo ha un solo figlio vuol dire che il confronto è già stato effettuato e quindi l'esito è già determinato.

Un esempio per n = 3 è: Ordinamento Pagina 17

Proprietà:

• Per una particolare istanza, la sequenza di confronti eseguiti dall'algoritmo A su quella istanza è rappresentata da un cammino dalla radice ad una foglia dell'albero di decisione
• Il numero di confronti fatti dall'algoritmo A nel caso peggiore è

Pari all'altezza dell'albero ovvero il cammino più lungo dalla radice a una foglia.

Il numero di confronti fatti dall'algoritmo A nel caso medio è pari all'altezza media dell'albero ovvero la lunghezza media dei cammini dalla radice a una foglia.

Un albero di decisione per l'ordinamento di n elementi contiene n! foglie.

Teorema: Sia T un albero binario in cui ogni nodo interno ha esattamente due figli e sia k il numero delle sue foglie. L'altezza di T è almeno log k2.

Dimostrazione Per Induzione:

Indichiamo con h(k) l'altezza di un albero binario con k foglie e dimostriamo che h(k) ≥ log k2.

Caso Base: k=1 --> h(0) = 0 perché ha un unico nodo che è foglia. Quindi 0 ≥ log 12.

Passo Induttivo:

≥h(i) ≤ ≥ log i per i ≤ k - 1 --> h(k) ≥ log k2 2 ≥

Se divido l'albero in due sottoalberi uno ha almeno metà foglie, quindi h(k) ≥ h( ≥ e quindi ≥ per l'ipotesi induttiva avremo che h( log2 ≥.

h(k) 1 + log cioè l'altezza totale è maggiore o uguale a 1 più l'altezza del sottoalbero.

Facendo dei semplici passaggi matematici otteniamo:

h(k) 1 + log ≥ ≥ ≥ ≥h(k) 1 + log ^k - log ² → h(k) 1 + log ^k - 1 → h(k) log ^k2 2 2 2 2

Teorema: Il numero di confronti necessari per ordinare n elementi è Ω(n logn) nel caso peggiore

Dimostrazione:

Il numero di foglie in un albero è n!, il numero di confronti nel caso peggiore è uguale all'altezza ≥ dell'albero quindi h(n!) log n!.

Sappiamo che n! per un n sufficientemente grande. Quindi:

log n! log ² ma sappiamo che log ² = log (2πn) + log ² = log 2π + log n + nlog n - nlog ² 2 2 2 2

La quantità maggiore è nlog n - O(n). Siccome l'altezza è il numero dei confronti avremo che l'altezza ≥ sarà Ω(n log n). Il costo è superiore a n log n, e quindi per n sufficientemente grande

Sarà à Ω(n² 2log n)
Qualsiasi algoritmo di ordinamento fa almeno nlogn
Se troviamo algoritmi di ordinamento che hanno costo O(n log n) saranno algoritmi ottimi perché
Upper Bound e Lower Bound coincidono.
Ordinamento Pagina 182
Algoritmi Di Ordinamento Con Costo O(n )
Sono algoritmi che ordinano in loco, ma hanno il peggior tempo di esecuzione. Alcuni di questi sono:
Selection Sort
Se i primi k elementi sono ordinati, cerco il minimo degli n-k elementi (elementi non ordinati) e lometto in posizione k+1 2
Teorema: L'algoritmo ordina in loco n elementi eseguendo nel caso peggiore θ(n ) confronti.
Analizziamone il costo:
Nel for più interno cerco il minimo tra gli elementi non ordinati e faccio n - (k+2) + 1 confronti(perché controllo da k+2 a n compresi). Quindi n - k - 1 confronti (svolgendo le operazioni).
Questi confronti li faccio al variare di k che varia da 0 a n - 2 (for esterno)
In definitiva il numero di confronti sarà:
Ponendo i = n - k -

1 otteniamo che per k = 0 --> i = n - 1 invece per k = n - 2 ---> i = 1. Invertendo gli estremi e riscrivendo la serie otteniamo: 2

Poiché esistono due costanti avremo che T(n) = θ(n ) Insertion Sort

Suppongo che i primi k elementi siano ordinati tra di loro ma non rispetto agli altri. Quindi, quello che l'algoritmo deve fare è prendere, di volta in volta, l'elemento k+1 e metterlo nella posizione che gli compete. Ordinamento Pagina 19

Il costo dell'algoritmo in termini di memoria è O(1) quindi costante perché ordina in loco

Teorema: l’algoritmo ordina in loco n elementi eseguendo, nel caso peggiore, θ(n ) confronti

Nella seconda parte dell'algoritmo dove spostiamo gli elementi non facciamo confronti. Invece incide sul costo il secondo for che fa k+1 confronti per n-1 volte (poiché annidato in un for più grande)

Quindi: 2

Quindi T(n) = O(n ) Bubble Sort

Ogni scansione confronta coppie di valori adiacenti e li scambia

se non sono ordinate. Ogni volta l'elemento maggiore viene spostato verso destra. A ogni iterazione mi fermo all'elemento n - i dove i è il numero di iterazioni e quindi il numero di massimi ordinati. Se dopo una scansione non viene fatto nessuno scambio vuol dire che l'array è ordinato.

Un esempio è:

Lemma: Dopo l'iesima operazione gli elementi con indice A[n-i+1],...,A[n] sono ordinati. Significa che:

∀h,k h ≤ k e anche n-i+1 ≤ k ≤ n → A[h] ≤ A[k] con 1 ≤ h ≤ k e anche n-i+1 ≤ k ≤ n → A[h] ≤ A[k] con 1 ≤ h ≤ k

Dimostrazione Per Induzione

Definiamo h = indice elemento da ordinare e k = indice elementi ordinati

Caso Base: i = 1, il valore massimo dell'array A è l'elemento A[n-i+1] = A[n]

Passo Induttivo

Supponiamo sia vero per i-1 scansioni e verifichiamo per la scansione i

Per l'ipotesi induttiva i = i-1 quindi andando a sostituire

otteniamo: ∀h,k h ≤ k e anche n-i+2 ≤ k ≤ n ---> A[h] ≤ A[k] e in particolare dopo l'i-esima iterazione il massimo valore dell'array è A[n-i+2], e quindi risulta che ∀h ≤ n-i+2 e quindi A[h] ≤ A[n-i+2] (Pag 46 Slides 6.Ordinamento) 2Teorema: l'algoritmo ordina in loco n elementi eseguendo, nel caso peggiore θ(n) confronti Nel secondo for vengono fatti n-i+1 confronti ma siccome il ciclo parte da 2 e c'è un if con un confronto i confronti sono n-i+1-2+1 = n-i. Questi confronti vengono ripetuti per n-1 volte (per il for esterno). Quindi: Ponendo j = n-i avremo che per i = 1 --> j = n - 1 e per i = n - 1 --> j = 1. Quindi invertendo gli estremi otteniamo Algoritmi Di Ordinamento Con Costo O(n logn) Sono algoritmi basati sul modello dei confronti HeapSort Questo algoritmo usa lo stesso approccio del selection sort, ma esegue nel caso peggiore un numero inferiore di confronti grazie all'uso di

strutture dati efficienti. Il problema cruciale per rendere velocel'ordinamento per selezione è quello di progettare una struttura dati che esegue efficientemente:

• Dato un array A genera velocemente un'istanza della struttura
• Trovare efficientemente un oggetto nella struttura
• Cancellare efficientemente un e oggetto nella struttura

La struttura che andremo ad usare si chiama HEAP

Un heap è un albero binario completo, almeno fino al penultimo livello (cioè che i nodi del penultimo livello possono avere un solo figlio o non averne). Gli elementi sono memorizzati nei nodi dell'albero, e ogni nodo memorizza un solo elemento (chiave(v)). Il valore dell'elemento in un nodo è sempre maggiore o uguale al