Appunti di Algoritmi e strutture dati

ALGORITMI ITERATIVI

Insertion sort

È un algoritmo che serve per ordinare dei dati. Data una sequenza di numeri n l’output atteso è una

permutazione degli elementi tali che siano ordinati. L’Insertion Sort è come avere delle carte in mano e una

volta pescata una nuova carta la vogliamo inserire nella posizione corretta confrontandola quindi via via con

le altre singole carte.

CORRETTEZZA DI UN ALGORITMO

Un algoritmo si dice corretto se, per ogni istanza di input, termina con l’output giusto. Mostrare che un

algoritmo funziona con un certo input non è una dimostrazione di correttezza. Per algoritmi iterativi come

l’Insertion Sort si utilizza un invariante di ciclo, altrimenti si può procedere per induzione matematica.

Correttezza per induzione matematica () .

Lo scopo è quello di mostrare che una proprietà vale per qualsiasi

= { ∈ ∶ ()}

Prendendo U insieme universo:

• (1) (0)).

Passo base: dimostro che vale (o

• () ( + 1),

Passo induttivo: suppongo che valga per un generico e dimostro che vale anche per

∈ + 1 ∈

sapendo che se allora anche

Esempio: serie aritmetica n(n+1)

() = 1 + 2 + 3 + 4 + ⋯ + = 2

• () = 1

Passo base: dimostro che è vera per

1(1+1)

→ (1) = =1

2

• Passo induttivo: (+1)

• ( ( (n

( + 1) = 1 + 2 + ⋯ + + + 1) = () + + 1) = + + 1) =

2

(n+1)((n+1)+1)

= = P(n + 1)

2

() .

Quindi concludo che è valida per ogni

Correttezza tramite invariante di ciclo

L’invariante di ciclo è una proprietà per la quale devo dimostrare tre cose:

→

1. Inizializzazione è vera prima della prima iterazione del ciclo.

2. Conservazione → se è vera prima della prima iterazione rimane vera anche prima della i-esima

iterazione

3. Conclusione → deve essere vera anche alla fine del ciclo

Esempio: Svolgiamo l’esempio facendo riferimento all’algoritmo Insertion Sort.

Invariante di ciclo =”All’inizio di ogni iterazione del ciclo for, il sottoarray A[1...j-1] è ordinato ed è formato

dagli stessi elementi che erano originariamente in A[1...j-1], ma ordinati”

Dimostrazione:

• →

Inizializzazione è vera prima della prima iterazione perché inizialmente abbiamo j=2 e quindi

l’array A[1,j-1]=A[1,1] e quindi è ordinato e formato dagli stessi elementi originali.

• Conservazione → è vera perché all’inizio della j-esima iterazione l’array A[1…j-1] conteneva tutti i

valori j-1 ordinati, entro nel ciclo e sposto il j-esimo elemento quindi l’array A[1…j] è ordinato e non

contiene altri valori. Ù

• Conclusione → L’array A[1...n] è ordinato ed è formato dagli stessi valori originali.

COMPLESSITA’ DI UN ALGORITMO

È l’analisi delle risorse impiegate da un algoritmo per risolvere un problema, in funzione della dimensione e

del tipo di input. Queste risorse sono:

• Tempo per completare l’algoritmo.

• Spazio di memoria utilizzata.

• Banda, ovvero la quantità di bit spediti.

Il tempo viene condizionato da diversi fattori:

• bravura del programmatore.

• linguaggio di programmazione.

• codice generato dal compilatore.

• processore, memoria, sistema operativo, processi in esecuzione.

Per stimare il tempo necessario allo svolgimento di un algoritmo ci baseremo sul numero di operazioni

elementari.

ANALISI ASINTOTICA

In Informatica il calcolo asintotico è utilizzato per analizzare la complessità di un algoritmo ovvero per stimare

quanto aumenta al crescere della dimensione dell’input.

→

()

misura il numero dei comandi eseguiti dall’algoritmo in funzione della dimensione dell’input

()).

(analizzare la crescita di

Ci si concentra, quindi sulla risorsa TEMPO (tempo di esecuzione in funzione della dimensione dell’input).

Per determinare la il comportamento asintotico degli algoritmi importiamo alcune notazioni dalla

matematica:

• (o grande): ci consente di fornire delle delimitazioni superiori alla complessità di un algoritmo

• Ω (omega grande): fornisce delle delimitazioni inferiori

• (theta grande): fornisce delle delimitazioni strette, sia superiori che inferiori

NOTAZIONE ≥0 +

( ).

, : → () = (())

Siano Diciamo che se:

∃ , > 0

due costanti tali che:

0

≤ () ≤ () ≥

per ogni

(), ()

Significa che a meno di un fattore costante, cresce al più come

() ().

Quindi è un limite asintotico superiore per È come se dicesse

“peggio di così non puoi fare”.

Per calcolare si studia il caso peggiore dell’algoritmo.

NOTAZIONE ≥0 +

( ).

, : → () = Ω(())

Siano Diciamo che se:

∃ , > 0

due costanti tali che:

0

≤ () ≤ () ≥

per ogni

(), ()

Significa che a meno di un fattore costante, cresce almeno come

() (),

è un limite asintotico inferiore per è come se dicesse “la tua

funzione sta sopra quindi meglio di cosi non puoi fare”.

Ω

Per calcolare si studia il caso ottimo dell’algoritmo.

NOTAZIONE ≥0 +

( ).

, : → () = (())

Siano Diciamo che se:

∃ , , > 0

delle costanti tali che:

1 2 0

≤ () ≤ () ≤ () ≥

per ogni

(),

Significa che a meno di un fattore costante, cresce esattamente come

()

() (),

è un limite asintoticamente stretto per è come se dicesse che non

possiamo fare né peggio né meglio.

Per calcolare si studia il caso medio dell’algoritmo.

() = (()) () = (()) () = (())

Teorema →

Classi di complessità:

→

() complessità costante: per algoritmi che eseguono sempre lo stesso numero di operazioni

1 indipendentemente dalla dimensione dei dati

→

(), < complessità sottolineare: esempio ricerca binaria o ricerca logaritmica

→ per algoritmi che eseguono un numero di operazioni proporzionali ad n.

() complessità lineare:

2 Es: ricerca sequenziale

→

( ) es: algoritmi di ordinamento ottimi

2

→ )

( ≥ (

), es: bubble sort con

3 →

)

( complessità esponenziale

Esempio 1:

• 2 )

() = (

L’algoritmo A ha complessità (di tempo) 2

→

significa che A non richiede al più tempo per dare l’output.

• 2 )

() = (

L’algoritmo A ha complessità (di tempo) 2

→

significa che A richiede tempo almeno prima di fornire l’output.

Esempio 2:

Esempio 3 - Costo di Insertion-sort

L’istruzione avrà un costo e sarà ripetuta n volte,

1

perché si considera anche l’istruzione finale

Le istruzioni all’interno del for vengono eseguite n-1

volte perché non c’è l’iterazione finale

indica che si sommano tutti i tempi che ho per

ordinare gli n-1 valori che vano da A[2] ad A[n]

→

Linea impiega ()

()

Dipende dal e

−

dall’iterazione

Si può osservare che il ciclo while dipende da quanto è ordinato il vettore. Possiamo quindi considerare tre

casi:

• →

Caso migliore: si ha quando il vettore è completamente ordinato non entriamo mai nel ciclo while

→ = 1,

(A[i]≤key) si ha un costo di 1 in quanto eseguiamo solo un’iterazione che ci dice che non

dobbiamo entrare nel ciclo. =2

∑

( ( (

() = + − 1) + − 1) + 1 + − 1) =

→ 1 2 4 5 8

( ( ( (

= () = + − 1) + − 1) + − 1) + − 1) = ().

1 2 4 5 8

È quindi una funzione lineare.

• Caso peggiore: Si ha quando il vettore è ordinato al contrario (in senso decrescente), quindi avremo

che A[i]>key e quindi devo fare tutti i confronti tra key e i j-1 elementi alla sx di j. Si entra nel while

=2 2

→ ∑ )

= () () = (

per il numero massimo di volte si ha che e quindi .

2 2 →

) )

() = () + ( = ( ()

→ con è il costo dei termini senza sommatoria mentre

=2

2 ∑

)

( ()

è il costo di tutti i termini che hanno una sommatoria

• Caso medio: In questo caso avremo sempre una funzione quadratica di n, ma circa la metà del caso

peggiore.

ALGORITMI RICORSIVI

Sono definiti anche come algoritmi “divide et impera” in quanto sono svolti in tre fasi:

• Divide: in questa parte si procede alla suddivisione dei problemi in problemi di dimensione minore;

• Impera: nella seconda parte i problemi vengono risolti in modo ricorsivo. Quando i sottoproblemi

arrivano ad avere una dimensione sufficientemente piccola, essi vengono risolti direttamente

tramite il caso base;

• Combina: l'ultima fase del paradigma prevede di ricombinare l'output ottenuto dalle precedenti

chiamate ricorsive al fine di ottenere il risultato finale.

Rispetto agli algoritmi iterativi non presentano cicli al loro interno ma chiamate a loro stessi.

Se l’algoritmo è ricorsivo in coda (se la chiamata a sé stesso è l’ultima istruzione eseguita e ha al massimo

una chiamata ricorsiva) può essere trasformato in uno iterativo equivalete.

A questo punto posso applicare l’invariante di ciclo. Un esempio è il FATTORIALE:

Esempio: Il fattoriale È corretto? Si, lo dimostriamo con la definizione ricorsiva.

Quanto tempo impiega? Lo trovo tramite l’albero di ricorsione.

È corretto? Si, lo dimostriamo con l’invariante di ciclo.

Quanto tempo impiega? Ho solamente un ciclo su N valori, quindi costa N

Analizzare algoritmi divide et impera:

Il tempo di esecuzione totale è descritto da un’equazione di ricorrenza.

→ () =

tempo esecuzione per problema di dimensione

Equazione di ricorrenza:

≤ (1).

Se con qualche costante si ha il caso base che viene risolto in

/ () ()

Altrimenti si divide in sottoproblemi di dimensione questo mi costa per dividere e per

combinare.

Dopodiché per trovare la soluzione di una ricorrenza esistono tre metodi di soluzione riportati nelle pagine

seguenti. Sono il metodo di sostituzione, metodo dell’albero di ricorsione e metodo dell’esperto.

MERGESORT

Utilizza il paradigma DIVIDE ET IMPERA. Analizzare un algoritmo di questo genere significa utilizzare

un’equazione di ricorrenza per descrivere il tempo di esecuzione totale.

→

T(n) tempo esecuzione per problema di dimensione n;

In generale: per risolvere un problema di dimensione n in merge sort significa risolvere 2 problemi di

dimensione ½ + un tempo per dividere ((1)) + un tempo per combinare (())

Serve per ordinare un vettore A[p...r] agisce nel seguente modo:

• Divide A in A[p...q] e A[q+1...r]

• Impera ordinando ricorsivamente questi vettori

• Combina fondendo i due sottoarray ordinati in un singolo array ordinato

Importante: Non effettua un ordinamento sul posto

()

Complessità: (1)

C. costante:

(/2) // ci dice quanti sono gli elementi del 1° sottoarray

Tempo costante // ci dice quanti sono gli elementi del 2° sottoarray

Tempo

proporzionale a

= +

1 2

Tempo costante

n iterazioni, ciascuna

richiedente un tempo

⇒

costante Tempo

proporzionale a n (),

Tempo di esecuzione MERGE: si hanno n iterazioni nell’ultimo for (equivale a scansionare tutto il

/2)

vettore risultante di lunghezza per ordinare al suo interno i 2 vettori di dimensione

Tempo di esecuzione MERGE-SORT – METODO DELL’ESPERTO:

⇒ /2

Supponiamo che sia una potenza di 2 2 sottoproblemi di dimensione

• (1)

Caso base: n = 1, la complessità di merge-sort in questo caso è di

• Se n ≥ 2, i tempi per i passi divide et impera sono:

o ⇒ () = (1)

Divide: Calcola

o /2 ⇒ 2 · (/2)

Impera: Risolve 2 sottoproblemi di dim

o ⇒ () = (),

Combina: fonde un array con n elementi complessità del merge

• Equazione di ricorrenza:

Con il metodo dell’esperto si va a risolvere l’equazione di ricorrenza: () = (/) + ()

Il metodo dell’esperto fornisce una soluzione ad equazioni di ricorrenza fatte così:

() () = ())

Adesso si guarda la di merge-sort (sarebbe e si va a vedere quale caso del teorema

dell’esperto è più appropriato:

dato che abbiamo si ricade nel secondo caso del teorema che dice:

log −ϵ log

(n) = (n () = ( )

) allora:

1

→ → →

)

= 2, = 2 log 2 = 1 (n) = (n

Nel nostro caso siamo in questo caso

2 1

() = ( ) = ( )

Soluzione alla ricorrenza (complessità merge-sort):

Tempo di esecuzione MERGE-SORT – METODO DELL’ALBERO DI RICORSIONE:

Definendo la costante come il massimo tra il tempo di esecuzione per il caso base e il tempo per dividere e

combinare per ogni elemento.

La ricorrenza è la seguente: → ·

L’albero di ricorsione mostra espansioni successive partendo dal problema originario

/2 /2 + 2 (/4)

Ogni sotto-problema di dim costa sottoproblemi

Si continua ad espandere fino ad arrivare a problemi di dimensione 1:

· :

Ogni livello ha costo

• ·

1 livello:

• · /2(2 · · /2 = · )

2 livello: 2 sottoproblemi con costo

• · /4(4 · · /4 = · )

3 livello: 4 sottoproblemi con costo

→ costo per livello costante

+ 1 ),

Si hanno livelli (altezza: ad ogni livello dimezzo i dati:

•

Al livello si ha dimensione , la radice ha dimensione n

2

•

= 1 → = 2 → = =

Caso base (foglia) con un solo elemento: 2

2

Costo totale: ( + 1)

Il costo totale si ricava dall’albero di ricorsione che ha livelli ognuno dei quali costa quindi avrò

che il costo totale è: (

= ∗ ∗ + 1) → = ()

→

Esempio di mergesort

Correttezza di Merge – invariante di ciclo: [. . − 1] −

All'inizio di ciascuna iterazione dell'ultimo ciclo for, la sottosequenza contiene i elementi

[] []

più piccoli di ed ordinati. Inoltre, e sono i più piccoli elementi dei loro array a non essere stati

ricopiati in A →

Inizializzazione L'invariante è vero prima della prima iterazione:

(

= , [. . − 1] − = 0). [1] [1]

Per la sottosequenza è vuota e sono i più piccoli elementi dei loro

array a non essere stati ricopiati in

→

Conservazione Un’iterazione del ciclo conserva la verità dell'invariante:

• [. . − 1] −

contiene i elementi più piccoli di ed ordinati

• [] []

e sono i più piccoli elementi dei loro array a non essere stati ricopiati in

• [] ≤ [], [] [] ⇒ [. . ] − + 1

Se viene ricopiato in contiene i elementi più piccoli di

,

ed ordinati. Incrementando ed si ristabilisce l'invariante per la successiva iterazione

• [] < []

Analogo discorso se

→

Conclusione: L'invariante prova che l'algoritmo è corretto:

• = + 1, [. . − 1] [. . ])

Il ciclo termina quando quindi la sequenza (i.e., contiene i

(=

− − + 1)

elementi più piccoli di e ordinati

• − + 1 [. . ]

Gli elementi più piccoli di e coincidono con tutti gli elementi originariamente in

COMPLESSITÀ ALGORITMI RICORSIVI:

Studiare un algoritmo ricorsivo è più complicato:

• →

Correttezza se è possibile ritrasformarlo in un algoritmo iterativo per utilizzare l’invariante di ciclo

(questa cosa non è possibile con il merge sor