Algoritmi
Per arrivare in gita a Firenze, la prof. dice: «Se piove portate l'ombrello, altrimenti no». È una regola che chiunque può eseguire senza pensare: basta leggere i passi e rispettarli. In matematica succede lo stesso quando calcoliamo un MCD o risolviamo un'equazione. Una domanda per il resto della pagina: come si descrive una procedura in modo così preciso che persino una macchina possa eseguirla, e come si fa a sapere se è anche veloce?
Che cos'è un algoritmo
Un algoritmo è una sequenza finita di istruzioni non ambigue che, a partire dai dati iniziali (input), produce un risultato (output) in un numero finito di passi. Il nome viene da al-Khwarizmi, un matematico persiano del IX secolo; un esempio antichissimo è l'algoritmo di Euclide per il MCD.
Lo scriviamo in pseudocodice: un italiano molto schematico, con poche parole fisse.
| Istruzione | Significato |
|---|---|
| leggi $a$, $b$ | acquisisci i dati in ingresso |
| $x \leftarrow$ espressione | assegna a $x$ il valore dell'espressione |
| stampa $x$ | mostra il risultato |
| se condizione allora … altrimenti … | scelta tra due strade |
| per $i$ da 1 a $n$: … | ripeti per $i = 1, 2, \dots, n$ |
| finché condizione: … | ripeti fino a quando la condizione è vera |
La freccia $\leftarrow$ non è un'uguaglianza: $s \leftarrow s + 1$ significa «prendi il valore di $s$, aggiungi 1 e metti il risultato di nuovo in $s$». Come operazione useremo anche $a \bmod b$, il resto della divisione di $a$ per $b$.
Descrivi con un elenco di passi (pseudocodice) un algoritmo che, dati due numeri $a$ e $b$, stabilisce quale dei due è maggiore.
Descrivi con un elenco di passi (pseudocodice) un algoritmo che, dati due numeri $a$ e $b$, stabilisce quale dei due è maggiore.
Eseguire a mano: la tabella di traccia
Per capire che cosa fa un algoritmo, lo si esegue a mano riportando in una tabella i valori delle variabili a ogni passo. È la tecnica che si usa anche per cercare gli errori.
Un altro strumento utile è il resto: $a \bmod 2$ vale 0 se $a$ è pari e 1 se è dispari. Perciò «se $n \bmod 2 = 0$ allora stampa "pari" altrimenti stampa "dispari"» decide la parità.
Esegui a mano il seguente algoritmo con $n = 5$: 1. $s \leftarrow 0$ 2. per $i$ da 1 a $n$: $s \leftarrow s + i$ 3. stampa $s$ Che cosa calcola l'algoritmo?
Esegui a mano il seguente algoritmo con $n = 5$:
-
$s \leftarrow 0$
-
per $i$ da 1 a $n$: $s \leftarrow s + i$
-
stampa $s$
Che cosa calcola l'algoritmo?
Scrivi un algoritmo che, dato un numero intero positivo $n$, stabilisce se è pari o dispari, usando il resto della divisione per 2.
Scrivi un algoritmo che, dato un numero intero positivo $n$, stabilisce se è pari o dispari, usando il resto della divisione per 2.
Cicli e condizioni: media, massimo, equazioni
Le tre strutture di base sono la sequenza, la selezione (se… allora… altrimenti) e l'iterazione (ciclo). Con queste si scrive qualsiasi algoritmo.
Equazione $ax + b = 0$. Si distinguono tre casi:
-
se $a \neq 0$: stampa $x = -\frac{b}{a}$;
-
altrimenti, se $b = 0$: stampa «indeterminata» (ogni $x$ è soluzione);
-
altrimenti: stampa «impossibile».
Per $(4, -6)$ si ottiene $x = \frac{6}{4} = \frac{3}{2}$. È la stessa classificazione dei sistemi: determinato, indeterminato, impossibile.
Scrivi in pseudocodice un algoritmo che, data una sequenza di 6 voti, calcola la media e il voto massimo. Eseguilo poi con i voti 7, 5, 8, 6, 9, 7.
Scrivi in pseudocodice un algoritmo che, data una sequenza di 6 voti, calcola la media e il voto massimo. Eseguilo poi con i voti 7, 5, 8, 6, 9, 7.
Un algoritmo risolve l'equazione $ax + b = 0$. a) Scrivilo in pseudocodice considerando i casi $a \neq 0$, $a = 0$ con $b = 0$, e $a = 0$ con $b \neq 0$. b) Eseguilo con…
Un algoritmo risolve l'equazione $ax + b = 0$.
- a) Scrivilo in pseudocodice considerando i casi $a \neq 0$, $a = 0$ con $b = 0$, e $a = 0$ con $b \neq 0$.
- b) Eseguilo con $(a, b) = (4, -6)$, $(0, 0)$ e $(0, 5)$.
L'algoritmo di Euclide
Il MCD si calcola con divisioni successive: il MCD di $a$ e $b$ è uguale al MCD di $b$ e del resto $r = a \bmod b$. Si ripete finché il resto è 0.
Considera l'algoritmo: 1. leggi $a$ e $b$ (interi positivi) 2. finché $b \neq 0$: $r \leftarrow a \bmod b$, $a \leftarrow b$, $b \leftarrow r$ 3. stampa $a$ a) Esegui…
Considera l'algoritmo:
-
leggi $a$ e $b$ (interi positivi)
-
finché $b \neq 0$: $r \leftarrow a \bmod b$, $a \leftarrow b$, $b \leftarrow r$
-
stampa $a$
- a) Esegui l'algoritmo con $a = 84$, $b = 36$ riportando i valori a ogni passo.
- b) Che cosa calcola?
Efficienza e strategie
Due algoritmi possono risolvere lo stesso problema ma uno essere molto più veloce. Si misura contando le operazioni nel caso peggiore.
Numeri primi: basta fermarsi a √n
Per sapere se $n$ è primo si provano i divisori $d = 2, 3, \dots$ finché $d \le \sqrt{n}$. Se $n = a \cdot b$ con $a \le b$, allora $a^2 \le a \cdot b = n$, cioè $a \le \sqrt{n}$: ogni numero composto ha un divisore non superiore a $\sqrt{n}$. Se non ne troviamo fino a lì, non ne esistono oltre.
Ricerca binaria
Per indovinare un numero tra 1 e 1.000 si chiede «è maggiore di $m$?» con $m$ a metà dell'intervallo: a ogni domanda i candidati si dimezzano.
Con $k$ domande si distinguono al più $2^k$ numeri. Poiché $2^9 = 512 < 1.000 \le 1.024 = 2^{10}$, bastano 10 domande. La ricerca sequenziale («è 1? è 2? …») nel caso peggiore ne richiede 999 (o 1.000).
Progetta un algoritmo che, dato un intero $n \geq 2$, stabilisce se $n$ è primo provando i divisori fino a $\sqrt{n}$. a) Scrivi lo pseudocodice. b) Giustifica perché…
Progetta un algoritmo che, dato un intero $n \geq 2$, stabilisce se $n$ è primo provando i divisori fino a $\sqrt{n}$.
- a) Scrivi lo pseudocodice.
- b) Giustifica perché basta fermarsi a $\sqrt{n}$.
- c) Eseguilo con $n = 91$ e $n = 97$.
Un algoritmo di ricerca binaria cerca un numero tra 1 e 1.000 ponendo domande del tipo «è maggiore di $m$?». a) Descrivi la strategia. b) Calcola il numero massimo di…
Un algoritmo di ricerca binaria cerca un numero tra 1 e 1.000 ponendo domande del tipo «è maggiore di $m$?».
- a) Descrivi la strategia.
- b) Calcola il numero massimo di domande necessarie, giustificando con le potenze di 2.
- c) Confronta con la ricerca sequenziale nel caso peggiore.
Iterazione e ricorsione
Un algoritmo è iterativo se ripete un blocco di istruzioni con un ciclo. È ricorsivo se il calcolo di un valore si definisce in termini di valori precedenti dello stesso tipo, a partire da uno o più casi base.
Considera l'algoritmo: 1. $a \leftarrow 0$, $b \leftarrow 1$ 2. ripeti 8 volte: stampa $b$; $t \leftarrow a + b$; $a \leftarrow b$; $b \leftarrow t$ a) Esegui…
Considera l'algoritmo:
-
$a \leftarrow 0$, $b \leftarrow 1$
-
ripeti 8 volte: stampa $b$; $t \leftarrow a + b$; $a \leftarrow b$; $b \leftarrow t$
- a) Esegui l'algoritmo e scrivi i valori stampati.
- b) Riconosci la successione generata.
- c) Spiega la differenza tra un algoritmo iterativo e uno ricorsivo, riscrivendo la definizione in forma ricorsiva.
Vuoi altri esercizi?
In sintesi
Vuoi tornare al punto di partenza? La regola dell'ombrello è un algoritmo con una selezione: ogni procedura precisa, finita e senza ambiguità lo è.