Algoritmi e Strutture dati

Algoritmi e strutture dati

Cambiago Silvia Anno Accademico 2021-2022 Prof. Alberto Dennunzio

Algoritmo

Un algoritmo è una sequenza finita di istruzioni non ambigue che, eseguita a partire da un insieme di dati, produce altri dati in un numero finito di passaggi.

I dati devono essere rappresentabili in modo finito, utilizzando quindi una quantità finita di informazione. Non si possono quindi ricevere in input dati non rappresentabili con un numero finito di cifre, come ad esempio π. Ciò però non va a limitare l’insieme dei possibili input, il quale può essere anche costituito da un numero infinito di elementi (es ℕ, ℤ). Non tutto l’insieme ℝ è, invece, un input idoneo, in quanto contiene anche i numeri irrazionali.

I dati prodotti sono in relazione con i dati a partire dai quali l’esecuzione viene applicata mediante una funzione (l’algoritmo deve essere quindi deterministico):

®f: I O (I = input, O = output)

Problema computazionale

Un problema computazionale prevede la presenza di un’istanza, ossia l’input necessario alla computazione della soluzione, e di quest’ultima, quindi l’output. Il testo del problema descrive in termini appartenenti al linguaggio comune la funzione che lega input e output.

Esempio

Problema: Eseguire l’ordinamento di un array di n elementi interi.

∈Istanza: x ℤ* () = ()() = (

Soluzione: () = sequenza vuota ≠ ()# ∀n ∈y deve essere una permutazione di x e y > y {1,…,n-1}n+1 n

Notazioni asintotiche

Sia g una funzione asintotica non negativa.

Il limite asintotico superiore, od O grande, è definito come:

((())) = { | ∃ , > 0 | ∀ > 0 ≤ () ≤ ⋅ ()}! ! ⋅

A partire da n , c g(n) è0 sempre più grande di f(n).

g(n) è limite asintotico superiore per f(n), il che vuol dire che f(n) cresce al più come g(n) a meno di un fattore costante. La funzione f(n) è detta “O grande” di g(n).

1

L’O grande è solitamente impiegato per descrivere la complessità del caso peggiore di un algoritmo, prendendo l’ordine più grande di una funzione polinomiale ignorando le costanti ® ∞).(trascurabili per n

Il limite asintotico inferiore, od omega, è definito come:

Ω((())) = { | ∃ , > 0 | ∀ > 0 ≤ ⋅ () ≤ ()}! ! ⋅g(n)

A partire da n , c è0 sempre più piccola di f(n). g(n) è limite asintotico inferiore per f(n), il che vuol dire che f(n) cresce almeno come g(n) a meno di un fattore costante. La funzione f(n) è detta “omega” di g(n).

Questa notazione è utilizzata per descrivere la complessità del caso migliore di un algoritmo.

Il limite asintotico stretto, o theta, è definito come:

θ((())) = { | ∃ , , > 0 | ∀ > 0 ≤ ⋅ () ≤ () ≤ ⋅ ()}" # ! ! " #

A partire da n , f(n) è0 sempre compresa tra ⋅g(n) ⋅g(n).c e c g(n) è1 2 limite asintotico stretto per f(n), il che vuol dire che f(n) cresce esattamente come g(n) a meno di un fattore costante. La funzione f(n) è detta “theta” di g(n).

Questa notazione è utilizzata per descrivere la complessità di tutti i casi di un algoritmo compresi tra quello migliore e quello peggiore.

Pseudocodice

Tipicamente, gli algoritmi vengono scritti in pseudocodice, linguaggio che esprime il significato ed il senso dell’algoritmo rimanendo indipendente dalla macchina su cui dovrà essere implementato, pur essendo sintatticamente simile ai principali linguaggi di programmazione.

Nella scrittura dello pseudocodice è necessario rispettare determinate convenzioni:

2

• Dato che non tutti i linguaggi di programmazione hanno la stessa modalità di rappresentazione degli operatori di confronto e assegnamento, si usa l’operatore = per il confronto e := per l’assegnamento;
• In caso siano presenti cicli, l’indentazione va a distinguere il corpo del ciclo dal resto dell’algoritmo;
• Nel ciclo for l’indice viene scritto subito dopo la keyword e, in caso questo si incrementi ad ogni iterazione, si scrive to prima del valore che indica l’uscita dal ciclo;
• L’istruzione di controllo del for si esegue n – i + 2 volte, quella del while n – i – 1.

Tempo di esecuzione ed efficienza

L’efficienza di un algoritmo è legata al tempo di esecuzione: minore sarà l’ordine di quest’ultimo, soprattutto considerando input di grandi dimensioni, più efficiente sarà l’algoritmo. Per calcolare la complessità di un algoritmo si usano le notazioni asintotiche viste nel paragrafo precedente, in quanto permettono di avere un’idea dell’efficienza dell’algoritmo considerando un caso peggiore (O grande), uno migliore (omega) ed uno medio (theta). Infatti, ovviamente, fissato un numero di dati in input, il tempo di esecuzione varia a seconda di quali dati vengono inseriti. Ad esempio, nel caso degli algoritmi di ordinamento, è chiaro che se gli elementi dell’array sono già ordinati il tempo di esecuzione sarà minore del caso in cui ci si trovi davanti ad un array ordinato nel senso contrario.

Tipicamente ci si interessa al caso medio, assumendo che ogni caso abbia la stessa probabilità di verificarsi, infatti la notazione asintotica prescelta è la theta. Il tempo di esecuzione è il lasso di tempo che impiega un algoritmo per completare tutta l'elaborazione e corrisponde al risultato della somma dei tempi di esecuzione delle singole istruzioni.

Ricerca sequenziale

La ricerca sequenziale, dato un valore chiave k da trovare in un array A di lunghezza n, esegue la scansione uno ad uno di tutti gli elementi di A per trovare k. Quando viene trovato un elemento uguale a k, il ciclo termina.

Di seguito lo pseudocodice ed una variante dell’algoritmo implementato su un array ordinato:

3

(1).

Nel caso migliore, quello in cui k sia il primo elemento di A, la complessità è Nel caso peggiore, quando l’elemento chiave è l’ultimo della sequenza oppure non è presente, la(), complessità è in quanto n sono i confronti da effettuare.

Per ottenere la complessità nel caso medio, si somma il numero di confronti da eseguire caso per caso: ( + 1)1 + 2 + 3 + ⋯+ = 2

e lo si divide per la lunghezza dell’array n, ne risulta:

+12 (n/2) (n).

La complessità nel caso medio è quindi =

Una rappresentazione grafica della ricerca sequenziale è la seguente:

Ricerca dicotomica

L’algoritmo di ricerca dicotomica è impiegato nella ricerca di un numero k all’interno di un array ordinato V di n elementi. Il processo di ricerca è effettuato dividendo ripetutamente a metà la sequenza. Se il numero cercato è minore dell’elemento in mezzo all’array, allora l’operazione viene ripetuta valutando la prima metà, se è maggiore verrà considerata la seconda.

Di seguito è mostrato lo pseudocodice della ricerca dicotomica:

4

Caso migliore Caso peggiore

1 11 11 1log + 11 !log 0 !log 0 !// log 0 !0 log !1 11 0//0 1

Vengono memorizzati gli elementi iniziale e finale della sequenza che si sta analizzando e si trova il centro ad ogni iterazione facendo la media tra essi.

Il caso migliore si ha quando l’elemento chiave si trova al centro e si effettua una sola iterazione.

Il tempo di esecuzione è quindi:

() = 1 + 1 + 1 + 1 + 1 + 1 = 6 = θ(1)

Il caso peggiore si verifica invece quando l’elemento cercato non è presente nella sequenza.

La lunghezza dell’array si dimezza ad ogni iterazione. Detto x il numero di iterazioni, la$lunghezza dell’array rimanente è . Nel caso peggiore tale valore è 1, quindi:

!#% Þ Þ() (2) () = 2 = ⋅ = # # #()

Il numero di iterazioni diventa quindi ed il tempo di esecuzione rimane:

#() () ()() = 3 + + 1 + 3 ⋅ + 2 = 4 ⋅ + 6 = θG()H# # #θ(()).

La complessità, di conseguenza, è

Di seguito un esempio grafico del funzionamento:

5

Insertion-sort

L’insertion-sort è un algoritmo che attua l’ordinamento di un array di lunghezza n inserito in input. Funziona come di seguito:

• Imposta il secondo valore dell’array come elemento chiave (key);
• Confronta key con il suo predecessore;
• Se key è minore dell’elemento precedente, viene confrontato con gli elementi ancora precedenti, fino all’inizio dell’array o finché non viene trovato un elemento minore di key;
• L’elemento chiave viene inserito nella posizione successiva al primo elemento minore trovato (oppure, in caso non ne fossero presenti, all’inizio);
• Key viene incrementato ed il ciclo prosegue finché non è stato iterato tutto l’array.

Di seguito è mostrato lo pseudocodice:

Caso migliore Caso peggiore

1 1n nn – 1 n – 1n – 1 n – 1!! ""1 # $# $ !0 " – 1% # $!0 " − 1% # $n – 1 n – 1

Il caso migliore è quello in cui l’array si presenta già ordinato: l’elemento k è già più grande di V[j] in tutti i casi. Di conseguenza il controllo del while viene eseguito una sola volta per ogni iterazione del for ed il corpo del ciclo while non viene mai eseguito.

Quindi il numero di ripetizioni dell’istruzione del controllo del ciclo while è:

(%1 = − 2 + 1 = − 1) * !

Il tempo totale di esecuzione (sempre considerando il caso migliore) rimane quindi:

() = 1 + n + n − 1 + − 1 + − 1 + − 1 = 5 − 3 = θ()

Nel caso peggiore, ossia un array ordinato in senso contrario, per ogni elemento in posizione i vengono eseguite i-1 iterazioni per portarlo nella posizione corretta, quindi il controllo del while viene eseguito i-1 volte più una finale per controllare l’uscita dal ciclo, quindi i volte. Il numero totale delle esecuzioni di tale istruzione è:

( ( + 1)% = −12) * !

Per quanto riguarda invece il corpo del ciclo while il ragionamento è analogo all’istruzione di controllo, meno la volta in cui si gestisce l’uscita, quindi:

6

( ( + 1) ( + 1)(% − 1 = − 1 − − 1) = −2 2) * !

Il tempo totale di esecuzione del caso peggiore risulta:

( ) 3 7 + 1 #() = 1 + n + n − 1 + − 1 + − 1 + ( + 1) − 2 + − 1 = + − 32 22# )= θ(

Nella figura seguente è mostrato un esempio grafico di implementazione dell’insertion-sort:

Selection-sort

Un algoritmo di ordinamento alternativo all’insertion-sort è il selection-sort, che ordina l’array cercando l’elemento minimo, piazzandolo all’inizio, e restringendo ad ogni iterazione la porzione di array in cui esegue la ricerca e la selezione. Lo pseudocodice è il seguente:

Caso peggiore

Caso migliore

11 nn n – 1n – 1 ! & '! & ' " + − + 1." + − + 1. # '# ' ! & '! & ' " + − ." + − . # '# ' ! & '0 " (2[ − − 1)]% # ' n – 1n – 1 3(n – 1)0

Le sommatorie descritte da parte alla figura valgono:

$ % & ( − 1) 1( (" − + 1) = − 1) − + − 1 = ( − 1) + − 12 2' ( &$ % & 1(" − ) = ( − 1)2' ( &$ % & 1(2" [ − − 1)] = ( − 1) − 2 ⋅ ( − 1) + − 1 = − 12' ( &

Nel caso migliore, il tempo di esecuzione è:

71 1() = 1 + n +