Tip:
Highlight text to annotate it
X
Cos'è un algoritmo?
Nella scienza informatica,
un algoritmo è una serie di istruzioni
per risolvere, passo dopo passo, alcuni problemi.
In genere gli algoritmi sono eseguiti da computer,
ma anche noi esseri umani abbiamo in nostri algoritmi.
Ad esempio: come approcci il problema di contare
il numero di persone in una stanza?
Be', se tu fossi come me,
probabilmente indicheresti ciascun presente,
uno alla volta,
e conteresti a partire da 0:
1, 2, 3, 4 eccetera eccetera.
Bene, quello è un algoritmo.
Infatti, cerchiamo di esprimerlo
un po' più formalmente come un pseudocodice,
una sintassi simile al lunguaggio umano
con le apparenze di un linguaggio di programmazione.
Ammettiamo n uguale a 0.
Per ciascuna persona nella stanza, impostiamo n = n + 1.
Come si interpreta questo pseudocodice?
Be', la linea 1 dichiara, per dire,
una variabile chiamata n
a cui assegniamo un valore pari a zero.
Questo significa solo che all'inizio del nostro algoritmo
la cosa con cui stiamo contando
parte dal valore zero.
Dopotutto, prima di iniziare a contare,
non abbiamo ancora contato nulla.
Chiamare questa variabile 'n' è solo una consuetudine.
Avrei potuto assegnargli quasi qualsiasi nome.
Ora, la linea 2 demarca l'inizio di una istruzione ripetuta, un loop,
una sequenza di passaggi che si ripeteranno un tot di volte.
Quindi, ad esempio, il passaggio che stiamo affrontando
è contare le persone nella stanza.
Al di sotto della linea 2 c'è la linea 3,
che descrive in maniera precisa come inizieremo il conteggio.
La rientranza implica che è la linea 3
ad essere ripetuta.
Quindi, lo pseudocodice sta dicendo
che dopo essere partiti con 0,
per ciascuna persona nella stanza,
accresceremo il valore di n di 1.
Ora: l'algoritmo è corretto?
Be', discutiamone un po'.
Funziona se ci sono due persone nella stanza?
Vediamo.
Nella linea 1 impostiamo n sullo zero.
Per ciascuna di queste 2 persone,
incrementiamo n di 1.
Quindi, al primo giro del loop
aggiorniamo n da zero a 1,
nel secondo giro del medesimo loop,
aggiorniamo n da 1 a 2.
E in questo modo, con la fine dell'algoritmo, n è 2,
che davvero rispecchia il numero di persone nella stanza.
Fin qui ci siamo con i conti.
E se introduciamo un caso limite?
Supponiamo che ci siano zero persone nella stanza,
oltre a me che sto contando.
Nella linea 1, di nuovo impostiamo n con il valore 0.
Questa volta, tuttavia, la linea 3 non viene eseguita
dato che non c'è una persona nella stanza,
e quindi, n rimane zero,
che è davvero il numero di persone nella stanza.
Piuttosto semplice, vero?
Ma contare le persone una alla volta è anche piuttosto inefficiente, no?
Certamente, e possiamo fare di meglio!
Perché non contare le persone due alla volta?
Invece di contare 1, 2, 3, 4, 5, 6, 7, 8, e così via,
perché non contare
2, 4, 6, 8, e via dicendo?
Suona anche più veloce, e di sicuro lo è.
Ora esprimiamo questa ottimizzazione in pseudocodice.
Impostiamo n con il valore zero.
Per ciascuna coppia di persone nella stanza,
impostiamo n = n + 2.
Una modifica piuttosto semplice, vero?
Invece di contare le persone una alla volta
le contiamo due alla volta.
Questo algoritmo è quindi due volte più veloce del precedente.
Ma può funzionare?
Vediamo.
Funziona se ci sono 2 persone nella stanza?
Nella linea 1 impostiamo n su 0.
Per quell'unica coppia di persone, incrementiamo n di 2.
E quindi, con la fine di questo algoritmo, n è 2,
che è davvero il numero di persone nella stanza.
Supponiamo ora che ci siano zero persone nella stanza.
Nella linea 1, impostiamo n col valore 0.
Come prima, la linea tre non viene affatto eseguita,
dato che non c'è alcuna coppia di persone nella stanza,
e quindi n rimane 0,
che rispecchia davvero il numero di persone nella stanza.
Ma se ci sono 3 persone nella stanza?
Come si comporta questo algoritmo?
Vediamo.
Nella linea 1, impostiamo n con il valore 0.
Per una coppia di quelle persone,
incrementiamo n di 2,
e poi cosa accade?
Non c'è un'altra coppia completa nella stanza,
quindi la linea 2 non si applica più.
E quindi, con questa fine dell'algoritmo,
n è ancora 2, che non è il valore corretto.
Questo algoritmo si dice che ha un bug
perché contiene un errore.
Ripariamolo con un po' di nuovo pseudocodice.
Impostiamo n con il valore 0.
Per cuascuna coppia nella stanza,
impostiamo n = n + 2.
se 1 persona rimane senza coppia,
impostiamo n = n + 1.
Per risolvere questo particolare problema,
abbiamo introdotto nella linea 4 una condizione,
altrimenti conosciuta come diramazione
che viene eseguita se c'è una persona
che non ptoremmo accoppiare con un'altra.
Adesso, quindi, se c'è 1 o 3
o un qualsiasi numero dispari di persone nella stanza,
questo algoritmo li conterà.
Possiamo fare ancora meglio?
Be', potremmo contare 3, 4, 5 o anche 10 alla volta,
ma oltre sarebbe
un po' difficile da indicare.
Alla fine della giornata
che sia eseguito da computer o da esseri umani,
gli algortismi sono solo una serie di istruzioni
con cui risolvere i problemi.
Questi erano solo tre.
Quale problema risolveresti con un algoritmo?