Informatica teorica

Informatica teorica

Con l'espressione informatica teorica ci si riferisce a un complesso di discipline scientifiche aventi per oggetto lo studio formale degli strumenti, dei metodi e dei processi per la rappresentazione dell'informazione e per la sua elaborazione. Come accade per altre discipline tecnico-scientifiche, anche nel caso dell'informatica esiste un insieme di concetti, di principi, di proprietà logico-matematiche che ne costituiscono il fondamento teorico. Su tale fondamento si basano i progettisti per realizzare modelli formali di sistemi e processi di calcolo, per progettare nuovi strumenti informatici e nuove applicazioni e per analizzarne e certificarne le prestazioni.

La locuzione informatica teorica è stato coniata in Francia agli inizi degli anni Settanta, contemporaneamente alla sua versione anglosassone (theoretical computer science). L'uso di tali termini si è consolidato a seguito della creazione di associazioni (come la European association for theoretical computer science) e di riviste scientifiche (come la rivista internazionale Theoretical computer science) che costituiscono importanti sedi di incontro e confronto per la comunità di studiosi del settore.

L'informatica ha assunto nel panorama scientifico degli ultimi decenni una notevole rilevanza legata alla diffusione dei sistemi di elaborazione nei più diversi ambiti dell'attività umana. L'informatica teorica ha accompagnato questo sviluppo creando le basi concettuali e culturali su cui l'innovazione tecnologica è maturata e contribuendo a migliorare le prestazioni dei sistemi per quanto riguarda affidabilità, efficienza, sicurezza. È interessante osservare, tuttavia, che il rapporto tra l'informatica e i suoi fondamenti teorici non è sempre lineare come accade per le teorie che sono alla base di altri settori tecnologici. Infatti, mentre in alcuni casi la filiera dell'innovazione (ricerca di base-ricerca applicata-sviluppo) si esplica su un arco temporale di qualche decennio (per es., il linguaggio di programmazione Java, oggi diffusamente utilizzato, si basa sui presupposti della programmazione a oggetti, che hanno avuto le loro origini negli anni Settanta), in altri casi l'incalzante evoluzione della tecnologia accelera o sovverte le fasi del processo innovativo. Un esempio significativo è costituito dal World wide web. Realizzato con approccio sperimentale da Tim Berners-Lee nel 1989 presso i laboratori del CERN a Ginevra come strumento di comunicazione per la comunità dei fisici, il Web è divenuto solo successivamente oggetto di studio da parte dell'informatica teorica quando, per realizzare motori di ricerca sempre più efficaci, si è reso necessario analizzare matematicamente la sua struttura.

Anche se l'informatica teorica nasce e si sviluppa in relazione all'elaborazione dell'informazione realizzata mediante calcolatore elettronico, è bene sottolineare che gran parte delle problematiche da essa studiate attengono a un ambito molto più vasto rispetto allo strumento utilizzato per l'elaborazione. Da un lato, infatti, l'informatica teorica riguarda temi che sono stati oggetto di studio ancor prima dell'avvento dei calcolatori elettronici (per es., il concetto di calcolo e di algoritmo); dall'altro, essa deve affrontare e rappresentare anche processi di elaborazione che avvengono in sistemi diversi dai sistemi elettronici (per es., l'elaborazione dell'informazione che si verifica, con meccanismi molecolari, in una cellula). L'informatica teorica, inoltre, fa proprie metodologie derivanti da altri campi scientifici, dalla matematica alla teoria dei giochi (per studiare la competizione per l'acquisizione di risorse in una rete di calcolatori), alla fisica (nell'analisi di strutture complesse).

Il ruolo metascientifico ed epistemologico dell'informatica teorica e le sue aree metodologiche

Due aspetti mettono in evidenza, in particolare, il ruolo metascientifico ed epistemologico dell'informatica teorica. Per analizzare e affrontare i problemi relativi all'elaborazione dell'informazione nei vari campi applicativi, è necessario seguire procedimenti di astrazione e di formalizzazione concettualmente non dissimili da quelli seguiti dai matematici ma basati su nuove strutture formali, diverse e dotate di maggiore potere espressivo rispetto a quelle utilizzate nei campi classici della matematica. Così, per esempio, per descrivere e ottimizzare sistemi di produzione industriale è stata utilizzata la teoria delle reti di Petri; per il controllo di sistemi in condizioni di incertezza si usano i cosiddetti insiemi sfumati (fuzzy sets); per studiare il comportamento di processi concorrenti sono state introdotte opportune logiche modali. In questo senso, dunque, l'informatica teorica costituisce un'estensione della matematica all'universo delle tecnologie informatiche e delle loro applicazioni. In secondo luogo, si deve tenere presente che l'informatica teorica ha come oggetto di studio aspetti caratteristici della sfera cognitiva dell'uomo: per esempio, i processi di comunicazione tra più agenti in un sistema di calcolo distribuito, la di strutture linguistiche, la rappresentazione di dati e di conoscenza, e così via. Lo studio dei principi matematici che sono alla base di tali concetti è dunque un obiettivo basilare dell'informatica teorica. Esso costituisce di fatto una prosecuzione e un arricchimento dell'opera dei logici (quali Kurt Gödel, Stephen Kleene, Alan Turing e Alonzo Church), che negli anni Trenta hanno affrontato e risolto i primi importanti interrogativi riguardanti la completezza e la consistenza delle teorie logiche e il potere computazionale dei sistemi formali di calcolo. Proseguendo questa linea di studi a carattere metateorico, lo sviluppo dell'informatica ha determinato ulteriori approfondimenti dei concetti e delle proprietà del calcolo, delle macchine, dei linguaggi. Esempi di problematiche affrontate nell'ambito dell'informatica teorica, che si collocano su questo piano fondazionale, sono: il potere espressivo di modelli formali, il concetto di trattabilità computazionale, il potere computazionale di nuovi modelli di calcolo (probabilistici, quantistici, molecolari).

In relazione ai diversi obiettivi e alle diverse problematiche precedentemente citate, si sono sviluppati, nell'ambito dell'informatica teorica, diversi settori di studio. Tra di essi, i seguenti hanno assunto, nel tempo, un ruolo particolarmente importante e costituiscono ormai capitoli ben definiti dell'informatica teorica: modelli di calcolo e calcolabilità, teoria degli automi e dei linguaggi formali, analisi e progetto di algoritmi e strutture dati, algoritmi paralleli, algoritmi di approssimazione, algoritmi probabilistici, algoritmi on-line, geometria computazionale, complessità di calcolo, complessità descrittiva, teoria dei protocolli crittografici, teorie logiche della programmazione, semantica dei programmi, teoria delle basi di dati e della rappresentazione della conoscenza, teoria dei sistemi distribuiti e dei processi concorrenti.

Si tratta, come si vede, di una pluralità estremamente ampia di tematiche, nell'ambito di ciascuna delle quali si sono sviluppate verie e proprie teorie scientifiche, dotate di complessi apparati concettuali, di tecniche di analisi, di strumenti deduttivi logico-formali, di risultati fondamentali, di applicazioni.

Nell'impossibilità di fornire, in questa sede, un quadro così ampio, ci limitiamo a presentare alcune delle più importanti tra le suddette tematiche, raccogliendole in due filoni culturali, uno riguardante gli aspetti relativi alla complessità dei problemi e alla loro risoluzione con algoritmi efficienti, l'altro riguardante gli aspetti relativi al comportamento dei programmi e dei processi, che possiamo denominare, rispettivamente, teoria degli algoritmi e della complessità di calcolo e teoria dei programmi e dei processi di calcolo. In una terza e ultima sezione, discuteremo invece caratteristiche e potenzialità di nuovi modelli computazionali (neuronali, quantistici, molecolari).

Teoria degli algoritmi e della complessità di calcolo

In molte applicazioni dell'informatica (come nel caso dei ), la tempestività della risposta del sistema di elaborazione è una condizione vincolante per il funzionamento dell'applicazione stessa.

Peraltro, anche nei casi in cui non si richiedono tempi di risposta particolarmente stringenti, come nei sistemi di analisi finanziaria o nella gestione di dati satellitari, l'efficienza dei programmi è resa necessaria dalla grande mole di informazioni che devono essere elaborate.

La necessità di garantire, nelle applicazioni informatiche, la maggiore efficienza possibile, compatibilmente con l'intrinseca complessità delle applicazioni, ha portato allo sviluppo di una serie di metodologie per il progetto di algoritmi e per l'analisi delle loro prestazioni, nonché alla classificazione dei problemi rispetto alla loro complessità intrinseca, cioè rispetto al costo (quantità di tempo di calcolo o quantità di memoria) necessario per la loro risoluzione. Nel seguito esporremo alcune delle principali e attuali direzioni della ricerca nel campo dell'algoritmica, iniziando dalle aree più classiche relative alle tecniche di progetto di algoritmi e alla caratterizzazione della complessità di problemi.

Tecniche di progetto di algoritmi efficienti

Da quando hanno cominciato a essere utilizzati i primi calcolatori, tecniche algoritmiche di grande rilevanza sono state sviluppate nell'ambito delle loro varie applicazioni (calcolo numerico, , gestione di grandi archivi di dati). Gli studi svolti nell'ambito dell'informatica teorica hanno contribuito in modo decisivo a sviluppare ulteriormente le tecniche di progetto di algoritmi e migliorarne le prestazioni. Numerosi testi, a cominciare dalla fondamentale opera di Donald E. Knuth in 3 volumi (1969-1973), presentano le principali tecniche di progetto di algoritmi sviluppate nel corso degli anni e ne illustrano le applicazioni. A titolo esemplificativo citiamo alcuni esempi legati a tre importanti tecniche di progetto.

Divide et impera. - È nota con questo nome la tecnica di risoluzione di problemi basata sulla decomposizione in sottoproblemi. Supponiamo di dover ordinare una lista di n interi. Consideriamo l'algoritmo di ordinamento mediante fusione, consistente nel suddividere la lista in due parti uguali, nell'ordinare separatamente con lo stesso metodo le due metà (di n/2 elementi) e nel fondere le liste ordinate così ottenute. Il costo C(n) di questo metodo è O(nlogn) e si ottiene risolvendo la semplice relazione di ricorrenza C(n)=2C(n/2)+n, direttamente ricavabile dalla struttura ricorsiva dell'algoritmo. Ricordiamo, per maggiore chiarezza, che il costo di un algoritmo è O(f(n)) se esistono due costanti c ed n′ tali che per ogni n>n′, per ogni dato di dimensione n, l'algoritmo esegue un numero di passi limitato da cf(n) e che i logaritmi utilizzati in questo ambito sono logaritmi in base 2, se non diversamente indicato.

L'uso della tecnica divide et impera consente in molti casi di realizzare algoritmi particolarmente efficienti e inoltre ha il pregio di facilitare l'analisi delle prestazioni poiché, come si è visto, si può esprimere il costo di esecuzione mediante una relazione di ricorrenza che riflette la struttura ricorsiva dell'algoritmo. Esempi storicamente importanti di applicazione del metodo divide et impera sono l'algoritmo di James W. Cooley e John W. Tukey (1965) per la trasformata rapida di Fourier ‒ che può essere realizzata in tempo O(nlogn) ‒ e l'algoritmo per il prodotto di matrici, dovuto a Volker Strassen (1969), che ha permesso per la prima volta di battere il classico algoritmo con tempo di esecuzione O(n³) e di effettuare il prodotto di matrici in tempo O(n^2,81), aprendo così la strada a una serie di miglioramenti che hanno portato Don Coppersmith e Shmuel Winograd (1990) alla realizzazione di algoritmi con tempo di esecuzione O(n^2,38). Pur non essendo utilizzabile in pratica, l'algoritmo di Coppersmith e Winograd è asintoticamente il miglior algoritmo oggi noto per il prodotto di matrici e non si sa se possa essere ulteriormente migliorato.

Bilanciamento. - In molte applicazioni in cui si richiede l'accesso rapido a un'ingente quantità di dati è necessario organizzare le informazione in strutture basate sul concetto di albero bilanciato. Se, per esempio, associamo opportunamente ai nodi di un albero binario n numeri interi (per esempio, numeri di matricola di impiegati) e se tale albero è bilanciato, cioè il sottoalbero destro e il sottoalbero sinistro hanno quasi lo stesso numero di nodi, è possibile reperire le informazioni riguardanti un impiegato in tempo O(logn). Nel caso in cui si faccia uso di alberi m-ari (cioè tali che ogni nodo interno abbia m figli), come accade nei cosiddetti B-alberi introdotti da Rudolf Bayer e Edward M. McCreight (1972), si possono ottenere prestazioni ancora migliori, perché l'accesso diviene proporzionale al log_mn. Più recentemente, sono state proposte altre strutture di dati efficienti per la gestione di dati su memoria secondaria, nelle quali il bilanciamento viene garantito realizzando una redistribuzione casuale delle informazioni sulle varie foglie dell'albero (hashing dinamico, hashing lineare, e così via).

Dinamizzazione. - Un numero crescente di applicazioni informatiche richiede la gestione di informazioni con una rapida evoluzione temporale e quindi soggette ad aggiornamenti molto frequenti. Ciò si verifica, per esempio, nelle reti di telecomunicazioni, nella visione di scene in movimento, nella grafica interattiva. In questi casi, è necessario utilizzare strutture di dati dinamiche che possono essere facilmente aggiornate e che garantiscono un buon comportamento, se non a ogni operazione, almeno su un'intera sequenza di operazioni di aggiornamento. È opportuno osservare che per determinare la qualità delle prestazioni di un algoritmo che gestisce una struttura dinamica si deve utilizzare un metodo di analisi del costo di esecuzione che tenga conto della ripartizione di tale costo sulle operazioni di una intera sequenza (analisi ammortizzata). Il maggior contributo in questa direzione è stato dato da Robert E. Tarjan che ha introdotto varie strutture di dati autoadattative, in particolare i Fibonacci heaps, che permettono di eseguire efficientemente sequenze di operazioni di interrogazione e di aggiornamento (ricerca dell'elemento minimo, inserimento, fusione, cancellazione, ecc.). L'uso di strutture autoadattative ha anche consentito il miglioramento della soluzione di alcuni problemi di ottimizzazione, come il problema del minimo albero di connessione in un , per il quale Michael L. Fredman e Tarjan hanno fornito il primo algoritmo sostanzialmente lineare; oppure, il problema della massimizzazione del flusso in una rete, per il quale Andrew V. Goldberg e lo stesso Tarjan hanno proposto nel 1988 una soluzione di costo O(nmlog(n²/m)) per grafi con n nodi ed m archi, trent'anni dopo il classico (ma inefficiente) algoritmo di Ford e Fulkerson (1956).

I risultati riguardanti la realizzazione di algoritmi efficienti, ottenuti a seguito di ricerche nell'ambito dell'informatica teorica e degni di nota per la loro rilevanza pratica, sono innumerevoli. Tra i campi in cui sono stati fatti progressi significativi possiamo ancora citare: la , un'importante classe di problemi di ottimizzazione, in passato ritenuta di costo intrinsecamente esponenziale, per la quale sono stati individuati invece algoritmi polinomiali; la gestione ottimale di reti (i migliori algoritmi oggi noti per il problema del minimo albero di connessione e per il problema del massimo flusso sono dovuti, rispettivamente, a Bernard Chazelle e ad Andrew V. Goldberg e Satish Rao); la geometria computazionale (per la quale sono stati definiti algoritmi efficienti di localizzazione di punti in regioni dello spazio e di triangolazione di superfici). Un importante risultato è stato ottenuto recentemente da Manindra Agrawal, Neeraj Kayal e Nitin Saxena, i quali hanno realizzato un algoritmo polinomiale per il test di primalità di un numero intero, prima ritenuto un problema di costo necessariamente esponenziale.

Caratterizzazione della complessità intrinseca dei problemi

Nel campo dell'informatica teorica, con il termine complessità ci si riferisce, usualmente, alla complessità computazionale, cioè alla quantità di risorsa (in termini di tempo di calcolo o memoria) necessaria e sufficiente per risolvere un problema con un determinato modello di calcolo. Classici modelli di calcolo utilizzati a tale scopo sono la RAM e la . La RAM (direttamente ispirata al modello strutturale dei normali calcolatori, detto modello di von Neumann, dal nome di uno degli scienziati che hanno contribuito alla realizzazione dei primi calcolatori elettronici) è dotata di un nastro di ingresso, di un nastro di uscita, di una memoria costituita da un numero potenzialmente illimitato di celle (registri), ciascuna delle quali capace di contenere numeri interi arbitrariamente grandi, e di un'unità di elaborazione capace di eseguire semplici istruzioni (simili a quelle previste dai calcolatori reali: trasferimento di dati, somma, sottrazione, prodotto, verifica di uguaglianza a zero, ecc.). La macchina di Turing (introdotta da Alan M. Turing negli anni Trenta con lo scopo di definire formalmente il concetto di algoritmo) dispone di una memoria interna con un numero finito di stati e di un nastro suddiviso in celle e potenzialmente illimitato su cui essa può leggere e scrivere caratteri mediante un'apposita testina di lettura e scrittura. A ogni passo (transizione di stato) la macchina legge un carattere sul nastro e, in base allo stato interno in cui si trova, effettua le seguenti operazioni: scrittura di un nuovo carattere, passaggio ad un altro stato interno e spostamento a destra o a sinistra della testina. Nonostante questo modello sia lontano dai reali calcolatori, esso è tuttora utilizzato per la sua grande semplicità sia nella teoria degli automi e dei linguaggi formali sia nella teoria della complessità di calcolo. Per caratterizzare la complessità di un problema è importante individuare i fattori che ne influenzano il costo di risoluzione. Da questo punto di vista, la conoscenza di un algoritmo risolutivo per un dato problema e del suo costo di esecuzione ci fornisce solo una delimitazione superiore della complessità del problema ma non ci dice nulla sulle caratteristiche intrinseche che rendono più o meno difficile la soluzione del problema stesso e che derivano dalla sua natura combinatoria. È lo studio di queste proprietà che permette di individuare il costo necessario per risolvere il problema, fornendo una delimitazione inferiore della sua complessità. Quando tali delimitazioni coincidono, la complessità del problema è stata esattamente caratterizzata. Formalmente, diciamo che la complessità di un problema è O(f(n)) se esiste un algoritmo che lo risolve con un costo O(f(n)); Ω(f(n)), se ogni algoritmo comporta almeno un costo dell'ordine di f(n); Θ(f(n)), se essa è sia O(f(n)) sia Ω(f(n)).

Consideriamo ancora il problema dell'ordinamentodi interi. Possiamo mostrare che la sua complessità èΘ(nlogn): infatti, (a) essa è Ω(nlogn) perché il numero di possibili ordinamenti di un vettore di n elementi è n! e, nel caso peggiore, il numero di confronti necessari per individuare l'ordinamento corretto è log(n)≅nlogn (ogni confronto può al più suddividere in due semispazi di uguale cardinalità lo spazio degli ordinamenti possibili); (b) l'algoritmo di ordinamento mediante fusione, come abbiamo visto, opera in O(nlogn).

In base alla loro complessità, i problemi vengono raggruppati in classi. Per esempio, i problemi risolubili in tempo polinomiale ‒ cioè in tempo O(n^k) per qualche valore di k ‒ costituiscono la classe P. Tipici esempi di problemi appartenenti a P sono l'ordinamento di interi, la moltiplicazione di matrici, la determinazione di cammini minimi e alberi di connessione minimi in grafi e reti, la programmazione lineare. Si noti che, poiché RAM e macchine di Turing possono simularsi reciprocamente in tempo polinomiale, se un problema appartiene alla classe P non dobbiamo specificare a quale modello di calcolo facciamo riferimento. Altre classi significative sono le classi di problemi risolubili in tempo esponenziale (EXP), e quelle dei problemi che richiedono una quantità di spazio (memoria) logaritmica (LOGSPAZIO) o polinomiale (PSPAZIO).

Le classi di complessità temporale e spaziale sono (parzialmente) ordinate rispetto all'inclusione e lo studio della struttura di tale ordinamento (chiamato complessità strutturale) costituisce uno dei capitoli più importanti dell'informatica teorica. Iniziatori della teoria della complessità computazionale, a metà degli anni Sessanta, sono stati Juris Hartmanis, Richard E. Stearns e Philip M. Lewis, i quali hanno definito e studiato il concetto di classe di complessità per le macchine di Turing. A tali studi hanno fatto seguito quelli di Manuel Blum e Albert Meyer, aventi per oggetto le proprietà astratte (indipendenti da specifici modelli di calcolo) del concetto di misura di complessità e di classe di complessità e, successivamente, negli anni Settanta, le ricerche di Stephen A. Cook, David S. Johnson, Richard M. Karp, Leonid A. Levin, Walter J. Savitch e altri, volte a caratterizzare la complessità di problemi di rilevante interesse applicativo.

Al centro dell'interesse della teoria della complessità si trova il concetto di trattabilità computazionale. Un problema si dice trattabile se esso appartiene a P, cioè è risolubile con un algoritmo di costo polinomiale ed è quindi possibile risolverlo efficientemente in pratica. La scelta di considerare trattabile un problema di complessità polinomiale può apparire arbitraria ma essa è giustificata dal fatto che i benefici derivanti dal potenziamento dei mezzi di elaborazione incidono soprattutto nel caso di problemi risolubili in tempo polinomiale e arrecano poco giovamento nella risoluzione di problemi che hanno tempi di risoluzione esponenziali. Supponiamo, per esempio, che in un minuto di calcolo si sappia risolvere un caso di un problema di dimensione k. Ebbene, se il costo della soluzione del problema cresce come n², un processore 1000 volte più veloce ci permette di affrontare, nella stessa quantità di tempo, un caso di dimensione 30k, ma se il problema richiede tempo dell'ordine di 2ⁿ, il calcolatore più potente potrà al più risolvere, sempre nell'intervallo di un minuto, casi di dimensione k+10. Il vantaggio conseguito sarà quindi marginale.

Problemi la cui soluzione richiede tempo crescente in modo non limitato da un polinomio (per es., n^logn o 2ⁿ) vengono considerati intrattabili, poiché per essi il costo di risoluzione diviene proibitivo non appena i dati in ingresso raggiungono una dimensione ragguardevole. Per molti problemi di interesse pratico si conoscono attualmente solo algoritmi che richiedono tempo esponenziale, ma non è provato che essi non possano essere risolti in tempo polinomiale. Non si sa quindi se siano trattabili o meno. Esempi di problemi di tale tipo sono la risolubilità di un sistema di equazioni lineari a variabili intere, la soddisfacibilità di un'espressione booleana, il problema dello scheduling (decidere se si può allocare un insieme di lavori su più macchine in modo da rispettare una data scadenza), il problema del commesso viaggiatore (decidere se esiste un percorso che consente di visitare un dato numero di città entro un dato limite di tempo).

Una particolarità comune a questi problemi è che in ogni caso l'insieme delle soluzioni possibili (per es., l'insieme di tutte le assegnazioni di valori di verità alle variabili della formula booleana) è esponenziale, mentre la verifica del fatto che una data soluzione soddisfi la proprietà richiesta (per es., che una data assegnazione di valori di verità soddisfi la formula) può essere effettuata in tempo polinomiale. La classe dei problemi che hanno questa natura è chiamata NP (poiché essa coincide con la classe di problemi risolubili in tempo polinomiale con una macchina non deterministica). Chiaramente la classe NP contiene la classe P ma allo stato attuale non è noto se qualche problema in NP sia effettivamente di complessità non polinomiale (e quindi, P≠NP) o se non sia possibile trovare, per tutti i problemi in NP, algoritmi di costo polinomiale (e quindi, P=NP). È interessante osservare che, per le sue rilevanti implicazioni sia teoriche che pratiche, la questione della relazione tra P ed NP è uno dei più importanti problemi aperti dell'informatica e, più in generale, della matematica. Esso infatti è incluso tra i sette principali problemi del XXI sec. per la soluzione dei quali il Clay Mathematical Institute offre un premio di un milione di dollari.

In particolare, tra i problemi in NP si trovano i cosiddetti problemi NP-completi, la cui struttura combinatoria è talmente ricca da permettere che ogni altro problema in NP sia Karp-riducibile a essi, in tempo polinomiale. Un problema di decisione A è Karp-riducibile in tempo polinomale a un problema di decisione B se dato un caso x del problema A è possibile creare (in tempo polinomiale) un caso f(x) del problema B tale che x ha soluzione positiva se e solo se f(x) ha soluzione positiva. In base a tale proprietà (dimostrata da Cook nel 1971 per il problema della soddisfacibilità di formule booleane e successivamente dimostrata da Karp per numerosi altri problemi), se anche per un solo problema NP-completo si individuasse un algoritmo di costo polinomiale, tutti i problemi in NP sarebbero risolubili in tempo polinomiale e risulterebbe P=NP. Esempi di problemi NP-completi sono tutti i problemi citati precedentemente come problemi in NP per cui non sono noti algoritmi polinomiali, ma nuovi problemi NP-completi si incontrano quotidianamente in ogni campo dell'informatica e di altri settori scientifici (dalla matematica alla biologia).

Algoritmi di approssimazione

Così come accade per i problemi di decisione considerati precedentemente, anche molti importanti problemi di ottimizzazione combinatoria sono probabilmente intrattabili: infatti, l'esistenza di un algoritmo polinomiale per la loro soluzione implicherebbe P=NP. Tali problemi sono chiamati NP-ardui. Per esempio, nel caso del problema del commesso viaggiatore, se potessimo trovare un percorso di costo minimo in tempo polinomiale, avremmo anche un algoritmo polinomiale per risolvere il corrispondente problema decisionale, il quale, come abbiamo visto, è NP-completo. Dovendo affrontare in pratica un problema di ottimizzazione NP-arduo, o si adotta un algoritmo risolutivo di costo esponenziale (adattandosi a utilizzarlo solo su istanze particolarmente semplici), oppure si può fare ricorso a un algoritmo di costo polinomiale, ottenendo però, in genere, una soluzione approssimata.

Chiamiamo algoritmo di approssimazione a qualità garantita un algoritmo eseguibile in tempo polinomiale che risolve in modo approssimato un problema di ottimizzazione NP-arduo, fornendo sempre una soluzione il cui valore può presentare, rispetto all'ottimo, un errore di entità limitata.

Si consideri il seguente problema NP-arduo: data una rete stradale con m strade, si deve determinare il minimo numero di vigili da disporre agli incroci in modo che ogni strada abbia un vigile ad almeno una delle due estremità. Se ci si accontenta di una soluzione approssimata che fa uso di un numero di vigili (al più) doppio rispetto al minimo possibile, la si può determinare in tempo O(m) nel seguente modo. Si seleziona una strada qualsiasi e si assegnano due vigili agli incroci che sono alle sue estremità. Poi si cancellano dalla rete tutte le strade che portano ai due incroci e si seleziona un'altra strada. Si procede in questo modo finchè non esistono più strade non sorvegliate. Il numero di vigili utilizzati con tale approccio è al più il doppio dell'ottimo: in qualunque soluzione ottima, ognuna delle strade prese in considerazione, a cui sono stati assegnati due vigili, dovrà avere comunque un vigile ad almeno una delle estremità.

Vari problemi di ottimizzazione NP-ardui ammettono, come quello visto nell'esempio, soluzioni approssimate di qualità garantita. Tra di essi sono particolarmente interessanti il problema della determinazione del massimo taglio in un grafo (approssimabile con un errore inferiore al 13%), quello della massimizzazione del numero di clausole soddisfacibili in un'espressione booleana in forma normale congiuntiva (approssimabile con un errore inferiore al 17%) e quello del commesso viaggiatore, nel caso in cui i costi di percorrenza delle strade che collegano le varie città soddisfino la disuguaglianza triangolare (in tal caso si può ottenere una soluzione che non eccede mai più del 50% il costo minimo).

Per alcuni problemi di ottimizzazione le condizioni di approssimabilità sono ancora più forti: per essi, qualunque sia il grado di approssimazione che vogliamo raggiungere, esiste un algoritmo di costo polinomiale che garantisce tale risultato. È il caso, per esempio, del problema della bipartizione consistente nel dividere oggetti di valore, ciascuno dei quali non scomponibile in due insiemi, in modo da minimizzare la differenza di valore degli insiemi stessi, oppure del problema della bisaccia, consistente nel massimizzare il valore degli oggetti che possono essere inseriti in una bisaccia senza eccedere la capacità della bisaccia stessa.

Sfortunatamente, non tutti i problemi NP-ardui ammettono algoritmi di approssimazione a qualità garantita operanti in tempo polinomiale. Per alcuni di essi, la ricerca di una soluzione di qualità garantita è altrettanto complessa quanto la ricerca di una soluzione ottima. Ciò accade, per esempio, per il problema della colorazioneottima di grafi, consistente nel minimizzare il numero di colori applicabili ai nodi di un grafo con il vincolo che a due nodi collegati da un arco vengano assegnati colori diversi; oppure, per il problema del commesso viaggiatore, nel caso in cui non ci siano restrizioni sui costi di percorrenza delle strade.

I motivi che rendono alcuni problemi di ottimizzazione NP-ardui approssimabili ‒ e altri no ‒ sono ancora oggetto di ricerca. Tecniche molto efficaci per dimostrare la non approssimabilità di alcuni problemi o per individuare con precisione i limiti di approssimabilità di altri, sono state introdotte negli anni Novanta da Sanjeev Arora, Shmuel Safra, Madhu Sudan e altri studiosi. Esse sono basate su una singolare proprietà della classe NP (teorema delle dimostrazioni verificabili in modo probabilistico): per ogni insieme S∈NP, se un elemento appartiene a S, esiste una dimostrazione di questo fatto (codificata in una sequenza binaria) che può essere verificata, in tempo polinomiale, da un algoritmo che ne esamina solo pochi bit, scelti a caso.

Algoritmi probabilistici

L'introduzione di elementi di casualità nella realizzazione di algoritmi è un altro importante strumento che consente, in alcuni casi, di ottenere efficientemente la soluzione di un problema a patto di accettare un limitato rischio di errore. Intuitivamente, un algoritmo che sfrutta la casualità (algoritmo probabilistico, o randomizzato) può essere realizzato prevedendo che, in alcuni suoi passi, anziché procedere deterministicamente, ci si affidi al lancio di una moneta e si proceda differentemente a seconda che il risultato sia testa o croce. In realtà, per effettuare scelte casuali in un algoritmo probabilistico si ricorre a un generatore di valori casuali (un singolo bit 0 o 1 o un valore in un certo intervallo) ma va sottolineato che il problema di disporre di una sorgente di bit realmente casuali è tuttora uno dei temi cruciali nel campo degli algoritmi probabilistici. Uno dei primi algoritmi probabilistici, volti alla soluzione di un problema complesso, è stato l'algoritmo proposto da Michael O. Rabin nel 1980 per decidere se un dato numero è un numero primo (test di primalità), un problema per il quale allora non era noto alcun algoritmo polinomiale. Altri algoritmi probabilistici sono stati realizzati per risolvere problemi di ricerca di occorrenze di stringhe in un testo, problemi di conteggio, problemi di taglio minimo su grafi, ecc. Consideriamo il seguente problema: date tre matrici A,B,C si vuole determinare se AB=C. Allo stato attuale, non conosciamo alcun algoritmo deterministico che possa risolvere questo problema in un tempo inferiore a O(n^2,38), il miglior tempo noto per il prodotto di matrici. Il seguente algoritmo risolve il problema in tempo O(n²) con un errore ≤1/2. Date A,B,C l'algoritmo crea un vettore x con valori 1 o −1 attribuiti a caso. Poi calcola i prodotti: A(Bx) e Cx. Se risulta A(Bx)=Cx allora dà risposta positiva (accetta), altrimenti dà risposta negativa (rifiuta). Chiaramente, se l'algoritmo rifiuta, esso si comporta correttamente, mentre quando accetta potrebbe errare, infatti potrebbe accettare anche se AB≠C. Si può dimostrare, però, che ciò non può accadere con probabilità superiore a 1/2. Per ottenere una probabilità di errore inferiore è sufficiente iterare l'esecuzione dell'algoritmo.

Per analogia con un metodo di integrazione numerica basato su un approccio probabilistico, un algoritmo di questa natura viene chiamato algoritmo Monte Carlo.

L'uso della casualità può risultare utile anche per velocizzare algoritmi. In molti casi, infatti, una redistribuzione casuale delle informazioni in ingresso può rendere la soluzione più efficiente con elevata probabilità. Solo occasionalmente l'algoritmo continuerà ad avere un costo di esecuzione elevato. Per questo tipo di algoritmo è stato adottato il nome di algoritmo Las Vegas.

Il potere computazionale degli algoritmi probabilistici di vario tipo è tuttora oggetto di studio. Chiaramente, gli algoritmi probabilistici non sono più potenti delle macchine di Turing (è sempre possibile simulare un qualunque tipo di algoritmo probabilistico con una macchina di Turing). Ciò che non è stato caratterizzato ‒ e rappresenta una delle grandi sfide intellettuali che continuano a impegnare la ricerca nel campo dell'informatica teorica ‒ è il potere degli algoritmi probabilistici operanti in tempo polinomiale. Se chiamiamo RP la classe dei problemi di decisione risolubili in tempo polinomiale con un algoritmo probabilistico che può errare (con probabilità non superiore a 1/2) solo quando risponde positivamente, si può osservare che P⊆RP⊆NP, ma finora non esiste alcuna dimostrazione che il primo contenimento sia stretto, ovvero che esista qualche problema intrattabile che può essere risolto in tempo polinomiale ammettendo una limitata probabilità di errore. In altri termini, non si sa se la casualità possa realmente aiutare nella risoluzione di problemi complessi.

In pratica, gli algoritmi probabilistici hanno consentito importanti progressi in molti campi dell'informatica, in particolare nel campo dei protocolli crittografici che hanno un ruolo importante nel commercio elettronico, nell'accesso elettronico ai servizi bancari e nell'utilizzazione di servizi a pagamento su Internet.

Uno dei più interessanti casi di applicazione di algoritmi probabilistici in quest'area riguarda i protocolli interattivi e, in particolare, le cosiddette dimostrazioni a conoscenza nulla. La nozione di dimostrazione a conoscenza nulla è stata introdotta da Shafi Goldwasser, Silvio Micali e Charlie Rackoff, intorno alla metà degli anni Ottanta; in modo indipendente, nello stesso periodo, László Babai ha introdotto un analogo tipo di protocolli chiamati 'giochi tra Artù e Merlino'. In questo tipo di protocolli, si ipotizza un dialogo tra un dimostratore P e un verificatore V in merito a una determinata asserzione. Se l'asserzione è vera, P riesce a convincere V di ciò, senza peraltro trasmettergli alcuna conoscenza relativa al metodo di prova; se l'asserzione è falsa, anche barando, P non riuscirebbe a convincere V della correttezza dell'asserzione, con probabilità maggiore di 1/2.

I protocolli interattivi e gli algoritmi probabilistici che ne sono alla base hanno avuto un ruolo molto importante nell'ambito dell'informatica teorica, per quanto attiene la caratterizzazione di classi di complessità: per esempio, abbiamo già visto che la classe NP può essere caratterizzata mediante un tipo particolarmente semplice di protocollo interattivo, le dimostrazioni verificabili in modo probabilistico.

Risultati analoghi, con opportuni protocolli, valgono anche per la classe PSPAZIO e per altre classi di complessità.

Algoritmi dinamici e algoritmi on-line

Una delle caratteristiche delle moderne applicazioni dei calcolatori consiste nel fatto che i dati da elaborare non sono statici ma variano con elevata frequenza. Per esempio, in Internet, le tabelle di instradamento dei messaggi devono essere continuamente aggiornate perché alcuni collegamenti tra nodi della rete cadono e vengono ripristinati con elevata frequenza. In tali situazioni, si devono sviluppare algoritmi (chiamati algoritmi dinamici) che consentono di risolvere un problema e mantenerne efficientemente aggiornata la soluzione in presenza di modificazione dei dati di ingresso, senza che la soluzione stessa debba essere ricalcolata ogni volta ex novo.

Tipiche applicazioni in cui queste tecniche sono risultate particolarmente utili sono il mantenimento efficiente (dal punto di vista ammortizzato) di un minimo albero di connessione e dei cammini minimi in un grafo, in presenza di frequenti inserimenti ed eliminazioni di archi.

Un altro contesto, dove il fatto che i dati non siano noti a priori gioca un importante ruolo, è quello delle cosiddette applicazioni on-line. In tale caso, i dati di ingresso vengono rivelati via via e un algoritmo deve far fronte ai nuovi dati adattando la propria strategia risolutiva. Una situazione di questa natura si presenta, per esempio, in un sistema di radio-taxi (un caso particolare del problema di instradamento on-line di veicoli), in cui un taxi collettivo deve servire richieste di utenti che pervengono telefonicamente e deve, di conseguenza, riconfigurare il proprio percorso per ottimizzare il tempo di servizio globale. Per valutare la qualità della soluzione fornita da un algoritmo per applicazioni on-line, si determina il rapporto tra il valore di tale soluzione e quello della soluzione ottima off-line, cioè la soluzione che un algoritmo ottimo potrebbe ottenere, conoscendo a priori tutte le richieste di servizio che perverranno.

Un classico problema on-line è quello della paginazione. In un sistema di elaborazione la cui memoria è organizzata a pagine accade che durante l'esecuzione di un programma si debba accedere a dati posti nelle pagine memorizzate su memoria secondaria e quindi si debba decidere quale pagina in memoria principale deve essere copiata su memoria secondaria per essere rimpiazzata da quella richiesta. È noto che una scelta ottima (off-line) consiste nel rimpiazzare la pagina che verrà utilizzata più avanti nel tempo. Dovendo risolvere il problema in modo on-line si è costretti a effettuare scelte che possono essere non ottimali. Sia k il numero di pagine disponibili in memoria principale. Utilizzando le politiche FIFO (First in, first out) o LRU (Least recently used) si ottiene un rapporto di competitività pari a k, un risultato non migliorabile con algoritmi deterministici. Se, invece, si utilizza un algoritmo randomizzato, che sceglie a caso la pagina da rimpiazzare tra quelle non ancora utilizzate, si può ottenere un rapporto di competitività pari a 2H_k dove H_k è il k-esimo numero armonico (H_k=1+1/2+1/3+…+1/k).

Algoritmi per ingenti masse di dati

Negli ultimi anni, abbiamo assistito a un costante aumento della dimensione dei dati che devono essere trattati nelle applicazioni informatiche (gestione di dati multimediali, meteorologici, astronomici e così via). Pergestire flussi di dati così massicci, i moderni elaboratori prevedono strutture di memoria complesse che includono i registri dell'unità centrale, uno o più livelli di memoria veloce (cache), una memoria principale e una memoria secondaria; tali architetture richiedono, però, tecniche algoritmiche opportune per evitare che gli accessi alla memoria secondaria divengano causa di inefficienze.

Una prima soluzione consiste nel progettare algoritmi che sono consapevoli della struttura della memoria e la sfruttano in modo ottimale. In un modello di questo tipo (il parallel disk model), definito da Jeff S. Vitter e Elizabeth A. M. Shriver nel 1994, le prestazioni degli algoritmi sono valutate in funzione di vari parametri: la quantità di dati da elaborare, la dimensione dei blocchi che vengono gestiti in una operazione di trasferimento tra memoria centrale e memoria secondaria, la capacità della memoria centrale, il numero di dischi acceduti in parallelo.

Un modello alternativo di gestione di dati su più livelli di memoria, è quello chiamato cache-oblivious. In tale modello, gli algoritmi vengono progettati in modo tale che il loro comportamento sia ottimale indipendentemente dalle modalità con cui il sistema operativo dell'eleboratore gestisce il trasferimento di blocchi tra vari livelli di memoria. Gli algoritmi cache-oblivious hanno il vantaggio di liberare l'utente dalla necessità di conoscere i meccanismi di gestione della memoria e, pur non potendo, in linea di principio, avere sempre la stessa efficienza degli algoritmi progettati per il parallel disk model, in molti casi possono raggiungere asintoticamente le stesse prestazioni.

Un terzo approccio per la gestione di dati su memoria secondaria è quello denominato a flusso di dati (data-stream). In questo paradigma, cui si riferiscono diversi modelli studiati recentemente, si ipotizza che la quantità di dati che fluiscono sia così elevata da non consentire la loro memorizazzione ma solo una veloce scansione 'al volo', eventualmente in più passate. Tale situazione si presenta, per esempio, nell'analisi di dati derivanti da esperimenti di fisica delle particelle o di dati relativi al traffico telefonico o su Internet (il numero di e-mail scambiate negli Stati Uniti giornalmente è dell'ordine dei miliardi).

Problematiche algoritmiche legate a Internet e al Web

La diffusione di Internet e delle applicazioni basate su tale rete, a partire dall'inizio degli anni Novanta, ha rappresentato una rivoluzione epocale nel mondo dell'informatica. Le caratteristiche fondamentali di questa rivoluzione sono da un lato l'onnipresenza della rete in tutti i contesti (dalla comunicazione personale alla gestione di informazioni fino al supporto delle applicazioni aziendali e dei servizi al cittadino) e, dall'altro, il volume straordinario dei dati gestiti attraverso la rete e il Web, miliardi di volte maggiore della quantità di dati gestiti in un normale sistema informativo. Queste due caratteristiche rendono l'efficienza del software che gestisce la rete e le sue applicazioni assolutamente cruciale e richiedono all'informatica teorica la risoluzione di problemi mai prima affrontati. Per semplicità ci limiteremo a considerare tre questioni sulle quali si stanno concentrando impegnative attività di ricerca.

Ricerca e gestione di informazioni nel Web. - La ricerca di informazioni nel World wide web costituisce la maggiore attività di elaborazione svolta nell'ambito di Internet. I principali motori di ricerca indicizzano oggi circa 10 miliardi di pagine e ogni giorno devono visitare e analizzare milioni di nuove pagine, che si vanno ad aggiungere a quelle già visitate; essi richiedono quindi l'utilizzo di tecniche algoritmiche molto sofisticate. Un'ampia serie di problemi di natura algoritmica sono legati all'indicizzazione e alla ricerca delle informazioni nel Web. Tra di essi, una problematica di importanza cruciale è quella del ranking delle pagine restituite dal in risposta alle interrogazioni. Le soluzioni più valide di tale problema sono basate sull'utilizzazione della struttura dei link tra pagine del Web. Una rassegna delle sfide poste dai moderni motori di ricerca all'innovazione nel campo degli algoritmi è stata fornita da Monika R. Henzinger nel 2004.

Analisi della struttura del Web. - La struttura dei collegamenti (link) tra le pagine del Web (o, come si usa dire, la struttura del grafo del Web) è stata oggetto di molti studi negli anni recenti, per esempio a opera di Albert-László Barábasi.

Nonostante il Web si sviluppi in base a una serie di iniziative autonome e scorrelate, la struttura del grafo che ne consegue presenta una forte caratterizzazione: il numero di link in ingresso e in uscita dalle pagine segue leggi di potenza. Per esempio, si è osservato che il numero di pagine Web che hanno esattamente k link in entrata è proporzionale a k^−2,1, il grafo ha una natura frattale e autosimilare e i collegamenti tra le pagine presentano il 'fenomeno del mondo piccolo'. Sulla base di diversi esperimenti, è stato infatti mostrato che, con elevata probabilità, due pagine del Web scelte a caso sono raggiungibili l'una dall'altra attraversando 19 link. Tali esperimenti si sono ispirati agli studi del sociologo Stanley Milgram che nel 1967 ha mostrato che due cittadini qualsiasi degli Stati Uniti sono collegati da una catena di al più cinque conoscenti. Lo studio di queste e altre proprietà del grafo del Web è fondamentale per lo sviluppo di motori di ricerca sempre più efficienti.

Teoria dei giochi e gestione di reti. In reti costituite da un numero molto elevato di elaboratori, come Internet o le cosiddette reti peer-to-peer, non esiste un controllo centralizzato che garantisca costantemente un uso efficiente della risorse della rete. La realtà che si presenta nell'uso delle reti ha qualche somiglianza con ciò che accade in un sistema economico e può essere analizzata con modelli simili, in particolare con modelli basati sulla teoria dei giochi. Gli utenti di una rete, così come gli attori di un sistema economico, perseguono solo il proprio profitto e procedono nel migliorare la propria posizione fino a che raggiungono una situazione di equilibrio. I punti di equilibrio cui possono pervenire gli attori di un sistema economico (che tipicamente hanno una qualità inferiore a quella della soluzione ottima che si otterrebbe con una gestione centralizzata delle risorse), sono stati oggetto di studio in economia con un approccio basato sulla teoria dei giochi e possono essere rappresentati mediante il concetto di equilibrio di Nash (un ottimo locale da cui ognuno dei giocatori non ha interesse a distaccarsi poiché ogni mossa peggiorerebbe comunque il suo profitto). Anche la gestione di risorse in una rete può essere modellata come un gioco, caratterizzando le soluzioni cui si perviene in modo distribuito come equilibri di Nash. La perdita di efficienza che deriva dall'aver adottato una strategia di risoluzione distribuita anziché centralizzata per un dato problema, può essere misurata esaminando il rapporto tra il valore di una soluzione ottima e il valore di un equilibrio di Nash. Christos Papadimitriou ed Elias Koutsoupias hanno denominato nel 1999 tale rapporto, con un'espressione suggestiva: costo dell'anarchia.

Teoria dei programmi e dei processi di calcolo

La soluzione di problemi mediante elaboratore richiede come prima condizione che i programmi effettuino correttamente le operazioni per le quali sono stati realizzati. Purtroppo, nonostante i grandi progressi compiuti con la diffusione di metodologie di progetto e sviluppo di programmi, il problema della correttezza funzionale del software rimane un problema aperto nel senso che nella maggioranza dei casi la rilevazione di errori avviene ancora con metodi di verifica empirici e, a volte, gli errori vengono individuati solo a seguito di malfunzionamenti. Chiaramente, il problema di garantire il comportamento corretto dei programmi si presenta ancora più complesso nel caso di applicazioni distribuite su rete, che sono ormai la grande maggioranza delle applicazioni.

Nell'area che abbiamo denominato teoria della programmazione e dei processi di calcolo esistono vari approcci allo studio del comportamento dei programmi e delle loro possibili interazioni. Tali approcci sono basati sulla definizione formale del comportamento dei programmi mediante modelli astratti e hanno diverse finalità: dotare i linguaggi di programmazione di vario tipo (sequenziali, paralleli, concorrenti) di una semantica formale definita in modo rigoroso, consentire verifiche di correttezza dei programmi rispetto alla specifica fornita dall'utente, definire e studiare nuovi concetti e paradigmi di programmazione che agevolino la produzione di software corretto e affidabile.

Per questi ultimi aspetti, gli studi nel campo dell'informatica teorica hanno un ruolo significativo nei confronti delle aree più applicative dei linguaggi, delle metodologie e degli ambienti di programmazione che formano l'ingegneria del software.

Semantica formale

Per definire formalmente la semantica di un programma sono stati sviluppati nel tempo diversi approcci che hanno dato luogo a vere e proprie scuole di pensiero alternative. Anche se negli anni più recenti si è sviluppata, nell'ambito dell'ingegneria del software, la tendenza a utilizzare i diversi approcci in modo integrato, con un punto di vista sincretico, ci sembra opportuno identificare e descrivere brevemente almeno i tre principali filoni di questa importante area dell'informatica teorica.

Semantica operazionale. - Un primo approccio allo studio del comportamento dei programmi consiste nella definizione di un modello di calcolo astratto e nella rappresentazione dei passi di calcolo dei programmi in tale modello prescindendo dagli aspetti di comportamento che dipendono dalle caratteristiche tecnologiche della macchina utilizzata e concentrandosi, in prima istanza, sugli aspetti legati al linguaggio di programmazione. I dettagli tecnologici (per es., la lunghezza massima delle costanti numeriche prevista dal calcolatore) potranno, poi, essere reintrodotti come parametri della semantica formale. Tra gli antesignani dell'approccio operazionale alla semantica dei linguaggi di programmazione possiamo citare John Mc Carthy e Peter Landin, per i loro lavori sulla semantica operazionale del LISP e dell'Algol. In un approccio molto utilizzato, di tipo essenzialmente sintattico, il modello di calcolo astratto è costituito da tutte le espressioni (termini) costruibili con i simboli di funzione e i simboli di variabile disponibili nel linguaggio. Formalmente, ogni simbolo di variabile x₁,…,x_n è un termine e, per ogni simbolo di funzione f_i, con m_i argomenti, se t₁,…,t_mi sono termini, anche l'espressione f_i(t₁,…,t_mi) è un termine. In particolare, i simboli di funzione con zero argomenti sono chiamati costanti. Per esempio, se f è una funzione unaria, x è una variabile e 0 una costante, avremo che l'insieme dei termini è: {0,x,f(0),f(x),f(f(0)),f(f(x)),…}. I passi di calcolo corrispondenti alle varie istruzioni del linguaggio sono descritti mediante regole di sostituzione (riscrittura) di termini con altri termini. Per esempio, le seguenti due regole di riscrittura definiscono il comportamento del costrutto if-then-else:

if true then T₁ else T₂→T₁

if false then T₁ else T₂→T₂.

La loro applicazione determina la sostituzione del termine al lato sinistro della freccia con quello al lato destro, indipendentemente dalla natura dei termini T₁ e T₂. L'esecuzione delle istruzioni di un programma (computazione), corrisponde a una serie di passi di riscrittura che si conclude quando si giunge a un termine che non ammette più sostituzioni (interpretabile come un valore costante nel dominio dei dati: un intero, un valore booleano, ecc.), o può non concludersi, se si entra in una serie ciclica di sostituzioni.

Una classica applicazione di questo approccio è volta allo studio dei meccanismi di chiamata di funzione e di esecuzione della nei linguaggi di programmazione. A seconda delle regole adottate per gestire la valutazione di funzioni (per es., regole di sostituzione che partono dall'interno di un termine o regole di sostituzione che partono dall'esterno) si possono avere, infatti, semantiche diverse, in cui, cioè, per alcuni valori dell'argomento, una funzione calcolata da un programma può essere definita o non definita.

Semantica denotazionale. - Un inconveniente delle semantiche di tipo operazionale è il fatto che esse dipendono da un modello di macchina astratta definito a priori. Un approccio che si prefigge di caratterizzare il comportamento di un programma definendo, invece, direttamente, in termini matematici, la funzione che esso calcola nel dominio dei dati, a partire dalla struttura sintattica del programma stesso, è l'approccio chiamato semantica denotazionale, introdotto da Dana Scott e Cristopher Strachey, nel 1971 (inizialmente chiamato semantica matematica).

Nella semantica denotazionale di un programma, ogni struttura sintattica composta viene associata a un oggetto matematico, chiamato denotazione (per es., la funzione che quella particolare struttura definisce), che deriva esclusivamente dalle denotazioni delle sottostrutture che la compongono (proprietà di composizionalità). A strutture elementari corrispondono oggetti matematici primitivi (funzioni base). La funzione definita da un programma viene così individuata in base alla struttura del programma, con un meccanismo di induzione strutturale. Una delle caratteristiche dell'approccio denotazionale è l'uso del concetto di punto fisso. Come domini dei dati si assumono, anzichè insiemi, insiemi parzialmente ordinati completi e, potendosi interpretare i programmi di un linguaggio di programmazione come funzionali continui su tali insiemi, è possibile garantire l'applicabilità del teorema del punto fisso di Knaster-Tarski e individuare la funzione calcolata da un programma ricorsivo come il punto fisso del funzionale associato a tale programma.

L'approccio denotazionale ha il pregio di una notevole eleganza formale ed è uno strumento didattico fondamentale nello studio della semantica dei linguaggi di programmazione. Tra coloro che hanno maggiormente contribuito allo sviluppo di questo approccio, nelle sue varie forme, oltre allo stesso Dana Scott e a Michael J.C. Gordon, citiamo Jaco de Bakker, Dines Björner, Gordon D. Plotkin, John C. Reynolds. Gli sviluppi attuali riguardano la possibilità di trattare con un approccio denotazionale gli aspetti di concorrenza, nonché gli aspetti tipici dei più recenti linguaggi a oggetti, come la modularità.

Semantica algebrica. - Un approccio alla semantica che ha avuto un notevole ruolo nella evoluzione dei linguaggi e delle metodologie di programmazione è quello denominato semantica algebrica. Esso è sostanzialmente basato sul concetto di tipo astratto di dato. I dati, anziché essere insiemi (come nei linguaggi di programmazione classici) o insiemi parzialmente ordinati (come nella semantica denotazionale) sono strutture algebriche, cioè insiemi di oggetti dotati di operazioni: in generale, Σ-algebre. Il fatto di considerare i dati, non come semplici insiemi di valori, ma come strutture algebriche, ha rappresentato un'importante innovazione nella teoria e nella pratica della programmazione.

L'idea, ispirata dal concetto di classe, introdotto nel 1970 da Olen-Johan Dahl e Kristen Nygaard nel linguaggio di programmazione SIMULA (e ripreso nell'ambito di linguaggi a oggetti come il ++ e il ), è stata sviluppata e formalizzata, a metà degli anni Settanta, per opera di John V. Guttag, Barbara Liskov, Stephen N. Zilles e del gruppo di ricercatori costituito da Joseph A. Goguen, James W. Thatcher, Eric G. Wagner e Jesse B. Wright (denominato gruppo ADJ). Essa ha dato luogo, da un lato, allo sviluppo dell'approccio algebrico alla semantica, dall'altro, alle metodologie di specifica algebrica del software. Una specifica algebrica consiste in un insieme di tipi astratti di dati (la cui gestione può avvenire solo tramite le operazioni previste nella specifica, in modo che tutti gli aspetti realizzativi siano schermati all'esterno) e in un insieme di equazioni che ne caratterizzano le proprietà. La semantica formale di una specifica è definita mediante il concetto di classe di omomorfismi tra le Σ-algebre che soddisfano la specifica. La semantica algebrica e i metodi di specifica algebrica del software hanno avuto, negli ultimi anni, un notevole sviluppo che ha riguardato vari aspetti (tuttora oggetto di studio), con lo scopo di rendere tale approccio più potente (per es., prevedendo che la specifica utilizzi formule più generali delle equazioni), in grado di esprimere aspetti di programmazione particolari (come la concorrenza), adatto alla specifica formale di sistemi informatici di grandi dimensioni (introducendo meccanismi di specifica gerarchica) e in grado di esprimere la riusabilità del software (mediante il concetto di specifica parametrica). Dal punto di vista dell'evoluzione dei linguaggi di programmazione, oltre al già citato ruolo che i tipi astratti di dati hanno avuto sullo sviluppo dei linguaggi orientati a oggetti, va segnalato l'impatto dell'approccio algebrico sui linguaggi di specifica. Vari linguaggi di specifica sono stati definiti utilizzando concetti e strutture sviluppate nell'ambito degli studi sulla specifica algebrica del software (CLEAR, OBJ, ACT ONE, CASL, RSL, ecc.) e in alcuni linguaggi di programmazione ‒ come ML ‒ sono stati aggiunti meccanismi di tipo algebrico per la specifica di tipi di dati e programmi.

Semantica di processi concorrenti

In un reale sistema informatico, l'elaborazione delle informazioni non dà necessariamente luogo a una computazione sequenziale come nei modelli teorici (macchina di Turing, RAM e così via); al contrario, generalmente, in un sistema di elaborazione sono sempre attive più computazioni (processi). Ciò avviene, in particolare, nei sistemi distribuiti, basati cioè su una pluralità di unità di elaborazione (processori) connesse in rete, che cooperano, comunicando mediante messaggi o mediante unità di memoria condivise, nella risoluzione di un particolare problema o nei sistemi transazionali in cui molti utenti collegati in rete, accedono a una base informativa interrogandola ed eseguendo operazioni che ne modificano il contenuto. Anche nei sistemi monoprocessore e monoutente, la semplice presenza del sistema operativo che interagisce con l'utente per gestire le risorse del calcolatore dà luogo all'attività simultanea di più processi. Sistemi nei quali siano contemporaneamente presenti più processi vengono detti sistemi concorrenti. Si noti che in un sistema concorrente i processi possono interagire tra loro in modo cooperativo, per il raggiungimento di un obiettivo comune, ma possono anche interagire negativamente, contendendosi l'uso delle risorse del sistema e determinando, in caso di errato coordinamento, un'evoluzione scorretta delle singole attività. Ciò si verifica, per esempio, nei seguenti classici casi (già analizzati dall'olandese Edsger W. Dijkstra negli anni Sessanta).

Aggiornamento del valore di una variabile. - Quando più processi accedono a una variabile condivisa (per es., il saldo di un conto corrente bancario) per leggerla ed eventualmente aggiornarla, al fine di garantire la correttezza del sistema è necessario che ogni processo mantenga il controllo della variabile fino a che non abbia ultimato l'aggiornamento; è necessario, cioè, che si realizzi la cosiddetta mutua esclusione.

Condivisione di risorse. - Quando più processi necessitano di varie risorse (per es., diverse unità periferiche) per completare il loro compito, si possono verificare situazioni di stallo (nessun processo è in condizione di evolvere, perché essi sono reciprocamente in attesa del rilascio di risorse da parte degli altri processi) o di privazione (alcuni processi evolvono ma altri sono impossibilitati a procedere), e si devono, quindi, instaurare opportune politiche di gestione delle risorse stesse che evitino tali inconvenienti. Per dare una facile intuizione dei termini del problema, Dijkstra utilizzò la metafora dei filosofi a pranzo: cinque filosofi siedono a tavola davanti a un piatto di spaghetti; alla destra di ognuno è disponibile una forchetta. I filosofi alternativamente pensano e mangiano ma per mangiare hanno bisogno di due forchette (la metafora è legata alla tradizionale difficoltà degli olandesi nel mangiare gli spaghetti) e devono quindi utilizzare sia quella alla loro destra sia quella alla loro sinistra. Chiaramente ciò dà luogo ad una contesa di risorse che deve essere opportunamente regolamentata per evitare fenomeni di stallo e di privazione.

Cooperazione tra processi mediante scambio di messaggi. - In questo caso, siamo in presenza di più processi scrittori e più processi lettori, che comunicano lasciando messaggi in una memoria tampone; nel caso che la memoria sia limitata, la correttezza della cooperazione è compromessa se non si fa uso di opportune politiche.

Molti importanti problemi di concorrenza nascono nella gestione di basi di dati e nell'ambito di sistemi distribuiti e reti, per esempio il problema della sincronizzazione tra processi, il problema del raggiungimento del consenso circa il valore di una variabile, anche in presenza di alcuni processori inaffidabili (il cosiddetto problema dei generali bizantini) o il problema dell'elezione di un processore che funga da leader tra più processori omogenei. In tutti questi casi, il problema di garantire il comportamento corretto degli algoritmi è particolarmente complesso. Rispetto al caso dei sistemi sequenziali, il problema della correttezza del comportamento di sistemi concorrenti è caratterizzato inoltre da due fattori: i sistemi concorrenti sono dipendenti dal tempo (il comportamento può essere corretto o scorretto a seconda di come avviene fisicamente l'evoluzione dei processi) e reattivi (in genere, in un sistema concorrente, per es., un sistema di controllo di processi, non abbiamo un input e un output, ma il sistema può non terminare mai e il suo comportamento è definito in base a come esso interagisce con l'ambiente). Per questi motivi, per l'analisi e lo studio dei sistemi concorrenti sono state sviluppate semantiche (operazionali e denotazionali) diverse e più complesse di quelle utilizzate per i sistemi sequenziali.

Uno dei primi modelli utilizzati per descrivere sistemi concorrenti da un punto di vista operazionale sono le reti di Petri (introdotte da Carl Adam Petri nel 1962) che, in versioni sempre più sofisticate e ricche di espressività, hanno continuato, con varia fortuna, a essere utilizzate fino a oggi. Nella sua versione più elementare, una è costituita da un insieme finito di posti (che rappresentano condizioni per l'attivazione di processi) e di transizioni (che rappresentano processi) e da archi che li collegano (che rappresentano relazioni di precedenza e/o flussi di risorse). Lo stato di una rete di Petri è caratterizzato dalla presenza di nessuna, una o più marche (che rappresentano risorse) in corrispondenza dei posti. Poiché un processo consuma risorse quando è attivato e le rilascia al termine, lo scatto di una transizione determina un flusso di risorse e un cambiamento di stato della rete.

I modelli formali per descrivere e analizzare sistemi concorrenti si differenziano in base a varie caratteristiche. Innanzitutto, analogamente ai modelli di sistemi sequenziali, essi possono essere di tipo operazionale ‒ cioè orientati a descrivere il sistema in base al suo comportamento interno ‒ oppure di tipo denotazionale ‒ cioè orientati a descrivere il sistema in base al comportamento osservabile dall'esterno. Inoltre, essi si caratterizzano a seconda del tipo di concorrenza che esprimono: modelli a interposizione (interleaving), che rappresentano una computazione concorrente come una scelta non-deterministica in un insieme di computazioni sequenziali in cui gli eventi si susseguono in tutte le sequenze ammissibili, e modelli di autentica concorrenza, in cui gli eventi sono del tutto asincroni e si svolgono, secondo regole locali di causa ed effetto, in punti diversi del sistema (come accade per le reti di Petri).

Uno dei primi approcci utilizzati per descrivere sistemi concorrenti e verificarne la correttezza del comportamento è stato proposto da Charles A.R. Hoare alla fine degli anni Settanta. Nella sua teoria dei processi sequenziali comunicanti (teoria CSP), che ha ispirato lo sviluppo dei primi linguaggi di programmazione concorrenti (per es., i linguaggi Ada e Occam), Hoare formalizza tre concetti: il parallelismo dei processi, la comunicazione tra processi con appuntamento (rendez-vous), il non-determinismo, cui possono essere estesi i metodi di prova sviluppati dallo stesso Hoare per i linguaggi sequenziali.

Più recentemente, i metodi di specifica e verifica di sistemi concorrenti si sono concentrati nelle due direzioni (in un certo senso complementari) delle logiche temporali (introdotte da Amir Pnueli sempre alla fine degli anni Settanta) e delle algebre di processi (introdotte da Jan Bergstra e Jan Willem Klop all'inizio degli anni Ottanta).

Le logiche temporali sono logiche modali (di tipo proposizionale o predicativo), i cui operatori fondamentali esprimono la validità di un'asserzione p da un certo istante in poi (Gp) o in qualche istante futuro (Fp) o nel prossimo istante (Xp), ovvero la validità di un'asserzione p fino a quando una nuova asserzione q non diventa valida (pUq). La nozione del tempo può ipotizzare un'unica dimensione temporale su cui tutti gli eventi vengono proiettati (tempo lineare) o situazioni in cui, in alcuni istanti, il tempo si dirama, dando luogo a diverse scale temporali non più confrontabili (tempo ramificato). In quest'ultimo caso, la validità di un'asserzione temporale (per es., Gp) potrà verificarsi in tutte le scale temporali future (AGp) o solo in qualche ramo (EGp).

L'utilizzazione di logiche temporali e di sistemi a stati finiti per la descrizione del comportamento di sistemi reattivi ha condotto allo sviluppo di un metodo di verifica di correttezza dei sistemi concorrenti basato sull'analisi di modelli a stati finiti (model checking). Questo metodo, nonostante la complessità derivante dalla crescita del numero di stati ‒ che può essere esponenziale in funzione del numero di processi presenti nel sistema ‒, si sta rivelando utile nella realizzazione di strumenti automatici di verifica e nel loro impiego per analizzare la correttezza di sistemi complessi (protocolli di comunicazione, componenti hardware, ecc.).

Per quanto riguarda le algebre dei processi, con tale locuzione si fa oggi riferimento a una varietà di modelli nei quali il comportamento di un sistema può essere specificato a diverso livello di astrazione e la correttezza di realizzazione viene espressa come equivalenza operazionale (anche se originariamente il termine fu introdotto da Bergstra e Klop per indicare uno specifico approccio alla semantica della concorrenza: l'algebra dei processi comunicanti). In questa più generale accezione, tra le algebre dei processi possiamo includere sia i processi sequenziali comunicanti di Hoare sia il calcolo di sistemi comunicanti (CCS) di Robin Milner (1980), evolutosi poi in una serie di successivi sistemi formali chiamati π-calcolo (ispirato al λ-calcolo) e calcolo delle azioni.

A titolo di esempio, mostriamo alcune delle espressioni che possono essere costruite utilizzando gli operatori del linguaggio:

(a) α.E (prefisso): rappresenta il processo che esegue l'azione α e poi si comporta come il processo descritto da E;

(b) ∑_iE_i (sommatoria): rappresenta un processo che può comportarsi non deterministicamente come uno qualsiasi dei processi descritti dalle espressioni E_i;

(c) E₀∣E₁ (parallelismo): rappresenta la composizione in parallelo dei due processi descritti da E₀ ed E₁.

Sono inoltre disponibili operatori di punto fisso (ricursione), operatori di ridenominazione di azioni, invio di valori su una porta di uscita e ricezione di valori su una porta di entrata e così via. La semantica del linguaggio può essere fornita in modo operazionale mediante sistemi di transizioni etichettate (in cui, cioè, le transizioni sono annotate con il nome delle azioni eseguite dai processi) o con un metodo equazionale (chiamato bisimulazione) che, sostanzialmente, permette di stabilire l'equivalenza di sistemi quando essi possono eseguire le stesse sequenze di azioni.

Gli sviluppi delle tecnologie informatiche lasciano prevedere che i problemi della specifica e della verifica di sistemi concorrenti saranno, in futuro, sempre più rilevanti. Infatti, le questioni relative ai sistemi con vincoli temporali stringenti (real time), ai sistemi resistenti ai malfunzionamenti (fault tolerant), ai sistemi ibridi (in cui sussistono componenti digitali e componenti analogiche, come nei sistemi di automazione industriale), richiedono il raffinamento delle metodologie fin qui utilizzate o lo sviluppo di nuovi sistemi formali capaci di rappresentare adeguatamente le realtà di interesse e di consentire efficienti metodi di dimostrazione di correttezza.

Logiche della programmazione e verifica di correttezza

L'approccio logico all'analisi dei programmi è basato sul principio che un programma sequenziale contenga tutte le informazioni necessarie per determinare il suo comportamento e, pertanto, sia possibile definire un sistema deduttivo che consenta di derivare in modo formale, partendo dalla struttura del programma, asserzioni riguardanti le sue proprietà (per es., la terminazione) nonché la sua correttezza.

L'esigenza di dimostrare formalmente la correttezza di un programma non era sfuggita a due precursori dell'informatica teorica come Alan M. Turing e John von Neumann; tuttavia, solo alla fine degli anni Sessanta, sono state proposte adeguate metodologie per opera di Robert W. Floyd, Peter Naur e, in particolare, Hoare. Nel sistema formale proposto da Hoare (chiamato logica di Hoare o, a volte, semantica assiomatica) viene data particolare enfasi all'analisi della correttezza di un programma rispetto alla specifica delle proprietà che lo stato deve verificare prima e dopo l'esecuzione del programma. Essa può essere quindi utilizzata sia come sistema per la verifica a posteriori della correttezza di un programma, sia come metodo di specifica e sviluppo di un programma corretto.

Una classica asserzione di correttezza parziale della logica di Hoare si presenta nel seguente modo:

[1] {φ} p {ψ}

(se prima dell'esecuzione del programma p vale la proprietà φ, dopo l'esecuzione, se essa termina, vale la proprietà ψ). I predicati φ e ψ si chiamano precondizione e postcondizione. Gli assiomi della teoria definiscono il comportamento delle istruzioni elementari di un programma.

Per esempio, l'assioma:

[2] {φ[x/e]}x ≡ e{φ}

afferma che, se prima dell'esecuzione dell'assegnazione vale la proprietà φ (in cui ogni occorrenza di x è sostituita dal termine e), dopo l'assegnazione vale la proprietà φ. Nel corso di una dimostrazione di correttezza si propagano le precondizioni e le postcondizioni lungo il programma, sfruttando le regole di inferenza che specificano il comportamento dei costrutti del linguaggio. Per esempio, la regola:

[3] {φ} p {ψ}, {ψ} q {ξ} ⇒ {φ} p; q {ξ}

specifica che se per le istruzioni p e q valgono le condizioni φ, ψ e, rispettivamente, ψ, ξ per la composizione sequenziale delle due istruzioni valgono le condizioni φ e ξ. In conclusione, se la dimostrazione ha successo, si verificherà che le condizioni sono soddisfatte dall'intero programma.

Contemporaneamente all'approccio assiomatico alla semantica dei programmi, nell'ambito dell'informatica teorica si sono sviluppati altri approcci formali alla logica della programmmazione, per lo più estensioni modali di logiche del prim'ordine. L'uso delle logiche modali è motivato dal fatto che un'asserzione valida in un certo momento dell'esecuzione di un programma (per es., x è pari) può diventare falsa in un momento successivo, per effetto di un'istruzione di assegnazione (x≡x+1) che ha mutato il valore di una variabile. Iniziati da Ernst-Jochen Thiele ed Erwin Engeler alla fine degli anni Sessanta, gli studi in questo campo hanno portato alla definizione di vari sistemi logici: la logica dinamica (Vaughan R. Pratt, 1976), la logica algoritmica (Andrzej Salwicki, 1977), la logica monadica delle programmazione (Robert L. Constable, 1978), approcci che oggi vengono genericamente inclusi sotto il nome di logica dinamica.

In questi sistemi il linguaggio del prim'ordine viene arricchito introducendo istruzioni e costrutti di un linguaggio di programmazione (per es., composizione sequenziale, iterazione, alternativa in base al valore di verità di un predicato) e uno o più operatori modali che esprimono relazioni tra asserzioni sullo stato del sistema ed esecuzione di programmi. Un tipico esempio di formula modale di questa natura è il seguente:

[4] [p] φ

che appartiene alla logica dinamica ed esprime il fatto che, se l'esecuzione del programma p termina, ci si trova in uno stato che soddisfa la proprietà φ. Gli assiomi e le regole di inferenza delle teorie logiche della programmazione contengono, oltre agli assiomi e alle regole di inferenza delle logiche del prim'ordine, assiomi e regole che stabiliscono relazioni tra programmi e proprietà dello stato. L'assioma che descrive le proprietà della composizione sequenziale è, per esempio, il seguente (anch'esso appartenente alla logica dinamica):

[5] [p;q] φ ≡ [p] [q] φ.

Dopo i risultati teorici sviluppati negli anni Settanta e Ottanta, gli anni Novanta hanno visto le prime concrete applicazioni dei metodi basati sulla logica formale a casi reali di dimensioni medio-grandi (come le verifiche di correttezza di microprogrammi), grazie alla realizzazione di strumenti in grado di realizzare verifiche di correttezza in modo automatico (o semiautomatico).

Nuove forme di calcolo

I grandi filoni dell'informatica teorica, che abbiamo illustrato nelle due precedenti sezioni, si sono via via sviluppati avendo come principali punti di riferimento concettuali, da un lato, i primi modelli astratti sviluppati dai logici negli anni Trenta e Quaranta (il modello proposto da Turing, fondato sul concetto di transizione di stato, e quello funzionale sviluppato da Church e Kleene) e, dall'altro, i modelli concretamente realizzati nell'architettura dei calcolatori elettronici, primo fra tutti il modello di von Neumann e, successivamente, i vari modelli di architetture distribuite e parallele. Negli ultimi due decenni del secolo scorso, tuttavia, hanno cominciato ad affermarsi, nell'ambito dell'informatica teorica, paradigmi di calcolo ispirati a meccanismi elaborativi presenti in vario modo in natura e per tale motivo definiti, a volte, modelli di calcolo naturali o di soft computing. Esempi di tali paradigmi sono il calcolo neuronale, il calcolo quantistico e il calcolo molecolare. L'interesse per tali modelli ‒ ai quali dedicheremo un breve cenno ‒ è dovuto non solo alla possibilità che essi offrono di esaminare e affrontare la soluzione di problemi con nuovi approcci computazionali, ma anche al fatto che, in alcuni casi, sistemi di elaborazione basati su tali paradigmi sono fisicamente realizzabili o si ritiene che possano diventare realizzabili in futuro.

Reti neuronali artificiali

La possibilità di realizzare sistemi di elaborazione capaci di emulare il comportamento del sistema nervoso animale, e in particolare del cervello, ha attratto notevoli energie fin dai primordi dell'informatica. I primi studi di Warren S. McCulloch e Walter Pitts, e dello stesso John von Neumann, volti alla realizzazione di neuroni artificiali, risalgono infatti al 1943. In un neurone artificiale le quattro componenti fondamentali della struttura neuronale animale (il corpo della cellula, i dendriti, l'assone e le sinapsi) assumono rispettivamente i ruoli (astratti) di: elemento di elaborazione primitivo, canali di ingresso, canale di uscita, interconnessioni. Secondo questa schematizzazione, quindi, se in ingresso sono presenti i valori (segnali) x₁,…,x_n un neurone artificiale calcola una semplice funzione f(x₁,…,x_n). Nelle versioni più elementari la funzione f è, per esempio, una funzione binaria (funzione soglia) che decide se il valore y=∑_iw_ix_i (dove i coefficienti w_i sono pesi che vengono attribuiti ai segnali in ingresso x_i) supera o meno una certa soglia τ, o una sigmoide, f(y)=1/(1+e^−cy), che realizza una soglia modulata dal parametro c. Una rete neuronale artificiale è costituita da un'interconnessione di neuroni artificiali. La caratteristica fondamentale delle reti neuronali come modelli di calcolo è che, in esse, l'informazione non è localizzata in forma simbolica, come in un normale elaboratore, ma è distribuita nei segnali presenti alle interconnessioni fra i diversi neuroni, cioè, intuitivamente, nelle sinapsi. I vari tipi di reti differiscono essenzialmente per il tipo di funzioni realizzate dai neuroni, per la struttura di interconnessione e per le modalità di temporizzazione dei segnali. In particolare, possiamo identificare due tipi fondamentali di reti: quelle di tipo direzionale (feed-forward), chiamate anche sistemi di classificazione, e quelle di tipo bidirezionale (feed-back). Il primo tipo deriva sostanzialmente dal modello, chiamato , introdotto nel 1958 da Frank Rosenblatt e successivamente studiato da Marvin L. Minsky e Seymour Papert alla fine degli anni Sessanta, e ha avuto un particolare impulso dall'opera di David E. Rumelhart, che ha introdotto il metodo di apprendimento chiamato retropropagazione. Il secondo tipo è prevalentemente legato all'opera di Hopfield (1982).

Calcolo quantistico

Nonostante sia alla base dei processi che avvengono nei componenti a stato solido che costituiscono i calcolatori, la meccanica quantistica non ha mai avuto un ruolo nei processi di calcolo che essi eseguono. Negli anni Novanta, sulla base di intuizioni di Paul A. Benioff e Richard P. Feynman nel decennio precedente, si è cominciato a studiare il concetto di calcolo quantistico, il suo potere computazionale, le possibilità di una realizzazone fisica. Alla base del modello di calcolo quantistico è il qubit, la versione quantistica del bit. Lo stato di un qubit è espresso dalla funzione ∣ψ>=α∣0>+β∣1> in cui le ampiezze α e β sono due arbitrari numeri complessi che verificano la relazione ∣α∣²+∣β∣²=1. Per effetto del principio di indeterminazione di Heisenberg un tentativo di misurare il valore del qubit porta lo stato a collassare sul valore 0 oppure sul valore 1. Un'immediata conseguenza dell'approccio quantistico è, per esempio, che, in particolari circostanze, da due qubit si può ricavare una quantità di informazione superiore al doppio di quella che si ottiene da un singolo qubit. Per analoghi motivi, in un calcolatore quantistico (a differenza di quanto accadrebbe in uno probabilistico, nel quale, se si intraprende un percorso, ciò che sarebbe accaduto seguendo l'altro percorso non produce alcun effetto), più percorsi vengono intrapresi contemporaneamente e il risultato è la sovrapposizione degli stati corrispondenti ai diversi percorsi. In tal modo, due diversi percorsi alternativi possono interferire (in modo costruttivo o distruttivo, esattamente come avviene con le onde luminose) ed è questo effetto che, a quanto sembra, rende il calcolo quantistico più potente del calcolo classico. Importanti risultati di Peter W. Shor e di Lov K. Grover hanno mostrato che, in linea di principio, i calcolatori quantistici potrebbero essere più potenti di quelli deterministici, in quanto essi consentono di eseguire la fattorizzazione di interi in tempo polinomiale ed effettuare operazioni di ricerca in un insieme di n dati non ordinati in tempo O(n), risultati non ritenuti possibili con i normali calcolatori. Allo stato attuale, tuttavia non è noto se i calcolatori quantistici siano reralmente più potenti di quelli classici. Se chiamiamo QP la classe dei problemi risolubili in tempo polinomiale con macchine quantistiche il fatto che l'inclusione di P in QP sia o meno stretta è uno dei tanti problemi aperti che costellano la teoria della complessità computazionale.

Calcolo molecolare

Il paradigma di calcolo chiamato calcolo molecolare (o anche DNA computing) è stato introdotto in alcuni lavori di Leonard M. Adleman (1994) e Richard J. Lipton (1995). In questo caso non è stata l'evoluzione delle tecnologie elettroniche che ha portato allo sviluppo di questo modello, bensì l'evoluzione delle biotecnologie, in particolare le crescenti capacità acquisite dagli sperimentatori nella manipolazione del materiale genetico, evoluzione che non solo ha ispirato il modello di calcolo astratto ma ne lascia anche prefigurare la possibile realizzazione. Nel calcolo molecolare l'informazione è codificata in filamenti di DNA mediante opportune sequenze delle quattro basi fondamentali Adenina, Timina, Guanina, Citosina. I filamenti (corrispondenti quindi a stringhe di caratteri) sono contenuti in provette. Le operazioni che possono essere eseguite sono quelle classiche della manipolazione genetica: per esempio, individuare e separare dagli altri i filamenti che contengono un particolare carattere in una data posizione, attaccare una sequenza particolare a tutti i filamenti contenuti in una provetta, fondere il contenuto di due provette, e così via.

Un'operazione di centrifugazione permette inoltre di separare i filamenti anche rispetto al peso. Per ricavare la soluzione di un problema (per es., il problema del commesso viaggiatore) si deve innanzitutto codificare l'istanza del problema con filamenti, poi si eseguono operazioni che trasformano via via i filamenti (generando filamenti che rappresentano tutti i possibili percorsi sul grafo), fino a che un'opportuna fase di filtraggio non consente di estrarre i filamenti che rappresentano soluzioni accettabili (il percorso inizia e termina in una data città e ogni città viene visitata una e una sola volta) e la centrifugazione permette di selezionare le soluzioni migliori (più leggere). Si noti che il modello, come altri modelli ispirati al comportamento del materiale cellulare (per es., i membrane systems, chiamati anche P-systems), è intrinsecamente a elevato parallelismo e non-deterministico. Attualmente si ritiene che, in un futuro peraltro remoto, meccanismi di calcolo basati su proprietà del DNA possano essere utilizzati in modo complementare ai normali calcolatori per realizzare processi di calcolo in cui risulti importante disporre di un elevato parallelismo o convenga impiegare componenti a scala molecolare (come nella realizzazione di nanostrutture).

Bibliografia

Agrawal 2004: Agrawal, Manindra - Kayal, Neeraj - Saxena, Nitin, PRIMES is in P, "Annals of mathematics", 160, 2004, pp. 781-793.

Alon 1999: Alon, Noga - Matias, Yossi - Szegedy, Mario, The space complexity of approximating the frequency moments, "Journal of computer and system sciences", 58, 1999, pp. 137-147.

Ausiello 1999: Ausiello, Giorgio e altri, Complexity and approximation. Combinatorial optimization problems and their approximability properties, Berlin, Springer, 1999.

Ausiello 2003: Ausiello, Giorgio - d'Amore, Fabrizio - Gambosi, Giorgio, Linguaggi, modelli, complessità, Milano, Angeli, 2003.

Barabási 2004: Barabási, Albert-László, Link. La scienza delle reti, Torino Einaudi, 2004.

Björner 2006: Björner, Dines, Software engineering, Berlin-New York, Springer, 2006, 3 v.

Borodin, El-Yaniv 1998: Borodin, Allan - El-Yaniv, Ran, Online computation and competitive analysis, Cambridge, Cambridge University Press, 1998.

Chazelle 2000: Chazelle, Bernard, A minimum spanning tree algorithm with inverse-Ackermann type complexity, "Journal of the Association for Computing Machinery", 47, 2000, pp. 1028-1047.

Cormen 2001: Cormen, Thomas H. e altri, Introduction to algorithms, 2. ed., Cambridge (Mass.), MIT Press, 2001.

Cormode, Muthukrishnan 2005: Cormode, Graham - Muthukrishnan, S. Muthu, What's hot and what's not. Tracking most frequent items dynamically, "ACM transactions on database systems", 30, 2005, pp. 249-278.

Demetrescu, Italiano 2004: Demetrescu, Camil - Italiano, Giuseppe F., A new approach to dynamic all pairs shortest paths, "Journal of the Association for Computing Machinery", 51, 2004, pp. 968-992.

De Nicola, Piperno 1999: De Nicola, Rocco - Piperno, Adolfo, Semantica operazionale e denotazionale dei linguaggi di programmazione, Torino, CittàStudi, 1999.

Ehrig, Mahr 1985: Ehrig, Hartmut - Mahr, Bernd, Fundamentals of algebraic specifications, Berlin-New York, Springer, 1985.

Fokkink 2000: Fokkink, Wan J., Introduction to process algebra, Berlin-New York, Springer, 2000.

Garey, Johnson 1979: Garey, Michael R. - Johnson, David S., Computers and intractability. A guide to the theory of NP-completeness, San Francisco, Freeman, 1979.

Goldberg, Rao 1998: Goldberg, Andrew V. - Rao, Satish, Beyond the flow decomposition barrier, "Journal of the Association for Computing Machinery", 45, 1998, pp. 783-797.

Goldberg, Tarjan 1988: Goldberg, Andrew V. - Tarjan, Robert E., A new approach to the maximum flow problem, "Journal of the Association for Computing Machinery", 35, 1988, pp. 921-940.

Gruska 1999: Gruska, Jozef, Quantum computing, London, McGraw-Hill, 1999.

Harel 2000: Harel, David - Kozen, Dexter - Tiuryn, Jerzy, Dynamic logic, Cambridge (Mass.), MIT Press, 2000.

Harel, Politi 1998: Harel, David - Politi, Michel, Modeling reactive systems with statecharts: the statemate approach, New York-London, Mc Graw-Hill, 1998.

Hemaspaandra, Ogihara 2002: Hemaspaandra, Lane A. - Ogihara, Mitsunori, The complexity theory companion, Berlin, Springer, 2002.

Henzinger, King 2001: Henzinger, Monika R. - King, Valerie, Maintaining minimum spanning trees in dynamic graphs, "SIAM journal on computing", 31, 2001, pp. 364-374.

Hromkovic 2005: Hromkovic, Juraj, Design and analysis of randomized algorithms, Berlin, Springer, 2005.

Kleinberg 1999: Kleinberg, Jon e altri, The web as a graph: measurements, models and methods, "Proceedings of the Fifth annual international conference on computing and combinatorics", LNCS 1627, 1999, pp. 1-18.

Knuth 1968-1973: Knuth, Donald E., The art of computer programming, Reading (Mass.), Addison Wesley, 1968-1973.

Paun 2005: Paun, Gheorge - Rozenberg, Grzegorz - Salomaa, Arto, DNA computing, Berlin, Springer, 2005.

Rojas 1996: Rojas, Raúl, Neural networks. A systematic introduction, Berlin-London, Springer, 1996.

Roughgarden 2005: Roughgarden, Tim, Selfish routingand the price of anarchy, Cambridge (Mass.), MIT Press, 2005.

Van Leeuwen 1990: Handbook of theoretical computer science, edited by Jan van Leeuwen, Amsterdam, Elsevier, 1990.

Vazirani 2001: Vazirani, Vijay, Approximation algorithms, Berlin, Springer, 2001.