A passeggio con l'informatica #13 – Raggiungere un accordo non è mai facile

di Enrico Nardelli

In questa tappa affrontiamo il terzo dei problemi rilevanti per la computazione distribuita, quello del consenso. Anche in questo caso lo introduciamo con un esempio ispirato alla vita d’ufficio.

Lo scenario considerato è quindi quello di due colleghi, Anna e Bruno, che devono presentarsi insieme dal capo-ufficio per sostenere una causa comune. Poiché sono consapevoli del fatto che andando insieme avranno maggiori opportunità di farsi valere, mentre se va uno solo dei due una punizione è certa, hanno già concordato il possibile giorno e ora in cui incontrarsi davanti alla porta del capo. A questo punto devono solo decidere se realizzare o no questo piano. Allo scopo si scambiano messaggi: il problema però è che qualche messaggio può perdersi a causa di guasti o malfunzionamenti degli strumenti che usano, che non prevedono una “ricevuta di consegna”, cioè una conferma ricevuta dal mittente che il messaggio è arrivato al destinatario. Ciò non deve sorprendere perché, anche in un’epoca di sistemi digitali, non sempre si ha la certezza che un messaggio di posta elettronica sia stato effettivamente consegnato al destinatario. Questo vuol dire, ad esempio, che dopo che Anna ha inviato un messaggio a Bruno, non può avere la certezza che esso sia arrivato e può soltanto attendere una risposta o inviarlo di nuovo. In altre parole, Anna non può distinguere la situazione in cui il suo messaggio è andato perso dalla situazione in cui è la risposta di Bruno che si è persa. Solo quando le giunge la risposta di Bruno può dedurre che il suo messaggio è arrivato. Ma a questo punto è Bruno che si trova in una situazione di incertezza: non è sicuro che la sua risposta sia stata consegnata ad Anna.

Come possono fare Anna e Bruno per risolvere questa situazione? Esiste un algoritmo che possa aiutarli ad avere la sicurezza che si sono messi d’accordo e nessun messaggio è andato perso? La risposta, sorprendente ma vera, è che, anche in questo semplicissimo scenario, non esiste un tale algoritmo.

Ne diamo la prova con il meccanismo della dimostrazione per assurdo. Con questo procedimento matematico si assume che qualcosa sia vero, poi si fa vedere che da questa assunzione deriva una contraddizione logica (ad esempio, si deriva che un’affermazione è contemporaneamente vera e falsa) e a questo punto si conclude che l’assunzione iniziale è assurda, cioè non vera.

Supponiamo, allora, che esista un algoritmo, che chiamiamo Accordo, che consente di mettersi d’accordo per realizzare il piano presentandosi entrambi dal capo-ufficio. Consideriamo poi lo scenario, che chiamiamo Possibile, in cui Accordo ha fatto effettivamente mettere d’accordo Anna e Bruno con lo scambio del numero minimo di messaggi. Consideriamo poi un secondo scenario, chiamato Alternativo, in cui Anna e Bruno si scambiano con l’algoritmo Accordo esattamente gli stessi messaggi scambiati nello scenario Possibile : nello scenario Alternativo però l’ultimo messaggio, che ipotizziamo sia stato inviato da Anna a Bruno, non raggiunge quest’ultimo perché viene perso. Dal punto di vista di Anna, non c’è differenza tra i messaggi che ha ricevuto nello scenario Possibile e quelli che ha ricevuto in quello Alternativo : quindi va all’appuntamento in entrambi gli scenari. Dal punto di vista di Bruno, nello scenario Alternativo gli è arrivato un messaggio in meno e l’algoritmo Accordo può far compiere a Bruno una di queste due azioni: (1) Bruno non va all’appuntamento, oppure (2) Bruno va all’appuntamento. Nel caso 1 si deduce che l’algoritmo Accordo è scorretto, perché Anna si presenta dal capo-ufficio mentre Bruno no: questa è una contraddizione con l’assunto iniziale che Accordo li faccia presentare entrambi e prova l’assurdità dell’esistenza di Accordo. Nel caso 2 si ottiene che Anna e Bruno hanno effettivamente scambiato nello scenario Alternativo un messaggio in meno per andare entrambi all’appuntamento, e questo contraddice l’ipotesi che Possibile sia lo scenario col numero minimo di messaggi. Anche nel caso 2, quindi, tale contraddizione prova l’assurdità dell’esistenza dell’algoritmo ottimo Accordo. Notate che potremmo assumere che l’ultimo messaggio sia quello inviato da Bruno ad Anna ma il ragionamento precedente rimarrebbe dello stesso tipo e le sue conclusioni ugualmente valide.

Questo è quello che ci dice la teoria. Nella pratica, quando due persone concordano un appuntamento in questo modo, man mano che si scambiano messaggi il loro livello di confidenza aumenta (anche in funzione del livello di conoscenza che ognuna di esse ha dell’affidabilità dell’altra) e, generalmente, quando una delle due parti ha ricevuto due messaggi dalla controparte, si ritiene ragionevolmente sicura che l’accordo sia stato raggiunto. È la situazione illustrata nella figura sottostante:

Quelli un po’ più diffidenti magari faranno un terzo scambio di messaggi, ma tendenzialmente si riterranno abbastanza sicuri di aver raggiunto il consenso. Ovviamente, quando la posta in gioco è alta e serve la certezza al 100% le persone usano il telefono, cioè la comunicazione sincrona, oppure meccanismi di comunicazione che certificano l’avvenuta consegna del messaggio.

Nel prossimo post prenderemo brevemente in esami i “protocolli di comunicazione” ovvero l’insieme di regole che definiscono come due esecutori si coordinano per scambiare informazioni.

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

A passeggio con l’informatica #12 – La sincronizzazione fra più esecutori

di Enrico Nardelli

Come descritto nel post introduttivo alla computazione distribuita, un secondo problema rilevante è quello della sincronizzazione, in cui i vari esecutori non devono coordinare il loro lavoro, che ognuno svolge in maniera autonoma, ma devono evitare di intralciarsi nell’uso di risorse che servono a tutti.

Lo discutiamo attraverso l’esempio di un ufficio in cui due impiegati, Rossi e Bianchi, devono ognuno controllare le proprie pratiche senza doversi coordinare nella loro gestione. Assumiamo per semplicità che il loro lavoro consista solo nel controllo, seguito dal rifiuto o dall’approvazione della pratica in esame. L’approvazione della pratica avviene suggellando la decisione attraverso un timbro particolare, fatto da due parti che si trovano in due posti diversi. Se i due impiegati non attuano una qualche forma di sincronizzazione, si possono trovare nella situazione in cui uno ha preso una parte del timbro, l’altro ha preso l’altra parte e nessuno dei due può approvare la pratica. Escludiamo strategie particolari che le persone potrebbero attuare in casi come questi, per esempio andando a trovare l’altro responsabile e concordando che uno dei due ceda la sua parte all’altro per fargli timbrare la sua pratica per poi ricevere indietro il timbro completo per approvare la propria.

Questo è il più semplice esempio possibile di sincronizzazione. Può essere risolto facendo eseguire a entrambi gli agenti uno stesso algoritmo, detto di Peterson, che non riporto interamente qua per la sua complessità formale, rimandando al mio libro La rivoluzione informatica per la sua spiegazione di dettaglio e fornendo nel seguito una descrizione intuitiva.

L’algoritmo assume che vi siano tre “variabili globali” che, nel contesto di un ufficio quale quello che stiamo considerando, possiamo considerare come tre bacheche che tutti gli impiegati possono leggere. Ogni bacheca è identificata da un nome: Rossi_vuole_timbrare, Bianchi_vuole_ timbrare, Adesso_è_il_turno_di. All’inizio dell’algoritmo in ognuna delle prime due bacheche è scritto FALSO, mentre ciò che è scritto sulla terza è irrilevante. L’algoritmo ripete in continuazione la sequenza di azioni descritta nel seguito.

L’impiegato che deve approvare la sua pratica dichiara che vuole timbrare, cioè scrive VERO sulla bacheca che inizia col suo nome, e scrive il nome dell’altro impiegato sulla bacheca che esprime di chi è il turno.

Dopo di questo, controlla se è contemporaneamente vero che l’altro impiegato vuole timbrare e che è il suo turno, e in caso positivo (chiamiamo “semaforo rosso” questa eventualità) si mette ad aspettare che questa situazione diventi falsa.

Quando ciò accade (cioè non vi è più il semaforo rosso) allora (1) va a prendere entrambi le parti del timbro, (2) approva la pratica, (3) rilascia entrambe le parti del timbro. Queste tre azioni vengono tecnicamente definite “sezione critica”, perché sono quelle che devono essere eseguite solo da un automa per volta, per non causare la situazione di blocco descritta all’inizio.

Successivamente all’esecuzione della sezione critica l’impiegato scrive FALSO sulla bacheca che inizia col suo nome e continua a controllare le sue pratiche.

Terminata la descrizione dell’algoritmo facciamo vedere che effettivamente la sezione critica può essere eseguita solo da un automa alla volta e che solo un automa alla volta può essere nello stato di attesa.

Assumiamo che Bianchi stia eseguendo la sua sezione critica e che Rossi sia in attesa. Allora Rossi potrà entrare nella sua sezione critica solo quando Bianchi uscirà dalla sua e scriverà FALSO sulla bacheca Bianchi_vuole_timbrare (rendendo così falsa la condizione che teneva Rossi in attesa, ovvero rimuovendo il semaforo rosso). Quando questo accade, Bianchi si trova a controllare pratiche e Rossi entra nella sezione critica: dopo un po’ anche Rossi uscirà dalla sua sezione critica e passerà a controllare pratiche.

Immaginiamo adesso che, mentre Bianchi continua a controllare pratiche, Rossi dichiari che vuole timbrare. Se Bianchi continua sempre a controllare pratiche allora Rossi non deve attendere (perché su Bianchi_vuole_timbrare c’è scritto FALSO) ed entra nella sua sezione critica. Se, in questa fase in cui Rossi è nella sua sezione critica, anche Bianchi dichiara di voler timbrare, allora troverà il semaforo rosso (perché su Rossi_vuole_timbrare c’è scritto VERO e inoltre sulla bacheca del turno c’è scritto che è il turno di Rossi) e rimarrà in attesa. Siamo quindi nella situazione precedentemente descritta, a parti invertite tra Rossi e Bianchi.

Vediamo invece che succede se, proprio subito dopo che Rossi ha dichiarato che vuol timbrare, anche Bianchi scrive VERO sulla bacheca Bianchi_vuole_timbrare. Allora non può accadere che entrambi vadano nello stato di attesa perché, anche se tentano di scrivere contemporaneamente sulla bacheca che esprime di chi è il turno potranno scrivere solo uno dopo l’altro e alla fine sulla bacheca ci sarà scritto o Bianchi o Rossi. Nel primo caso è Rossi che va in attesa e Bianchi entra nella sezione critica, nel secondo caso, avviene il contrario. Se invece il tentativo di scrittura sulla bacheca del turno, dopo aver dichiarato entrambi la volontà di timbrare non è contemporaneo ma avviene prima (ad esempio) quello di Rossi, allora sarà Rossi a entrare in attesa, ma solo momentaneamente, perché quando poi Bianchi arriva a scrivere sulla bacheca del turno renderà falsa la condizione che bloccava Rossi nello stato di attesa, consentendo a quest’ultimo di entrare nella sua sezione critica mentre lui (Bianchi) va in attesa.

Nel prossimo post esamineremo il terzo importante problema della computazione distribuita, quello del consenso.

--
Versione originale pubblicata da "Osservatorio sullo Stato digitale" dell'IRPA - Istituto di Ricerche sulla Pubblica Amministrazione l'11 dicembre 2024.

A passeggio con l'informatica #11 – Come fanno più automi a mettersi d’accordo?

di Enrico Nardelli

Come abbiamo introdotto nel post precedente, stiamo considerando il caso di più agenti che devono eseguire collettivamente un’elaborazione. La comunicazione tra di essi in questo contesto avviene mediante lo scambio asincrono di messaggi. Ricordo che lo scambio asincrono è ciò che avviene con la posta elettronica, mentre lo scambio sincrono è il caso di una telefonata, che richiede la disponibilità contemporanea di entrambi gli interlocutori.

Dobbiamo inoltre precisare con esattezza le caratteristiche dell’insieme degli automi e della loro organizzazione. Per rimanere a un livello molto semplice (e rimandando al mio libro La rivoluzione informatica per maggiori dettagli) assumiamo che ogni esecutore sia identificabile tramite un diverso numero intero. Tutti gli automi eseguono lo stesso algoritmo, ma in ogni esecutore l’algoritmo può prendere decisioni diverse in base ai messaggi ricevuti e al suo identificatore.

Un ultimo elemento rilevante da definire è quale sia la struttura della rete di comunicazione disponibile per l’insieme di automi, cioè con quali altri agenti si possono scambiare i messaggi che sono necessari per realizzare il coordinamento. Ad esempio, un esecutore può parlare con tutti gli agenti o solo con un sottoinsieme? Trascurando i casi irrilevanti di automi che non parlano con alcun altro automa, sono possibili diverse scelte, da quelle assolutamente estreme (e quindi in qualche modo poco interessanti) in cui ogni agente parla solo con un altro agente (il caso a sinistra nella figura sotto) oppure in cui ogni agente parla con tutti gli altri agenti (a destra).

Un modello semplice ma comunque non banale di struttura della rete di comunicazione è quello del cosiddetto “anello”, in cui si immagina l’insieme degli agenti disposti a cerchio e ogni agente parla solo con chi gli sta a destra e a sinistra.

Il più semplice problema che si può affrontare, in tema di cooperazione, è quello della scelta di un “comandante” o “direttore”, per eventualmente in futuro guidare l’azione del collettivo.

All’inizio nessuno degli agenti dell’anello è il direttore. La soluzione corretta del problema si ha quando esattamente uno degli agenti è il comandante e lo rimane stabilmente, nel senso che il processo di elaborazione che ha portato alla sua scelta non gli fa più cambiare stato, e questa informazione è nota a tutti.

Un semplice algoritmo, detto di Chang-Roberts, per risolvere questo problema nelle ipotesi che stiamo considerando è fatto nel modo che adesso descriviamo. Ricordiamo che questo algoritmo viene eseguito da ogni agente.

Ogni esecutore inizia l’algoritmo o per sua spontanea decisione o perché gli arriva un messaggio dall’agente alla sua destra. Se un esecutore riceve un messaggio con identificatore minore del suo non fa niente. Se un esecutore riceve un messaggio con un identificatore maggiore del suo lo inoltra all’agente alla sua sinistra. Se un esecutore riceve un messaggio con il suo identificatore si proclama il direttore e lo annuncia all’agente alla sua sinistra. Se un esecutore riceve un messaggio con il risultato dell’elezione del direttore lo inoltra all’agente alla sua sinistra, a meno che non si tratti del suo identificatore. In ogni caso l’esecuzione dell’algoritmo in questo agente termina.

Un esempio di esecuzione nel caso di un insieme di 6 automi è mostrato nella figura più sotto, cui il numero all’interno di ogni cerchietto è l’identificatore e il numero accanto alla freccia rossa è il messaggio che viene inviato.

Nell’esempio, per facilità di illustrazione, tutti gli esecutori iniziano nello stesso momento, ma l’algoritmo è indipendente da questa assunzione. I vari passi della computazione sono mostrati uno alla volta procedendo da sinistra a destra e poi dall’alto in basso. Per ogni esecutore, quello successivo in senso orario nella figura è quello che l’algoritmo considera alla sua sinistra. L’ultima immagine rappresenta sinteticamente il fatto che l’agente 6, avendo ricevuto al passo precedente il messaggio con il suo identificatore, l’ha inoltrato come messaggio di scelta del direttore alla sua sinistra e ha ricevuto il messaggio di scelta del direttore dall’agente alla sua destra.

Possiamo convincerci che l’algoritmo sia corretto osservando che l’identificatore di valore massimo viene inoltrato da tutti gli esecutori fino a raggiungere quello identificato da esso (prime sei immagini), mentre ogni altro identificatore viene prima o poi fermato. Quindi uno solo degli agenti determinerà di essere il direttore e avviserà tutti gli altri (la settima immagine).

Ci possiamo porre il problema di quanti messaggi in tutto siano necessari per terminare questo algoritmo. Rimandando al testo La rivoluzione informatica per una discussione più approfondita, ricordo qui soltanto che, prendendo in considerazione solo il caso pessimo (come discusso nella puntata Ma quanto ci mette quest’algoritmo?), questo si ha quando gli identificatori degli automi sono sempre decrescenti, andando lungo l’anello in senso orario. In tal caso il numero di messaggi necessario è proporzionale a N ². Con un’analisi più sofisticata si può dimostrare che in media il numero di messaggi utilizzati da questo algoritmo è N∙(log N ). Questa è anche la complessità che il miglior algoritmo conosciuto per questo problema (si tratta di quello di Hirschberg-Sinclair) garantisce nel caso pessimo. Tale algoritmo è anche il migliore possibile, dal momento che si è dimostrato che qualunque algoritmo ha bisogno di inviare almeno N∙(log N ) messaggi.

Nel prossimo post affronteremo il secondo dei problemi più importanti che caratterizzano la computazione distribuita, quello della sincronizzazione.

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

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.

A passeggio con l'informatica #5 – Come istruire un computer

di Enrico Nardelli

Con questo post completiamo il discorso sugli automi (termine tecnico che si usa nell’informatica per denotare i computer), cioè i meccanismi che eseguono le elaborazioni di cui abbiamo bisogno.

Nel post precedente abbiamo descritto una versione molto semplice di macchina a registri (MR), un automa che nonostante la sua semplicità ho lo stesso potere computazionale dei computer che vengono quotidianamente usati.

Dobbiamo adesso parlare del linguaggio che la MR è in grado di “comprendere”, cioè descrivere quali istruzioni essa è in grado di eseguire. Sono possibili tante scelte, ma per i nostri scopi divulgativi possiamo rimanere al minimo necessario per poter esprimere qualunque computazione. A questo scopo sono necessarie solo le quattro istruzioni presentate in dettaglio nel seguito che, nonostante costituiscano tutto il linguaggio che possiamo usare per comandare la MR, le danno lo stesso potere computazionale di qualunque altro computer.

• L’istruzione Fine è quella che arresta il funzionamento della MR, cioè è quella che fa percorrere la transizione verso lo stato “Fine” all’automa a stati finiti che descrive il comportamento dell’Unità di Controllo della MR.
• L’istruzione Incrementa X è quella che aumenta di 1 il valore contenuto nella cella di memoria di indirizzo X. Nel seguito diremo “cella X” per indicare in modo più sintetico la “cella di memoria di indirizzo X”.
• L’istruzione Vai X è quella che fa sì che la prossima istruzione che eseguirà la MR sarà quella all’indirizzo X. Questo viene ottenuto scrivendo il valore X dentro IC.
• L’istruzione X Dim o Vai Y è composta di due parti. Dapprima si verifica se il contenuto della cella il cui indirizzo è scritto dentro la cella X è maggiore di 0. Se questo è vero allora il contenuto della cella il cui indirizzo è scritto dentro la cella X viene diminuito di 1. Se questo non è vero si scrive invece il valore Y dentro IC (e quindi al passo successivo la MR eseguirà l’istruzione contenuta nella cella Y).

Si invita il lettore a prestare attenzione al fatto che nell’istruzione “Incrementa X” è il contenuto della cella X che viene modificato, mentre nell’istruzione “X Dim o Vai Y” viene manipolato non il contenuto della cella X ma il contenuto della cella il cui indirizzo è scritto nella cella X.

Presentiamo adesso nella parte sinistra della seguente tabella il programma che risolve il problema enunciato due post fa (cioè contare quanti “2” ci sono in una sequenza), mostrando nella parte destra un’istanza (cioè, uno specifico esempio) del problema da risolvere.

Abbiamo assunto che IC sia la cella di indirizzo 0 e che il valore iniziale dentro di essa sia 1, cioè che il programma da eseguire sia memorizzato a partire dalla cella di memoria di indirizzo 1. Abbiamo altresì assunto che i dati del problema, cioè la sequenza di valori per la quale bisogna calcolare quanti sono i valori “2”, sia nella memoria a partire dalla cella di indirizzo 12 (si tratta, per quest’istanza, di una sequenza di sei valori, di cui l’ultimo è “0” e che contiene tre “2”). La cella di memoria di indirizzo 10 serve per contare quanti valori “2” si sono finora incontrati e quindi conterrà, quando la MR si arresta, il valore di conteggio desiderato, mentre la cella di memoria di indirizzo 11 serve per poter scandire la sequenza di valori da processare. L’idea che il programma realizza è quella di decrementare per due volte di seguito il contenuto della cella il cui indirizzo è scritto nella cella 11. Se dopo il primo decremento il valore arriva a zero allora la cella non conteneva “2” e non si incrementa il contatore nella cella 10. Altrimenti, conteneva “2” e il contatore viene incrementato. In entrambi i casi si passa a considerare il successivo valore della sequenza.

Se il lettore avrà la pazienza di eseguire passo dopo passo, in modo meccanico, le istruzioni del programma proposto, potrà appunto verificare che viene calcolato il valore desiderato (tre, per questa istanza). Si suggerisce anche di provare l’esecuzione del programma con altre sequenze di valori in ingresso, così da convincersi del fatto che esso risolve in modo completamente meccanico qualunque istanza del problema considerato.

Rimane un ultimo aspetto da discutere. Come fa l’automa a “capire” cosa vuol dire, per esempio, l’istruzione “Incrementa X” o le altre istruzioni? Come abbiamo visto per l’istruzione “Vai X”, il suo significato è dato dalle azioni che il progettista dell’automa stesso ha associato all’istruzione data. Nel caso di “Vai X” il suo “significato” è quindi dato dal fatto che quando essa viene incontrata nel corpo del programma il valore di X viene scritto dentro IC. A questo scopo, in effetti, non c’è bisogno che nel programma ci sia scritto “Vai X”, basta scrivere un breve codice numerico, ad esempio 10, e far sì che questo, quando viene “eseguito”, attivi i meccanismi fisici (normalmente, circuiti elettronici) che realizzano il comportamento desiderato. Seguendo questa linea si ottiene un programma scritto interamente in codifica binaria: è il livello cosiddetto del linguaggio macchina, cioè quel linguaggio che la macchina fisica, cioè la realizzazione fisica dell’esecutore è, con buona approssimazione, in grado di comprendere ed eseguire direttamente. Si può pensare, per fare un’analogia meccanica, che sia il livello al quale agiscono le leve e ruote dentate di un oggetto meccanico. Il programma presentato inizialmente è invece al livello cosiddetto del linguaggio simbolico.

Per ora accenniamo soltanto che il passaggio da un programma scritto in un linguaggio simbolico alla sua versione in linguaggio macchina può, e questo non dovrebbe sorprenderci, essere eseguito in modo del tutto meccanico da parte di appositi programmi di traduzione, che discuteremo più avanti, quando riprenderemo questo discorso parlando di virtualizzazione.

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

A passeggio con l'informatica #4 – Come funziona un computer

di Enrico Nardelli

In questo post proseguiamo il discorso sugli automi, cioè gli esecutori meccanici delle elaborazioni, modello astratto dei nostri computer. Come visto nel precedente post, un automa a stati finiti non possiede tutto il potere computazionale che ci serve. A questo scopo è necessario un esecutore più potente e la macchina universale di Turing (MUT), un modello formale di un automa definito dal matematico inglese Alan Turing nel 1936, è quello che fa al caso nostro. Il suo autore ha evidenziato che essa è in grado di calcolare tutto ciò che noi esseri umani riteniamo calcolabile. È importante fare attenzione al fatto che questa affermazione non è un teorema matematico: si chiama infatti “tesi di Turing” e non “teorema di Turing” proprio perché non esiste una definizione matematicamente precisa di “calcolabilità” che sia indipendente dall’esecutore usato. Si è visto però che è un approccio robusto, perché altri modelli formali di esecutori meccanici hanno portato agli stessi risultati.

L’esposizione della MUT richiederebbe complicazioni eccessive per i nostri scopi, per cui presento una sua versione più facilmente comprensibile che ha lo stesso potere computazionale, la macchina a registri (MR), nella versione minimale che ci serve per capirne i princìpi di funzionamento. I computer che usiamo ogni giorno, anche quelli annidati all’interno dei dispositivi più o meno smart che sempre di più fanno parte della nostra vista, sono tutti esempi di MR, tecnologicamente molto sofisticati, ma con il suo stesso potere computazionale.

La MR ha le componenti illustrate nella figura sotto e descritte nel seguito:

• Una prima serie di celle di memoria, ognuna delle quali ha un indirizzo numerico, che è un intero positivo, ed è in grado di contenere un'istruzione del linguaggio che la macchina è in grado di eseguire. L’insieme delle istruzioni che in un certo momento si trovano nelle celle di memoria costituisce il programma che la macchina sta eseguendo.
• Una seconda serie di celle di memoria, dette registri, che contengono i dati. Anche queste celle hanno un indirizzo numerico costituito da un intero positivo e assumiamo che i dati contenuti in esse siano soltanto interi non negativi.
• Un registro particolare (di indirizzo prefissato che indichiamo con il nome simbolico IC) che contiene l'Indirizzo Corrente della prossima istruzione da eseguire.
• Un’Unità di Controllo (UC) che dirige il funzionamento generale della macchina.
• Un’Unità Aritmetico-Logica (UAL) che esegue le computazioni aritmetiche e logiche di base.

Quella appena descritta è quindi la struttura (o architettura) della MR, chiamata anche “architettura di von Neumann”, dal nome del matematico di origine ungherese John von Neumann che la propose nel 1945. Nella nostra descrizione prescindiamo dall’interazione tra la MR e il mondo esterno, che avviene tramite i dispositivi di ingresso e uscita (input e output), fondamentali per il suo effettivo utilizzo, ma trascurabili ai fini di questa presentazione. Osserviamo che abbiamo distinto le celle di memoria che contengono il programma e quelle che contengono i dati solo per semplicità concettuale. In realtà questa distinzione non esiste, in linea generale, ed è alla base di quella dualità tra dati e programmi che rappresenta una delle conquiste culturali più importanti dell’informatica.

Il comportamento della MR è determinato dalla UC, che esegue quanto descritto dall’automa a stati finiti della figura sotto.

In altre parole, la macchina a registri ha un “motore” (cioè la UC) che ripete sempre le stesse due semplici azioni: leggere l’istruzione presente nella cella di memoria il cui indirizzo è il nome simbolico IC ed eseguirla. Nel seguito, useremo più semplicemente “IC” per indicare “la cella di memoria il cui indirizzo è il nome simbolico IC”, come già fatto nella figura sopra.

La prima domanda che viene in mente riflettendo su questo comportamento è: dal momento che il contenuto di IC viene incrementato ogni volta di 1, come può la macchina fare qualcosa di diverso dall’eseguire una semplice lista sequenziale di istruzioni? La risposta è che una delle istruzioni della MR è in grado di scrivere dentro IC un valore determinato da chi ha realizzato il programma, in modo tale che l’istruzione eseguita dopo quella corrente non sia più quella di indirizzo immediatamente successivo ad essa ma una qualunque altra.

La seconda domanda è: chi effettua davvero i calcoli che servono? La risposta è che i passi elementari che sono necessari vengono svolti dalla UAL, la quale ha bisogno, in ultima analisi, di saper fare, di tutte le operazioni matematiche, solo l’addizione. Senza entrare in dettagli tecnici complicati, ricordiamo infatti che la sottrazione può essere ricondotta all’addizione, la moltiplicazione e la divisione possono essere ricondotte alla ripetizione di, rispettivamente, addizioni e sottrazioni. Altre operazioni matematiche possono essere ottenute a partire dalle quattro operazioni aritmetiche. Allo stesso modo ogni operazione logica può essere ottenuta a partire da una sola. Opportuni programmi consentono, ripetendo in opportuna combinazione i passi elementari che è in grado di svolgere la UAL, di eseguire tutti i calcoli di cui abbiamo bisogno.

Nel post successivo vedremo come si fa a dare le istruzioni alla MR, ovvero qual è il linguaggio che la MR è in grado di “comprendere”, e un programma per la MR che risolve il problema enunciato alla fine del precedente post (cioè contare quanti “2” ci sono in una sequenza).

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

A passeggio con l'informatica #3 – Automa e linguaggio

di Enrico Nardelli

Nel post precedente abbiamo parlato di come rappresentare i dati. Una volta stabilita la rappresentazione va specificata la sequenza di istruzioni che vogliamo far compiere meccanicamente all’automa (o esecutore o agente) per eseguire l’elaborazione desiderata. Cos’è l’automa? Il termine è preso dalla lingua greca ed è la radice di termini quali “automatico” e “automatismo” che indicano appunto ciò che viene eseguito senza riflessione, senza coscienza e senza possibilità di deviare dalla strada tracciata. Come la rappresentazione digitale in sé non è un fatto recente, così non lo è l’automazione. Ricordiamo gli automi meccanici, che in Occidente sono stati ampiamenti studiati nell’età ellenistica, che copre approssimativamente gli ultimi trecento anni prima di Cristo. Da molti secoli l’umanità è in grado di costruire macchine per fare automaticamente dei calcoli (dette “macchine calcolatrici”) e quelle per automatizzare i calcoli aritmetici sono state sviluppate con una certa regolarità almeno a partire dal Seicento.

Per poter definire la sequenza di istruzioni (chiamata anche procedura o programma) da far eseguire all’automa dobbiamo però sapere quali sono le specifiche istruzioni che esso è in grado di eseguire, cioè le specifiche operazioni che è in grado di compiere. Un aspetto fondamentale da tener presente è che esse sono strettamente legate alla natura dell’esecutore stesso. Ecco quindi che definire l’automa di riferimento per le elaborazioni, cioè specificare l’insieme delle istruzioni che tale agente è in grado di eseguire e illustrare esattamente quali operazioni vengono compiute per eseguirle e chiarire in ogni dettaglio come questo possa essere ottenuto meccanicamente, è un passo preliminare alla concretizzazione di ogni processo di elaborazione delle rappresentazioni.

Tale definizione va effettuata insieme alla definizione del linguaggio, chiamato linguaggio di programmazione, che verrà poi usato per descrivere, di volta in volta, le specifiche elaborazioni che l’esecutore dovrà attuare. Si può quindi dire che la definizione dell’automa e del suo linguaggio di programmazione sono due lati della stessa medaglia: non ha senso dotare un automa di un’operazione se non c’è un’istruzione nel relativo linguaggio che è in grado di invocarla e – simmetricamente –non ha senso inserire nel linguaggio un’istruzione che l’automa non è in grado di eseguire.

La caratterizzazione precisa di cosa costituisce un automa è un aspetto fondamentale dell’informatica, su cui la ricerca non ha ancora terminato le proprie indagini. Bisogna inoltre aggiungere che non tutti gli automi sono uguali, cioè non hanno tutti lo stesso “potere computazionale”. In altre parole non sono tutti in grado di effettuare le stesse elaborazioni. Va però chiarito subito che tutti i calcolatori elettronici oggi effettivamente usati sono basati su un modello di automa che è il più potente definibile.

Un automa di tipo molto semplice è l’automa a stati finiti, che può realizzare computazioni “ricordando” cosa è successo in passato. Questa memoria del passato si chiama “stato” e costituisce un concetto abbastanza intuitivo.

Ecco un esempio che è in grado di eseguire l’addizione tra numeri binari. Ricordiamo brevemente che nella rappresentazione in binario i numeri sono scritti utilizzando solo le due cifre “0” e “1” (da cui l’aggettivo “binario”).

Una cifra nella posizione meno significativa (la prima da destra) rappresenta direttamente uno dei due possibili valori “zero” o “uno”.

Il valore rappresentato da una cifra nella seconda posizione da destra si ottiene moltiplicando la cifra per due, ovvero per il numero di possibili valori rappresentati dalla cifra alla sua destra.

Il valore rappresentato da una cifra nella terza posizione da destra deve essere moltiplicato per quattro, ovvero per il numero di possibili valori rappresentati dalle due cifre nelle due posizioni alla sua destra. Così facendo si arriva, per esempio, a rappresentare il numero scritto in decimale come “20” con la rappresentazione binaria “10100”, dal momento che 1∙16 + 0∙8 + 1∙4 + 0∙2 + 0∙1 = 20.

L’addizione in binario funziona analogamente a quella in decimale tranne che, in binario, quando sommando due cifre si raggiunge (o si supera) il due, allora “si scrive 0 (oppure 1) con riporto 1”. Nella tabella viene rappresentato quello che avviene indicando tutte le possibili situazioni di cifre da sommare e con presenza o meno del riporto.

Possiamo adesso definire un automa a stati finiti che è in grado di sommare numeri binari di qualunque lunghezza. Per semplicità assumiamo che siano rappresentati con lo stesso numero di cifre. Forniamo all’automa i numeri binari una cifra per volta, in coppia, una cifra per ognuno dei due numeri, a partire dalla coppia di cifre più a destra. Ogni coppia di cifre fornite in ingresso (la coppia scritta sugli archi nella figura sotto) causa il passaggio da uno stato a un altro rappresentato dalla freccia su cui la coppia compare (gli stati sono rappresentati da cerchi e il “passaggio di stato” può avvenire anche dallo stato verso sé stesso) e produce in uscita una cifra del risultato (scritta sugli archi dopo la barra). Lo stato R0 rappresenta la situazione in cui la precedente addizione di due cifre ha prodotto un riporto di 0 e lo stato R1 rappresenta la situazione simmetrica con un riporto di 1. L’automa, rappresentato nella figura sotto, inizia nello stato R0, dal momento che all’inizio dell’addizione non c’è alcun riporto. Le 4 frecce uscenti da R0 rappresentano i 4 passaggi di stato determinati dalle 4 possibili coppie di cifre in ingresso, di cui uno solo determina un reale cambiamento dello stato da R0 a R1. Una volta effettuato il passaggio di stato corrispondente alla coppia in ingresso, questa viene eliminata e si prende in considerazione la coppia successiva. Quando non vi sono più coppie in ingresso l’addizione è terminata e sono state prodotte in uscita tutte le cifre del risultato.

Se il lettore avrà la pazienza di usare tale automa per effettuare la somma tra i due numeri binari 0101 (cioè sette) e 0011 (cioè tre) vedrà che con esso si calcola automaticamente, meccanicamente il risultato 1010 (cioè dieci).

Esistono però dei casi nei quali l’automa a stati finiti non è in grado di produrre un risultato, ovvero non ha un sufficiente potere computazionale. Un esempio semplice di una classe di problemi di questo genere è quella in cui l’automa può ricevere una sequenza arbitrariamente lunga di cifre, in cui appaiono solo “1” o “2”, usando “0” per indicare che la sequenza è finita, e in cui è necessario contare quanti “2” sono presenti nella specifica sequenza che è arrivata. Poiché non possiamo sapere a priori quanti “2” conterrà lo specifico esempio, non possiamo costruire l’automa che sia in grado risolvere qualunque istanza di un problema di questa classe.

Vedremo nella prossima puntata un tipo di automa che è il più generale e potente possibile e che è alla base di tutti i dispositivi informatici (PC, tablet, smartphone) che usiamo. Possiamo dunque star tranquilli che tutti i nostri dispositivi informatici sono sufficientemente potenti da un punto di vista computazionale, anche se possono essere più o meno veloci da un punto di vista tecnologico.

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

A passeggio con l'informatica #2 – La rappresentazione dei dati

di Enrico Nardelli

Nell’informatica si parla spesso – impropriamente – di elaborazione delle informazioni. Da un punto di vista formale il termine informazione denota però un dato la cui acquisizione da parte di un ricevente determina una riduzione della sua incertezza rispetto a un qualche fenomeno. Un esempio tipico può essere la percentuale dei voti ottenuti da un partito in un’elezione, che è comunque un dato, ma che costituisce un’informazione solo se chi la riceve non ne è a conoscenza. Un dato costituisce un singolo bit di informazione, cioè ha un valore informativo unitario, se riduce nel ricevente un’incertezza binaria (cioè l’incertezza se qualcosa sia vero o falso). A questo proposito ricordo che in informatica il termine “bit” deriva dalla contrazione dell’espressione inglese binary digit e si usa per indicare la rappresentazione di un valore binario, cioè, p.es., vero o falso, presente o assente, acceso o spento, mediante le due cifre 0 e 1.

Dal momento che nell’informatica il punto di vista non è la riduzione di incertezza di chi riceve i dati, ma l’automa che li elabora meccanicamente, è opportuno utilizzare in un contesto informatico sempre il termine “dati” invece di “informazioni” e – se si vuole il massimo di rigore – parlare di “rappresentazioni”, poiché i dati devono necessariamente essere codificati in qualche modo affinché possano essere elaborati dall’automa.

Il dato infatti esiste, anche se astratto, indipendentemente da una sua rappresentazione materiale che eventualmente lo concretizza, che viene scelta da noi. Questo si capisce bene con i numeri, concetti che non hanno in sé una realtà fisica. Il numero “cinque” (cioè quel numero che nella codifica in base decimale scriviamo come “5”), ad esempio, è il concetto che corrisponde a quanti oggetti ci sono in ogni insieme fatto da cinque oggetti, cioè l’astrazione che rappresenta ciò che è comune a tutti gli insiemi di cinque oggetti. Il numero “cinque” quindi esiste nel mondo delle astrazioni, e sono io che posso scegliere di rappresentarlo concretamente mediante bit (101), con l’alfabeto (cinque), o con altre codifiche. Un termine alternativo a rappresentazione è infatti “codifica”, e possiamo considerarli sinonimi.

Osserviamo ancora che, mentre il significato dei numeri è formalizzabile senza troppa difficoltà, per la maggior parte delle parole questo obiettivo è estremamente sfuggevole perché coinvolge l’interpretazione da parte del ricevente. Questo è vero all’interno dello stesso linguaggio, ma ancora di più tra linguaggi diversi, aspetto che costituisce una delle maggiori difficoltà della traduzione. Si pensi, ad esempio, che “casa” corrisponde in inglese sia a house che a home. La stringa “casa” è una rappresentazione, cioè un dato espresso in una forma materiale, che per gli esseri umani è simbolo di (cioè, un segno che si riferisce a) un “significato” che è univocamente determinato solo all’interno di una certa comunità linguistica. Ad esempio, la stringa “camera” ha significato di “stanza” per l’italiano ma di “macchina fotografica” per l’inglese. Quando parliamo di informatica in relazione ai calcolatori (utilizzeremo indifferentemente questo termine o l’equivalente inglese “computer”) usiamo il termine “rappresentazioni” e non “simboli” perché, anche se dal punto di vista umano quelle rappresentazioni sono appunto simbolo di qualcosa di significativo, per l’automa esse non hanno alcun significato, né posseggono un significato – per l’automa – le loro elaborazioni.

Le rappresentazioni possono essere classificate in due grandi categorie: analogica e digitale. La prima è quella che, fino a qualche decennio fa, è stata la più usata nella storia dell’umanità. L’esempio tipico è la posizione delle lancette in un quadrante o la lunghezza di un’ombra per indicare l’ora del giorno. La seconda – in base alla quale per lo stesso esempio il tempo viene rappresentato mediante cifre – caratterizza ormai la società contemporanea, che proprio per questo viene denominata “società digitale”. Nella rappresentazione analogica c’è una proporzione, un’analogia. Quanto più la lancetta si è mossa dalla sua posizione iniziale o quanto più l’ombra è lunga, tanto maggiore è il tempo trascorso. Nella rappresentazione digitale ci sono una serie di segni arbitrariamente scelti, le cifre, ai quali assegniamo un valore. Osserviamo però che la rappresentazione delle quantità mediante cifre è stata utilizzata dall’umanità da millenni: l’usavano i Babilonesi per il calcolo delle orbite astronomiche e l’usavano gli Egizi per il calcolo delle superfici dei terreni. Ogni popolazione rappresentava le quantità col proprio insieme di segni. Il “digitale” non è quindi un fenomeno moderno.

Anche l’elaborazione meccanica e automatica delle rappresentazioni può essere realizzata in modo analogico oppure digitale. Le prime calcolatrici aritmetiche meccaniche eseguivano somme e sottrazioni mediante spostamenti di aste o ruote, cioè con una manipolazione analogica di dati analogici. I moderni computer, invece, elaborano in modo digitale rappresentazioni digitali, cioè costituite da cifre. In tal caso la somma di due valori, ad esempio, non è la lunghezza totale delle due aste (ognuna delle quali rappresenta un valore) messe in fila, ma è il risultato dell’addizione tra i due numeri ognuno dei quali è la rappresentazione digitale del numero. Le dieci cifre del nostro sistema di rappresentazione (denominato appunto “sistema decimale”) sono sostituite, all’interno dei computer, da un sistema binario (cioè che utilizza solo i due valori “zero” e “uno”) per semplice convenienza tecnologica. Per un moderno calcolatore basato sull’elettricità avere due soli valori da rappresentare costituisce una notevolissima semplificazione, che porta a ottenere dispositivi di calcolo più piccoli e più veloci. I calcolatori adottano quindi una codifica binaria per la rappresentazione dei valori.

Completiamo questo post osservando che anche i caratteri alfabetici possono essere rappresentati mediante una codifica binaria, associando progressivamente alle varie lettere una rappresentazione binaria. È quello che è stato fatto con il famoso codice ASCII (lo standard universale per la rappresentazione binaria dei caratteri dell’alfabeto) che codifica la lettera ‘A’ con la rappresentazione binaria ‘01000001’, corrispondente al numero decimale ‘65’, la lettera ‘B’ con ‘01000010’, corrispondente a ‘66’ e così via. Procedendo in modo analogo, si possono definire metodi per costruire rappresentazioni binarie di immagini, suoni e video. Un approfondimento sulla rappresentazione dei dati mediante il sistema binario si trova nella guida didattica del progetto “Programma il Futuro” disponibile a questo link.

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

A passeggio con l'informatica #1 – Cos'è l'informatica

di Enrico Nardelli

Fornire una definizione esatta di cos’è una disciplina scientifica è un compito non facile, anche perché gli stessi studiosi della materia – se interrogati – producono formulazioni diverse tra loro. Per l’informatica il compito è ancora più difficile, dal momento che tale termine, nel corso dei decenni, è venuto via via comprendendo al suo interno un enorme spettro di concetti, da quelli più tecnologici e operativi (p.es. la connessione a distanza tra due dispositivi digitali) a quelli più astratti e scientifici (p.es. la dimostrazione della risolubilità meccanica di un problema). Tale parola viene usata, per fare alcuni esempi, quando si parla sia del dispositivo tecnologico (come tablet o smartphone) su cui vengono eseguite le varie app (cioè i programmi informatici che usiamo per cercare informazioni o per giocare) sia del software di sistema che rende possibile il funzionamento di tale dispositivo che, ancora, delle formule e dei teoremi che dimostrano la correttezza del processo di calcolo.

In questa serie di post mi occupo dell’informatica come scienza e sappiamo che ogni scienza studia alcuni fenomeni specifici. Ad esempio, la matematica studia quantità, misure e le loro relazioni, la fisica la materia non vivente e il suo comportamento nello spazio e nel tempo, la biologia gli organismi viventi e le loro evoluzioni.

Cosa studia allora la scienza chiamata informatica? Per orientare comunque il lettore ecco la mia definizione:

L’informatica è la disciplina che studia
l’elaborazione automatica di rappresentazioni.

Analizziamo adesso più in dettaglio i termini della definizione, iniziando col discutere cosa si intende con l’aggettivo automatica. Conosciamo bene il concetto di automazione. A partire dalla Rivoluzione Industriale avviatasi nel Settecento è ben chiaro a tutti che automatizzare un processo produttivo vuol dir farlo fare alle macchine. Prodotti che un tempo venivano realizzati a mano, artigianalmente, vengono fabbricati da macchinari.

Come esempio pratico, pensate a un vestito di lana. Un tempo bisognava tosare le pecore, filare la lana, realizzare la tela, poi tagliarla e infine cucirla, e il tutto veniva realizzato da persone. Nel corso dei secoli tutti questi passi sono stati automatizzati e vengono ormai svolti dalle macchine. Ogni qualvolta parliamo di “macchina” intendiamo un dispositivo che si comporta in modo meccanico, vale a dire che messo nelle stesse condizioni di partenza esegue sempre invariabilmente le stesse operazioni, senza possedere alcuna coscienza di ciò che sta facendo, quindi senza conoscere il significato né di ciò che sta manipolando (o elaborando) né delle operazioni di manipolazione (o elaborazione) che sta compiendo.

L’aggettivo “automatica” nella definizione è essenziale per caratterizzare il fatto che l’informatica si occupa solo ed esclusivamente di quelle situazioni in cui l’elaborazione avviene in modo “meccanico”, cioè deterministico e non soggetto a quella coscienza e quel libero arbitrio che invece caratterizzano gli esseri umani. Il termine tecnico che si usa nell’informatica per indicare un dispositivo che realizza un’elaborazione automatica di rappresentazioni è “automa”, dalla parola greca autòmaton, che è la radice di “automazione” e “automatico”. Un PC o un tablet, uno smartphone o un smartwatch sono realizzazioni tecnologicamente sofisticate di automi molto complessi. Useremo anche termini come “agente” o “esecutore”, riferendoci sempre a un automa.

Col termine elaborazione faccio appello al senso comune che fa riferimento a una manipolazione di qualcosa, a una trasformazione di qualcosa in qualche altra cosa.

Nell’esempio di automazione precedentemente descritto, la lana della pecora viene trasformata, cioè elaborata, attraverso una serie di diversi passaggi fino a ottenere un vestito. In un contesto più astratto, quello dei numeri, l’operazione di addizione (3+5) trasforma o elabora gli addendi 3 e 5 nella loro somma (8). Infatti, le elaborazioni dell’informatica vengono chiamate anche “computazioni”, dal momento che, in una progressione storica, i primi scenari di applicazione sono stati quelli relativi ai calcoli numerici.

Il sostantivo rappresentazioni può suscitare delle perplessità, dal momento che, in genere, quando si parla di informatica si usano parole come “dati” o “informazioni”. Rimandando a un successivo post un approfondimento del significato di questi termini e delle loro relazioni, per il momento chiarisco che indico con “rappresentazione” il modo – arbitrario ma condiviso all’interno di una qualche comunità di persone – con cui rendiamo concreto nel mondo fisico un dato, cioè un generico elemento presente alla nostra coscienza, indipendentemente dalla circostanza che si riferisca a fatti oggettivi o ad acquisizioni soggettive.

Ritornando all’esempio dei numeri, osserviamo che essi non hanno in sé realtà fisica. Il concetto di “cinque cose” può essere fisicamente rappresentato da un qualunque insieme di cinque oggetti, ma è in sé astratto. La rappresentazione che noi usiamo è “5”, ma per gli antichi romani era “V”. Altre popolazioni usano rappresentazioni ancora diverse. Impariamo nei primi anni di scuola, non senza una certa fatica, a capire il significato delle rappresentazioni dei numeri e a fare calcoli con essi. In questo caso facciamo anche noi, come esseri umani, un’elaborazione di rappresentazioni, ma non è del tutto automatica, perché siamo persone e non meccanismi.

Nei successivi post di questa serie, approfondiremo prima il concetto di rappresentazione, perché sono queste proprio queste rappresentazioni che vengono elaborate dall’esecutore. Successivamente, capiremo come può essere fatto questo agente (l’automa) e in che linguaggio (più precisamente, linguaggio di programmazione) dobbiamo fornirgli le istruzioni che riteniamo necessarie per condurre l’elaborazione. Proseguiremo poi con un ulteriore concetto fondamentale, relativo alla specifica di quale sia la procedura di elaborazione (tecnicamente, l’algoritmo) che vogliamo realizzare. In seguito considereremo il caso di elaborazioni realizzate non da un singolo esecutore ma da un loro insieme, scenario detto di computazione distribuita. Infine, discuteremo una fondamentale caratteristica dell’informatica, l’astrazione, che pur non essendo un aspetto esclusivo di questa disciplina, dal momento che ogni scienza costruisce i propri modelli dei fenomeni attraverso un processo di astrazione dai dettagli, permette di realizzare macchine in grado di simulare altre macchine (virtualizzazione). Come ultimo concetto affronteremo quello che, da un punto di vista culturale generale, è forse il lascito più importante dell’informatica, ovvero la dualità tra rappresentazioni e programmi.

La seconda parte della serie sarà dedicata ad affrontare alcune delle problematiche conseguenti alla sempre maggiore diffusione di sistemi e dispositivi basati sull’informatica.

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

Scienza e Istruzione: quo vadis Europa ?

di Enrico Nardelli

È stato pubblicato qualche giorno fa l’elenco proposto dalla confermata Presidente della Commissione Europea, Ursula von der Leyen, per i membri che saranno in servizio per il quinquennio 2025-2029. Ricordo che si tratta di una proposta, dal momento che è soggetta a un voto di approvazione del Parlamento Europeo. In tale elenco viene indicato, come accade anche in Italia per la proposta dei Ministri che il Presidente del Consiglio incaricato formula al Presidente della Repubblica, il titolo della delega assegnata ad ogni commissario (in Italia, è il titolo del Ministro).

Si tratta di un aspetto importante dal punto di vista politico, dal momento che le strutture burocratiche che supportano l’azione dei commissari, cioè i Dipartimenti (denominati Directorate-general, che in Italia corrispondono ai Ministeri), normalmente conservano lo stesso nome e la stessa struttura, mentre le deleghe assegnate esprimono la visione che il Presidente vuole imprimere al suo mandato.

Dato il mio ambito professionale, ho esaminato se e come era stata modificata quella che nella precedente commissione era la delega per “Innovazione, ricerca, cultura, istruzione e gioventù”.

Prima di tutto ho constatato che “ricerca e innovazione”, rispetto al mandato 2020-2024, sono state spostate in una delega separata per “Start-up, ricerca e innovazione”. La situazione nei 25 anni precedente era stata la seguente:
2014-19 (Juncker) – Ricerca, scienza e innovazione;
2010-14 (Barroso II) – Ricerca, innovazione e scienza;
2004-09 (Barroso I) – Scienza e ricerca;
2000-04 (Prodi) – Ricerca;
1995-99 (Santer) – Scienza, ricerca e sviluppo.

Quindi, mentre per cinque lustri, con una sola eccezione, era stata sempre assegnata una delega per la Scienza, si conferma adesso l’impostazione della precedente commissione che la Scienza non sia un tema che meriti un’attenzione politica. “Le parole sono importanti!”, si diceva in un famoso film. Ritengo che questa omissione sia inevitabilmente legata a ciò cui abbiamo assistito in questi ultimi anni con la trasformazione del dubbio scientifico in verità di fede. Penso che tale mutazione sia un tradimento dell’eredità di Galileo Galilei e che la comunità europea degli scienziati dovrebbe lottare per ristabilire la sua dignità.

In secondo luogo, la delega per la parte “cultura, istruzione e gioventù” è diventata una delega per “equità inter-generazionale, cultura, gioventù”. Lasciando a più fini esegeti l’analisi dell’espressione “equità inter-generazionale”, ricordo anche qui cosa era accaduto nei 25 anni precedenti:
2014-19 (Juncker) – Istruzione, cultura, gioventù e sport;
2010-14 (Barroso II) – Istruzione, cultura, multilinguismo e sport;
2004-09 (Barroso I) – Istruzione, formazione, cultura e gioventù;
2000-04 (Prodi) – Istruzione e cultura;
1995-99 (Santer) – Risorse umane, istruzione, formazione e gioventù.

In questo caso, quindi, almeno per 30 anni il tema dell’istruzione è stato un caposaldo nell’agenda politica della Commissione. Giustissimamente, dal momento che l’investimento nell’istruzione è il migliore che possa fare una comunità per assicurare a sé stessa un continuo miglioramento delle condizioni di vita. Secoli di storia stanno lì a dimostrarcelo. La lotta per l’istruzione obbligatoria per tutti è stata una delle conquiste fondamentali dei secoli XIX e XX, messa in moto dalla spinta illuminista verso una comprensione razionale del mondo e resa possibile dalla rivoluzione culturale causata dall’invenzione della stampa a caratteri mobili.

Adesso, un faticoso cammino plurisecolare rischia di venir cancellato con un colpo di penna. Se non insistiamo sul recuperare il fondamentale ruolo dell’istruzione (che non è l’educazione, come quelli che non sanno l’inglese traducono education) c’è davvero il rischio di un feudalesimo digitale, come ho discusso nel mio libro La rivoluzione informatica, di un nuovo Medioevo in cui signoreggiano tecno-feudatari incuranti delle masse.

Spero davvero di no, spero in un ravvedimento che possa avvenire durante il processo di approvazione di questa proposta.

Ricordo che già 5 anni fa, nella proposta di nomina della precedente Commissione, la delega assegnata alla Commissaria Mariya Gabriel era stata inizialmente intitolata solo “Innovazione e gioventù”. Di fronte alla vigorosa protesta di una ventina di premi Nobel, di più di trecento tra leader di centri universitari e di associazioni scientifiche e scienziati vincitori di finanziamenti dello European Research Council, e di più di 13.000 ricercatori, l’improvvida decisione fu modificata aggiungendo i temi della “ricerca, istruzione e cultura”.

Ci si sta provando una seconda volta: non è un bel segno. Spero che il Parlamento Europeo possa riflettere sulla domanda Quo vadis Europa ?

--
Versione originale pubblicata su "StartMAG" il 19 settembre 2024.

A passeggio con l'informatica #0 – Introduzione

di Enrico Nardelli

Inizio con questo post un “viaggio” che intende stimolare l’interesse del lettore verso l’Informatica, quella disciplina scientifica che è alla base dell’odierna società digitale. Troppo spesso la comunicazione in questo ambito è dettata da mode tecnologiche o pressioni commerciali. Attraverso una serie di interventi divulgativi, intendiamo invece toccare sia i principali concetti della disciplina che alcune delle conseguenze che derivano dal sempre maggiore utilizzo delle tecnologie basate sull’informatica. I post di questa serie sono basati sul mio libro La rivoluzione informatica: conoscenza, consapevolezza e potere nella società digitale, al quale si rimanda per approfondimenti.

La società in cui viviamo è ormai pervasa da un’enorme quantità e varietà di dispositivi digitali: basti pensare alla sfera dei media e della comunicazione, dove lettere, articoli e libri si sono ormai completamente smaterializzati in forma di tweet, messaggi di posta elettronica, post sui blog (con i relativi sistemi di gestione, anch’essi digitali) oppure alla sfera delle relazioni sociali, dove i sistemi digitali di comunicazione e interazione sostituiscono in misura sempre maggiore quelli che un tempo erano riunioni in presenza e incontri diretti. Un impatto ancora maggiore è atteso con la diffusione delle tecniche della cosiddetta intelligenza artificiale (artificial intelligence ), tra le quali hanno particolare rilievo e importanza quelle di apprendimento automatico (machine learning ), che promettono di fornire assistenti digitali in grado di rendere il lavoro più efficace e più efficiente.

Tutti questi sistemi digitali sono governati da leggi scientifiche, analogamente a quanto accade con i sistemi fisici, quelle dell’Informatica. Essa è una disciplina scientifica con un suo corpus di concetti, teorie, princìpi, metodi, conoscenze e problemi aperti [The Royal Society 2012; Académie des Sciences 2013]. I suoi effetti si vedono sia nella creazione di questo mondo digitale, virtuale solo in apparenza, dal momento che costituisce una realtà sempre più rilevante, sia nell’accelerazione che sta dando allo sviluppo di scienza e tecnologia, in tutti i campi, creando anche nuove aree di studio e ricerca. Le trasformazioni che la tecnologia informatica ha apportato in tutti i settori fanno sì che ogni professione e ogni disciplina ne sia in qualche modo influenzata e costituiscono uno dei fattori fondamentali dello sviluppo economico degli ultimi 50 anni.

L’impatto sociale dell’informatica è evidente sia nell’ubiquità del World Wide Web e della sua estensione in corso all’Internet delle Cose (Internet of Things ) che nell’attenzione che i legislatori in tutto il mondo hanno posto e stanno ponendo alla regolamentazione della gestione dei dati digitali e dell’utilizzo delle tecniche di intelligenza artificiale. L’importanza scientifica è testimoniata dalla pubblicazione, nei suoi quasi 70 anni di vita come scienza autonoma, di circa 2 milioni di articoli scientifici, a fronte di una stima di un totale di 70 milioni per tutte le discipline [Informatics for All 2020].

Sul piano didattico, vi è la recente approvazione da parte del Consiglio dell'Unione Europea della proposta di Raccomandazione della Commissione Europea sull'insegnamento dell'informatica nella scuola (Consiglio dell’Unione Europea, 2023). La Raccomandazione approvata affronta la necessità di far sì che l'istruzione supporti la trasformazione digitale, fornendo le competenze necessarie a questo scopo. Pertanto, viene raccomandato a tutti gli Stati Membri di sviluppare un’istruzione di qualità in informatica nell’istruzione sia primaria che secondaria.

In modo più specifico, si raccomanda di:

• inserire un insegnamento di alta qualità in informatica dall’inizio dell’educazione obbligatoria, avendo stabilito in modo chiaro gli obiettivi di apprendimento, il tempo dedicato e i metodi di valutazione, allo scopo di offrire a tutti gli studenti la possibilità di sviluppare le loro competenze digitali in modo scientificamente ben fondato,
• far sì che l’insegnamento dell’informatica sia erogato da insegnanti qualificati, che abbiano a disposizione risorse didattiche di qualità, approcci didattici ben fondati, e appropriati metodi di valutazione degli obiettivi di apprendimento.

Si manifesta quindi chiaramente a tutti gli Stati Membri la necessità di avere l’informatica come disciplina scientifica fondamentale per l’istruzione di tutti i cittadini nel 21-mo secolo. È un’indicazione quanto mai opportuna. Ricordiamo infatti che, con il passare da una società agricola ad una società industriale, il processo educativo delle persone è mutato, introducendo nell’istruzione obbligatoria elementi di quelle scienze (fisica, biologia, chimica, …) che sono alla base di ogni macchina industriale. Analogamente, nel passaggio dalla società industriale alla società digitale è necessario aggiungere nell’istruzione obbligatoria lo studio dell’informatica, indispensabile per comprendere le macchine digitali.

La comprensione dei princìpi fondamentali di questa scienza è infatti essenziale per consentire ad ogni persona di avere quella conoscenza di base necessaria per comprendere e influenzare lo sviluppo del mondo digitale, e contribuire a una crescita armoniosa di una società digitale giusta, equa e sicura.

Cercheremo quindi di fornire qualche utile pillola formativa a chi ci seguirà con attenzione e fedeltà e speriamo di indurlo a cercare di saperne di più sull’informatica, così da poter navigare e partecipare in modo responsabile e critico a una sfera comunicativa di informazioni – talvolta scorrette o incomplete – che rischia di essere sempre più controllata da algoritmi che potrebbero essere tendenziosi.

Con il prossimo post iniziamo questa “passeggiata” discutendo come può essere definita l’informatica.

Riferimenti bibliografici

Académie des Sciences (2013). L’enseignement de l’Informatique en France: Il est urgent de ne plus attendre, maggio 2013. http://www.academie-sciences.fr/pdf/rapport/rads_0513.pdf

Consiglio dell'Unione Europea (2023), Raccomandazione sul miglioramento dell'offerta di abilità e competenze digitali nell'istruzione e nella formazione, novembre 2023, https://eur-lex.europa.eu/legal-content/IT/TXT/HTML/?uri=OJ:C_202401030

Informatics for All (2020). Position paper for the public consultation on the renovation of the EU Digital Education Action Plan. https://www.informaticsforall.org/wp-content/uploads/2020/07/Informatics-for-All-position-paper.pdf

The Royal Society (2012). Shut down or restart? The way forward for computing in UK schools, gennaio 2012. https://royalsociety.org/topics-policy/projects/computing-in-schools/report/

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