Una rapida introduzione agli algoritmi

Il problema principale risolto dai computer è eseguire in modo rapido e affidabile operazioni ben definite. Nella lezione precedente abbiamo visto una serie di esempi di utilizzo dei computer in ambito scientifico e ingegneristico: dall'acquisizione di dati, all'esecuzione di calcoli complessi in simulazioni fisiche o nel calcolo simbolico, fino all'organizzazione e al mantenimento di dati in un database. In ognuno di questi esempi i computer eseguono miliardi di operazioni al secondo seguendo un insieme di istruzioni preciso. Questo ci pone davanti alla domanda su come fornire le istruzioni al computer. Più in generale, dobbiamo affrontare il seguente problema:

Come possiamo tradurre un compito o la soluzione di un problema in una serie di passaggi che garantiscano di raggiungere la risposta corretta?

La questione non è affatto banale, perché vogliamo che la soluzione sia sempre raggiunta, indipendentemente da chi esegue i calcoli. Chi legge le istruzioni deve essere quindi in grado sia di capirle che di eseguirle. Come è facile immaginare, questo problema è molto più antico dei computer programmabili. I metodi imparati nella scuola elementare per eseguire operazioni come somme e moltiplicazioni rispondono esattamente al problema che ci interessa e sono esempi base di algoritmi. Anche se la formalizzazione teorica moderna è del XX secolo, la parola "algoritmo" ha un'origine antica legata all'algebra. L'etimologia deriva dal nome di Muhammad ibn Musa al-Khwarizmi, uno dei più importanti matematici islamici, autore nel IX secolo del trattato "al-Kitāb al-Mukhtaṣar fī Ḥisāb al-Jabr wal-Muqābalah" (in italiano, all'incirca, "libro sul calcolo tramite bilanciamento e completamento"), dal cui titolo deriva la parola "algebra".

Obiettivi formativi

Al termine di questa lezione dovresti essere in grado di:

1. Dare una definizione operativa di algoritmo.
2. Verificare se una sequenza di istruzioni è non ambigua, finita ed eseguibile.
3. Leggere e scrivere semplici algoritmi in forma testuale, diagramma di flusso e pseudocodice.

Cos'è un algoritmo?

Nella definizione formale moderna:

Un algoritmo è un insieme ordinato di passi eseguibili ed efficaci, non ambigui, per portare a termine un compito o risolvere un problema.

Vediamo passo passo il significato degli elementi di questa definizione. Il primo è un "insieme ordinato" di passi. Deve cioè essere chiaro a ogni passo qual è l'istruzione seguente --cosa fare e quando--, ma non è detto che le istruzioni debbano essere una sequenza lineare. Ad esempio, nelle simulazioni al computer è normale spezzare calcoli complessi tra più processori che li eseguono in parallelo. Non è un algoritmo il seguente insieme di istruzioni del genere: "Quando l'acqua bolle -- per far prima puoi usare il bollitore -- butta la pasta, quando è al dente scolala. Puoi condirla con il sugo che vuoi".

Esercizio

Perché le istruzioni precedenti non sono un algoritmo?

Soluzione

1. non stiamo specificando quando va condita la pasta. Prima o dopo averla scolata?
2. Le istruzioni non sono univoche. Quanta pasta? Cosa significa "al dente"? Entrambe le cose sono soggettive e portano a risultati diversi a seconda delle persone. Lo stesso vale per la scelta del sugo.
3. Anche togliendo la soggettività di cui al punto precedente, resta il fatto che se parlate con qualcuno che non ha mai cucinato né mangiato una pastasciutta in vita sua "butta la pasta" potrebbe essere piuttosto misteriosa.

Insomma, per avere un algoritmo dobbiamo dare una ricetta non fraintendibile. Se i punti sopra vi sembrano fantasiosi, tenete conto che il sottoscritto si trovò a dover mangiare, in Galles, 250 g di pasta cotta per 15 minuti direttamente nel bollitore, condita da una confezione di passata rovesciata direttamente nell'acqua bollente. Il giorno successivo i cuochi si stupirono molto nel vederci usare una pentola per la pasta e un'altra per il sugo.

Le istruzioni poi non devono essere ambigue, come abbiamo visto nell'esempio precedente. Uno dei motivi principali per cui molte ricette di cucina non sono esattamente algoritmi è il fatto che i condimenti sono in genere specificati "q.b." (quanto basta), lasciando la scelta al cuoco. Questo è ottimo in cucina, ma non è desiderabile quando si vuole avere un insieme di istruzioni che producono sempre lo stesso risultato.

Dobbiamo tenere conto che l'ambiguità può dipendere anche dalle conoscenze condivise nella comunità di chi utilizza un algoritmo. Ad esempio, la frase "prendi un'altezza in piedi e trasformala in metri" è perfettamente comprensibile e attuabile da chiunque abbia una cultura aerospaziale, e costituisce un algoritmo all'interno di questa comunità. Ma in generale non conosciamo il fattore di conversione tra piedi e metri, e necessitiamo quindi di un insieme di istruzioni che non lasci alcuna ambiguità. Questo può essere espresso nel modo seguente:

\[ h_m = 0.3048 h_f,\]

dove \(h_m\) e \(h_f\) sono le altezze in metri ed in piedi rispettivamente. Notiamo che questa formula è essa stessa un algoritmo, equivalente a "prendi l'altezza in piedi e moltiplicala per il fattore 0.3048". Formule composte da più operazioni equivalgono ad algoritmi con più passi, il cui ordine è stabilito dalla precedenza delle operazioni algebriche.

Un altro aspetto importante della definizione di algoritmo è che i passi devono essere eseguibili. Con questo intendiamo due cose.

1. Ogni singolo passo deve essere eseguibile. Una lista di istruzioni come la seguente, ad esempio, "1. prendi due sorgenti termiche \(A\) e \(B\) aventi temperature \(T_A>T_B\). 2. Costruisci un motore in grado di trasferire calore da \(B\) ad \(A\), usando solo parte del calore estratto da \(B\) per generare il lavoro necessario per questa operazione. 3. Utilizza il maggior calore in \(A\) per generare lavoro" non è un algoritmo, perché il passo 2. viola il secondo principio della termodinamica ed è quindi fisicamente impossibile. Lo stesso vale se un passaggio non è fisicamente impossibile, ma semplicemente non è noto come eseguirlo, magari perché non abbiamo ancora gli strumenti matematici.
2. L'algoritmo deve essere composto da un numero finito di istruzioni. Per questo motivo "stampa tutte le cifre di \(\pi\)" non è un algoritmo: questa operazione non può mai giungere a fine e non potremo quindi eseguire tutte le operazioni, che sono infinite.

Rispetto al punto 2. qui sopra, la nostra definizione formale sembra lasciar fuori tutti i casi di algoritmi il cui numero di operazioni non è specificato fin da principio e può variare. Questi includono ad esempio una simulazione che viene lasciata girare finché non viene raggiunta qualche condizione, oppure il controllo di stabilità di un veicolo come un aereo o un'auto sportiva. Questi sono attivi solo fintanto che il veicolo è in moto. Ciò nonostante, si può chiaramente aggiungere nelle nostre istruzioni una condizione che garantisca il raggiungimento di un termine in un numero finito di passi, come ad esempio "finché la centralina riceve corrente dal motore dell'auto, esegui...".

I passi devono essere anche efficaci. Con questo alcuni autori intendono sia quello che noi abbiamo indicato come eseguibilità, sia il fatto che i passi devono essere il più semplici possibile e non dipendere da condizioni particolari di una macchina. Un buon modo per ottenere passi efficaci è scriverli in modo tale che siano eseguibili in un tempo finito da una persona con carta e penna. Questo fornisce anche un ottimo modo per testare i nostri algoritmi: prima di tutto, eseguiamoli a mano in casi semplici.

Infine, le istruzioni servono per portare a termine un compito o per risolvere un problema. Questo implica che un algoritmo necessiti di dati in ingresso (input) e fornisca dati in uscita (output) che rappresentano la soluzione del problema. Questi possono essere sia distinti dai dati in ingresso, sia una modifica diretta dell'input. Ad esempio, se abbiamo in mano \(N\) carte da gioco e le ordiniamo in base al loro valore, l'input è dato dalle carte disordinate e l'output è costituito dallo stesso insieme di carte ordinato da quella di minor valore a quella di maggior valore. Nel caso di meccanismi di controllo come quelli citati sopra, l'input viene dai sensori e l'output è dato da un'azione fisica, come mantenere velocità e quota costanti per un aereo.

Un semplice esempio: l'algoritmo di Euclide per il massimo comun divisore

Dati due numeri interi \(m,n \in \mathcal{N}\) vogliamo trovare il loro massimo comun divisore, cioè il più grande \(k \in \mathcal{N}\) che divide sia \(m\) che \(n\). Questo si può fare usando l'algoritmo di Euclide. Usiamo la lettera E (Euclide) per identificare i passi con l'algoritmo specifico.

• E1 [trova il resto]. Dividi \(m\) per \(n\), sia \(0 \leq r < n\) il resto.
• E2 [\(r\) è zero?]. Se \(r = 0\), termina e restituisci \(n\) come risposta.
• E3 [riduci]. Imposta \(m \leftarrow n\), \(n \leftarrow r\) e vai al passo E1.

Note

Da qui in avanti useremo la seguente notazione:

\[v \leftarrow a\]

significa "salva il valore \(a\) nella variabile \(v\). Possiamo considerare \(v\) come una nota che ci siamo lasciati per leggerla più tardi.

Più in generale

\[v \leftarrow \textrm{(expr)}\]

significa "esegui per prima cosa il calcolo in (expr) e salva il risultato nella variabile \(v\). expr può essere una qualunque espressione matematica, come ad esempio \(0.3048h_m\), complicata a piacere purché calcolabile in un numero finito di passi. expr può anche essere il risultato prodotto da un algoritmo.

In particolare, capita spesso di avere un' assegnazione del tipo:

\[v \leftarrow f(v) \]

dove \(f\) è una qualche funzione di \(v\). In base a quanto abbiamo detto è ovvio che si usa il vecchio valore di \(v\) per calcolare \(f(v)\) e solo in seguito si aggiorna il valore di \(v\) con il risultato di \(f\). Un esempio semplice è dato da \(n \leftarrow n + 1\), un'istruzione usata per far crescere un contatore.

In base a questa notazione, la formula precedente per il cambio di unità da piedi a metri diventa:

\[h_m \leftarrow 0.3048 h_f,\]

con $\leftarrow $ che sostituisce il simbolo \(=\) a cui siamo abituati. Questo è necessario per poter usare \(=\) nel suo significato logico:

\[a = b\]

e significa "i valori salvati nelle variabili \(a\) e \(b\) sono uguali tra loro". Più in generale, in questa notazione \(=\) si usa per indicare il verificarsi di una condizione.

Il modo migliore per comprendere questo algoritmo è applicarlo. Proviamo un caso semplice. Consideriamo come valori iniziali \(m \leftarrow 105\), \(n \leftarrow 42\). La sequenza di passi è la seguente.

1. E1 \(\frac{m}{n} = \frac{105}{42} = 2\), \(r \leftarrow 21\).
2. E2 Poichè il resto \(r\) non è zero, l' algoritmo continua.
3. E3 \(m \leftarrow 42\), \(n\leftarrow 21\).
4. E1 Il resto della divisione fra 42 e 21 è 0: \(r \leftarrow 0\).
5. E2 Poichè il resto è zero, restituisci il valore di \(n\), 21.

Esecizio

Verifica che l'algoritmo di Euclide funzioni anche se \(m < n\). Cosa succede, ad esempio, se iniziamo con \(m \leftarrow 42\) e \(n \leftarrow 105\)?

Soluzione

Il primo passo è calcolare il resto di \(m\) diviso \(n\). Poiché \(m < n\), il resto è \(m\) stesso, cioè \(r \leftarrow 42\). Il passo successivo è aggiornare \(m\) e \(n\): \(m \leftarrow 105\), \(n \leftarrow 42\). A questo punto siamo esattamente nella stessa situazione del caso precedente, e quindi l'algoritmo procede esattamente come prima, restituendo 21 come risposta.

Esercizio

Scrivere un semplice algoritmo che scambi i valori salvati in due variabili in modo tale che se in input riceve \(v_a = a\) e \(v_b = b\), in output ritorni \(v_a = b\) e \(v_b = a\).

Soluzione

Esistono due modi per scambiare i valori di due variabili. Il primo è quello di usare una variabile temporanea, come segue:

v_c \leftarrow v_a
v_a \leftarrow v_b
v_b \leftarrow v_c

Il secondo modo è quello di usare operazioni algebriche, ad esempio:

v_a \leftarrow v_a + v_b
v_b \leftarrow v_a - v_b
v_a \leftarrow v_a - v_b

In entrambi i casi utilizziamo tre passi per scambiare i valori di \(v_a\) e \(v_b\). Il secondo metodo è più efficiente in termini di spazio, perché non richiede l'uso di una variabile temporanea, ma è meno chiaro e può introdurre errori numerici. A meno di esigenze particolari, è quindi preferibile il primo metodo, che è più facile da capire e da verificare a mano.

Esercizio

Provare a scrivere in forma di algoritmo il calcolo del fattoriale di un numero naturale positivo \(N\).

Soluzione

• F1 Imposta \(F \leftarrow 1\).
• F2 Se \(N = 0\), ritorna \(F\).
• F3 Imposta \(F \leftarrow F \cdot N\).
• F4 Imposta \(N \leftarrow N - 1\) e vai al passo F2.

Altri esempi semplici

Trovare il valore più grande tra \(N\) numeri

Consideriamo un insieme \(X\) di \(N\) numeri \(X_1,\, X_2,\,\ldots\, ,X_N\). A ogni numero è associato un indice, cosicché possiamo recuperarlo dall'insieme (in ambito informatico si dice che l'insieme è iterabile). Vogliamo un algoritmo che identifichi l'indice \(j\) del valore più grande contenuto in \(X\) e ritorni sia \(j\) che \(X_j\). Vogliamo cioè trovare \(j | X_j = \max_{1\leq i\leq N} X_i\).
Il procedimento che utilizzeremo consiste nel confrontare i numeri uno alla volta, tenendo traccia del massimo \(m\) trovato fino a quel momento. \(j\) continua ad indicare l'indice del massimo trovato mentre \(k\) tiene traccia dell'indice del prossimo elemento da confrontare. Al primo passaggio, non avendo ancora confrontato nulla, possiamo inizializzare \(j\) e \(m\) con l'indice e il valore dell'ultimo elemento primo elemento, cioè \(j \leftarrow 1\) e \(m \leftarrow X_1\) poichè una lista con un solo elemento ha quel elemento come massimo. Usiamo la lettera M (massimo) per identificare i passi con l'algoritmo specifico.

• M1 [inizializza]. Imposta \(j \leftarrow N\), \(k \leftarrow N-1\), \(m \leftarrow X_j\). (Nota: a ogni passo abbiamo \(m = \max_{k\leq i \leq N} X_i\).)
• M2 [testati tutti?]. Se \(k = 0\), termina l'algoritmo e restituisci \(j\) e \(m\).
• M3 [paragona]. Se \(X_k \leq m\), vai a M5.
• M4 [aggiorna massimo]. Imposta \(j \leftarrow k\), \(m \leftarrow X_k\).
• M5 [decrementa]. Imposta \(k \leftarrow k-1\) e vai a M2.

Esercizio

Applica l'algoritmo M all'insieme \(X = [4, 9, 3, 9, 1]\). Quali valori finali ottieni per \(j\) e per\(m\)?

Soluzione

Il valore massimo è \(m = 9\). Con la versione attuale dell'algoritmo (che inizializza da destra e aggiorna solo se trova un valore strettamente maggiore), l'indice restituito è quello dell'ultima occorrenza del massimo, cioè \(j = 4\).

Rappresentare gli algoritmi

Prima di vedere come possiamo rappresentare gli algoritmi, è importante specificare che c'è una differenza tra l'algoritmo e il modo in cui questo è rappresentato, ad esempio come programma in un computer. Qui vedremo due modi tipici, entrambi molto utili, di scrivere gli algoritmi: lo pseudocodice e i diagrammi di flusso. Non sono gli unici. Rappresentazioni diverse hanno vantaggi diversi, e possono essere più o meno adatte a seconda delle applicazioni.

Esercizio

Quando preferiresti usare un diagramma di flusso invece dello pseudocodice?

Soluzione

In fase di progettazione iniziale, i diagrammi di flusso sono spesso più immediati per visualizzare biforcazioni e cicli. Lo pseudocodice diventa più pratico quando l'algoritmo cresce e serve descrivere dettagli operativi vicini a un linguaggio di programmazione.

Diagrammi di flusso

Un metodo "storico" ma decisamente utile per rappresentare gli algoritmi è quello del diagramma di flusso. Le istruzioni sono scritte in caselle unite tra loro da frecce. Questo permette di rappresentare facilmente le "biforcazioni" del flusso che accadono in corrispondenza di scelte logiche come quelle che avvengono nei passaggi E2 e M3 degli algoritmi visti in precedenza. Gli elementi grafici base utilizzati per rappresentare gli algoritmi sono i seguenti.

Esercizio

Nel diagramma, quale simbolo useresti per rappresentare una scelta logica tipo "se \(x>0\)"?

Soluzione

Il rombo (decisione). Ha un ingresso e in genere due uscite, ad esempio "vero" e "falso".

Come si vede, tutti gli elementi hanno una freccia in entrata, mentre uno solo ne ha due in uscita. L'algoritmo deve iniziare con il trapezio rovesciato che rappresenta il punto di partenza e terminare in uno dei trapezi che rappresentano la fine. Possono esserci più modi di terminare l'algoritmo, e quindi più punti di uscita. Nei casi più semplici gli elementi "inizio" e "fine" non si disegnano perché sono ovvi.

La rappresentazione tramite diagrammi di flusso può essere utile per una prima stesura di un algoritmo, in quanto fornisce un modo naturale per stimarne la complessità e per identificare se ci sono istruzioni che non portano a nulla o che causano cicli infiniti. Matematicamente, questa rappresentazione rende anche evidente la corrispondenza tra algoritmi e grafi direzionali.

L'algoritmo M visto in precedenza si può facilmente rappresentare come diagramma di flusso. Il risultato è riportato nella figura sottostante:

Procedure e funzioni

Un aspetto fondamentale degli algoritmi è che, avendo input, output e un'esecuzione determinata sia nel tempo sia nel risultato, possono essere inseriti a loro volta dentro altri algoritmi. Come accennato sopra per il sorting, gli algoritmi possono diventare essi stessi i mattoni per realizzare algoritmi più complessi. Ad esempio, se vogliamo trovare il valore massimo assunto da una funzione \(f\) su un insieme finito di punti \(X\), possiamo applicare l'algoritmo M dopo aver trasformato i valori dell'insieme \(X\) tramite la funzione \(f\). Potremmo poi voler utilizzare il risultato come input di un terzo algoritmo, e via così.

Per facilitare la scrittura di algoritmi composti e permettere di ragionare sugli algoritmi come pezzi indipendenti, usiamo due concetti, quello di procedura o routine e quello di funzione (in alcuni testi con "procedura" ci si riferisce ad entrambe).

1. Funzione. È un insieme di istruzioni che compongono un algoritmo che prendendo in input alcuni dati restituisce un output distinto da questi.
2. Procedura/routine. Come sopra, ma anziché restituire un output distinto, modifica direttamente i dati in ingresso. Questo è ad esempio il caso di un algoritmo di ordinamento che lavori direttamente sui dati in input, e non su una loro copia.

Procedure e funzioni sono rappresentate nei diagrammi di flusso come rettangoli con due linee verticali:

L'utilizzo di procedure e funzioni permette soprattutto di scrivere algoritmi secondo un approccio "top-down": si struttura una sequenza di istruzioni in cui i singoli passaggi sono procedure caratterizzate dal riuscire a eseguire correttamente un certo compito, dato un input ben definito. Cosa ci sia veramente all'interno di queste procedure non è così importante, purché implementino correttamente l'algoritmo dichiarato. Le procedure possono quindi essere sostituite in un secondo momento con altre più veloci, o più adatte a una macchina specifica, senza cambiare minimamente la correttezza dell'algoritmo che le contiene.

Esercizio

Qual è la differenza principale tra funzione e procedura/routine?

Soluzione

Una funzione restituisce un output distinto dagli input. Una procedura/routine modifica direttamente i dati in ingresso (o produce effetti sullo stato del sistema) senza necessariamente restituire un nuovo oggetto separato.

Pseudocodice

Come abbiamo visto poco sopra, alcuni concetti come le scelte if..then..else e i cicli (for.., while..) si possono usare come blocchi fondamentali di un algoritmo. Anche se la notazione a diagramma di flusso è molto utile nei casi semplici o per connettere tra loro diverse procedure, nel caso di algoritmi moderatamente complessi risulta più efficace la rappresentazione basata su qualche tipo di codice. Per non doversi legare a un particolare linguaggio di programmazione, in genere viene utilizzato uno pseudocodice, con gli elementi principali scritti in inglese.

Assegnazione variabili

\[ a \leftarrow \textrm{(espressione)}\]

oppure

\[ a = \textrm{(espressione)}\]

Commenti

È utile poter commentare lo pseudocodice per spiegare cosa succede al suo interno. Per i commenti useremo il carattere #, tipico di Python.

# Questa riga è un commento.

if-then-else

Le condizioni logiche viste sopra si rappresentano semplicemente con

if (condizione):
    ...
else:
    ...

È importante notare che l'istruzione else è facoltativa: se non è presente, semplicemente il programma continua se condizione non si verifica. In diversi casi è utile specificare delle sottocondizioni che vanno eseguite se non si verifica la precedente. Questo si fa con else if.

if (condizione):
    ...
else if (condizione 2):
    ...
else if (condizione 3):
    ...
else:
    ...

Nel caso del codice qui sopra, lo stato di verità di condizione 2 viene controllato solo se condizione è falsa. Quello di condizione 3 solo se condizione 2 è falsa, e così via, fino a else (che come al solito è facoltativo).

Cicli

for(condizione iniziale ; condizione finale ; incremento):

oppure

for i in (insieme iterabile):

oppure

while (condizione):

A tutti questi viene fatto seguire un codice indentato per far capire dove inizia e dove finisce il ciclo. Ad esempio, per sommare i numeri da uno a 10:

i <- 0
s <- 0
while i <= 10:
    s <- s + i
    i <- i + 1

Procedure e funzioni

Rappresentiamo le procedure e le funzioni tramite il loro nome, seguito da una lista di argomenti che queste prendono in input.

sort(lista) # procedura che ordina i dati di una lista

oppure

y <- max(set_x) # funzione che trova il massimo di un insieme chiamato set_x

Esercizio

Scrivi in pseudocodice un ciclo che calcoli la somma dei primi \(N\) interi positivi.

Soluzione

s <- 0
i <- 1
while i <= N:
    s <- s + i
    i <- i + 1

Riepilogo

In questa lezione abbiamo visto che:

1. Un algoritmo è una sequenza ordinata, non ambigua, finita ed eseguibile di passi.
2. Input e output sono parte essenziale della definizione.
3. Lo stesso algoritmo può essere rappresentato in forme diverse (testuale, diagramma di flusso, pseudocodice).
4. Conviene sempre testare gli algoritmi su casi semplici prima dell'implementazione completa.