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 dal

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:

+1

2 (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 1

1 1

1 1

log + 1

1 !

log

0 !

log

0 !

/

/ log

0 !

0 log

!

1 1

1 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 1

n n

n – 1 n – 1

n – 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)

% = −1

2

) * !

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 = + − 3

2 2

2

# )

= θ(

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 1

1 n

n n – 1

n – 1 ! & '

! & '

" + − + 1.

" + − + 1.

# '

# ' ! & '

! & '

" + − .

" + − .

# '

# ' ! & '

0 " (2

[ − − 1)

]

% # ' n – 1

n – 1 3(n – 1)

0

Le sommatorie descritte da parte alla figura valgono:

$ % & ( − 1) 1

( (

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

2 2

' ( &

$ % & 1

(

" − ) = ( − 1)

2

' ( &

$ % & 1

(2

" [ − − 1)

] = ( − 1) − 2 ⋅ ( − 1) + − 1 = − 1

2

' ( &

Nel caso migliore, il tempo di esecuzione è: 7

1 1

() = 1 + n +