A passeggio con l'informatica #10 – Come mettere al lavoro più automi

di Enrico Nardelli

Come abbiamo accennato nella tappa n.6 di questo viaggio (Comprendere gli algoritmi non è difficile), l’informatica come disciplina scientifica nasce – da un punto di vista culturale – quando si comincia a considerare la possibilità di eseguire algoritmi in modo meccanico attraverso un automa. Successivamente, però, ci si rende conto che un’elaborazione può essere attuata anche con la partecipazione di più agenti, condizione che nel periodo attuale è evidente anche all’uomo della strada, a causa dell’onnipresenza di Internet. Tale tipo di situazione, denominata in generale “computazione distribuita”, presenta diversi aspetti. Nel corso delle prossime tappe esamineremo tre dei più importanti, che qui introduciamo brevemente.

Un primo aspetto è la cooperazione, che fa riferimento a un insieme di automi che devono effettuare collettivamente un’elaborazione e, quindi, cooperano nel raggiungimento di quest’obiettivo. Un po’ come quando un gruppo di persone deve realizzare un certo compito in collaborazione. Ad esempio, vi può essere una pratica d’ufficio che necessita di controlli su aspetti differenti, ognuno di competenza di un differente responsabile e da svolgere secondo un ordine stabilito. In tal caso si rende necessaria una comunicazione tra i differenti esecutori per coordinare le varie elaborazioni che ognuno svolge.

Un secondo è la sincronizzazione, in cui vi è la necessità di non intralciarsi nell’uso di risorse condivise, senza che necessariamente vi sia una cooperazione. Sempre per rimanere nel contesto dell’approvazione di pratiche d’ufficio, si immagini che ogni responsabile abbia le sue pratiche da approvare, senza doversi coordinare con gli altri per la decisione. Il processo di approvazione richiede però di mettere un timbro particolare su di essa. La particolarità del timbro è che è composto da due parti, ognuna conservata in un differente deposito. È quindi necessario che i vari responsabili si sincronizzino per evitare il caso di un responsabile che, dopo aver prelevato una parte del timbro, si trovi bloccato perché contemporaneamente un altro responsabile ha già prelevato l’altra parte dall’altro deposito.

Un terzo aspetto, il consenso, fa riferimento al fatto che sia le comunicazioni tra i vari agenti, sia il loro comportamento, possono essere soggetti a guasti o errori. Come facciamo quindi ad essere sicuri che le comunicazioni che abbiamo inviato siano effettivamente arrivate? Come essere sicure di aver ricevuto la risposta della controparte? Osserviamo che questo aspetto è estremamente rilevante nelle applicazioni pratiche, dove guasti, temporanei o permanenti, possono normalmente accadere, nonostante tutte le precauzioni che possono essere prese affinché questo non succeda.

Chiariamo infine che, per semplicità di presentazione, esaminiamo solo il caso di agenti fatti tutti nello stesso modo e quindi in grado di eseguire le istruzioni di uno stesso linguaggio. Inoltre assumiamo che essi abbiano tutti lo stesso livello gerarchico, ovvero non c’è uno che comanda e altri che obbediscono, e che eseguano tutti lo stesso algoritmo.

Considereremo quindi questi tre problemi, cooperazione, sincronizzazione e consenso, nei prossimi tre post, e concluderemo il nostro excursus nell’ambito della computazione distribuita con un post dedicato ai protocolli di comunicazione, che sono un ingrediente fondamentale di quella “rete delle reti”, più comunemente conosciuta come Internet, che è stata il fattore fondamentale per la diffusione dei sistemi digitali nella vita quotidiana di ogni persona.

--
Versione originale pubblicata da "Osservatorio sullo Stato digitale" dell'IRPA - Istituto di Ricerche sulla Pubblica Amministrazione il 27 novembre 2024.

A passeggio con l'informatica #9 – Algoritmi al confine

di Enrico Nardelli

Per completare il quadro della risoluzione algoritmica dei problemi, dobbiamo discutere ancora una situazione, estremamente importante nel contesto odierno. In base a quanto detto nel post precedente, possono esistere dei problemi per i quali non si conoscono algoritmi con funzione di complessità polinomiale (e quindi non si può dire che appartengono alla classe P), ma per cui non si è ancora trovata la dimostrazione di impossibilità di ottenerli (e quindi non si può dire che appartengono propriamente alla classe EXP). Ciò vuol dire che per essi si conosce almeno un algoritmo risolutivo (la cui funzione di complessità è esponenziale), e questo li classifica come problemi computabili, ma non si sa dire se siano problemi che appartengono alla varietà “buona” (cioè ammettono algoritmi polinomiali, ossia sono trattabili) oppure “cattiva” (con solo algoritmi esponenziali, cioè intrattabili). In questo caso il problema è in una specie di limbo, nel quale gli informatici teorici hanno individuato un insieme molto importante detto classe NP, che marca il confine fra la trattabilità e l’intrattabilità.

Senza entrare nel dettaglio di come tale classe venga definita (per cui rimando al mio libro La rivoluzione informatica), possiamo dire che ad essa appartengono i problemi le cui soluzioni sono verificabili in tempo polinomiale e per i quali si conoscono solo algoritmi risolutivi di complessità esponenziale. In effetti esistono centinaia di questi problemi (migliaia se ne consideriamo le varianti), per i quali è stata dimostrata l’equivalenza reciproca. Questa equivalenza vuol dire che se per uno solo di essi si trovasse un algoritmo polinomiale, allora tutti questi problemi rientrerebbero nella classe P (sarebbero, cioè, problemi trattabili). Se per uno solo di essi si dimostrasse invece l’appartenenza propria alla classe EXP, allora verrebbero tutti classificati come intrattabili (anche se quest’ultima ipotesi appare poco probabile alla maggior parte degli studiosi).

Allo stato attuale delle conoscenze dell’informatica teorica si sa che la classe P è strettamente contenuta nella classe EXP (ricordo che un insieme A è strettamente contenuto nell’insieme B se ogni elemento di A appartiene anche a B e inoltre si è certi dell’esistenza di elementi che appartengono a B e non appartengono ad A). Però, le relazioni note tra le classi P, NP ed EXP sono solo di contenimento, cioè che P è contenuta in NP e che NP è contenuta in EXP, ma non si sa esattamente quale di questi contenimenti sia stretto. L’aspetto più interessante riguarda la relazione tra le classi P e NP. Potrebbe essere stretto oppure le due classi potrebbero coincidere. Il problema se la classe P e la classe NP coincidano o meno, ovvero

P=NP ?

è probabilmente il problema aperto più famoso dell’informatica teorica. Il Clay Mathematics Institute lo ha inserito nel 2000 fra i sette problemi del millennio e ha offerto un premio di un milione di dollari per la sua dimostrazione.

Il problema ha un interesse particolare dal momento che problemi nella classe NP che si pensa non siano in P sono spesso alla base dei metodi crittografici, che proteggono la sicurezza delle transazioni commerciali su Internet. Ad esempio, il sistema di cifratura a chiave pubblica RSA ha alla base della sua sicurezza il fatto che la scomposizione di un numero intero in fattori primi è uno di questi problemi.

Poiché non si conoscono, al momento attuale, algoritmi efficienti (cioè eseguibili in tempo polinomiale) per scomporre un intero nei suoi fattori primi, il sistema non può essere violato in un tempo accettabile. Va ricordato che, con sufficienti attrezzature hardware dedicate (che sono alla portata di organizzazioni di grandi dimensioni che possono contare su ingenti risorse economiche quali, ad esempio, l’NSA, acronimo di National Security Agency, l’agenzia per la sicurezza nazionale degli Stati Uniti) si riescono a scomporre interi di 1.024 bit, che era il valore raccomandato per la costruzione delle chiavi di RSA fino a qualche anno fa. Bruce Schneier, esperto USA di sicurezza, ha raccomandato nel 2007, quando è stata annunciata la scomposizione di un intero di circa 1.024 bit (anche se di un tipo particolare che ha reso il lavoro più semplice) di abbandonare le chiavi di questa lunghezza. La disponibilità di computer cosiddetti “quantistici” è un’altra possibile minaccia alla cifratura a chiave pubblica RSA, ma anche per questa eventualità si stanno prendendo le opportune contromisure.

--
Versione originale pubblicata da "Osservatorio sullo Stato digitale" dell'IRPA - Istituto di Ricerche sulla Pubblica Amministrazione il 20 novembre 2024.

A passeggio con l'informatica #8 – Ma quanto ci mette quest’algoritmo?

di Enrico Nardelli

Abbiamo visto nel post precedente che per alcune elaborazioni non è possibile trovare alcun algoritmo. In aggiunta, dal momento che siamo mortali e non abbiamo a disposizione un tempo infinito per ottenere una risposta, ci interessa anche sapere quanto tempo può metterci un certo algoritmo a completare la sua elaborazione.

In prima istanza ci interessa distinguere quei problemi, chiamati trattabili, in cui man mano che il problema cresce di dimensione continuiamo a dover aspettare un tempo “umano” per la risposta, e quei problemi, detti invece intrattabili, in cui questo non accade. Invece di parlare di tempo, discuterò questi aspetti facendo riferimento al numero di passi necessario per risolvere il problema da parte del miglior algoritmo noto per esso. Il motivo di questa scelta è che il tempo può dipendere dalla velocità intrinseca dello specifico calcolatore usato per l’esecuzione del (programma che concretizza) l’algoritmo, mentre noi siamo interessati a una caratterizzazione indipendente dalle evoluzioni tecnologiche. In ogni caso, i risultati in termini di trattabilità o intrattabilità non cambiano. Viceversa, ma non ne parleremo in questi post e vi rimando al libro La rivoluzione informatica per una discussione, l’utilizzo di computer quantistici rende trattabili alcuni dei problemi che sono intrattabili usando un computer classico (che è un automa equivalente alla MUT).

Ogni algoritmo, una volta espresso in un programma, richiede un tempo proporzionale al numero delle istruzioni che devono essere eseguite. Dato quindi l’algoritmo, si può scrivere la funzione matematica, detta funzione di complessità dell’algoritmo, che esprime questo numero in base alla dimensione N del problema. Dovremmo ricordare tutti, per averla studiata a scuola, la differenza tra una funzione polinomiale e una funzione esponenziale. Nella prima, l’argomento N è la base di una potenza (p.es. N ² oppure N ³ o anche N¹⁰), mentre nella seconda è l’esponente della potenza (p.es. 2^N oppure 3^N o anche 10^N ). Le funzioni esponenziali crescono molto più velocemente di quelle polinomiali. Nella tabella seguente riportiamo il valore di queste funzioni per differenti valori dell’argomento N. Ricordiamo che il simbolo “ ~ ” vuol dire “circa”, “approssimativamente”, e che la notazione, ad esempio, 10¹⁰ indica la cifra 1 seguita da 10 zeri, cioè il valore 10 miliardi. Nella tabella si vede che già per N = 60, tutte le funzioni esponenziali presentate hanno valore maggiore di tutte le funzioni polinomiali.

È importante ricordare che la funzione di complessità viene espressa, per ogni algoritmo, in riferimento al cosiddetto “caso pessimo” per l’esecuzione dell’algoritmo stesso, ovvero a quello più sfavorevole in termini di numero di istruzioni da eseguire (assumendo, per semplicità, che tutte le istruzioni richiedano uno stesso tempo). Consideriamo il primo dei problemi presentati nel post precedente, quello dell’ordinamento. Vogliamo sapere quale sia il tempo massimo garantito di esecuzione dell’algoritmo in funzione della quantità N, qualunque cosa possa accadere con gli N dati in ingresso. Si può dimostrare che per questo problema il miglior algoritmo conosciuto garantisce un tempo proporzionale a N⋅log(N ), dove “log” è la funzione logaritmica che dovremmo ricordarci dalle scuole superiori, e questo risultato non è migliorabile.

Assumiamo ora che l’esecuzione di una singola istruzione richieda a un moderno computer un nanosecondo, cioè un miliardesimo di secondo. In formula, 10^-9, cioè (1/10)⁹ secondi. Consideriamo poi il secondo problema, dei cammini minimi, per il quale il miglior algoritmo garantisce nel caso pessimo l’esecuzione di al più N ³ istruzioni per una lista con N città (trascurando miglioramenti marginali ottenuti negli ultimi anni). Allora siamo in grado di risolverlo per 100 città in un millesimo di secondo (perché 1.000.000, cioè 10⁶, moltiplicato per 10^-9 fa 10^-3, cioè (1/10)³ = 0,001) e per 1.000 città in un secondo (1.000³ = 10⁹, che moltiplicato per 10^-9 fa esattamente 1). Se avessimo poi bisogno di risolverlo per 10.000 città, servirebbero 1.000 secondi, ovvero circa 17 minuti. Per 100.000 città sarebbe addirittura necessario un milione di secondi, pari a circa 12 giorni: un tempo molto lungo, ma tutto sommato accettabile.

Vediamo invece cosa accade per il terzo problema, del commesso viaggiatore, per il quale i migliori algoritmi conosciuti richiedono l’esecuzione di 2^N istruzioni per una lista con N città. In questo caso potremmo risolverlo per 20 città in appena più di un millesimo di secondo, ma già per 30 città sarebbe necessario un secondo, 40 città richiederebbero 17 minuti, e 50 sarebbe il massimo numero di città per cui il problema è risolvibile aspettando un tempo di 12 giorni. La risoluzione per 60 città potrebbe essere ottenuta in circa 32 anni, chiaramente un tempo inaccettabile.

Ecco quindi che la distinzione tra problemi “trattabili” e problemi “intrattabili” viene data in base al tipo di funzione che esprime il numero di passi necessario per i suoi algoritmi risolutivi. In particolare, se è noto un algoritmo risolutivo per il quale tale funzione di complessità è polinomiale, cioè il problema ammette un algoritmo polinomiale, allora il problema è detto trattabile (cioè, si dice che appartiene alla classe P). Se invece si è dimostrato che ogni possibile algoritmo risolutivo ha una funzione di complessità esponenziale, il problema è intrattabile (cioè, si dice che appartiene propriamente alla classe EXP).

Mentre nel primo caso basta trovare un solo algoritmo polinomiale per definire il problema come trattabile, nel secondo caso la dimostrazione deve essere condotta prescindendo da specifici algoritmi, dal momento che l’insieme dei possibili algoritmi risolutivi è infinito e il fatto che un algoritmo di complessità polinomiale non sia stato finora trovato non implica che non esista.

Per discutere questa situazione da un altro punto di vista e far comprendere meglio che l’intrattabilità non può essere risolta con gli avanzamenti tecnologici, consideriamo cosa accadrebbe se avessimo un computer mille volte più veloce di quelli attuali. Avendo allora a disposizione 12 giorni, saremmo in grado di risolvere il secondo problema per un milione di città invece che per 100.000. Nel caso del terzo problema, nello stesso tempo di 12 giorni riusciremmo a passare solo da 50 a 60 città!

Il prossimo post, l’ultimo dedicato agli algoritmi, prenderà in considerazione una situazione di confine fra la trattabilità e l’intrattabilità molto rilevante sia da un punto di vista culturale che pratico.

--
Versione originale pubblicata da "Osservatorio sullo Stato digitale" dell'IRPA - Istituto di Ricerche sulla Pubblica Amministrazione il 13 novembre 2024.

A passeggio con l'informatica #7 – Possiamo sempre trovare un algoritmo?

di Enrico Nardelli

La domanda con cui ci siamo lasciati nel post precedente era se sia sempre possibile trovare l’algoritmo per effettuare l’elaborazione che abbiamo in mente.

A questo scopo bisogna prima di tutto chiarire che le situazioni alle quali possiamo applicare gli algoritmi richiedono che sia possibile descrivere con precisione sia l’insieme dei possibili dati di ingresso (detto input ) all’algoritmo stesso che l’insieme dei risultati in uscita (detto output ) accettabili, espressi in funzione degli input. Ma anche per i problemi formulabili in questo modo, vedremo nel seguito che la risposta è negativa. Aggiungiamo che la descrizione viene eventualmente fatta, per algoritmi che non terminano mai perché le elaborazioni che devono effettuare non si devono interrompere, con riferimento a un determinato intervallo temporale.

Consideriamo adesso quattro problemi che presentano caratteristiche diverse in termini di computabilità (o calcolabilità, i termini che denotano il settore dell’informatica che si occupa di questi aspetti), che verranno discusse in questo e nel successivo post.

1. Un primo esempio di problema (detto “ordinamento”) affrontabile algoritmicamente prevede in input una lista di N numeri interi e richiede in output la lista dei numeri ordinati per valore crescente.
2. Un secondo esempio di problema (detto “cammini minimi”) prevede in input una lista di N città, per ognuna delle quali è specificato un elenco di città (appartenenti alla lista stessa) alle quali esse sono connesse direttamente da un tratto di strada di cui viene data la lunghezza. In output si richiede, per ogni coppia di città P e Q dell’elenco, la successione dei tratti di strada che porta da P a Q che ha lunghezza totale minima.
3. Un terzo esempio (detto “commesso viaggiatore”) ha lo stesso input del secondo, ma l’output richiede di ottenere una successione di tratti di strada che passi per tutte le città dell’elenco una volta sola e abbia lunghezza totale minima.
4. Un quarto problema (detto “arresto”) ha come input uno specifico programma scritto in un determinato linguaggio di programmazione e uno qualunque dei possibili dati di ingresso al programma. L’output richiesto è “VERO” se quel programma elaborando questi dati si arresta dopo un tempo finito, “FALSO” altrimenti.

Osserviamo che l’algoritmo, per essere tale, deve “funzionare”, cioè produrre l’output corretto, per tutti i possibili input. Ciò vuol dire, per il primo problema, per tutte le possibili liste di N numeri; per il secondo e il terzo problema, per tutte le possibili liste di N città con tutte le possibili connessioni a città adiacenti; per il quarto problema, per tutti i possibili programmi scritti nel linguaggio scelto e tutti i loro possibili dati di ingresso.

Per i primi tre problemi sopra descritti esistono algoritmi risolutivi, quindi si dice che i problemi sono computabili, mentre il quarto problema, quello dell’arresto, non ammette alcun algoritmo risolutivo, ed è quindi un problema incomputabile. A questo punto qualcuno potrebbe pensare, visto che un algoritmo deve essere comunque espresso in un determinato linguaggio di programmazione mediante un programma che deve essere eseguito da un determinato automa, che basterebbe avere un linguaggio più moderno o un automa più potente.

Non è così. È stato proprio Alan Turing a dimostrare, nell’articolo scientifico del 1936 che viene considerato la nascita dell’informatica come disciplina scientifica autonoma, che il quarto problema non è intrinsecamente risolvibile, a prescindere da quale siano il linguaggio di programmazione o l’automa usati. In altre parole, non esiste un algoritmo per il problema dell’arresto.

Sottolineo che tale risultato rimane vero anche considerando automi di tipo “quantistico” (che sono il modello teorico dei cosiddetti “computer quantistici ” di cui molto si parla in questi anni). Si tratta di un risultato importantissimo, non solo dal punto di vista culturale ma anche su un piano filosofico, perché definisce dei limiti ben precisi a ciò che può essere realizzato mediante i calcolatori e, quindi, anche alla nostra possibilità di “conoscere” qualcosa attraverso procedimenti algoritmici. Il che non può che farci piacere, visto che come esseri umani abbiamo a nostra disposizione altri modi di “conoscere”, che esulano dall’assoluta razionalità meccanica di un automa e che questi ultimi non possiedono.

Nel prossimo post ci occuperemo del tempo necessario per l’esecuzione degli algoritmi e di come questo possa variare da situazioni accettabili ad altre del tutto insostenibili.

--
Versione originale pubblicata da "Osservatorio sullo Stato digitale" dell'IRPA - Istituto di Ricerche sulla Pubblica Amministrazione il 6 novembre 2024.

A passeggio con l'informatica #6 – Comprendere gli algoritmi non è difficile

di Enrico Nardelli

Molti utilizzano la parola algoritmo, ma non sempre è chiaro il significato di tale concetto. Intanto cominciamo con il dire che il termine algoritmo risale al latino medievale, epoca in cui, secondo il vocabolario Treccani online, «indicava i procedimenti di calcolo fondati sopra l’uso delle cifre arabiche ». Come penso ormai molti sappiano, la parola deriva dall’appellativo al-Khuwārizmī del matematico arabo del IX secolo Muḥammad ibn Mūsa, che era nativo di Khwarizm, regione dell’Asia Centrale. Nell’informatica si indica con questo termine una versione astratta, cioè indipendente da uno specifico linguaggio reale di programmazione, dell’elaborazione desiderata. Un algoritmo è quindi un metodo risolutivo, che prescinde (cioè astrae) da una specifica forma fisica di espressione. Tale astrazione è fondamentale dal punto di vista scientifico, perché fornisce generalità al modo di descrivere le varie elaborazioni.

D’altro canto, un algoritmo può essere effettivamente eseguito soltanto se viene specificato qual è l’automa (detto anche esecutore o agente) che lo deve attuare. Questa indicazione non era rilevante prima della nascita dell’informatica, quando erano solo i matematici a eseguire algoritmi, cioè procedimenti risolutivi di problemi. Le radici culturali dell’informatica risiedono nello sforzo che i matematici hanno attuato nei primi decenni del XX secolo per automatizzare la dimostrazione dei teoremi. Da questo tentativo (frustrato dai risultati di incompletezza dell’aritmetica dimostrati negli anni 20 di quel secolo da Gödel) che è nata quella focalizzazione sull’esecutore meccanico che ha portato, da un punto di vista culturale, alla nascita dell’informatica come disciplina autonoma.

All’interno dell’informatica, la specifica di un algoritmo fa quindi sempre riferimento, implicitamente o esplicitamente, a una specifica tipologia di automa. Come abbiamo visto nel primo dei post in cui abbiamo spiegato il concetto di automa, ne esistono infatti alcuni che non riescono a realizzare una certa elaborazione (gli automi a stati finiti) mentre altri (le macchine a registri) sono in grado di risolvere qualunque problema che sia risolvibile in modo meccanico, così come è in grado di fare la macchina universale di Turing (MUT). Per questo è importante indicare sempre qual è l’agente che si ha in mente per l’esecuzione dell’algoritmo stesso. D’ora in avanti assumeremo – com’è abituale nell’informatica – che sia uno qualunque degli automi equivalenti alla MUT. Aggiungiamo che, richiedendo come necessario che la specifica di un algoritmo faccia riferimento all’automa che lo eseguirà, ne deriva che ogni passo dell’algoritmo deve necessariamente corrispondere a una o più istruzioni che l’agente è direttamente in grado di attuare. In altre parole, se ogni passo non è meccanicamente e automaticamente eseguibile, il procedimento descritto non è un algoritmo. D’altro canto, il fatto che l’algoritmo debba terminare in un tempo finito non è un aspetto rilevante in assoluto, considerato che ci sono situazioni nelle quali le elaborazioni non terminano mai: si pensi, ad esempio, agli algoritmi di controllo di apparati industriali che devono essere operativi senza interruzioni.

Si dice spesso – a livello divulgativo – che l’algoritmo è come una ricetta di cucina. Quest’analogia è vera nel senso che la descrizione di una ricetta è indipendente sia dagli specifici ingredienti che vengono veramente usati (la specifica di “100 grammi di farina doppio zero” e “300 grammi di marmellata di albicocche” non prescrive specifiche marche o varietà) sia da come avviene la loro effettiva manipolazione (“mescolare la farina e lo zucchero” non prescrive l’uso di mani o spatole). Il termine algoritmo denota quindi l'insieme finito delle istruzioni che specificano il procedimento di elaborazione a un livello più astratto rispetto a ogni possibile rappresentazione mediante un linguaggio direttamente comprensibile dall’automa che lo deve eseguire. In altre parole, l'algoritmo è ciò che è invariante, dato un agente, rispetto a tutti i modi di esprimerlo mediante specifiche liste finite di istruzioni direttamente eseguibili dall’agente stesso.

Sia nel caso di una ricetta che di un algoritmo l’esecutore deve essere in grado di attuare le istruzioni ricevute. Però, l’agente che esegue una ricetta di cucina è un essere umano che certamente non realizza meccanicamente e automaticamente le proprie azioni, ma utilizza la sua intelligenza e flessibilità per ottenere lo scopo descritto anche (in una certa misura che dipende dalla sua specifica esperienza) in presenza di errori nella ricetta o di variazioni nel contesto in cui opera. Questo permette di eseguire anche ricette le cui specifiche istruzioni fanno appello alla valutazione dell’esecutore come, ad esempio, “aggiungere sale quanto basta”. Non si tratta certamente di un’esecuzione meccanica, perciò una ricetta di cucina non è un algoritmo! Diversamente, un automa non ha alcuno spazio per interpretazione, adattamento e flessibilità. Anche una semplicissima differenza tra ciò che gli viene chiesto di fare e ciò che è in grado di fare, intrinsecamente o nell’ambiente, determina l’impossibilità di eseguire con successo il programma.

Per specificare quindi un algoritmo che un automa deve attuare è necessario usare le istruzioni del linguaggio di programmazione che l’automa è in grado di eseguire e scrivere il relativo programma informatico, cioè uno dei tanti diversi possibili modi di esplicitare l’algoritmo in quello specifico linguaggio di programmazione.

Nella figura sotto presentiamo graficamente le relazioni tra questi concetti: il linguaggio di programmazione è il mezzo attraverso cui l’algoritmo assume la forma concreta di un programma che viene eseguito dall’automa.

Con un paragone letterario, possiamo dire che tra un algoritmo e un programma (una qualunque delle tante diverse possibili concretizzazioni) sussiste, attraverso il linguaggio di programmazione, la stessa relazione che c’è tra un pensiero e una sua forma scritta (una delle tante possibili), attraverso il linguaggio scelto per esprimersi. Usando invece una terminologia filosofica, possiamo dire che l’algoritmo è la “idea platonica” di uno specifico processo di elaborazione, mentre un programma è una delle sue tante concretizzazioni possibili.

Vedremo nel prossimo post se c’è sempre un algoritmo per qualunque elaborazione vogliamo effettuare.

--
Versione originale pubblicata da "Osservatorio sullo Stato digitale" dell'IRPA - Istituto di Ricerche sulla Pubblica Amministrazione il 30 ottobre 2024.