Vai al contenuto
Fondamenti di Informatica

Algoritmi: diagrammi di flusso, programmazione strutturata e complessità

Proprietà di un algoritmo, diagrammi di flusso e pseudocodice con l'algoritmo di Euclide, teorema di Böhm-Jacopini, notazione O e ricerca binaria.

3 min di lettura 0 commenti

Un algoritmo è una sequenza finita di istruzioni non ambigue che risolve un problema. La parola viene dal nome del matematico persiano al-Khwarizmi, e il primo algoritmo che conosciamo, quello di Euclide per il massimo comun divisore, ha più di duemila anni. Prima di scrivere codice conviene progettare l’algoritmo: è lì che si decide se il programma sarà corretto e veloce. In questa lezione vediamo come si descrive un algoritmo, le strutture di base della programmazione strutturata e come si misura il costo, cioè la complessità.

Le proprietà di un algoritmo

  • Finitezza: termina dopo un numero finito di passi.
  • Non ambiguità: ogni passo ha un solo significato.
  • Ingresso e uscita: riceve dei dati e produce un risultato.
  • Efficacia: ogni passo si può eseguire davvero, con le operazioni disponibili.
  • Generalità: risolve una classe di problemi, non un solo caso.

Come si descrive: diagrammi di flusso e pseudocodice

Il diagramma di flusso rappresenta l’algoritmo con blocchi collegati da frecce: ovali per inizio e fine, parallelogrammi per ingresso e uscita, rettangoli per le operazioni, rombi per le decisioni.

Diagramma di flusso dell'algoritmo di Euclide per il massimo comun divisore con la tabella di esecuzione
L’algoritmo di Euclide: finché b è diverso da zero, si sostituisce la coppia (a, b) con (b, a mod b). A destra l’esecuzione con a = 48 e b = 18: dopo tre passi b vale 0 e il risultato è a = 6.

Il pseudocodice descrive lo stesso algoritmo con un linguaggio a metà tra l’italiano e un linguaggio di programmazione, più compatto del diagramma:

leggi a, b
finché b ≠ 0:
    r ← a mod b
    a ← b
    b ← r
scrivi a

Perché funziona. Ogni divisore comune di a e b divide anche r = a - qb, e viceversa: quindi \text{MCD}(a, b) = \text{MCD}(b, r). Poiché r \lt b, il secondo numero diminuisce a ogni passo e arriva a 0 in un numero finito di passi, e \text{MCD}(a, 0) = a.

La programmazione strutturata

Il teorema di Böhm-Jacopini (1966, due informatici italiani) dimostra che qualsiasi algoritmo si può scrivere usando solo tre strutture:

  1. sequenza: un’istruzione dopo l’altra;
  2. selezione: se una condizione è vera fai una cosa, altrimenti un’altra (if);
  3. iterazione: ripeti finché una condizione è vera (while).

Non servono i salti arbitrari (goto), che rendono il codice difficile da seguire: è la base della programmazione strutturata, e del C che vedremo dalla prossima lezione.

La complessità

Due algoritmi corretti per lo stesso problema possono avere tempi molto diversi. La complessità computazionale misura come cresce il numero di operazioni al crescere della dimensione n dei dati. Si usa la notazione O: un algoritmo è O(f(n)) se per n grande fa al massimo un numero di operazioni proporzionale a f(n).

ComplessitàEsempion = 1000n = 10^6
O(1)accedere a un elemento di un array11
O(\log n)ricerca binaria in un array ordinato1020
O(n)trovare il massimo di un array10^310^6
O(n\log n)merge sort, FFT10^42\times 10^7
O(n^2)ordinamento a bolle, DFT diretta10^610^{12}
O(2^n)provare tutti i sottoinsiemi10^{301}impossibile

A un miliardo di operazioni al secondo, 10^{12} operazioni richiedono un quarto d’ora; 2\times 10^7 due centesimi di secondo. Migliorare l’algoritmo conta molto più che comprare un computer più veloce.

Esempio: quanti passi fa Euclide. Ogni due passi il primo numero almeno si dimezza (si dimostra con poca fatica), quindi i passi sono al massimo circa 2\log_2 del numero più piccolo: O(\log n). Per numeri di 300 cifre, come quelli della crittografia RSA, servono qualche migliaio di passi, una frazione di millisecondo. Provare tutti i divisori sarebbe impossibile.

Ricerca lineare e ricerca binaria

Cercare un valore in un array di n elementi non ordinati richiede di guardarli uno a uno: O(n). Se l’array è ordinato si può fare molto meglio: si guarda l’elemento centrale, e a seconda che sia più grande o più piccolo del valore cercato si scarta metà dell’array. Dopo k passi resta n/2^k elementi, quindi bastano \log_2 n passi: 20 confronti per un milione di elementi, 30 per un miliardo.

/* restituisce l'indice di x nell'array ordinato v di n elementi, oppure -1 */
int ricerca_binaria(const int v[], int n, int x)
{
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;   /* evita di calcolare lo + hi, che potrebbe andare in overflow */
        if (v[mid] == x) return mid;
        if (v[mid] < x) lo = mid + 1;
        else            hi = mid - 1;
    }
    return -1;
}

Il calcolo di mid come lo + (hi - lo) / 2 invece di (lo + hi) / 2 non è una pignoleria: con indici vicini al massimo valore di un int, la somma andrebbe in overflow. È un bug rimasto per anni nelle librerie standard di diversi linguaggi.

Articoli correlati

Subscribe
Notify of
guest
0 Comments
Oldest
Newest Most Voted
0
Would love your thoughts, please comment.x
()
x