di Sergio Mauri
Algoritmo, cos’è e a cosa serve? Nel XX secolo il concetto di algoritmo è stato formalizzato per risolvere il problema matematico della decisione posto da David Hilbert[1] nel 1928. Ma le formalizzazioni più famose sono quelle di Godel-Herbrand-Kleene[2] con le funzioni ricorsive[3] (1930-1935) e la Macchina di Alan Mathison Turing[4] (1936-37) che possiamo quasi definire il primo computer. Le operazioni che questa macchina poteva eseguire erano di due tipi: spostarsi per considerare la casella alla destra o alla sinistra di quella in esame, oppure cancellare o imprimere un simbolo. Dopo ognuna di queste operazioni lo stato della macchina poteva essere invariato o modificato. Secondo Turing, una funzione era computabile se si era in grado di calcolarla cioè se la macchina fosse stata messa in grado di farlo. Le macchine di Turing, nonostante la loro semplicità possono computare qualsiasi funzione anche quelle dei computer. Nell’articolo Macchine calcolatrici e intelligenza del 1950, Turing propose di sostituire la domanda: “le macchine possono pensare?” con il seguente problema: è possibile progettare una macchina che sia molto difficile identificare come tale nel corso di una conversazione “cieca”, nella quale cioè l’umano non vede il suo interlocutore e comunica con lui attraverso messaggi scritti? Qui parliamo di “test di Turing”, e questa discussione ha avuto un ruolo notevole nella discussione sull’intelligenza artificiale. Tra l’altro Turing pensava che per la fine del XX secolo, i progressi della tecnologia ci avrebbero permesso di parlare di macchine pensanti.
Continuando, per ciò che riguarda la teoria della ricorsività, oltre che in logica, essa ha trovato applicazioni anche in altri settori della matematica. Tra gli esempi ricordiamo: il decimo problema di Hilbert, che concerneva la questione se esistesse un algoritmo in grado di stabilire, data una equazione diofantea[5], se essa avesse una soluzione intera. Attraverso la ricorsività, a questa domanda è stato risposto negativamente nel 1970. Ricordiamo, inoltre, la teoria della ricorsività generalizzata e la teoria della complessità. La prima è nata provando ad estendere a domini diversi da quello dei numeri naturali, il concetto di funzione ricorsiva. Questo ha avuto ripercussioni in particolare nella teoria degli insiemi. Per quanto riguarda la teoria della complessità, essa si è mossa dalla necessità di applicazioni pratiche nell’ambito della computer science. Consiste nel tentativo di classificare le funzioni ricorsive in base al grado di difficoltà del loro calcolo.
Da allora sono cambiate molte cose, oggi l’algoritmo è parte integrante della nostra vita sotto varie forme e in ogni settore della vita privata e del lavoro. Questo perché tutto ruota attorno a dei calcoli matematici che possono essere considerati invisibili, in quanto quello che sta dietro al risultato ottenuto non è visibile ad occhio nudo. In questo periodo, l’obbligo di mantenere le distanze fisiche ci porta a sfruttare al massimo le capacità di un algoritmo attraverso l’uso di un personal computer o di uno smartphone, che se prima erano importanti, adesso sono diventati indispensabili.
Il termine algoritmo deriva dal matematico arabo al-Khwarizmi[6]. L’algoritmo è definito come una sequenza di istruzioni non ambigue per risolvere un problema in un tempo definito; quindi in modo ancora più formale possiamo dire che un algoritmo è una procedura: finita, completa, non ambigua ed eseguibile, che lavora su dati di ingresso e fornendo dati in uscita.
Descriviamo adesso le sue proprietà elencate prima: finita, completa, non ambigua, eseguibile.
Secondo la proprietà finita, dobbiamo sempre ricevere un risultato, cioè le istruzioni che la compongono e le azioni che vengono eseguite devono essere finiti.
Secondo la proprietà completa, durante l’esecuzione, l’istruzione deve contemplare tutti i passaggi per risolvere il problema.
Secondo la proprietà non ambigua, come dice la parola stessa, un numero c’è o non c’è, quindi per eseguire il calcolo, l’istruzione deve essere definita in modo preciso e senza possibilità di equivoci.
Infine, secondo la proprietà eseguibile, l’istruzione deve poter essere eseguita in qualsiasi computer, e in un tempo finito.
Quando scriviamo un algoritmo esso può essere rappresentato con un linguaggio testuale che può essere di programmazione, naturale, pseudocodice; o con un linguaggio grafico (Flow-chart), costituito da simboli a cui corrispondono precisi tipi di operazioni.
Possiamo anche dire che l’algoritmo è composto da dati di input, output e interni, e da istruzioni. Un dato può essere una costante o una variabile ed entrambe sono aree di memorie; mentre il valore di una costante rimane immutato nel tempo, quello della variabile può essere modificato durante l’esecuzione di un programma. I dati sono i componenti su cui operare. Le istruzioni sono, invece, passi da eseguire che permettono di dare comandi al computer come quelli di lettura, scrittura o assegnamento.
Attraverso delle strutture di controllo viene organizzato l’algoritmo, che consente di intervenire sul suo flusso di esecuzione. Le principali strutture di controllo sono quelle di selezione, sequenza e iterazione.
Una struttura di controllo viene definita di sequenza perché le istruzioni al suo interno devono essere eseguite una dopo l’altra, secondo l’ordine in cui sono state scritte.
Parliamo di struttura di controllo di selezione (costrutto di espressione booleana), quando si ha la possibilità di impostare percorsi diversi. A seconda della condizione possono essere ad una via (soluzione vera o falsa), a due vie (condizioni vera e falsa), in cascata (vengono valutate due o più condizioni), multipla (a più vie all’interno di insieme di valori predefiniti).
Infine, abbiamo la struttura di controllo di iterazione, dove si stabilisce un ciclo per eseguire un insieme di istruzioni. Le strutture di iterazione sono: For/Next; While/End While; Do/While.
Il ciclo For è definito perché è noto il numero di iterazioni da eseguire. Il ciclo While è indefinito precondizionale, perché valuta la condizione prima di entrare nel ciclo, quindi le sue iterazioni durano un numero indefinito di volte, dato che a differenza del for non si sa per quante volte dovrà essere eseguito il ciclo. Il ciclo Do/While, come il While, è indefinito ma postcondizionale, perché valuta la condizione dopo essere entrato almeno una volta nel ciclo, e le sue istruzioni verranno ripetute finché la condizione non diventa vera.
A completare la mia ricognizione su questo avvincente tema, vorrei citare il teorema di Bohm[7]-Jacopini[8], enunciato nel 1966 da due informatici italiani. Esso afferma che: qualunque algoritmo può essere implementato utilizzando tre sole strutture, la sequenza, la selezione, e il ciclo, da applicare ricorsivamente alla composizione di istruzioni elementari. Questa affermazione è solo a livello teorico, ma il teorema è importante perché ha contribuito all’evoluzione della programmazione, perché da queste basi si sono potute creare altre strutture per implementare l’algoritmo.
Svolgendo questo lavoro, infine, ho capito che il tema che andavo costruendo, nella sua organizzazione, poteva essere considerato un algoritmo. Questo perché l’argomento deve essere finito e il risultato deve avere un senso; deve essere completo perché deve contemplare i vari argomenti che gli danno un senso; non deve essere ambiguo perché chi lo legge deve capire di cosa sto parlando ed infine eseguibile, cioè chiunque deve poterlo valutare.
[1] Nato a Konigsberg nel 1862, morto a Gottingen nel 1943, è stato un influente matematico tedesco.
[2] Kurt Friedrich Godel, Jacques Herbrand, Stephen Kleene, furono tre eminenti matematici.
[3]Sono un capitolo fondamentale della logica matematica. In termini matematici, si tratta della classe delle funzioni dei numeri naturali computabili attraverso un algoritmo. In connessione con il concetto di funzione ricorsiva, abbiamo le nozioni di insieme decidibile e semi-decidibile. Un insieme di numeri naturali è decidibile, se esiste un algoritmo per decidere dato un numero n, se esso appartiene ad un insieme oppure no. Si dice semidecidibile, cioè ricorsivamente enumerabile, quando esiste un algoritmo che permette di generare uno dopo l’altro tutti i suoi elementi. Perciò ogni insieme decidibile è semidecidibile, ma non viceversa.
[4]Alan Mathison Turing (Londra 1912-1954), matematico inglese. Studiò a Cambridge e a Princeton, è famoso per avere lavorato per l’intelligence inglese durante la seconda guerra mondiale. Dopo la guerra, all’Università di Manchester collaborò alla realizzazione di uno dei primi calcolatori elettronici. Era molto interessato allo studio della ricorsività. È famoso anche per la macchina di Turing che si compone di un nastro potenzialmente infinito, suddiviso in caselle ognuna delle quali può essere o avere un simbolo costituente l’alfabeto della macchina.
[5] È un’equazione in una o più incognite con coefficienti interi di cui si ricercano le soluzioni intere.
[6] Abū Jaʿfar Muḥammad ibn Mūsā al-Khwārizmī fu matematico, astronomo, astrologo, e geografo persiano. Fu responsabile della biblioteca del califfo al-Ma mun, e lavorò presso la sua corte a Baghdad.
[7]Corrado Böhm (Milano 1923 – Roma 2017), è stato un matematico e informatico italiano, professore dell’Università La Sapienza di Roma. Ricercatore presso l’Istituto per le Applicazioni del Calcolo “Mauro Picone”, dove effettua ricerche sulla Macchina di Turing e sui linguaggi di programmazione.
[8] Giuseppe Jacopini (Genova 1936 – Roma 2001,) matematico e informatico teorico italiano. Ha contribuito allo sviluppo e alla diffusione dell’informatica in Italia. Ha lavorato allo IAC (Istituto per le applicazioni del calcolo) ed è stato docente di logica matematica e informatica presso l’Università La Sapienza di Roma.