INFORMATICA

INFORMATICA

(App. IV, II, p. 189)

Dalla metà degli anni Settanta alla fine degli Ottanta si è assistito non soltanto all'ingresso degli elaboratori in tante attività e nei più diversi luoghi delle società avanzate, ma anche a un consolidamento dell'i. e delle sue applicazioni in forma disciplinare formalizzata.

Complessità computazionale. - Riguarda sia la complessità di algoritmi da eseguire sequenzialmente su elaboratori con architettura alla von Neumann (v. elaboratori elettronici, in questa Appendice) o con automi di tipo astratto del tipo della macchina di Turing (v. App. IV, ii, p. 193), o di algoritmi da eseguire su elaboratori con alto grado di parallelismo, sia la complessità di reti di elaborazione formate da elaboratori o da componenti assai più elementari, o addirittura da porte logiche (NOR, NAND, AND, ecc.).

Per quanto riguarda la complessità degli algoritmi, era stato precedentemente formalizzato il concetto generico di algoritmo, inteso come procedimento di calcolo, specificando che esso doveva essere finito (cioè compiuto con un numero finito di passi) e relativo a un modello astratto di elaboratore. Questo poteva essere o una macchina di Turing o una macchina astratta alla von Neumann, con una memoria indirizzabile di capacità indefinita o macchine di modelli analoghi. In questo modo la nozione di algoritmo si assimila a quella di programma (per un elaboratore) astratto e, come si vedrà, la scelta di tale macchina astratta non è influente sulle considerazioni che seguiranno.

Algoritmi e programmi astratti sono ragionevolmente parametrici rispetto ai dati iniziali e, nello studio della complessità degli algoritmi, si definisce una ''misura'' dei dati iniziali stessi in base a un parametro N. Così se occorre sommare fra loro N numeri, oppure se occorre moltiplicarli fra loro od ordinarli in modo ascendente o discendente, oppure se si deve verificare se un certo numero è contenuto in una sequenza ordinata di N numeri, allora si dirà che una misura di tali dati è appunto N. Dopo di che si cercherà di valutare quanto la macchina astratta di riferimento è impegnata in termini di tempo (cioè di numero di operazioni eseguite) oppure in termini di memoria occupata. L'impegno in termini di tempo sarà detto complessità di tempo, quello in termini di memoria complessità di spazio, e sia l'uno che l'altro saranno funzioni di N.

Di tali funzioni f(N) non interesserà sempre dare un'espressione esplicita, ma talora un'approssimazione del suo ordine di grandezza, che sarà espressa con O(f(N)), con la condizione che se |O(f(N))| è il modulo del numero espresso da O(f(N)) allora esiste, per ogni istanza di questa espressione, una costante positiva K tale che è |O(f(N))|≤K|f(N)|. Si scriverà pertanto: f(N) = O(f(N)).

Perciò se f(N) è un polinomio di grado m di N, si dirà che f(N) = O(N^m). In altri termini, la notazione introdotta permette di esprimere le proprietà asintotiche di f(N), cioè per N arbitrariamente grande.

Così si può dire che dovendo sommare N numeri fra loro si dovranno fare (N-1) addizioni e perciò la complessità di tempo sarà O(N).

Per ordinare N numeri in ordine crescente si può confrontare il primo con il seguente e, se questo è minore, scambiarlo di posto, dopo di che si confrontano il secondo con il terzo, attuando uno scambio di posto se il terzo è minore del secondo, e così via fino all'ultimo posto in cui ci sarà un numero maggiore (o almeno non minore) di tutti i precedenti. Fatto ciò, si può ricominciare con la stessa regola dal primo al penultimo e poi ricominciare di nuovo finché non resta da ordinare che il solo primo elemento; allora si è finito. È facile persuadersi che la complessità temporale è O(N²) e quella di spazio è O(N) per questo particolare algoritmo per risolvere il problema dell'ordinamento.

Ci si può porre il problema se questo è il migliore algoritmo per risolvere il problema dell'ordinamento (la risposta sarebbe no), e se il tempo di esecuzione dell'algoritmo è sempre costante. A questo fine si può fare un altro esempio, quello di ricercare una determinata parola in un dizionario. Una possibilità è quella di confrontare la parola data con ciascuna voce del dizionario finché non si trova la corrispondenza; così, nel caso peggiore si dovranno fare N confronti se N sono le voci del dizionario, mentre nel caso migliore se ne farà solo uno. Un algoritmo migliore sarebbe tuttavia quello di confrontare la parola data con la voce di mezzo del dizionario e vedere se questa è uguale o se la precede o se la segue alfabeticamente. Nel primo caso ci si arresta, nel secondo si farà il confronto con la voce che è nel posto N/4; nel terzo si farà il confronto con la voce nel posto 3N/4 e così via. Con questo secondo algoritmo nel caso peggiore si fanno log₂N confronti (arrotondando il logaritmo all'intero immediatamente superiore) e in quello migliore uno solo. In genere si preferisce riferirsi al caso peggiore e, nel caso precedente, si assume che la complessità di tempo sia O(logN), omettendo l'indicazione della base dei logaritmi, che aggiungerebbe nella conversione solo una costante moltiplicativa.

Si noti che le complessità così definite riguardano il comportamento asintotico e perciò può darsi che un algoritmo con complessità O(N²) sia più veloce di uno con complessità O(N) per valori piccoli di N. Però, come vedremo meglio in seguito, quelle che interessano sono delle valutazioni molto generali, mentre per l'efficienza di programmi specifici per specifici elaboratori andrà fatta un'analisi molto più dettagliata (analisi dei programmi) svolta eventualmente su base probabilistica.

Diverso il problema quando, come in questo caso, siamo interessati a investigare le proprietà computazionali di algoritmi per vedere se sono divisibili in classi e se fra le varie classi si può stabilire una qualche gerarchia. In questo caso ciò che interessa è di dividere gli algoritmi di tipo P con complessità (asintotica e per il caso peggiore) di tipo polinomiale (cioè del tipo O(N^k) con K intero) e in algoritmi con complessità superpolinomiale, cioè che cresce con N più velocemente di O(N^k), come per es. la complessità esponenziale O(2^N) o fattoriale O(N!). Tale distinzione ha un duplice motivo: in primo luogo, un algoritmo superpolinomiale può essere utilizzato solo per valori piccoli di N anche su elaboratori assai veloci e con ampie memorie; in secondo luogo, si può dimostrare che la simulazione di un elaboratore astratto su un altro elaboratore astratto (fra quelli considerati inizialmente nella definizione di complessità) può essere fatta con complessità di tempo polinomiale. Ciò significa che la complessità di un algoritmo se è polinomiale per una macchina di Turing sarà polinomiale per una macchina astratta di von Neumann. Infatti l'algoritmo per la macchina di Turing potrà essere eseguito da quella von Neumann che simuli la prima, e ci si può facilmente persuadere che la complessità temporale sarà ancora polinomiale. A risultati analoghi si può pervenire anche nei riguardi della complessità di memoria.

Ciò posto, se è dato un problema (o il calcolo di una funzione) e se siamo in grado di dimostrare che la complessità di un qualunque suo algoritmo sarà, nel caso peggiore, superpolinomiale, allora si dirà che il problema (il calcolo della funzione) è intrattabile. Se invece la complessità nel caso peggiore è polinomiale, allora il problema (il calcolo della funzione) è detto trattabile. Inoltre si può dare la seguente gerarchia: i problemi risolubili in tempo logaritmico rispetto al parametro N relativo all'ingresso formano un insieme incluso in quello dei problemi risolubili con quantità logaritmica (rispetto a N) di memoria; questo insieme è a sua volta incluso in quello dei problemi risolubili in tempo esponenziale, che a sua volta è incluso nell'insieme dei problemi risolubili con quantità esponenziale di memoria.

Non sempre interessa indagare sui limiti superiori della complessità (caso peggiore), ma può essere interessante dimostrare che per un certo problema non c'è un algoritmo con limite inferiore di complessità che sia polinomiale. Questo accade, per es., nei problemi di decifrazione, in cui si vuole essere sicuri che la decifrazione abusiva abbia le caratteristiche di un problema intrattabile per ogni caso possibile.

Senza entrare nel merito dei problemi intrattabili (nel caso peggiore) su cui c'è un'ampia letteratura, è opportuno rilevare che la complessità relativa ai problemi trattabili e d'interesse applicativo non solo è polinomiale, ma usualmente è limitata a un esponente K di O(N^K) che in genere non supera il valore 3 e solo in qualche caso arriva a 5.

Complessità nell'elaborazione parallela. - Le considerazioni fin qui svolte hanno riguardato l'esecuzione seriale di algoritmi su modelli di elaboratori che eseguono un'istruzione alla volta (macchine di Turing, macchine astratte alla von Neumann, ecc.). È interessante, però, investigare cosa può succedere alla complessità quando si passi a modelli di elaborazione parallela.

Per es., se dobbiamo sommare N numeri fra loro lo potremmo fare in un tempo O(logN) disponendo di N/2, cioè di O(N) elaboratori che sommano prima N/2 numeri, poi N/4, poi N/8, e così via. Analogamente si può facilmente dimostrare che per ordinare N numeri, se si dispone di N/2 elaboratori, la complessità temporale diviene O(N), mentre se si ha un solo elaboratore la complessità temporale è O(NlogN).

Quanto si è visto in via esemplificativa si può generalizzare: l'aumento del numero di elaboratori può portare a una diminuzione della complessità di tempo, in modo che si può assumere come indice di efficienza di algoritmi diversi (con diverso grado di parallelismo e che risolvono lo stesso problema) il prodotto della complessità di tempo di ciascuno per la corrispondente quantità di elaboratori necessari.

Si noti che la relazione fra aumento di numero degli elaboratori e diminuzione del tempo di esecuzione è simile alla relazione che si ha, per gli algoritmi puramente sequenziali, fra tempo di esecuzione e spazio di memoria occupato per l'esecuzione. C'è però da osservare che nel caso dell'elaborazione parallela il costo di N celle di memoria è molto inferiore a quello di N elaboratori, e che in pratica è difficile pensare di poter disporre di un numero illimitato di elaboratori in un sistema parallelo. Tuttavia, anche in un unico elaboratore, la memoria disponibile in realtà è limitata, e le considerazioni sulla complessità sono, come si è detto, a carattere molto generale, e tendenti a mettere in evidenza l'esistenza di classi di problemi con caratteristiche simili di complessità e le relazioni di gerarchia fra tali classi.

A ciò va aggiunto che, in un sistema di elaborazione parallela, il collegamento fra gli elaboratori è d'importanza fondamentale. Il sistema di collegamenti può essere fisso solo se è destinato essenzialmente a risolvere una classe particolare di problemi, come per es. nelle schiere sistoliche (v. elaboratori elettronici, in questa Appendice). In generale però si vuole che i collegamenti possano essere variabili, il che si può ottenere con reti di commutazione multistadio oppure può essere simulato da memorie condivise fra i vari elaboratori.

È interessante sottolineare che i vari sistemi di collegamento finora proposti sono mutuamente equivalenti, a meno di un fattore di complessità sempre polinomiale. Perciò le classi di complessità e le loro gerarchie già descritte restano, a meno di un fattore polinomiale. Però nel caso di parallelismo, oltre alla distinzione fra complessità polinomiale e superpolinomiale, si fa distinzione fra questi tipi di complessità e quella polilogaritmica, cioè del tipo O((logN)^k), che è la complessità cui si tende in cambio della notevole complicazione strutturale sia nell'architettura di elaborazione sia nella programmazione e nell'uso di elaboratori paralleli cui si accennerà in seguito.

Si noti infine che l'uso di memorie condivise impone l'uso di protocolli di sincronizzazione fra i vari processi in atto, che possono portare a impegni non convenienti di memoria e, soprattutto, di tempo di elaborazione.

Complessità strutturale. - Nel caso di elaborazione parallela si può pensare che gli elementi di elaborazione siano dei veri e propri elaboratori o delle unità centrali, però si può anche pensare che siano degli elementi più semplici: addizionatori o anche semplici porte logiche che calcolano una semplice funzione booleana, elementi a soglia, ecc. In questo caso si arriva a considerare i circuiti logici realizzati con tecnologia integrata e si definisce una complessità area-tempo analoga alla complessità data dal prodotto di quella temporale per quella relativa al numero di processori a cui si è accennato (v. sopra).

Nella complessità area-tempo, indicata AT, l'area A in questione è quella attiva della piastrina di semiconduttore, rapportata alla larghezza l delle linee di collegamento fra i vari transistori i quali, corrispondentemente, hanno area l² all'incirca. Invece T è il tempo di elaborazione degli operandi, caratterizzati da N (che, in genere, dà il numero dei loro bit). Così si può dimostrare che, entro certe ipotesi, per un certo tipo di moltiplicatore di due fattori di N bit ciascuno, vale la relazione AT² ≥ KN², dove K è una costante.

Si noti che, nel caso della complessità strutturale, interessano le relazioni effettive fra A, T ed N e non tanto il comportamento asintotico, perché i valori di N sono raramente superiori a 100.

La complessità strutturale delle reti computazionali più semplici (reti logiche) può prescindere dai contributi portati dalle interconnessioni ed essere valutata in modo molto elementare.

Correttezza e funzionalità computazionale. - I progressi delle tecnologie di costruzione degli elaboratori hanno consentito di affidare compiti di controllo e di gestione sempre più impegnativi a elaboratori e ai programmi in essi contenuti. Comportamenti inaspettati o disastrosi di tali sistemi sono stati sempre più dovuti a non corrispondenza dei programmi alle loro specifiche di progetto oppure a errori nel progetto o nell'analisi di quanto andava richiesto al progetto stesso.

I problemi di progettazione hanno dato luogo a ricerche di tipo applicativo in cui entrano in gioco anche fattori umani, mentre la correttezza di un programma rispetto alle sue specifiche e la verifica di tale correttezza hanno dato luogo a ricerche di tipo sia teorico sia applicativo che si cercherà di tratteggiare rapidamente.

Per es., per programmi sequenziali con un solo punto d'ingresso e un solo punto di uscita, che si può pensare calcolino una funzione, c'è un impianto teorico stabilito (che può anche essere esteso a casi più generali). Un predicato d'ingresso fornisce per tali programmi le proprietà dei dati d'ingresso al programma stesso e un predicato di uscita descrive le proprietà del risultato dell'esecuzione del programma. Il linguaggio del primo ordine dell'aritmetica di Peano può essere sufficiente, ma il calcolo dei predicati (se non quello proposizionale), con aggiunta la possibilità di usare espressioni e notazioni matematiche diffuse, possono rendere più espressivi i predicati suddetti. Il programma viene allora a essere considerato un trasformatore di predicati d'ingresso in predicati di uscita.

Con certe restrizioni sui linguaggi programmativi e sui relativi costrutti da usare, si danno procedimenti che permettono di verificare la correttezza di un programma ai predicati d'ingresso e di uscita. Tali procedimenti si prestano a essere realizzati su elaboratore facendo uso di tecniche di dimostrazione automatica di teoremi e di possibilità d'interazione fra programmi di verifica ed esperti umani.

Le ricerche sull'argomento hanno suggerito nuove metodologie di redazione dei programmi in modo che la produzione di un programma e la verifica della sua correttezza possano procedere di pari passo. È comunque da rilevare che anche la progettazione di un sistema di programmi può, in una certa misura, essere perfezionata e adattata in modo più o meno contemporaneo alla redazione dei programmi stessi, quando con tali programmi reagiscono operatori umani il cui comportamento futuro può essere poco prevedibile e comunque condizionato dall'interazione con i programmi stessi.

È però da sottolineare che non tutti i programmi si limitano a realizzare un algoritmo e a calcolare una funzione dell'ingresso, anche se al termine funzione si dà un significato per quanto possibile vasto. Alcuni programmi sono soggetti a limitazioni temporali. Per es. devono compiere certe elaborazioni in un tempo minore di un tempo prefissato, come nel caso di programmi che intervengono in caso di allarmi. In altri casi, però, l'azione di un programma deve svolgersi in un tempo superiore a un tempo minimo. Altri programmi possono avere più punti d'ingresso e accettare dati estemporaneamente, e avere più di un'uscita. Inoltre certi programmi devono svolgersi contemporaneamente (o, come si dice, in parallelo) ad altri, cooperando a un fine comune oppure non cooperando e, anzi, dovendone restare del tutto indipendenti almeno per quanto riguarda i risultati forniti in uscita. Infine certi programmi non realizzano un algoritmo (che per essere tale deve terminare in un tempo finito) ma solo un certo comportamento continuo, in modo che non terminano mai, ma si ripetono indefinitamente. Casi tipici di questa categoria sono i sistemi operativi, i protocolli, i programmi per il controllo continuo dei processi (industriali, amministrativi, ecc.).

In questi casi il problema della correttezza, cioè della corrispondenza alle specifiche, si complica non solo perché non c'è una funzione (nel senso matematico del termine) da calcolare, ma anche perché devono essere specificate e osservate certe regole d'interazione e certe proprietà relative al lungo periodo.

Un primo tipo d'interazione è quella indiretta, che si può avere fra l'esecuzione di programmi mutuamente indipendenti eseguiti su un elaboratore che opera in multiprogrammazione e che attraverso la protezione evita interferenze dirette indebite (v. elaboratori elettronici, in questa Appendice), evita cioè l'uso contemporaneo di stesse aree di memoria o di altri organi. L'interazione indiretta consiste nel fatto che programmi indipendenti usano una stessa risorsa (per es. un'unità periferica) a turno, in modo che il tempo di esecuzione di un programma può darsi che si prolunghi per questo effetto.

Tale prolungamento deve però essere finito e anche ragionevolmente breve, e pertanto si richiede che il supervisore (v. elaboratori elettronici, App. IV, i, p. 650) assegni le risorse con criteri di equità e intervenga in caso di stallo. Per stallo s'intende un'interazione indiretta che prolunga all'infinito l'attesa della fine dell'esecuzione di due o più programmi. Ciò può accadere perché l'esecuzione di un programma è bloccata, in quanto per proseguirla c'è bisogno di una risorsa (per es. un'unità periferica) che viceversa è a disposizione esclusiva per l'esecuzione di un altro programma, che però è a sua volta bloccata in attesa di altra risorsa, che viceversa è per il momento a disposizione esclusiva dell'esecuzione del primo programma.

Nel caso invece d'interazione diretta fra l'esecuzione di due programmi occorrerà stabilire protocolli d'interazione e di sincronizzazione che possono riguardare, per es., l'accesso a turno a un'area comune di memoria o la trasmissione di dati fra un programma e un altro. Questi protocolli saranno realizzati con programmi e, se impiegano un numero di variabili ragionevolmente piccolo, ciascuna con un piccolo numero di possibili valori, allora esistono algoritmi di verifica della loro correttezza usabili in pratica.

Quando invece si voglia dare impostazione formale al problema di evitare che più programmi operanti contemporaneamente su uno stesso sistema di elaborazione presentino comportamenti inaspettati, occorre allora ampliare il concetto di correttezza con concetti di funzionalità generale, che riguardino anche i problemi d'interazione.

Le esigenze di funzionalità ne generano altre classificabili in esigenze di sicurezza (safety) e in esigenze di ''vitalità'' (liveliness), e talora richiedono il soddisfacimento di determinate condizioni in termini probabilistici. Le esigenze di sicurezza possono tradursi in predicati che affermano che non si presenterà un certo evento (per es. uno stallo) per tutti gli istanti successivi a un certo istante (per es. quello dell'attivazione dell'esecuzione di certi programmi). Le esigenze di vitalità si possono viceversa tradurre in termini di predicati che affermano che esiste almeno un istante nel futuro in cui certi eventi si verificheranno. Per es. il protocollo che regola l'accesso a un dato (o a una struttura di dati) che rappresenta un conto corrente ed è accessibile da parte di più operatori, dovrà curare non solo un accesso alla volta da parte di un solo operatore, ma anche permettere che tutti gli operatori possano ottenere l'accesso in tempi ragionevolmente brevi.

Non è possibile in questa sede dare altro che un cenno anche su problemi come questi, che possono richiedere l'uso di logiche modali; tale cenno può tuttavia indicare i campi in cui la ricerca ha portato a notevoli risultati, utili sia a inquadrare concettualmente i problemi, sia anche a risolvere problemi particolari, che per la loro delicatezza (nuclei di sistemi operativi, software di controllo di processi critici, ecc.) giustificano sforzi notevoli per arrivare a dimostrare la correttezza e la funzionalità di particolari programmi.

È però da rilevare che nel caso di dimostrazioni di correttezza di programmi assai complessi, condotte con ausili, con metodi euristici, con valutazione sperimentale più o meno estesa e con vari altri metodi più o meno mutuamente integrati, è sempre lecito (e, anzi, necessario) ritenere possibile qualche errore. Inoltre è anche legittimo sospettare che la correzione di errori trovati in un programma possa essa stessa essere fonte di nuovi errori. Le stesse riviste di matematica, d'altra parte, contengono spesso errata, confutazioni e controconfutazioni di dimostrazioni prima ritenute ineccepibili.

Sistemi archiviali. - Molte applicazioni correnti dell'i., invece di coinvolgere la realizzazione di algoritmi complessi da usare ripetutamente con dati diversi, coinvolgono brevi sequenze di operazioni estemporanee su un complesso di dati che vengono usati ripetutamente (e anche contemporaneamente) da più utenti. Le operazioni su questi dati possono anche essere operazioni aritmetiche ma, in genere, riguardano la semplice lettura di un dato o il suo aggiornamento.

Caso tipico è quello di un'anagrafe comunale nella quale vengono registrati nuovi abitanti con nome, cognome, luogo e data di nascita, indirizzo, stato civile, e altri dati eventuali; dalla quale vengono cancellati gli abitanti che lasciano il comune; nella quale possono essere aggiornati l'indirizzo o gli altri dati. Tutto ciò da parte di personale di diversi uffici comunali e per scopi diversi: rilascio di certificati, verifiche fiscali, statistiche, ecc.

Si può anche pensare che ogni ufficio per ciascuno scopo possa avere un proprio archivio (o, addirittura, un proprio calcolatore); sono tuttavia ovvi i vantaggi di condividere un archivio unico in modo che ogni aggiornamento fatto da un ufficio sia subito disponibile a tutti gli altri. Occorrerà naturalmente prevedere che alcuni uffici possano compiere alcune operazioni in modo esclusivo: per es., la stampa di certificati. Tutti i dati dell'archivio, poi, devono corrispondere a un determinato schema: prima il cognome (per cui può essere a disposizione un certo numero di caratteri) poi il nome, poi il luogo e la data di nascita da registrare secondo un certo formato, poi l'indirizzo, ecc.

È nata così l'idea di una base di dati, cioè di un insieme di dati registrati secondo un certo schema fisico (determinato in base a considerazioni di efficienza) ma che dal punto di vista dell'uso può essere considerato secondo uno o più schemi concettuali, che astraggono da dettagli non utili ai fini dell'uso. Poiché gli usi possono essere diversi, si possono avere diversi schemi dell'intero insieme di dati oppure diversi sottoschemi per sottoinsiemi particolari di dati.

Si avrà poi un sistema di programmi di servizio che costituiscono il sistema di gestione della base di dati il quale dovrà in genere:

a) permettere l'uso dei dati o di parte di essi facendo uso sia di linguaggi ad hoc per definire la struttura dei dati e i modi di accesso per la manipolazione dei dati, sia di linguaggi (che possono essere diversi dai primi) che servono a eseguire accessi e manipolazioni;

b) permettere il caricamento dei dati iniziali;

c) controllare l'accesso degli utenti ai dati e alle operazioni su di essi, poiché alcune categorie di persone potranno, per es., solo estrarre dati, altre potranno anche modificarli, altre ancora potranno modificare lo schema fisico, ecc.;

d) registrare modi e tempi d'accesso, per ricavare dati circa l'efficienza del sistema e per eventuali modifiche migliorative;

e) permettere di riprendere il servizio dopo interruzioni di vario genere (mancanza di corrente elettrica, cadute di collegamenti di trasmissione dati, ecc.) senza perdita di dati o della loro validità.

Le operazioni di accesso e di manipolazioni sono chiamate transazioni, e il sistema di gestione della base di dati deve non solo permettere lo svolgimento contemporaneo di centinaia o di migliaia di transazioni, ma anche evitare che transazioni diverse portino a situazioni incongrue. Per es., mentre è in corso una transazione per la prenotazione di un certo posto su un certo volo, non si possono permettere altre transazioni sullo stesso posto.

I linguaggi di accesso e di manipolazione dei dati si possono integrare in alcuni degli usuali linguaggi programmativi, in modo che quando occorre operare sulla base di dati sia possibile farlo con il suo linguaggio, che permette di esprimere solo quanto c'è da fare, senza preoccuparsi dei dettagli, quali quelli relativi alla locazione fisica dei dati.

La teoria (e la pratica) delle basi di dati non possono essere descritte in uno spazio limitato come il presente, però sembra utile accennare al modello dei dati che appare come il più significativo: quello relazionale.

Con modello di dati s'intende in genere un metodo e una notazione per descriverli e per definire le operazioni su di essi. Nel modello relazionale i dati che costituiscono una base di dati vengono visti come relazioni fra i dati elementari che li compongono secondo un unico schema.

Il termine ''relazione'' è qui usato in senso matematico, di relazione fra n insiemi (non necessariamente distinti), cioè come insieme di n-uple formate da un elemento del primo insieme, uno del secondo, ecc. e uno dell'n-esimo. Nel caso presente ciascun insieme è formato da dati elementari: per es. un insieme di cognomi, uno di nomi, uno di luoghi di nascita, uno di date di nascita, ecc., in modo che un elemento della relazione fra tali insiemi è un elemento della base di dati dell'anagrafe comunale a cui si è accennato all'inizio.

Il concetto matematico di relazione è, com'è noto, molto ampio e include quello di funzione, e ciò può spiegare la flessibilità e la generalità di uso delle basi di dati. Inoltre una relazione n-aria può essere espressa con (n-1) relazioni binarie e, mentre una relazione binaria è rappresentabile con un grafo, una relazione n-aria può essere rappresentata con un ipergrafo.

Ai fini delle rappresentazioni delle basi di dati si possono usare vari tipi di grafici − che non è il caso di descrivere in questa sede − che ne aiutano la progettazione e l'uso. Inoltre al fine di formalizzare le basi di dati e le operazioni su di esse sono stati introdotti sia un calcolo relazionale sia un'algebra relazionale. Il calcolo relazionale è basato sul calcolo dei predicati e può essere usato per esprimere asserzioni e condizioni sugli elementi di una base di dati ai fini dell'accesso alla stessa. L'algebra relazionale invece definisce particolari operazioni sulle basi di dati, esprimibili con operatori algebrici.

I linguaggi per l'accesso alle basi di dati (query languages) tendono naturalmente a incorporare il calcolo o l'algebra relazionale. Non potendo entrare nei dettagli di tali formalismi e di tali linguaggi, si può però accennare al fatto che linguaggi di tipo logico si prestano a rappresentare la conoscenza a proposito di fatti o di proprietà di fatti o di proprietà di oggetti e soggetti, in modo che le basi di dati si possono estendere per includere le basi di conoscenza.

Queste sono sistemi archiviali che permettono l'uso di linguaggi, di carattere più dichiarativo che algoritmico, per la definizione delle proprietà dei dati stessi e il relativo accesso a essi, in modo che è particolarmente adatto per reperire le conoscenze derivabili dai dati archiviati nel sistema.

Teoria e applicazioni delle basi di conoscenza sono meno sviluppate di quelle relative alle basi di dati, che sono maturate nell'arco di più di vent'anni e sono ampiamente in uso da tempo.

Sistemi informativi. - Con il termine di sistema informativo si tende a indicare un sistema intercomunicante di elaboratori, basi di dati o di conoscenze, sistemi archiviali tradizionali, software, persone, procedure, ecc., che concernono lo scambio e l'archiviazione di dati e di informazioni relativi a un ente o comunque a un'organizzazione (pubblica o privata, civile o militare, ecc.).

Chiaramente il ruolo dei mezzi di elaborazione, trasmissione, presentazione di dati in varia forma (alfabetica, numerica, grafica, acustica, visiva) e il ruolo sia dei mezzi di registrazione di dati, informazioni e conoscenze, sia dei linguaggi e del software diviene sempre più notevole e prevalente per motivi di economicità, efficienza, velocità, affidabilità, ecc., rispetto ai mezzi e ai metodi tradizionali.

L'influenza dei metodi dell'i. per la progettazione della struttura, delle procedure, dei sistemi archiviali tipici di tale disciplina è stata tale che oggi la struttura di un'organizzazione, anche basata su mezzi essenzialmente tradizionali, viene spesso ideata e realizzata usando le metodologie escogitate per i sistemi informativi automatizzati. Tale influenza si sente particolarmente quando l'organismo interessato è di grandi dimensioni e ha funzioni e procedure complesse (un ministero, una grande azienda manufatturiera, un sistema di prenotazione di posti e di gestione dei voli, ecc.); quando tale organismo è gestito efficientemente; quando il personale (dirigente e non) ha le conoscenze, gli atteggiamenti e le attitudini idonee. È opinione corrente in Italia che ciò non accada nella pubblica amministrazione, il che può essere vero; però non sembra che sia vero solo in questo caso.

Aspetti educativi dell'informatica. - Il carattere innovativo dell'i. nel campo culturale deriva dal fatto che i suoi mezzi e i suoi metodi riguardano la capacità di operare automaticamente con delle macchine su rappresentazioni di concetti, idee, informazioni, conoscenze e simili. L'''invenzione'' del linguaggio ha permesso alla specie umana la trasmissione immediata di tali rappresentazioni mediante suoni, gesti, mimica facciale, ecc., fra un limitato numero di persone. L'invenzione della stampa e, successivamente, delle radiodiffusioni, della televisione, della registrazione su film o su mezzo magnetico ha permesso la trasmissione di tali rappresentazioni nel tempo e nello spazio.

Lo sviluppo degli elaboratori e delle metodologie informatiche permette ora di operare su tali rappresentazioni sia sotto forma alfabetica o numerica, sia sotto forma iconica. Il word-processor, cioè l'elaboratore di testi, è un tipico esempio a livello assai basso, e così la produzione di fumetti televisivi alla ''Mazinger''.

Lo sviluppo dell'i. come disciplina e lo sfruttamento efficace della microelettronica e della micromeccanica si sono realizzati nello spazio di appena una generazione e hanno investito alcuni aspetti delle discipline tecniche e scientifiche, delle applicazioni contabili e militari; ma la penetrazione in altri campi culturali è forzatamente lenta, benché se ne parli molto. La scuola è stata marginalmente influenzata, perché occorre dare una nuova formazione agli insegnanti, fornire loro mezzi e strutture adeguate e adatte ai loro compiti particolari. Ma c'è soprattutto da tener presente che lo sviluppo disciplinare e culturale avviene con un ritmo che segue l'avvicendamento generazionale. D'altra parte anche lo sviluppo di un'utenza accorta, che sappia pretendere e sappia cosa pretendere, è condizione necessaria per lo sviluppo di attività industriali e soprattutto di attività di servizio di buon livello. Da ciò è derivato lo sviluppo, fuori delle usuali strutture scolastiche, di un'attività di addestramento e formazione (anche se in genere a livelli non alti) in campo informatico, di notevole peso economico.

Aspetti giuridici dell'informatica. − Un problema che ha sollevato ampie discussioni e che in alcuni paesi ha portato alla formulazione di una legislazione particolare è stato quello della privatezza, cioè del diritto del cittadino a non vedere divulgate informazioni che lo riguardano e che ne possano compromettere l'immagine sociale, gli interessi o la libertà attraverso l'uso improprio di mezzi informativi privati e (particolarmente) pubblici. Ciò ha riflessi diversi in società diverse e con diversi gradi di sviluppo, ma si va consolidando in una serie di diritti, più o meno unificata, nei paesi a democrazia avanzata.

Altro aspetto interessante è, in prospettiva, la verifica (sia della coerenza logica sia della fattibilità, in termini informatici e organizzativi) di leggi e regolamenti emanati dal corpo legislativo e da organi ministeriali. Accanto a tali criteri e verifiche di fattibilità si potranno affiancare verifiche di costi aggiuntivi (o sottrattivi) sui sistemi informativi pubblici (e non).

Ulteriore problema giuridico di notevole interesse economico e industriale è quello della protezione dei diritti di chi produce software. I tipi di protezione sono essenzialmente due: la protezione accordata ai brevetti e la protezione sulla base del diritto d'autore. Il brevetto protegge processi e dispositivi nuovi e perciò sembrerebbe il modo naturale di proteggere il software che è la specifica di un processo. Non è però brevettabile una teoria, un teorema, un'idea, e alcuni ritengono che un programma sia l'espressione di un'idea e perciò sia proteggibile solo mediante il diritto d'autore sul testo del programma (ed eventuali varianti banali). D'altra parte, anche uno spartito musicale può essere considerato come la specifica di un'esecuzione da parte di un'orchestra, un solista, un coro, ecc.

Dal punto di vista pratico si può dire che il software finora è stato protetto principalmente con il copyright sia negli Stati Uniti, che sono di gran lunga il maggior produttore e il più innovativo, sia negli altri paesi. La giurisprudenza degli Stati Uniti si è spesso espressa in modo non favorevole alla brevettabilità del software, però più recentemente si è iniziato a concedere brevetti, anche se viene obiettato che ciò potrebbe ostacolare versioni innovative di un software esistente, prodotte eventualmente da piccoli produttori.

C'è in effetti da notare che, per es., in un'automobile sono sfruttati per le varie parti brevetti diversi e molteplici. Però nel campo del software la componentistica non è sviluppata così come accade nel campo meccanico o elettrico, forse per ragioni profonde e non facili da superare, sì che non sempre la soluzione brevettabile appare la migliore per la collettività. Comunque le copie abusive del software sono diffuse quanto quelle musicali, anche se nel software si possono inserire alcune protezioni utili per l'uso su elaboratori medi e grandi ed eventualmente alcune parti (virus) che possono danneggiare il contenuto degli archivi di un utente abusivo.

Infine accenniamo alla creazione e all'uso di basi di dati legislative, che risultano di massima importanza sia per la formulazione sia per l'applicazione delle leggi; in questo campo in Italia si è avuta qualche realizzazione notevole.

Bibl.: G. Ausiello, Complessità di calcolo delle funzioni, Torino 1975; G. J. Myers, Software reliability, New York-Chichester 1976; J. De Bakker, Mathematical theory of program correctness, Englewood Cliffs (N.J.) 1980; B. W. Boehm, Software engineering economics, ivi 1981; M. C. Gemignani, Legal protection of software: a survey, in Advances in Computers, 22, San Diego 1983; A. Albano, R. Orsini, Basi di dati, Torino 1985; P. Atzeni, C. Batini, V. De Antonellis, La teoria relazionale dei dati, ivi 1985; D. Harel, Algorithmics, Wokingam-Reading (Mass.) 1987; J. D. Ullmann, Principles of database and knowledge-base systems, 1, New York 1988; 2, ivi 1989; I. Sommerville, Software engineering, Wokingam-Reading (Mass.) 1989³; E. V. Krishnamurti, Parallel processing, ivi 1989; C. Ghezzi, M. Jazayeri, Concetti dei linguaggi di programmazione, Milano 1989; C. Ghezzi, D. Mandrioli, Informatica teorica, ivi 1990; B. Codenotti, M. Leoncini, Fondamenti di calcolo parallelo, ivi 1990. Cfr. anche i numerosi periodici e atti di convegni pubblicati a cura dell'ACM (Association for Computing Machinery) di New York e dell'IEEE (Institute of Electrical and Electronics Engineers), Computer Society di Washington, in particolare le riviste Computing Reviews e Computing Surveys dell'ACM.