algoritmi

algoritmi

Istruzioni per far funzionare da sole le macchine

Molte attività umane non si possono svolgere senza seguire precise indicazioni. Come le 'istruzioni per l'uso' spiegano il funzionamento di certi elettrodomestici, così un algoritmo fornisce una serie di istruzioni che possono essere eseguite sia da un essere umano sia, ed è la cosa più importante, da una macchina. Oggi, a cominciare dai computer e dai robot industriali, sono moltissimi i dispositivi che funzionano in maniera automatica o semiautomatica, seguendo le istruzioni indicate da appositi algoritmi

Algoritmi per cucinare, per contare e per lavare

La parola algoritmo deriva dal nome del matematico arabo Muhammad Ibn Musa al-Khuwarizmi (vissuto nel 9° secolo a Baghdad) e indica una successione di istruzioni per risolvere un problema, cioè per ottenere un preciso risultato a partire da un certo numero di dati iniziali. Anche una ricetta di cucina è, in senso generale, un algoritmo: i dati iniziali sono gli ingredienti, le istruzioni sono quelle che indicano come combinare fra loro gli ingredienti e il risultato finale è il piatto che si intende preparare. Ma è nel campo della matematica che gli algoritmi sono nati come procedure di calcolo: per esempio, il procedimento per eseguire una divisione fra due numeri interi è di tipo algoritmico.

Il grande sviluppo degli algoritmi è coinciso con l'invenzione di macchine capaci di eseguire da sole (automaticamente) o quasi (semiautomaticamente) diversi compiti. Le prime macchine del genere sono state i telai tessili, che funzionavano grazie a una serie di istruzioni riprodotte su schede perforate. Oggi sono moltissime le macchine automatiche in grado di eseguire serie di istruzioni, o algoritmi, senza l'intervento dell'uomo: dai robot (automi) usati nell'industria agli elettrodomestici come le lavatrici, il cui ciclo di lavaggio viene effettuato in base a un apposito algoritmo.

La lingua dei computer

La macchina che più di tutte utilizza gli algoritmi è il calcolatore, o computer. Tutte le operazioni che un computer esegue sono frutto dell'applicazione di algoritmi. Per la precisione, il computer può portare a termine l'operazione indicata dall'algoritmo solo dopo che l'algoritmo sia stato tradotto in un programma, cioè in una serie di istruzioni scritte in un linguaggio comprensibile al computer. Il programma e i dati su cui deve operare sono registrati in un dispositivo di memoria, ma è l'unità di controllo del computer a leggere il programma e a eseguire le istruzioni. La lingua dei computer si chiama codice binario e permette di immagazzinare le informazioni in sequenze numeriche fatte solo di 0 e 1 ripetuti. Il codice binario è difficile sia da leggere sia da scrivere e si preferisce quindi usare un linguaggio intermedio, poi tradotto in forma binaria da un programma che funziona come 'interprete'.

Macchine poco intelligenti

Le indicazioni fornite al computer devono essere semplici e chiare. A un essere umano, dotato di intelligenza, si possono invece impartire istruzioni generiche o complesse. Per esempio gli si può dire "aggiungi un po' di sale", un'istruzione generica perché un po' non è una quantità precisamente determinata, oppure gli si può dire "telefonami verso le sette". Anche questa è un'istruzione generica, perché verso le sette indica un'ora approssimativa, e complessa, perché l'azione del telefonare comporta una serie di atti più elementari: alzare la cornetta, comporre il numero, attendere la risposta, chiedere di parlare con una determinata persona.

Quando si deve costruire un algoritmo per far funzionare un computer, invece, bisogna descrivere azioni ben precise ed elementari, cioè non composte, a loro volta, da altre azioni. L'algoritmo, inoltre, deve indicare esattamente, data un'azione, qual è l'azione successiva e si deve poter eseguire in un numero finito di passaggi, portando a un risultato ben preciso. Insomma un computer, non essendo dotato di intelligenza, non può capire o interpretare le indicazioni che gli vengono date: può soltanto eseguirle, passo passo. È importante osservare che un singolo algoritmo, per esempio quello che permette l'addizione di due numeri, può essere utilizzato dal computer per risolvere non un solo problema, ma un intero gruppo di problemi che hanno la stessa struttura. Per esempio, se il computer, o più semplicemente un calcolatore tascabile, è in grado di eseguire la somma tra 2 e 3, saprà anche sommare tutti gli altri numeri: cambiano i dati iniziali, ma non la procedura di calcolo.

Un esempio di algoritmo: il calcolo del massimo comun divisore

Il matematico greco Euclide, famoso per i suoi teoremi di geometria, creò anche un algoritmo per il calcolo del massimo comun divisore (MCD) fra due numeri interi. L'algoritmo si basa sulla proprietà, facilmente dimostrabile, che se due numeri, a e b, sono divisibili per un terzo numero, c, allora anche la loro differenza a−b lo è. Attraverso sottrazioni successive, perciò, si può calcolare il MCD fra a e b effettuando il calcolo su numeri sempre più piccoli. Ricordiamo che il MCD fra due numeri interi è il più grande intero per cui siano divisibili entrambi i numeri. Per esempio, dati i due numeri 30 e 18, il loro MCD è 6: anche 2 e 3 sono divisori di 30 e 18, ma sono più piccoli e quindi 6 è il massimo comun divisore.

Se a e b sono due numeri interi, con a maggiore di b, l'algoritmo euclideo si può scrivere così:

• Prendi a, prendi b;

• Esegui a−b;

• Sostituisci a−b ad a;

• Se b è maggiore di a, allora scambia a con b;

• Ripeti il ciclo fintantoché a si mantiene positivo;

• b è il MCD cercato.

È importante tener presente che a e b, durante l'esecuzione dell'algoritmo, assumono valori diversi.

I diagrammi a blocchi

Un diagramma a blocchi, o diagramma di flusso (in inglese flow chart), è un modo per rappresentare un algoritmo con simboli grafici, i blocchi elementari, uniti da frecce che indicano in quale ordine vanno eseguiti i vari passi dell'algoritmo. I blocchi elementari sono di quattro tipi e hanno forme diverse.

Blocco iniziale/blocco finale. Indica l'inizio e la fine dell'esecuzione dell'algoritmo.

Blocco di lettura/blocco di scrittura. Indica i dati da leggere o da scrivere.

Blocco di azione. Indica l'istruzione da eseguire.

Blocco di controllo. Si usa quando si deve eseguire una certa istruzione se è soddisfatta una certa condizione, altrimenti se ne deve eseguire un'altra; dentro il blocco si scrive la condizione: se la condizione si verifica (SÌ), si passa a una determinata istruzione; se non si verifica (NO) si passa a un'altra istruzione.

Algoritmi di calcolo egiziani

Già gli antichi Egizi si servivano di alcuni algoritmi di calcolo basati sul metodo scelto per scrivere i numeri. Usavano, infatti, una scrittura di tipo additivo in base dieci: avevano un simbolo per le unità, uno per le decine, uno per le centinaia e così via. Ciascun simbolo veniva poi ripetuto tante volte quante era necessario e in questo modo per sommare due numeri bastava semplicemente sommare tra loro per prime le unità e poi progressivamente decine, centinaia, migliaia e così via, facendo gli opportuni cambi. Per eseguire la moltiplicazione, invece, si usava il sistema della duplicazione. Per esempio, per calcolare 25×17 si cominciava con il calcolare 25+25, cioè 25×2; il risultato veniva poi raddoppiato, ottenendo così 25×4, poi raddoppiato ancora due volte per arrivare a 25×16. A questo punto si aggiungeva 25 al risultato così ottenuto.