MATEMATICA E TECH

Algoritmi, facciamo chiarezza sui diversi tipi

Ci sono diversi tipi di algoritmi, a seconda del tipo di problema e di soluzione che si vuole trovare. Non tutti prevedono machine learning/intelligenza artificiale. Solo pochi sono “black box”. Sul punto c’è parecchia confusione: ecco un quadro utile

12 Mar 2020
Nicola Gatti

direttore dell'Osservatorio Artificial Intelligence del Polimi e membro dell’Associazione Italiana per l’Intelligenza Artificiale (AIxIA)

algoritmi

Un algoritmo è comunemente definito come un procedimento che risolve un determinato problema tramite un numero finito di passi elementari. Analizziamo come funziona questo concetto fondamentale nell’informatica, cardine della fase di programmazione dello sviluppo del software e punto di partenza per le nuove tecnologie del futuro, dalla blockchain all’Intelligenza artificiale.

Prima di esaminare le possibili declinazioni di un algoritmo, è utile soffermarsi sulla natura del problema da risolvere. Dal punto di vista formale, un problema viene definito da una coppia input/output, dove l’input specifica la struttura dell’istanza del problema da risolvere e l’output una soluzione che soddisfa delle specifiche proprietà.

Algoritmo, il problema del commesso viaggiatore

Si consideri, ad esempio, il problema del commesso viaggiatore, in cui, dati un insieme di città, le strade che le connettono e i tempi di percorrenza media tra ogni coppia di città, si vuole trovare il tragitto con il minimo tempo di percorrenza che un commesso viaggiatore deve seguire per visitare tutte le città una ed una sola volta. In questo caso, l’input di una istanza del problema è costituito da un insieme di città, le strade di connessione e dai tempi di percorrenza tra queste, mentre l’output è costituito da ogni tragitto che tra tutti quelli che attraversano ogni città una e una sola volta ha il tempo di percorrenza minimo.

WHITEPAPER
Porta il tuo Contact Center ad un livello successivo con speech analytics e sentiment analysis
Intelligenza Artificiale
Marketing

Un problema può presentarsi in alcune varianti, ognuna delle quali può richiedere soluzioni algoritmiche diverse. Si riportano alcune tra le varianti più significative.

Algoritmo: prima variante del problema

Nella prima variante, ogni elemento dell’istanza del problema è perfettamente noto. Ad esempio, nel caso del problema del commesso viaggiatore, questo vuol dire che sono note tutte le città, come sono connesse e i tempi di percorrenza.

Quando l’istanza di un problema è perfettamente nota, si hanno tre principali classi di algoritmi. La prima classe è costituita da algoritmi esatti, cioè algoritmi che restituiscono soluzioni ottime per il problema dato. Un algoritmo esatto viene utilizzato ogni qual volta il suo tempo di esecuzione è compatibile con l’applicazione. In particolare, si distinguono algoritmi che richiedono tempo polinomiale nella dimensione dell’istanza del problema da quelli che richiedono tempo esponenziale.

Nell’esempio del commesso viaggiatore, la dimensione dell’istanza è il numero di città ed è noto che è improbabile l’esistenza di un algoritmo esatto che richieda tempo polinomiale nel numero di città.

Algoritmi di approssimazione e stocastici

Problemi che non ammettono algoritmi esatti polinomiali sono detti difficili e, non potendo essere risolti in modo esatto entro un tempo compatibile con l’applicazione se non per piccole istanze, è necessario ricorrere ad algoritmi di approssimazione. Questi ultimi richiedono tempo polinomiale nella dimensione dell’istanza del problema e forniscono una garanzia teorica alla qualità della soluzione approssimata restituita. Nel caso del commesso viaggiatore, un algoritmo approssimato garantisce che la distanza di percorrenza totale della soluzione approssimata non è superiore, ad esempio, a due volte la distanza di percorrenza ottima. Qualora un algoritmo approssimato non fornisca alcuna garanzia teorica sulla qualità della soluzione è detto euristico. In molti problemi particolarmente difficili, è comune il fatto che non sia possibile costruire un algoritmo di approssimazione in tempo polinomiale con delle garanzie teoriche e quindi l’uso di tecniche euristiche risulta necessario. 

Algoritmi esatti, di approssimazione ed euristici possono essere deterministici o stocastici. Un algoritmo esatto/di approssimazione deterministico restituisce una soluzione esatta/approssimata con probabilità 1. Invece, un algoritmo esatto/di approssimazione stocastico restituisce una soluzione esatta/approssimata con una certa probabilità inferiore ad 1. Solitamente gli algoritmi stocastici sono versioni ripetute di algoritmi deterministici parametrizzati in cui, ad ogni ripetizione (potenzialmente eseguita parallelamente alle altre), si usano parametri generati in modo casuale. Spesso capita infatti che diverse parametrizzazioni dello stesso algoritmo possono dare prestazioni radicalmente differenti su istanze diverse del problema e provando varie parametrizzazioni si può avere alta probabilità di trovare una buona parametrizzazione.

Un esempio è l’algoritmo Quicksort, il quale ordina gli elementi di un insieme in tempo quadratico nel numero di elementi, ma, se reso stocastico, in alta probabilità completa l’ordinamento in tempo quasi lineare. 

Algoritmo: seconda variante del problema

La seconda variante del problema è quando alcuni elementi dell’istanza del problema non sono noti e non è possibile apprendere quell’informazione. Ad esempio, nel problema del commesso viaggiatore, la rete di strade che connette le città potrebbe non essere nota. In questo caso, l’algoritmo scopre le connessioni stradali accessibili da una città ogni volta che la città viene raggiunta e sulla base di questa informazione prende la decisione sul prossimo spostamento. Un tale algoritmo è detto online. Gli algoritmi online sono detti competitivi se forniscono garanzie teoriche rispetto al caso in cui l’informazione sia perfettamente nota. In altre parole, si vuole garantire che la mancanza di informazione non impedisca all’algoritmo di trovare una soluzione di qualità troppo peggiore rispetto a quella ottima.

Algoritmo: terza variante del problema

La terza variante del problema è quando alcuni elementi dell’istanza non sono noti ed è possibile apprendere quell’informazione. Ad esempio, nel problema del commesso viaggiatore, è necessario apprendere i tempi di percorrenza media tra ogni coppia di città. In questa variante, il problema viene dunque esteso rispetto alle prime due varianti, includendo sia l’apprendimento dell’informazione che la risoluzione del problema originale.

Possiamo distinguere tre casi. Nel primo caso, l’apprendimento è totalmente offline e un algoritmo userà una collezione di dati precedentemente raccolta per stimare l’informazione mancante.

L’algoritmo può poi essere model-based se include un modello matematico specifico il cui sono presenti dei parametri i cui valori sono da apprendere, oppure può essere model-free se usa tecniche black-box, ad esempio reti neurali.

La fase dell’apprendimento

Nell’esempio del problema del commesso viaggiatore, si ha apprendimento offline quando sono disponibili i dati di molti viaggi fatti nel passato. Nel secondo caso, l’apprendimento è online ed è possibile spendere un certo intervallo di tempo per apprendere ripetendo la soluzione del problema e successivamente usare le stime ottenute. Questo caso è detto di pure exploration.

Tipicamente, nella fase di apprendimento, l’obiettivo è generare il miglior insieme di dati per poter apprendere al meglio i parametri. Ad esempio, se il commesso viaggiatore è sicuro del tempo di percorrenza tra due città, si concentrerà nella fase di apprendimento a provare altre strade per migliorare le sue stime sui tempi di percorrenza tra queste.

L’aspetto caratterizzante è che, durante la fase di apprendimento, non c’è alcun interesse nell’usare soluzioni buone, ma solo nell’apprendere, mentre, una volta chiusa la fase di apprendimento, l’obiettivo è di usare la migliore soluzione possibile. Le garanzie fornite dagli algoritmi riguardano l’accuratezza delle stime, assicurando che in alta probabilità l’errore di accuratezza è inferiore a un certo margine.

Nel terzo e ultimo caso, l’apprendimento è online e non è possibile spendere tempo per apprendere prima di usare la soluzione, ma l’apprendimento è contestuale all’uso della soluzione. Questo caso è detto di exploration/exploitation e richiede di trovare il miglior compromesso tra l’esplorazione di nuovi dati e la scelta della miglior soluzione in accordo con i dati osservati precedentemente. Le garanzie fornite dagli algoritmi sono dirette a limitare la perdita di qualità delle soluzioni usate nel tempo dovuta al costo di apprendere l’informazione mancante.

@RIPRODUZIONE RISERVATA

Speciale PNRR

Tutti
Incentivi
PA
Sostemibilità
Analisi
Formazione
Salute digitale
Sicurezza
Sostenibilità
Digital Economy
Formazione
Trasferimento tecnologico, il Mise mette sul piatto 7,5 milioni
Strategie
PSN e Strategia Cloud Italia: a che punto siamo e come supportare la PA in questo percorso
Dispersione idrica
Siccità: AI e analisi dei dati possono ridurre gli sprechi d’acqua. Ecco gli interventi necessari
PNRR
Cloud, firmato il contratto per l’avvio di lavori del Polo strategico
Formazione
Competenze digitali, stanziati 48 milioni per gli Istituti tecnologici superiori
Iniziative
Digitalizzazione delle reti idriche: oltre 600 milioni per 21 progetti
Competenze e competitività
PNRR, così i fondi UE possono rilanciare la ricerca e l’Università
Finanziamenti
PNRR, si sbloccano i fondi per l’agrisolare
Sanità post-pandemica
PNRR, Missione Salute: a che punto siamo e cosa resta da fare
Strategie
Sovranità e autonomia tecnologica nazionale: come avviare un processo virtuoso e sostenibile
La relazione
Pnrr e PA digitale, l’alert della Corte dei conti su execution e capacità di spesa
L'editoriale
Elezioni 2022, la sfida digitale ai margini del dibattito politico
Strategie
Digitale, il monito di I-Com: “Senza riforme Pnrr inefficace”
Transizione digitale
Pnrr: arrivano 321 milioni per cloud dei Comuni, spazio e mobilità innovativa
L'analisi I-COM
Il PNRR alla prova delle elezioni: come usare bene le risorse e centrare gli obiettivi digitali
Cineca
Quantum computing, una svolta per la ricerca: lo scenario europeo e i progetti in corso
L'indice europeo
Desi, l’Italia scala due posizioni grazie a fibra e 5G. Ma è (ancora) allarme competenze
L'approfondimento
PNRR 2, ecco tutte le misure per cittadini e imprese: portale sommerso, codice crisi d’impresa e sismabonus, cosa cambia
Servizi digitali
PNRR e trasformazione digitale: ecco gli investimenti e le riforme previste per la digitalizzazione della PA
Legal health
Lo spazio europeo dei dati sanitari: come circoleranno le informazioni sulla salute nell’Unione Europea
Servizi digitali
PNRR e PA digitale: non dimentichiamo la dematerializzazione
Digital Healthcare transformation
La trasformazione digitale degli ospedali
Governance digitale
PA digitale, è la volta buona? Così misure e risorse del PNRR possono fare la differenza
Servizi digitali
Comuni e digitale, come usare il PNRR senza sbagliare
La survey
Pnrr e digitale accoppiata vincente per il 70% delle pmi italiane
Missione salute
Fascicolo Sanitario Elettronico alla prova del PNRR: limiti, rischi e opportunità
Servizi pubblici
PNRR: come diventeranno i siti dei comuni italiani grazie alle nuove risorse
Skill gap
PNRR, la banda ultra larga crea 20.000 nuovi posti di lavoro
Il Piano
Spazio, Colao fa il punto sul Pnrr: i progetti verso la milestone 2023
FORUMPA2022
PNRR e trasformazione digitale: rivedi i Talk di FORUM PA 2022 in collaborazione con le aziende partner
I contratti
Avio, 340 milioni dal Pnrr per i nuovi propulsori a metano
Next Generation EU
PNRR, a che punto siamo e cosa possono aspettarsi le aziende private
Fondi
Operativo il nuovo portale del MISE con tutti i finanziamenti per le imprese
Servizi comunali
Il PNRR occasione unica per i Comuni digitali: strumenti e risorse per enti e cittadini
Healthcare data platform
PNRR dalla teoria alla pratica: tecnologie e soluzioni per l’innovazione in Sanità
Skill
Competenze digitali, partono le Reti di facilitazione
Gli obiettivi
Scuola 4.0, PNRR ultima chance: ecco come cambierà il sistema formativo
Sistema Paese
PNRR 2, è il turno della space economy
FORUM PA 2022
FORUM PA 2022: la maturità digitale dei comuni italiani rispetto al PNRR
Analisi
PNRR: dalla Ricerca all’impresa, una sfida da cogliere insieme
Innovazione
Pnrr, il Dipartimento per la Trasformazione digitale si riorganizza
FORUM PA 2022
PA verde e sostenibile: il ruolo di PNRR, PNIEC, energy management e green public procurement
Analisi
PNRR, Comuni e digitalizzazione: tutto su fondi e opportunità, in meno di 3 minuti. Guarda il video!
Rapporti
Competenze digitali e servizi automatizzati pilastri del piano Inps
Analisi
Attuazione del PNRR: il dialogo necessario tra istituzioni e società civile. Rivedi lo Scenario di FORUM PA 2022
Progetti
Pnrr, fondi per il Politecnico di Torino. Fra i progetti anche IS4Aerospace
Analisi
PNRR, Colao fa il punto sulla transizione digitale dell’Italia: «In linea con tutte le scadenze»
La Svolta
Ict, Istat “riclassifica” i professionisti. Via anche al catalogo dati sul Pnrr
Analisi
Spazio, Colao fa il punto sul Pnrr: i progetti verso la milestone 2023
FORUM PA 2022
Ecosistema territoriale sostenibile: l’Emilia Romagna tra FESR e PNRR
Il Piano
Innovazione, il Mise “centra” gli obiettivi Pnrr: attivati 17,5 miliardi
Analisi
PNRR: raggiunti gli obiettivi per il primo semestre 2022. Il punto e qualche riflessione
Analisi
PNRR: dal dialogo tra PA e società civile passa il corretto monitoraggio dei risultati, tra collaborazione e identità dei luoghi
Webinar
Comuni e PNRR: un focus sui bandi attivi o in pubblicazione
Analisi
Formazione 4.0: cos’è e come funziona il credito d’imposta
PA e Sicurezza
PA e sicurezza informatica: il ruolo dei territori di fronte alle sfide della digitalizzazione
PA e sicurezza
PNRR e servizi pubblici digitali: sfide e opportunità per Comuni e Città metropolitane
Water management
Water management in Italia: verso una transizione “smart” e “circular” 
LE RISORSE
Transizione digitale, Simest apre i fondi Pnrr alle medie imprese
Prospettive
Turismo, cultura e digital: come spendere bene le risorse del PNRR
Analisi
Smart City: quale contributo alla transizione ecologica
Decarbonizzazione
Idrogeno verde, 450 milioni € di investimenti PNRR, Cingolani firma
Unioncamere
PNRR, imprese in ritardo: ecco come le Camere di commercio possono aiutare
I fondi
Industria 4.0: solo un’impresa su tre pronta a salire sul treno Pnrr
Formazione
Trasferimento tecnologico, il Mise mette sul piatto 7,5 milioni
Strategie
PSN e Strategia Cloud Italia: a che punto siamo e come supportare la PA in questo percorso
Dispersione idrica
Siccità: AI e analisi dei dati possono ridurre gli sprechi d’acqua. Ecco gli interventi necessari
PNRR
Cloud, firmato il contratto per l’avvio di lavori del Polo strategico
Formazione
Competenze digitali, stanziati 48 milioni per gli Istituti tecnologici superiori
Iniziative
Digitalizzazione delle reti idriche: oltre 600 milioni per 21 progetti
Competenze e competitività
PNRR, così i fondi UE possono rilanciare la ricerca e l’Università
Finanziamenti
PNRR, si sbloccano i fondi per l’agrisolare
Sanità post-pandemica
PNRR, Missione Salute: a che punto siamo e cosa resta da fare
Strategie
Sovranità e autonomia tecnologica nazionale: come avviare un processo virtuoso e sostenibile
La relazione
Pnrr e PA digitale, l’alert della Corte dei conti su execution e capacità di spesa
L'editoriale
Elezioni 2022, la sfida digitale ai margini del dibattito politico
Strategie
Digitale, il monito di I-Com: “Senza riforme Pnrr inefficace”
Transizione digitale
Pnrr: arrivano 321 milioni per cloud dei Comuni, spazio e mobilità innovativa
L'analisi I-COM
Il PNRR alla prova delle elezioni: come usare bene le risorse e centrare gli obiettivi digitali
Cineca
Quantum computing, una svolta per la ricerca: lo scenario europeo e i progetti in corso
L'indice europeo
Desi, l’Italia scala due posizioni grazie a fibra e 5G. Ma è (ancora) allarme competenze
L'approfondimento
PNRR 2, ecco tutte le misure per cittadini e imprese: portale sommerso, codice crisi d’impresa e sismabonus, cosa cambia
Servizi digitali
PNRR e trasformazione digitale: ecco gli investimenti e le riforme previste per la digitalizzazione della PA
Legal health
Lo spazio europeo dei dati sanitari: come circoleranno le informazioni sulla salute nell’Unione Europea
Servizi digitali
PNRR e PA digitale: non dimentichiamo la dematerializzazione
Digital Healthcare transformation
La trasformazione digitale degli ospedali
Governance digitale
PA digitale, è la volta buona? Così misure e risorse del PNRR possono fare la differenza
Servizi digitali
Comuni e digitale, come usare il PNRR senza sbagliare
La survey
Pnrr e digitale accoppiata vincente per il 70% delle pmi italiane
Missione salute
Fascicolo Sanitario Elettronico alla prova del PNRR: limiti, rischi e opportunità
Servizi pubblici
PNRR: come diventeranno i siti dei comuni italiani grazie alle nuove risorse
Skill gap
PNRR, la banda ultra larga crea 20.000 nuovi posti di lavoro
Il Piano
Spazio, Colao fa il punto sul Pnrr: i progetti verso la milestone 2023
FORUMPA2022
PNRR e trasformazione digitale: rivedi i Talk di FORUM PA 2022 in collaborazione con le aziende partner
I contratti
Avio, 340 milioni dal Pnrr per i nuovi propulsori a metano
Next Generation EU
PNRR, a che punto siamo e cosa possono aspettarsi le aziende private
Fondi
Operativo il nuovo portale del MISE con tutti i finanziamenti per le imprese
Servizi comunali
Il PNRR occasione unica per i Comuni digitali: strumenti e risorse per enti e cittadini
Healthcare data platform
PNRR dalla teoria alla pratica: tecnologie e soluzioni per l’innovazione in Sanità
Skill
Competenze digitali, partono le Reti di facilitazione
Gli obiettivi
Scuola 4.0, PNRR ultima chance: ecco come cambierà il sistema formativo
Sistema Paese
PNRR 2, è il turno della space economy
FORUM PA 2022
FORUM PA 2022: la maturità digitale dei comuni italiani rispetto al PNRR
Analisi
PNRR: dalla Ricerca all’impresa, una sfida da cogliere insieme
Innovazione
Pnrr, il Dipartimento per la Trasformazione digitale si riorganizza
FORUM PA 2022
PA verde e sostenibile: il ruolo di PNRR, PNIEC, energy management e green public procurement
Analisi
PNRR, Comuni e digitalizzazione: tutto su fondi e opportunità, in meno di 3 minuti. Guarda il video!
Rapporti
Competenze digitali e servizi automatizzati pilastri del piano Inps
Analisi
Attuazione del PNRR: il dialogo necessario tra istituzioni e società civile. Rivedi lo Scenario di FORUM PA 2022
Progetti
Pnrr, fondi per il Politecnico di Torino. Fra i progetti anche IS4Aerospace
Analisi
PNRR, Colao fa il punto sulla transizione digitale dell’Italia: «In linea con tutte le scadenze»
La Svolta
Ict, Istat “riclassifica” i professionisti. Via anche al catalogo dati sul Pnrr
Analisi
Spazio, Colao fa il punto sul Pnrr: i progetti verso la milestone 2023
FORUM PA 2022
Ecosistema territoriale sostenibile: l’Emilia Romagna tra FESR e PNRR
Il Piano
Innovazione, il Mise “centra” gli obiettivi Pnrr: attivati 17,5 miliardi
Analisi
PNRR: raggiunti gli obiettivi per il primo semestre 2022. Il punto e qualche riflessione
Analisi
PNRR: dal dialogo tra PA e società civile passa il corretto monitoraggio dei risultati, tra collaborazione e identità dei luoghi
Webinar
Comuni e PNRR: un focus sui bandi attivi o in pubblicazione
Analisi
Formazione 4.0: cos’è e come funziona il credito d’imposta
PA e Sicurezza
PA e sicurezza informatica: il ruolo dei territori di fronte alle sfide della digitalizzazione
PA e sicurezza
PNRR e servizi pubblici digitali: sfide e opportunità per Comuni e Città metropolitane
Water management
Water management in Italia: verso una transizione “smart” e “circular” 
LE RISORSE
Transizione digitale, Simest apre i fondi Pnrr alle medie imprese
Prospettive
Turismo, cultura e digital: come spendere bene le risorse del PNRR
Analisi
Smart City: quale contributo alla transizione ecologica
Decarbonizzazione
Idrogeno verde, 450 milioni € di investimenti PNRR, Cingolani firma
Unioncamere
PNRR, imprese in ritardo: ecco come le Camere di commercio possono aiutare
I fondi
Industria 4.0: solo un’impresa su tre pronta a salire sul treno Pnrr

Articoli correlati