Appunti Algoritmi e strutture dati

Lezione 1 (29.09.2020)

Definizione di algoritmo

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.

Strutture dati

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.

Prestazioni ed efficienza

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.

Problema dell’ordinamento

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 lista 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 è già 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 sì che il contatore assuma i valori dal secondo fino all’ultimo: gli indici dei vettori iniziano 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)

Ripresa dell’Insertion Sort

Riprendiamo dall’Insertion Sort.

Avevamo già 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 è già 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:

Correttezza dell’algoritmo

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.

Convenzioni per lo pseudocodice

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.

Prestazioni e modello di calcolo

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 cache questo perché nella valutazione del tempo di esecuzione di un algoritmo, andrebbe tenuto in conto anche l’eventuale presenza di esse che consentono 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).

Complessità di Insertion Sort

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 tempo1 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 -15.

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