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)
• 2. Fattori che influiscono sul tempo:
• INPUT (dimensione);
• Qualità del codice scritto;
• Istruzioni disponibili nel linguaggio macchina;
• COMPLESSITÀ DELL’ALGORITMO: dipenderà anche dalla qualità del codice, dalle strutture utilizzate, etc… è funzione diretta della dimensione dell’input.

Commentato [AA1]: Il modello della macchina RAM è uno strumento classico per l'analisi delle procedure sequenziali. Questo modello è caratterizzato da una memoria ad accesso casuale formata da celle che possono contenere un intero qualsiasi; le istruzioni utilizzate sono quelle di un elementare linguaggio macchina che consente di eseguire istruzioni di input e di output, svolgere operazioni aritmetiche, accedere e modificare il contenuto della memoria, eseguire semplici comandi di salto.

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’input:

• 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 spazio occuperà durante l'esecuzione e quanto tempo richiederà prima di fornire la risposta.

Per poter studiare come aumentano il tempo e la memoria 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 espressioni servono per studiare quanto una funzione è simile ad un'altra, più conosciuta (si farà sempre riferimento a queste classi di funzioni: logaritmiche, polinomiali ed esponenziali

• 1. O (o grande): consente di fornire delle delimitazioni superiori alla complessità di un algoritmo (upper bound)

2n = O(n) è falso. n non può essere un limite superiore per n².

Dimostrazione per assurdo:

Se n² = O(n), allora devono esistere delle costanti c, n0 > 0 tali che 0 ≤ n² ≤ cn per ogni n ≥ n0, ossia (dividendo tutto per n) 0 ≤ n ≤ c per ogni n ≥ n0; il che è impossibile visto che c è 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 n0 > 0 tale che

• 1. 0 ≤ f (n) < cg(n) per ogni n ≥ n0

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. 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 ≥ n0

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.
• 5. (n²) costo quadratico: prende tutte le coppie di dati in input.

Esempio: ordinamento (bubble sort)

• 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 complessità

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 valutazione di uscita dal ciclo
• Analisi più grossolana: moltiplicare il costo di esecuzione di un’iterazione (caso peggiore) per il numero di iterazioni

Algoritmo bubble sort

For i=1 to a length -1 Do

For j – A length 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 dominata 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 = 12

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 nodo 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 per