Appunti Algoritmi e strutture dati

Lezione 1 (29.09.2020)

Il termine algoritmo spesso viene utilizzato in modo inappropriato : è una sequenza finita di passi

che consentono di risolvere un determinato problema.

La sequenza è finita perché l’algoritmo deve terminare e trovare la soluzione del problema in un

tempo finito. Riceve in ingresso un insieme di valori e fornisce in uscita un insieme di valori.

Un dato problema, può avere infinite istanze : il problema dell’ordinamento, è quello di ordinare

una sequenza di valori, ovviamente esso presenta infinite istanze ognuna corrispondente ad un

insieme da organizzare. L’algoritmo di ordinamento, deve fornire una soluzione a qualunque

istanza.

L’algoritmo risulta essere corretto se è in grado di risolvere qualunque istanza del problema

considerato.

Non è da confondere un algoritmo con un programma scritto in un determinato linguaggio di

programmazione : i passi dell’algoritmo possono essere specificati in qualunque modo, anche in

linguaggio naturale. Ovviamente gli algoritmi che vedremo, li specificheremo in modo più

formale per evitare ambiguità, ma un algoritmo non dipende assolutamente da un linguaggio di

programmazione. I programmi, rappresentano la traduzione in un algoritmo in uno specifico

linguaggio di programmazione (C,C++,Python,ecc.). Noi faremo riferimento a pseudo-codici.

Una struttura dati è una determinata modalità con cui memorizziamo e organizziamo i dati che

dobbiamo gestire : ad esempio, una lista, una pila, una coda sono strutture dati. Ciascuna di

questi esempi, rappresenta una diversa modalità per organizzare i dati. Le strutture dati si

differenziano in base al modo con cui vengono effettuate le operazioni sulle strutture dati : negli

esempi citati, le operazioni possono essere inserimento, eliminazione, ricerca e quindi in base a

come avviene ciò si differenziano le strutture dati.

Una struttura dati è più o meno conveniente a seconda della modalità di uso dei dati che devono

essere mantenuti.

Cominciamo a parlare di prestazioni ed efficienza di un algoritmo : non esiste un unico algoritmo

per risolvere un dato problema, in quanto esso può avere diversi approcci risolutivi che

ovviamente sono caratterizzati da diverse prestazioni.

Noi ci concentreremo soprattutto sulla complessità computazionale di un algoritmo, ovvero su

quante operazioni (quanti passi) l’algoritmo esegue per risolvere un problema, perché dal

numero di passi dipende ovviamente il tempo impiegato dall’algoritmo per risolvere un

problema. Il numero di passi non è un valore assoluto, ma è funzione del problema da risolvere.

2

Tra n e nlogn : l’ordine di crescita di un logaritmo è infinitesimamente piccolo, per cui andandolo

a confrontare con una potenza di n sarà sempre più piccola la sua crescita. Questa cosa ha un

impatto non trascurabile sui tempi di esecuzione.

Questo è un risultato ottenuto sotto ipotesi semplificative, ma non si discosta molto da quello

che si può riscontrare nella pratica : si può vedere una notevole differenza tra 0.02 sec e 16 min

per risolvere lo stesso problema. Al crescere della dimensione del problema, la differenza diventa

sempre più marcata, per questo motivo andremo a studiare la legge di crescita della complessità

computazionale degli algoritmi.

Queste leggi sono state ottenute ipotizzando ad esempio un esecutore che possiede un singolo

processore, se vogliamo eseguire un algoritmo su un processore che ha più core, sviluppando

quindi un algoritmo parallelo, risulterà essere diversa la complessità computazionale ; infatti si

dice che la complessità computazionale dipende comunque dal modello di esecutore (noi

considereremo sempre un solo core).

Un fattore che può essere importante è la memoria, oppure la quantità di banda richiesta (quanti

dati si devono scambiare i diversi processi generati dall’algoritmo). Sono dunque diversi gli

aspetti che bisogna tenere in considerazione.

Iniziamo ora ad affrontare il problema dell’ordinamento di una sequenza di valori.

Cominciamo col definire il problema :

Abbiamo detto che la soluzione del problema di ordinamento è una permutazione : l’approccio

banale forza bruta, consiste nel considerare tutte le possibili permutazioni fin quando non

troviamo quella che rispetta l’ordine crescente. Ovviamente il numero di possibili permutazioni è

n! , un numero che cresce in maniera molto rapida e quindi tale metodologia non risulta essere

efficiente. Scartata questa tecnica, proviamo ad individuare un approccio più intelligente/efficace

: partiamo dall’algoritmo Insertion Sort.

Consideriamo una sequenza :

La strategia adottata da Insertion Sort è di tipo incrementale, cioè prova ad ordinare la sequenza

in modo incrementale : creiamo prima una sottolista di un solo elemento, poi una lista di due

elementi ordinati utilizzando i primi 2 elementi della lsita data, poi una lista di tre elementi.. e

così via. Dopo di che arriveremo a ottenere la lista completamente ordinata. Nell’ordinare la lista

in modo incrementale, abbiamo il vantaggio che : supponiamo di avere i primi 3 elementi

ordinati, inserire un nuovo elemento in una lista già ordinata può essere fatto in maniera

agevole, l’idea è quella di far scorrere tutti gli elementi maggiori di quello da inserire in una

posizione verso destra.

1. La sotto-lista di un elemento : 5.

2. La sotto-lista di due elementi : prendiamo 2, come lo inseriamo in maniera ordinata nella lista

precedente (formata da 5)? Facciamo scorrere tutti gli elementi che sono maggiori dell’elemento

da inserire. 5 è maggiore di 2, quindi scorre di una posizione verso destra. 2 viene inserito

all’inizio della lista ed otteniamo una lista di due elementi.

3. La sotto-lista di tre elementi : prendiamo 4, e lo andiamo a confrontare con gli elementi che lo

precedono. Se incontriamo un elemento più grande, esso scorre verso destra, altrimenti ci

fermiamo e inseriamo il 4 dopo l’elemento più piccolo trovato. Confrontiamo il 4 con il 5, 5 è più

grande e scorre verso destra ; confrontiamo il 4 con il 2, ma 4 è più piccolo e resta lì.

4. La sotto-lista di quattro elementi : prendiamo 6, e lo andiamo a confrontare con il 6. Ma il 6 è

gia maggiore di 5, per cui resta lì, senza effettuare spostamenti.

5. La sotto-lista di cinque elementi : prendiamo 1, lo andiamo a confrontare con 6 e 6 scorre; lo

confrontiamo con 5, e 5 scorre ; lo confrontiamo con 4 e 4 scorre di una posizione; lo

confrontiamo con 2 e 2 scorre di una posizione.

6. La sotto-lista di sei elementi : prendiamo 6 e lo confrontiamo con 6, con 5, con 4, poi c’è il 2

che non è più grandi di 3 e quindi ci fermiamo.

Dobbiamo ora formalizzare i passi dell’algoritmo che abbiamo indicato con il nome Insertion Sort.

Il ciclo for è comodo utilizzarlo quando conosciamo già il numero di iterazioni dobbiamo

eseguire ; il ciclo while e do-while lo utilizziamo quando non sappiamo il numero di iterazioni da

seguire ma conosciamo la situazione di continuazione del ciclo. Qual è la differenza tra while e

do-while (oppure repeat-until)? Il ciclo do-while viene eseguito almeno una volta, l’altro invece

potrebbe anche non essere mai eseguito.

Nel caso dell’Insertion Sort abbiamo detto che ad ogni iterazione utilizziamo un diverso elemento

del vettore, quindi probabilmente il costrutto più opportuno è il costrutto for, anche perché se

abbiamo n elementi, effettuiamo n-1 iterazioni.

Siccome in ogni iterazione consideriamo l’elemento j-esimo, comodo far si che il contatore

assuma i valori dal secondo fino all’ultimo : gli indici dei vettori inziano da 1 (non da 0 come i

linguaggi di programmazione) , per cui il ciclo for inizia da 2 fino alla lunghezza dell’array “A”.

L’array “A” viene visto come un oggetto, “length[A]” oppure “A.length” stiamo andando ad

indicare l’attributo length dell’oggetto A.

Lezione 2 (30.09.2020)

Riprendiamo dall’Insertion Sort.

Avevamo gia osservato che in quest’algoritmo facciamo un certo numero di iterazione, e ad ogni

iterazione consideriamo l’i-esimo elemento della sequenza : noi conosciamo 3 strutture iterative,

for, while , do-while. Conoscendo già il numero di iterazioni da effettuare, utilizziamo un ciclo for :

può variare in un qualunque intervallo, noi consideriamo l’intervallo che parte da 2 fino alla

lunghezza del vettore (“length[A] oppure A.length”).

Ad ogni iterazione noi andiamo a mettere da parte l’elemento A[j], lo salviamo in una variabile

temporanea, perché poi sulla sua posizione andiamo a sovrascrivere :

abbiamo quindi salvato in “key” l’elemento che stiamo analizzando.

Successivamente, facciamo un ulteriore ciclo in cui andiamo a considerare tutti gli elementi che

precedono l’elemento da inserire : tra essi possiamo trovare o un elemento inferiore ad esso o

maggiore.

Non sappiamo quante iterazione faremo, quindi dobbiamo scegliere tra while e do-while :

siccome ci possono essere casi in cui non facciamo scorrere alcun elemento perché l’elemento è

gia maggiore del primo che analizziamo, è opportuno utilizzare il ciclo while.

L’indice del primo elemento del vettore è pari ad 1 , quindi l’indice i deve essere maggiore di

zero (vuol dire che i punta ad una posizione valida all’interno del vettore) e il valore contenuto in

esso è maggiore del valore key, allora possiamo eseguire un’iterazione del ciclo while in cui

l’elemento A[i] viene spostato verso destra.

Poi passiamo i ad i-1 per considerare l’elemento precedente nel vettore considerato e ripetere il

ciclo.

OSS: Potevo invertire le condizioni del while?

Non è la stessa cosa invertire le due condizioni, non perché la AND non gode della proprietà

commutativa, ma perché i linguaggi di programmazione quando traducono in linguaggio

valutazione del corto circuito

macchina, utilizzano la : quando c’è una valutazione tra due sotto-

condizioni, sappiamo che la AND è vera se tutte e due le sotto-condizioni sono vere. Se la prima

condizione è falsa, la seconda non viene proprio valutata. In questo caso, se tutti gli elementi

sono maggiori di quello da inserire, A[i]>key è sempre verificata, quando arriviamo a controllare

la condizione del ciclo nel momento in cui i=-1, se la prima condizione fosse stata “A[i]>key”

avremmo tentato di entrare nel ciclo causando un crash a tempo di esecuzione. Invece scrivendo

come abbiamo fatto, quando i non è più un indice valido all’interno del vettore, nel ciclo while

non proviamo proprio ad entrare ed evitiamo problemi con l’esecuzione del programma.

Ovviamente lo stesso discorso vale anche per la OR : basta che una sotto-condizione sia vera per

essere vera.

Terminato il ciclo while, dobbiamo andare ad inserire l’elemento j-esimo in quale posizione? Per

ottenere la condizione di terminazione, dobbiamo negare la condizione del ciclo while (Teorema

di De Morgan). Possiamo dire che, l’elemento salvato nella variabile key, deve essere salvato

nella posizione i+1 (risenti registrazione).

Algoritmo Completo Insertion Sort :

Possiamo vedere delle tecniche per valutare la correttezza dell’algoritmo e la complessità

computazionale.

Quando abbiamo algoritmi che contengono cicli iterativi, la correttezza può essere valutate

andando ad individuare un invariante per la struttura iterativa. Che cosa è un invariante? Un

invariante è una proprietà che dobbiamo dimostrare essere vera prima della prima iterazione del

ciclo e dobbiamo dimostrare che un’iterazione del ciclo preserva la verità dell’invariante.

Se riusciamo ad individuare una proprietà invariante, allora per induzione possiamo concludere

che l’invariante è anche vero quando usciamo dal ciclo : tipicamente andando a valutare

l’invariante all’uscita del ciclo, riusciamo a dimostrare la correttezza dell’algoritmo.

Normalmente si pensa prima all’invariante e poi viene costruito il ciclo in modo tale da

mantenere vero l’invariante ; in realtà, noi abbiamo proceduto proprio in questo modo. Qual è la

proprietà che abbiamo provato a mantenere vera?

Tutta la sotto-sequenza di A da 1 a j-1 contiene gli elementi che si trovavano in quelle posizioni

nel vettore di partenza e sono ordinati in modo crescente.

Dobbiamo dimostrare che quest’affermazione è vera prima del ciclo, rimane vera per l’iterazione

successiva e quindi, possiamo concludere per induzione che questa proprietà è vera anche

quando usciamo dal ciclo.

All’inizio della prima iterazione A[1] non l’abbiamo toccato, e A[1] è una sequenza banalmente

ordina. (VALIDA PRIMA DI INIZIARE).

Assumendo per ipotesi che questa proprietà è vera quando il contatore vale j, facciamo scorrere

gli elementi in modo che A[1] A[j] è ordinata. (risenti registrazione)

Questa proprietà è un invariante per il ciclo che abbiamo analizzato.

Che valore assume j quando usciamo dal ciclo for?

Quando j vale length[A], noi facciamo un’altra iterazione : quindi noi usciamo quando j vale n+1.

La sotto-sequenza

A[1]–A[n] contiene gli elementi di partenza ordinati in modo crescente.

Prima di passare alla valutazione della complessità, riprendiamo alcune convenzioni per lo

pseudocodice :

- quando abbiamo un blocco di istruzioni che racchiudiamo in parentesi graffe, nello pseudo-

codice utilizziamo l’indentazione.

- costrutti iterativi e di condizione hanno significato analogo ai linguaggi di alto livello

- i <- indica che il valore di j viene assegnato a i

- l’operatore [] viene utilizzato sia per l’operazione di accesso dell’elemento i-esimo, sia per

l’accesso ai campi di un oggetto

- i parametri sono passati per valore alle procedure

- gli operatori booleani AND e OR sono valutati secondo la tecnica del corto circuito

Le prestazioni di un algoritmo possono essere valutate in base a diversi criteri : occupazione di

memoria (quanta memoria è richiesta all’algoritmo per effettuare i propri passi), impegno di

banda (va valutato quanti dati si devono scambiare i diversi algoritmi), tempo di calcolo (tempo

necessario per l’esecuzione dell’algoritmo).

Per l’occupazione di memoria, l’algoritmo Insertion Sort è vantaggioso, perché come abbiamo

visto, per ordinare la sequenza oltre alla memoria richiesta per il vettore stesso di cui non

possiamo fare a meno, ha bisogno di una sola variabile “key” per mantenere temporaneamente

l’elemento da inserire nella posizione corretta. In questo caso significa che l’algoritmo “ordina

sul posto” .

Per quanto riguarda il tempo di calcolo, dobbiamo specificare il modello di calcolatore che viene

utilizzato per eseguire l’algoritmo. Il modello che utilizziamo noi è :

1. Basato su singolo processore

2. La memoria è ad accesso casuale, quindi il tempo di accesso ad un elemento è analogo ad

un qualsiasi altro elemento. Questo requisito è importante perché avere la possibilità di accedere

direttamente a qualunque elemento in un tempo costante, ma in Insertion Sort non è proprio

indispensabile perché noi ci spostiamo sempre tra elementi adiacenti tra loro.

3. Non ci sono gerarchie di memoria, non ci sono memorie cash questo perché nella

valutazione del tempo di esecuzione di un algoritmo, andrebbe tenuto in conto anche l’eventuale

presenza di esse che consento di accedere più velocemente ai dati a cui abbiamo fatto accesso

di recente. Questo potrebbe avere un impatto positivo sull’algoritmo. Quindi non andiamo a

considerare eventuali miglioramenti possibili.

Per ricavare una legge che esprima la complessità computazionale di un algoritmo, assumiamo

che le varie istruzioni aritmetiche richiedono un tempo costante (se eseguiamo più volte la

stessa istruzione all’interno di un ciclo, il tempo impiegato è sempre lo stesso).

Proviamo ad applicare questi concetti al caso di Insertion Sort.

Nel caso di algoritmi di ordinamento, la dimensione del problema si esprime con la lunghezza

della sequenza da ordinare. 1. La riga del ciclo for impiega un

tempo c , che è il tempo

1

impiegato per incrementare il contatore e verificare che il contatore rientra nell’intervallo

indicato. La variabile j varia da 2 a n (n=length[A]) ; allora il numero di iterazioni sarà n-

2+1 (estremo superiore – estremo inferiore + 1). Quindi n-1, però il numero di volte in cui

effettuo il controllo, sarà dato da un +1 che rappresenterà la volta che usciamo dal ciclo.

Quindi questo controllo viene eseguito n volte.

2. Le due righe successive la ripetiamo ovviamente n-1 volte

3. Il ciclo while non sappiamo quante volte sarà ripetuto. Utilizziamo questo parametro t j

4. Le due righe successive, che appartengono al ciclo, vengono ripetuto ovviamente ad un

numero precedente -1

5.

Al fine di minimizzare quest’espressione e quindi individuare il caso migliore, lo otteniamo

quando il minimo possibile di t = 1 in tutte le iterazioni del ciclo for. Che significa? Significa che il

j

vettore di partenza è già ordinato, per cui ad ogni iterazione il valore j-esimo è già maggiore di

quelli che lo precedono.

Andiamo a valutare il tempo peggiore. Nel caso peggiore, siamo nella situazione in cui vengono

eseguite il numero massimo di iterazioni possibili : ovviamente, ciò accade quando l’elemento

che vogliamo inserire è minore di tutti gli elementi del vettore e quindi deve essere inserito nella

prima posizione. Questo significa che il caso peggiore lo otteniamo quando questo succede ad

ogni iterazione, e quindi si verifica quando il vettore è ordinato in se