Algoritmi e strutture dati

PROGRAMMA DEL CORSO

1. Concetti fondamentali e complessità degli algoritmi

2. Strutture dati elementari

3. Alberi

4. Grafi

5. Algoritmi di ordinamento

6. Tecniche di progettazione di algoritmi

INTRODUZIONE

Quando si scrive un programma l’obiettivo è risolvere un problema. Per fare ciò si devono seguire dei passaggi:

1. Formulazione del problema:

Per risolvere un problema è necessario conoscerlo e specificarlo nel migliore dei modi. Più sarà preciso,

più l’algoritmo potrà raggiungere l’obiettivo con qualità

2. Definizione della soluzione (dopo aver capito la richiesta del problema)

Quando un modello è stato formulato secondo un modello formale si cerca una soluzione in termini

di quel modello. L’obiettivo è quello di trovare una soluzione nella forma di un algoritmo.

3. Implementazione della soluzione

La soluzione deve essere scritta sotto forma di codice

4. Testare la soluzione e verificarne il corretto funzionamento

5. Valutazione della soluzione (se è sufficiente e risolve correttamente il problema)

ALGORITMI

Il termine “algoritmo” deriva dal latino algorithmus (La parola algoritmo deriva dal nome di "al-Khwarizmi",

importante matematico arabo del nono secolo).

Un algoritmo è una sequenza finita di istruzioni eseguibili e non ambigue, che giunge certamente a

terminazione. Un algoritmo deve avere una struttura ben stabilita in termini di ordine di esecuzione dei suoi

passi.

A partire da dati iniziali, le istruzioni sono applicabili in modo deterministico:

Un algoritmo è corretto rispetto un problema se produce il risultato corretto per tutte le possibili istanze del

problema, quindi se termina e produce come output un risultato che risolve il problema (per tutte le istanze

del problema).

Istanza di problema = caso specifico di problema, ottenuto quando il problema si riferisce ad uno specifico

input.

Esempio:

problema = ordinamento di un insieme di numeri

Input= 31, 41, 56, 29, 41, 58

Output= 29, 31, 41, 41, 56, 58

Si possono usare diversi algoritmi: bubble sort, insertion sort, quick sort,…

ADT = ABSTRACT DATA TYPE

Un tipo di dato è un insieme di valori che una variabile può assumere, una volta che quest’ultima è stata

dichiarata con quel tipo.

Un tipo di dati astratto (ADT) è una rappresentazione astratta di una struttura dati, un modello che specifica:

• Il tipo di dati memorizzati;

• Le operazioni che si possono eseguire sui dati, insieme al tipo di informazioni necessarie per eseguire

tali operazioni

Le ADT sono quindi un modo per rappresentare le informazioni e operare su di esse. Un ADT incapsula un tipo

di dato nel senso che la definizione di dato e tutte le operazioni relative sono localizzate in un determinato

segmento di programma. Se si vuole cambiare la definizione di un determinato ADT, modificare o aggiungere

operazioni, sappiamo dove guardare, e siamo sicuri che una eventuale modifica non altererà il

comportamento del programma che lo utilizza.

Es. lista di numeri interi

operazioni: svuotare la lista, prendere il primo elemento, prendere l’ultimo elemento, inserire un elemento,

etc…

Astratto “funzionalmente” indipendente dalle varie possibili implementazioni:

→

• Le operazioni applicabili l’interfaccia dell’ADT

• Un ADT può essere implementato in vari modi pur mantenendo la stessa interfaccia. Attraverso diverse

implementazioni si può ottenere lo stesso risultato

Uno svantaggio delle ADT è che diverse ADT non condividono le operazioni.

STRUTTURE DATI

Gli algoritmi lavorano su dei dati; input e output altro non sono che dati. Le strutture dati servono a dare un

ordine logico, per sapere come sono organizzate le informazioni.

Una Struttura Dati è anche un modo per organizzare un Insieme di Informazioni, con delle precise regole per

aggiungere o togliere elementi, passare da un elemento all'altro, individuare il primo o l'ultimo elemento ecc.

Una struttura dati è un modo sistematico di organizzare i dati utilizzati da un algoritmo. Dato che gli algoritmi

lavorano sui dati, se i dati sono ben organizzati un algoritmo funziona meglio.

La cella è la componente di base di una struttura dati (variabile, elemento che può contenere un valore).

Struttura dati combina diverse celle, associa un nome e gli dà un significato logico.

→

Esempi: strutture dati molto usate sono:

• Array= sequenza di celle che hanno la caratteristica di far riferimento tutte allo stesso tipo (anche non

di base, ADT definita dell’utente). Il contatore rappresenta il numero della cella;

• Record (struct) = collezione di celle (campi), che possono essere di tipo diverso. Le celle possono

contenere anche un puntatore (variabile il cui valore è un riferimento (indirizzo locazione memoria)

che permette di far riferimento ad una altra variabile);

• Liste, alberi, grafi, pile e code, etc…

STUDIO DELLA COMPLESSITÀ

Dato un problema, formalizzato e descritto, esistono diversi algoritmi in grado di risolverlo, quale scegliere?

Criteri di scelta:

1. Facilità di comprensione e implementazione (non misurabile in termini oggettivi);

2. Efficienza in termini di tempo (per trovare soluzione) e uso delle risorse.

Risorse =

1. Spazio in termine di memoria usata

2. Tempo = Mantenere basso il tempo di esecuzione è un criterio fondamentale

Per valutare la complessità temporale di un algoritmo, e capire qual è il più veloce, si devono fare delle

assunzioni:

1. L’algoritmo opera su una macchina RAM (non si considera il parallelismo delle operazioni) Commentato [AA1]: Il modello della macchina RAM è uno

strumento classico per l'analisi delle procedure sequenziali.

Questo modello è caratterizzato da una memoria ad accesso

2. Fattori che influiscono sul tempo: casuale formata da celle che possono contenere un intero

• INPUT (dimensione); qualsiasi; le istruzioni utilizzate sono quelle di un

elementare linguaggio macchina che consente di eseguire

• Qualità del codice scritto; istruzioni di input e di output, svolgere operazioni

• Istruzioni disponibili nel linguaggio macchina; aritmetiche, accedere e modificare il contenuto della

memoria, eseguire semplici comandi di salto.

• COMPLESSITÀ DELL’ALGORITMO: dipenderà anche dalla qualità del codice, dalle strutture

utilizzate, etc… è funzione diretta della dimensione dell’input.

Il tempo impiegato da un algoritmo si misura in genere, in funzione della dimensione dell’input. Se si considera

un algoritmo di ordinamento, si considera la lunghezza della serie da ordinare. (cosa succede al variare della

lunghezza dell’input, se scalano bene o male).

T(n) = tempo richiesto ad un algoritmo per produrre un output, data la dimensione n dell’input = computa il

numero, senza alcuna unità di misura, di istruzioni base (svolte direttamente dal processore) da eseguire sul

processore per eseguire l’algoritmo.

Il numero di istruzioni che devono essere eseguite dipende anche dal contenuto (valori), non solo dalla

dimensione dell’inut:

1. Caso peggiore: massimo numero di istruzioni (massimo tempo), data la dimensione dell’input;

2. Caso medio: caso più frequente (difficile da individuare);

3. Caso migliore: minimo numero di istruzioni (tempo minimo);

Tipicamente si stima la complessità nel caso peggiore, per avere un’analisi più precisa.

Non sempre si possono fare queste analisi, per esempio: for i:=0, i<n; i++. Non ha un caso peggiore o migliore,

dipenderà solo dalla lunghezza di n, perché il ciclo verrà eseguito n volte.

È importante valutare l’algoritmo al crescere di n, perché se l’algoritmo è scritto male è probabile che con il

crescere dell’input risulti infattibile.

COMPLESSITÀ ASINTOTICA Commentato [AA2]: bisogna valutare l'utilizzo di

memoria e di tempo da parte dell'algoritmo in funzione

dell'input.

Dato un algoritmo (corretto) per la soluzione di un problema, una domanda importante da porsi è quanto Per poter studiare come aumentano il tempo e la memoria

spazio occuperà durante l'esecuzione e quanto tempo richiederà prima di fornire la risposta. all'aumentare dell'input, bisogna rifarsi alla stima asintotica,

Complessità asintotica = ordine di crescita dell’algoritmo:

• Crescita del tempo di computazione al crescere della dimensione dell’input n;

• A priori non si conosce la dimensione dell’input, ma si vuole calcolare come cresce T(n) quando n

cresce

Annotazione asintotica = formalismo per esprimere quanto cresce T(n) al crescere di n; per esprimere il

tempo di esecuzione di un algoritmo.

Per determinare il comportamento asintotico degli algoritmi si fa riferimento ad alcune notazioni dalla

matematica: Commentato [AA3]: O (o grande), Ω (omega grande), Θ

(theta grande) sono le tre espressioni asintotiche che

utilizzeremo per studiare i diversi algoritmi. Queste

1. O (o grande): consente di espressioni servono per studiare quanto una funzione

fornire delle delimitazioni è simile ad un'altra, più conosciuta (si farà sempre

riferimento a queste classi di funzioni: logaritmiche,

superiori alla complessità di un polinomiali ed esponenziali

algoritmo (upper bound)

2

n = O(n) è falso. n non può essere

2

un limite superiore per n .

Dimostrazione per assurdo:

2

Se n = O(n), allora devono

esistere delle costanti c, n > 0 tali

0

2

che 0 ≤ n ≤ cn per ogni n ≥ n

0,

ossia (dividendo tutto per n) 0 ≤ n

≤ c per ogni n ≥ n il che `e

0;

impossibile visto che c `e una

costante.

• Ω (omega grande): fornisce delle delimitazioni inferiori (tight bound)

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

NOTA:

Ulteriori notazioni asintotiche:

o -piccolo: f (n) = o(g(n)) se per ogni costante c > 0 esiste n > 0 tale che

1. 0

0 ≤ f (n) < cg(n) per ogni n ≥ n 0

Le definizioni di O ed o sono molto simili: nella prima, la condizione 0 ≤ f (n) ≤ cg(n) vale per un qualche

c > 0 nella seconda, 0 ≤ f (n) < cg(n) vale per ogni c > 0. Con o piccolo la disuguaglianza deve valere per

ogni c. 2 2 2

2n=o(n ), ma non vale 2n =o(n )

w-piccolo: f (n) = ω(g(n)) se per ogni costante c > 0 esiste n0 > 0 tale che

2. 0 ≤ cg(n) < f (n) per ogni n ≥ n 0

Le definizioni di Ω ed ω sono molto simili: nella prima, la condizione 0 ≤ cg(n) ≤ f (n) vale per un qualche

c > 0 nella seconda, 0 ≤ cg(n) < f (n) vale per ogni c > 0

PROPRIETÀ NOTAZIONI ASINTOTICHE

Molte delle proprietà delle relazioni tra i numeri reali si applicano anche ai fronti asintotici. Supporre che

f(n) e g(n) siano asintoticamente positive: 1+sin n

Non tutte le funzioni sono asintoticamente confrontabili, per esempio le funzioni n e n non possono

essere confrontate mediante la notazione asintotica.

SCELTA DELL’ALGORITMO

Si sceglie sempre l’algoritmo con una complessità asintotica più bassa. Si considera sempre il caso peggiore,

e di solito si predilige l’annotazione asintotica dell’O. Per scegliere l’algoritmo più adatto si tengono in

considerazione diversi aspetti:

1. Complessità temporale: si preferisce l’algoritmo che nel caso peggiore presenta un O asintotico più

piccolo. 4 funzioni che risolvono lo stesso problema: si preferisce la funzione

logaritmica, perché, anche se all’inizio tra le varie funzioni è simile, si

guarda la complessità quando la dimensione dell’input.

Quindi anche se all’inizio la funzione esponenziale è più bassa di

quella logaritmica, con il crescere dell’input i problemi con

complessità esponenziale possono diventare irrisolvibili.

2. Complessità di spazio: in alcune situazioni si tiene conto anche dello spazio occupato;

3. Semplicità di comprensione dell’algoritmo.

CLASSI DI COMPLESSITÀ

1. (1) costo costante: indipendentemente dalla dimensione dell’input si comportano nello stesso modo,

la complessità non dipende dalla dimensione dell’input.

Esempio: leggere la prima posizione di un array: se si hanno tre elementi o trecento, non cambia nulla

2. (log n) Costo logaritmico: si guarda solo una parte dell’input per ottenere una soluzione al problema,

grazie all’organizzazione dei dati.

Esempio: algoritmi sugli alberi. dato un nodo all’interno di un albero si sa da che parte stanno i valori

più piccoli e quelli più grandi. Se devo trovare valore minore guardo solo una parte dei dati.

3. (n) Costo lineare: un ammontare costante di lavoro è applicato su ciascun elemento in input.

Esempio: lettura di tutti gli elementi di una lista/array

4. (n log n) Costo poli logaritmico: polinomio dove qualche fattore è moltiplicato per il logaritmo della

dimensione dell’input. Il problema viene diviso in sotto problemi.

2

5. (n ) costo quadratico: prende tutte le coppie di dati in input.

Esempio: ordinamento (bubble sort)

n

6. (2 ) costo esponenziale: processa tutte le possibili combinazioni dei dati in input (è il caso più costoso).

Esempio: problema del commesso viaggiatore (trovare percorso per consegna dei dati)

REGOLA DELLA SOMMA

Dati due algoritmi A1 con costo O(f(n)) e A2 con costo O(g(n)), quanto costa la loro esecuzione in sequenza?

Costo O(f(n)) + O(g(n)) = O(max (f(n), g(n))) vince il più grande.

→

Dimostrazione:

REGOLA DEI PRODOTTI

Dimostrazione:

REGOLE GENERALI PER IL CALCOLO DI COPLESSITÀ

Input di dimensione n:

• Assegnamenti, letture, scritture, somma, … O(1)

→

• Sequenza di operazioni sommare complessità delle diverse parti (prendere il max)

→

• Costrutto if-then-else costo di valutazione della condizione (O(1)) + costo del ramo più costoso

→

• Cicli: Analisi precisa: sommare il costo di valutazione di ciascuna iterazione + il tempo di

o valutazione di uscita dal ciclo

Analisi più grossolana: moltiplicare il costo di esecuzione di un’iterazione (caso peggiore) per

o il numero di iterazioni

ALGORITMO BUBBLE SORT

For i=1 to a leght -1 Do

For j – A leght down to i+1 Do

If A[j] < A[j-1]

Then T = A[j-1]

A[j-1] = A[j]

A [j] = T

A=4 elementi ={50, 70, 20, 40}

Cosa fa l’algoritmo:

Per riassumere:

• È stato eseguito 3 volte il ciclo esterno

• Prima iterazione: 3 volte ciclo interno

• Seconda iterazione: 2 volte ciclo interno

• Terza iterazione: 1 volta ciclo interno

Complessità dell’algoritmo: si parte delle istruzioni più interne:

Si tratta di tre assegnamenti, quindi hanno un costo costante: O(1)

O(1)+O(1) = O(1)

Costo sommatoria che va da 1 a n-i:

In modo meno preciso:

In questo caso il risultato è lo stesso, ma non sempre è così. N-1 diventa O(n) perché le costanti si possono non

considerare e tra n e 1 vince n (vale il maggiore). La condizione del for influisce con 1, quindi viene dominato

dal resto.

VALUTAZIONE DEL COSTO COMPUTAZIONALE

Se le funzioni non sono ricorsive si utilizza la proprietà della somma, altrimenti diventa più complicato

calcolarne la complessità.

Chiamante a funzioni/procedure:

• Non ricorsive = calcolo il costo della funzione e sommo il risultato al chiamante

• Ricorsive = equazioni di ricorrenza per esprimere la complessità

EQUAZIONE DI RICORRENZA

Equazioni di ricorrenza: equazione che esprime il costo computazionale di una funzione in termini di sé

stessa, valutata su un input più piccolo. T(n) espressa in termini di T(k) dove k<n. Come estrarre la funzione

ricorsiva dal codice:

Esempio fattoriale (n):

Per risolvere le equazioni di ricorrenza si possono utilizzare tre differenti metodi:

METODO DI SOSTITUZIONE

Fare un’ipotesi sulla soluzione dell’equazione e verificarla. È un metodo semplice e veloce, ma non sempre

applicabile, perché la definizione dell’ipotesi richiede esperienza e non è detto che si riesca a trovare.

Se applicata a posteriori, dopo aver risolto l’equazione con l’albero, controllare se la soluzione

funziona.

Esempio:

Supporre che l’ipotesi sia vera per input di dimensione n/2 (dimensione chiamata ricorsiva) e

verificare che valga anche per input di dimensione n.

(2 perché si hanno 2 chiamate ricorsive)

Come prima cosa semplificare il 2:

Semplificare il logaritmo:

La base del logaritmo non si scrive perché le costanti non sono importanti, quindi si può

cambiare quando si vuole la base del logaritmo. Se log 2 = 1

2

METODO DELL’ALBERO DI RICORSIONE:

Albero = struttura caratterizzata dalla presenza di un nodo radice. I nodi alla stessa distanza dalla radice

fanno parte dello stesso livello:

Come disegnare un albero partendo da un’equazione ricorsiva:

• Rappresentare ogni chiamata come un nodo (figlio del chiamante);

• Il nodo rappresenta il costo della chiamata senza tenere conto della ricorsione;

• Sommando il costo di tutti i nodi si ottiene la complessità della funzione ricorsiva, soluzione

all’equazione di ricorrenza.

Come sommare il costo dei nodi:

1. Calcolare quanto è grande un odo a livello i, si parte dal livello 0 (radice). Come definire il nodo in

termini del suo livello:

Livello 0 = nessuna divisione

Livello 1 = dividere pe