LUCIANA ZOU.
INFORMATICA.
Introduzione.
 Il mondo dell'informatica  costituito da molteplici aspetti,
alcuni sono pi legati ai fondamenti teorici e alle origini mate-
matiche di questa scienza, altri sono di tipo tecnologico, altri
ancora riguardano le sue pi svariate applicazioni. Si percor-
rono, in questo testo, le linee guida di molte di queste aree di
interesse, senza soffermarsi su questioni troppo legate alle
tecnologie del momento, ma cercando di considerare solo le
idee fondamentali dell'informatica.
 Nella scienza informatica una questione cardine  come ri-
solvere problemi, problemi per i quali viene adottata una solu-
zione che deve essere elaborata dall'esecutore calcolatore. Al-
cuni problemi non sono risolubili, altri rientrano nel campo di
trattazione con il metodo informatico.
 La comunicazione tra uomo e calcolatore deve awalersi di
linguaggi propri dell'informatica, che fanno parte del pi va-
sto mondo dei linguaggi artificiali. L'architettura di un elabo-
ratore pu essere considerata solo per i suoi aspetti funziona-
li. Le idee, sulla base delle quali sono stati costruiti molti dei
programmi per il calcolatore normalmente utilizzati, costitui-
scono patrimonio indispensabile per una cultura informatica
diffusa; tra questi programmi, i sistemi operativi, i sistemi di
gestione di un archivio e di una base di dati, ne costituiscono il
nucleo portante.
 Le innumerevoli applicazioni dell'informatica suscitano, in
molti, entusiasmi e curiosit: alcune di queste applicazioni, ad
esempio i sistemi di scrittura, sono realmente gi in grado di
evidenziare le modificazioni irreversibili che l'informatica ha
introdotto nel contesto sociale; altre sono applicazioni ancora
acerbe ed  difficile valutarne la rilevanza e il peso che avran-
no in un prossimo futuro.
1. Il pensiero algoritmico





La definizione di un problema

 L'informatica  la scienza che aiuta a risolvere problemi. I pro-
blemi informatici, come quelli matematici, sono una traduzio-
ne semplificata di problemi reali. L'estrema ricchezza di una si-
tuazione reale, nella quale sono presenti elementi di varia natu-
ra, anche di tipo affettivo emozionale, non  riproponibile in
ambito informatico. E necessario ritagliare da questo reale cos
composito, ricco, a volte contraddittorio, solo quella parte che
interessa l'ambito informatico e che pu essere trattata proprio
in quanto costituisce una semplificazione della realt.
 La prima cosa che  necessario fare di fronte ad una situazio-
ne problematica, che si ipotizza di voler affrontare con l'aiuto
dell'informatica,  quella di estrarre e selezionare dalla situa-
zione reale tutti quegli elementi che possono concorrere ad
una definizione rigorosa delproblema. Con i problemi informa-
tici tutto ci che riguarda il problema deve essere dettagliato
e sminuzzato fin nei minimi particolari. La presenza del calco-
latore (chiamato, in modo equivalente, anche elaboratore o
computer), che da solo non sa fare proprio niente, ci obbliga
ad analizzare ogni elemento con estrema precisione. Per po-
ter quindi procedere verso una soluzione informatica di un
problema,  necessario arrivare a formularlo correttamente.
In genere, per stabilire se un problema  ben formulato,  im-
portante accertarsi di alcune questioni:

 - non deve essere evidente che il problema non ha soluzioni;
 - deve esistere un criterio di verifica della soluzione;
 - I'insieme dei dati iniziali deve essere completo.

 Le ragioni di questi vincoli sono evidenti: se appare gi chia-
ro che il problema non ha soluzioni, se non si sa come verifica-

re l'esattezza della soluzione trovata o se tutti gli elementi di
cui si dispone sono certamente insufficienti per poter affron-
tare il problema, in tutti questi casi il problema deve essere ri-
definito in altri termini per poter essere posto correttamente.
 Di fronte a un problema che si ipotizza dunque ben formu-
lato, I'informatico si pone in un ruolo di risolutore piuttosto
pignolo e, come soluzione, produce una sequenza di opera-
zioni da eseguire. L'informatico cerca, quando  possibile, di
scrivere delle soluzioni ai problemi sotto forma di istruzioni
che possano essere eseguite da una macchina; per fare que-
sto deve essere molto preciso, deve scomporre ogni azione in
azioni pi semplici, in azioni che la macchina considera ele-
mentari. La lista di operazioni da compiere scritte dal risolu-
tore informatico  un procedimento risolutivo per quel pro-
blema. Ma, quando il risolutore scrive l'elenco di operazioni
da compiere, ha in mente un potenziale esecutore. Quest'ese-
cutore, che potr essere di volta in volta un essere umano ma
anche una macchina o un qualche congegno automatico, do-
vr possedere tutte le capacit per eseguire le operazioni ri-
chieste e dovr saper interpretare la forrna con cui vengono
fornite le istruzioni dal risolutore.
 Ogni procedimento risolutivo identifica perci una classe di
possibili esecutori che posseggano almeno tutte le capacit ne-
cessarie per eseguire le operazioni indicate.
 Un discorso a parte merita la forma con la quale vengono
fornite queste istruzioni; il nostro esecutore deve capire esat-
tamente che cosa gli si chiede di fare con ogni istruzione e que-
sta deve corrispondere, senza ambiguit, ad un'azione che  in
grado di compiere.
 Il problema della comunicazione tra il risolutore e l'esecuto-
re di un procedimento risolutivo  centrale in tutta l'informa-
tica. Infatti, quando l'esecutore  un calcolatore,  necessario
esprimersi in modi molto particolari, con linguaggi adatti e
con molta precisione.

Lalgoritmo

 Se l'esecutore non  una persona ma un esecutore automati-
co, ad esempio una macchina o un calcolatore, i procedimenti
risolutivi devono essere chiamati algoritmi e, come  illustrato
      procedimenti risolutivi


algoritmi   I         esecutori
              automatki


dalla figura che precede, sono solo una parte di tutti i procedi-
menti risolutivi.
 Che cosa ha di pi un algoritmo rispetto a tutti gli altri proce-
dimenti risolutivi? Un algoritmo presenta tutte quelle carat-
teristiche che rendono un procedimento adatto ad un esecu-
tore automatico, considerando che in questo caso non  pos-
sibile far ricorso a doti umane, ad esempio l'iniziativa perso-
nale. Evidentemente, un procedimento risolutivo per un
esecutore automatico deve prevedere qualcosa in pi, deve
essere pi preciso ed analitico; owero, deve configurarsi
come una sequenza di ordini elementari, ciascuno effettiva-
mente comprensibile ed eseguibile dalla macchina.
 Pertanto, la prima fondamentale caratteristica di un algoritmo 
che ogni ordine deve essere espresso in modo non ambiguo;
deve cio essere interpretabile in un solo modo e deve fare rife-
rimento ad una precisa azione eseguibile dall'esecutore. E im-
plicita un'altra caratteristica degli algoritmi, oltre alla non ambi-
guit. Ogni ordine deve corrispondere ad un'unica e determina-
ta azione, senza alcun carico di scelta per l'esecutore. La frase
scrivi il numero 1, richiede che venga prodotta una e una sola
cosa: la scrittura del numero 1. Se significasse puoi scrivere il
numero 1 oppure il numero 3, questo comporterebbe una li-
bert che risulterebbe paralizzante per un calcolatore!
 In questo senso, si dice che un algoritmo, in quanto richiede
di eseguire una determinata azione in corrispondenza ad ogni
comando,  deterministico.
 Naturalmente, come per qualsiasi altro procedimento riso-
lutivo, la sequenza degli ordini, in un algoritmo, deve esserefi-
nita; non  infatti possibile prevedere una lista infinita di ope-
razioni da effettuare.
 Ma ancora, un algoritmo che si rispetti deve produrre dei

dati finali, e deve perci avere un termine, pur non mettendo
un limite al numero (comunque finito!) di operazioni che de-
vono essere eseguite per arrivare alla fine dell'esecuzione.
Questo comporta che si chieda di eseguire un numero finito
di operazioni e che ogni operazione preveda un tempo finito.
 In conclusione, il calcolatore, cos com', non  assolutamen-
te in grado di fare nulla. Per poter risolvere un problema con
il calcolatore,  necessario, dopo avere definito adeguata-
ment il problema, trovare un algoritmo di soluzione e, solo a
questo punto, utilizzare il calcolatore facendo in modo che
esegua l'algoritmo.
 Essendo il calcolatore un esecutore automatico, un automa,
perch questo automa risolva un problema  necessario:

 - sapere quali siano le capacit di esecutore del calcolatore;
 - fornire un algoritmo che risolva il problema (il vero risolu-
tore  umano!);
 - esprimere questo algoritmo in un linguaggio comprensibile
e univocamente decifrabile dal calcolatore.

 In sintesi, le attivit svolte rispettivamente dal risolutore e
dall'esecutore sono queste:


    RISOLUTORE       \         /    ESECUTORE

Analiza il problema               Acquisisce l'algoritmo

Formula l'algoritmo               Esegue l'algoritmo

                                             fornendo risultati
Comunica l'algoritmo
all'esecutore



 Dati un problema e un algoritmo,  possibile decidere con
certezza che l'algoritmo risolve correttamente il problema?
Come si fa ad individuare gli errori in un algoritmo e correg-
gerli in modo da renderlo corretto? La risposta a queste do-
mande costituisce un ampio settore dell'informatica teorica,
I'analisi degli algoritmi. Esistono metodi di tipo diverso (me-
todi basati su test e metodi formali) ma  lecito domandarsi:
sar possibile trovare un algoritmo per fare algoritmi? vve-
ro, esiste un procedimento automatico per generare algoritmi
garantiti e perfetti? La risposta a questa domanda : no! Pur-
troppo non ci sono neppure delle vaghe speranze:  stato di-
mostrato che un super-algoritmo di questo tipo non pu esi-
stere e quindi l'attivit di fare algoritmi  sempre in qualche
modo artigianale, ogni volta nuova e diversa.

Strutture di controllo

 Per rendere pi agevole l'attivit di algoritmizzazione, e per
consentire un facile controllo dei singoli algoritmi, si preferi-
sce articolare un algoritmo in un numero molto limitato di
parti elementari, variamente composte tra lor. Come si ap-
profondir nel seguito, I'algoritmo, per poter essere eseguito
da un calcolatore, dovr essere trasformato in programma.
L'attivit di predisporre programmi  chiamata programma-
zione. Nella storia dell'informatica, I'attivit di programma-
zione (e di algoritmizzazione)  stata inizialmente poco siste-
matica, ma presto si  convenuto sulla necessit di elaborare
delle modalit e regole per consentire di rendere la program-
mazione pi funzionale alla generazione di buoni algoritmi e,
quindi, di buoni programmi.
 In questo contesto trova collocazione la programmazione
strutturata. Con questo termine si intende un insieme di prin-
cpi, formulati nei primi anni Settanta, per migliorare la qua-
lit della programmazione. Il principio fondamentale della
programmazione strutturata prevede di usare, nella defini-
zione di un algoritmo, solo le seguenti strutture di controllo:

 - la sequenza;
 - la selezione;
 - I'iterazione.

 La programmazione non strutturata, che non segue questo
vincolo,  accusata di rendere potenzialmente illeggibili gli al-
goritmi e i programmi corrispondenti.
 Un importante teorema della storia dell'informatica, il teorema
diBohm-Jacopini, garantisce che ogni algoritmo pu essere defi-
nito facendo ricorso solo a queste tre strutture base di controllo.
 Si supponga di voler definire il seguente algoritmo: leggere
un numerO, moltiplicarlo per due, stampare il risultato. Le
operazioni previste sono tre e costituiscono logicamente una
sequenza, la pi semplice tra le tre strutture di controllo. Nel
definire algoritmi, si adotta spesso una forma grafica per vi-
sualizzare queste strutture. Nella modalit grafica secondo i
diagrammi di Nassi-Schneidermann (chiamati pi semplice-
mente NS), che verr adottata anche per i successivi diagram-
mi, I'algoritmo precedente sar cos schematizzato:


                              leggi n


             moltiplica n per 2


                          stampa risultato


 L'algoritmo  costituito da tre rettangoli sovrapposti, ogni ret-
tangolo contiene un'operazione. Naturalmente, la sola struttura
di sequenza non consentirebbe di descrivere appropriatamente
algoritmi appena pi complessi. Se si modifica il precedente al-
goritmo in questo modo: leggere un numero, se il numero  po-
sitivo stampare 1, altrimenti stampare -1, in questo caso  ne-
cessario introdurre un'altra struttura: laselezione. La struttura di
selezione consente di indicare quali operazioni svolgere, al veri-
ficarsi o meno di una certa condizione (nell'esempio, la condi-
zione  che il numero sia positivo). L'algoritmo, contenente la
struttura di selezione, sar cos schematizzato:


                              leggi n





                      stampa 1     stampa -1


 L'algoritmo  costituito, in questo caso, dalla sequenza di
un'operazione, il primo rettangolo, e da una struttura di se-
lezione. Nella struttura di selezione si separano, anche grafi-
camente, le due operazioni che vengono eseguite in alternati-
va; se il numero  positivo (la condizione n>0) allora viene
eseguita l'operazione scritta nel riquadro sotto il simbolo +,
altrimenti quella nel riquadro sotto il simbolo -.
 Per concludere la presentazione delle tre strutture di con-
trollo, si consideri l'algoritmo leggere un numero, se il nu-
mero  positivo, stampare a ritroso tutti i numeri, da quello
precedente a quello letto, fino a 0; se il numero  negativo non
fare nulla. L'algoritmo presenta evidentemente un procedi-
mento ripetitivo: dal numero dato bisogna passare al prece-
dente e stamparlo, da questo ancora al precedente, ecc. Non 
possibile utilizzare una struttura di sequenza: i numeri di ret-
tangoli da utilizzare dovrebbero infatti dipendere dal valore
che viene letto. La rappresentazione grafica dell'algoritmo,
con una struttura ripetitiva, potrebbe essere:


                                leggi n


                          finch n > O esegui
 L'algoritmo  costituito dalla sequenza dell'operazione di let-
tura e dal blocco ripetitivo. In questo blocco viene inizialmente
analizzata la condizione, se la condizione non  verificata (il nu-
mero  negativo o uguale a 0) si esce dalla struttura, altrimenti si
eseguono le operazioni previste nel rettangolo pi interno, che
sono quelle che verranno ripetute pi volte. La prima operazio-
ne (n ~ n -1) indica di sottrarre 1 ad n e di mettere il valore ot-
tenuto in n; la seconda operazione  la consueta stampa del va-
lore di n, gi vista nei precedenti algoritmi. Una volta eseguite le
due operazioni interne, viene valutata nuovamente la condizio-
ne all'inizio della struttura ripetitiva e il procedimento ricomin-
cia. Se, nell'esecuzione di questo algoritmo, viene letto il nume-
ro 3, verranno stampati i valori 2,1, 0.

 Questo modo di delineare l'algoritmo adotta la tecnica di sud-
dividerlo in parti elementari, ciascuna con una struttura ricono-
scibile. L'uso di questi blocchi di controllo, rappresentati in for-
ma grafica (come i diagrammi NS) o in altro modo, consente la
composizione di operazioni che, nel loro insieme, costituiscono
una procedura. In genere, ad una procedura viene attribuito un
nome, che la caratterizza.
 Ad esempio, il blocco utilizzato per descrivere la struttura ri-
petitiva potrebbe essere chiamato stampa-indietro ed essere
utilizzato, in questa forma, per tutti quegli algoritmi che ri-
chiedono di eseguire quelle operazioni. Il poter dare un nome
ad una procedura e, successivamente, definirne in dettaglio i
vari elementi, costituisce una tecnica chiamata top-down
(dall'alto verso il basso): con questa modalit  possibile do-
minare meglio la complessit di un problema, scomponendo
la sua soluzione in parti elementari da risolvere separatamente.

Dah semplici e dati strutturati

 Tutte le strutture di controllo operano su dati. Nel considerare
i dati senza alcun riferimento al come il singolo elaboratore  in
grado di gestire e operare sui dati, ci si riferisce a un tipo astratto
di dato. Si definisce tipo di dato un insieme di valori e l'insieme
delle operazioni che si possono compiere su quei valori.
 I dati si distinguono in semplici e strutturati. I dati semplici
non sono ulteriormente scomponibili, i dati strutturati risulta-
no definiti a partire da dati semplici o da altri dati gi def~niti.
 Il tipo semplice pi elementare  quello costituito dai due va-
lori di verit, vero e falso. Questo tipo  spesso chiamato tipo
booleano (in omaggio a George Boole, padre della logica boo-
leana). Le operazioni possibili su questo insieme di due valori
sono le operazioni logiche di and (congiunzione), or (disgiun-
zione), not (negazione).
 Le tre operazioni sono definibili attraverso le tabelle seguen-
ti, dette tavole di verit:

NOT =
vero falso
falso vero
 Un dato di tipo booleano pu quindi assumere uno dei pos-
sibili valori, vero o falso. Ma non sempre un dato booleano 
presente in forma esplicita; come si vede anche dagli esempi
precedenti, spesso nelle strutture di controllo sono presenti
espressioni che contengono una condizione (ad esempio,
n>0). Queste espressioni, espressioni condizionali, una volta
valutate, restituiscono un valore che  di tipo booleano, la
condizione  vera o falsa. Il tipo booleano, pur essendo il tipo
di dato pi elementare, assume quindi un ruolo essenziale nel-
la costruzione di algoritmi.
 Un altro tipo di dato semplice  il tipo carattere. L'insieme
dei valori di questo tipo  dato da tutti i simboli che sono rico-
noscibili dall'automa elaboratore, caratteri alfabetici, nume-
rici, simboli speciali e di punteggiatura. Le operazioni effet-
tuabili su questo tipo non sono molte: i caratteri risultano ave-
re un ordinamento,  possibile quindi, dato un carattere, pas-
sare al successivo o al precedente o, ancora, individuare il
carattere che si trova in una certa posizione.
 Naturalmente, un ruolo essenziale assumono i dati di tipo
numerico. Tra i dati numerici si distinguono i dati di tipo inte-
ro e quelli di tipo reale.
 Il tipo intero  costituito da un insieme di valori compresi in
un certo intervallo, da un minimo ad un massimo. Si tratta
quindi di un insieme finito di valori, che dipende, per quanto
riguarda il numero degli elementi, da una serie di fattori legati
all'elaboratore, come si chiarir nel seguito. Le operazioni
possibili su dati di tipo intero sono almeno tutte quelle dell'arit-
metica elementare (+, -, /, *); in ambito matematico, queste
operazioni, tranne la divisione, danno come risultato sempre un
elemento intero (I'insieme matematico degli interi  infini-
to!). In ambito informatico, nel trattare il tipo intero, ci si tro-
ver a dover risolvere il problema dato dal fatto che un'opera-
zione tra due numeri interi (ad esempio una moltiplicazione)
pu non dare il risultato previsto, perch quel valore non 
compreso nell'intervallo degli interi previsto dalla macchina
presa in considerazione. Anche questo problema verr affron-
tato successivamente, quando si considerer come la macchi-
na  in grado di trattare i dati.
 Il tipo reale, in ambito informatico,  in verit solo un sotto-
insieme dell'insieme matematico dei numeri razionali e,
come per il tipo intero, ha necessariamente delle limitazioni,
esiste un minimo e un massimo anche per i valori di questo
tipo. Anche il tipo reale  caratterizzato dalle usuali operazio-
ni antmetiche, con le considerazioni fatte per il tipo intero.
 I dati fin qui citati sono tutti di tipo semplice, in molte situa-
zioni  per necessario ricorrere all'associazione di dati in
modo da costituire dati strutturati, cio composti da elementi
pi semplici. Se, ad esempio, si vuole ordinare un insieme di
elementi,  necessario prima raggrupparli e poi procedere
all'ordinamento.
 Un tipico dato strutturato  quello costituito da un aggregato
di elementi, tutti dello stesso tipo, noto con il nome di array o
vettore, cos schematizzabile:

                               I A |

     2   3   4   5   6   7   8   9   10

 I valori vengono inseriti nelle singole caselle e ad essi si pu
accedere facendo riferimento alla loro posizione nell'ambito
dell'intera struttura. Ad esempio, I'elemento A  stato inseri-
to nella casella di posizione 6. In genere, i possibili valori delle
posizioni sono assunte, di volta in volta, da una variabile che
assume il ruolo di indice e che consente di accedere ai singoli
elementi dell'array.
 La possibilit di lavorare con dati strutturati consente di af-
frontare e risolvere problemi di una certa complessit e di
mantenere un'organizzazione dei dati, spesso molto vicina
alla situazione reale che rappresenta. Ad esempio, i punteggi
di una classifica potrebbero essere inseriti in un array, come
nella figura che segue: si tratta di dati tutti dello stesso tipo,
numerico; esiste un primo della classifica, e il suo punteggio
sar inserito nel primo elemento, esiste il secondo, ecc.

          52 1 45 1 44 1 40 1 38 1 37 1 36 1 30 1 25 1 20

     2   3   4   5   6   7   8   9   10

 Se gli elementi dell'array sono di tipo carattere, il tipo viene
spesso chiamato stringa. Quando  possibile utilizzare la strin-
ga come tipo autonomo, e non come semplice array di carat-
teri, le operazioni di lettura e stampa degli elementi risultano
plU agili.
 L'array presentato  ad una sola dimensione ma, in genere, 
possibile considerare array anche a due o pi dimensioni. Ad
esempio, una tavola pitagorica  generalmente rappresentata
con una struttura di array a due dimensioni:





 In casi come questo, per poter accedere ad un singolo ele-
mento della struttura, un singolo numero,  necessario utiliz-
zare due indici, uno che individua la riga e l'altro che indivi-
dua la colonna. Ad esempio, il numero 6 si trova sia nell'ele-
mento di riga 2 e colonna 3, che in quello di riga 3 e colonna 2.
Un array a due dimensioni viene anche chiamato matrice.
 Se gli elementi da raggruppare non sono tutti dello stesso
tipo, ad esempio non tutti interi o tutti caratteri, i dati vengo-
no raccolti in un record . Un record  scomponibile in elementi
chiamati campi, ciascuno caratterizzato da un tipo. Un dato di
tipo record che consenta di raccogliere i dati anagrafici di una
persona potrebbe avere il seguente aspetto:

                             I
    nome      data nascita    sesso    residenza

 Ciascuno dei campi del record, identificato con un nome
che lo caratterizza (nome, sesso, ecc.)  un dato di un tipo
specifico; il campo sesso pu essere espresso semplice-
mente con un dato di tipo booleano, il nome con un tipo
stringa (sequenza di caratteri). In genere, dati di tipo re-
cord vengono a loro volta raggruppati in un array; in que-
sto caso, il singolo elemento dell'array sar un particolare
record e l'intera organizzazione dei dati dar luogo ad una
tabella, come nella figura seguente:

 La prima riga della tabella costituisce il primo elemento
dell'array, la seconda riga il secondo, ecc. Un raggruppa-
mento di questo genere costituisce la base ideale per schedari
e archivi di varia natura.

Strutture di dati

 I dati, nelle varie situazioni reali, sono spesso organizzati in
forme tipiche che  possibile ricondurre ad una struttura
astratta, trattabile in quanto tale. Nella figura seguente  dise-
gnato ungrafo:





 Un grafo  costituito da nodi, contenenti una unit informa-
tiva, e da archi che li congiungono. Un arco che congiunge
due nodi rappresenta una relazione che li lega. Se i nodi con-
tenessero nomi di citt, il grafo rappresentato in figura po-
trebbe costituire una mappa stradale, un arco rappresente-
rebbe una strada che congiunge due citt. Se gli archi hanno un
verso di percorrenza il grafo sar orientato, come nella figura
che segue:
L'INFORMATICA

                                ~ \





 Un particolare grafo  l'albero. In questo caso, esiste un par-
ticolare nodo, detto radice dell'albero, e gli altri nodi sono
raggruppati in sottoalberi; in un albero gli archi non costitui-
scono mai dei cicli (non  possibile, percorrendo una sequen-
za di archi, tornare su uno stesso nodo). Esempi di alberi sono
tutte le strutture di tipo tassonomico, gli alberi genea]ogici, le
strutture di tipo gerarchico. Un esempio di albero  il seguen-
te:





 Se da ogni nodo dell'albero partono al massimo due archi,
oppure nessuno, I'albero  chiamato binario (in una definizio-
ne pi rigorosa, I'albero binario  considerato un tipo di dato
autonomo, non un caso particolare di albero).
 Un tipo di dato che riveste un ruolo importante  il tipo lista.
La lista si presenta come una successione di elementi; per
ogni elemento, tranne l'ultimo, esiste l'elemento successivo. A
differenza del tipo array, I'accesso ad un elemento non awie-
ne tramite un indice, ogni elemento si raggiunge passando
prima per gli elementi precedenti.
 Una lista si pu cos raffigurare:

 Ogni elemento  costituito da almeno due parti, oltre a quel-
la riservata a contenere l'informazione che interessa, un'altra
che consente di raggiungere l'elemento successivo. L'ultimo
elemento conterr un valore che lo identifica come l'ultimo
della lista (nel disegno  stato barrato il campo che, negli altri
elementi, consente di raggiungere il successivo). Nell'operare
su liste, le operazioni pi frequenti sono l'inserimento di un
nuovo elemento in un punto qualsiasi della lista, la cancella-
zione di un elemento, I'ordinamento degli elementi in base ad
un ordine prefissato.
 Sulla base del tipo lista si possono creare nuovi tipi di dati,
caratterizzati da come vengono effettuate le operazioni prin-
cipali. Due di questi, il tipo coda e il tipopila, sono particolar-
mente interessanti perch, come si intuisce dal loro stesso
nome, hanno modalit di procedere che corrispondono a fre-
quenti situazioni reali.
 Nel tipo coda, le operazioni di inserimento e cancellazione di
un elemento awengono dagli estremi opposti della struttura,
cos come una coda allo sportello di un ufficio.
 Nel tipo pila, sia l'inserimento che l'estrazione di un elemen-
to awengono dalla stessa parte.
 La figura che segue illustra l'organizzazione a coda e quella a
pila:

inserimento

tipo coda
                         estrazione


L__ ~ ~/~                 r -,

             tipo pila





inserimento e estrazione
2. Come comunicare con l'elaboratore





La descrizione di un linguaggio

 L'informatica  la scienza dei linguaggi e delle descrizioni.
Per comunicare con il computer, un esecutore perfettamente
formalizzato ma in possesso di un insieme limitato di capaci-
t,  necessario fornire a questo una sequenza di comandi in
modo che possa produrre i risultati attesi. L'esecutore calco-
latore  una macchina che richiede procedure di comunica-
zione assolutamente rigide, per cui  impossibile servirsi del
linguaggio naturale.
 L'ideazione, la definizione, la descrizione del linguaggio con
cui realizzare questo processo di comunicazione,  uno degli
ambiti pi complessi, creativi e caratterizzanti il mondo
dell'informatica. L'informatico  un produttore e un assiduo
utilizzatore di linguaggi. Le molteplici ricerche sui meccanismi
che regolano un linguaggio hanno in vario modo coinvolto il
mondo dell'informatica.
 Nella caratterizzazione di un linguaggio entrano in gioco un
insieme di aspetti: I'aspetto lessicale (i termini utilizzati),
l'aspetto sintattico (le regole grammaticali), I'aspetto seman-
tico (il significato), I'intonazione che accompagna il discorso,
i differenti stili, gerghi o linguaggi specialistici, e tante altre
caratteristiche.
 Per affrontare un settore cos complesso e spiegare le regole
soggiacenti alla struttura della lingua, sono stati tentati diffe-
renti approcci linguistici.
 Tra questi approcci, la linguistica strutturale che si svilupp
intorno agli anni Trenta ad opera principalmente di Ferdi-
nand de Saussurre e di Leonard Bloomfield. Si cercava di at-
tenersi solo ai fenomeni osservabili, al corpo del linguaggio,
definendone gli elementi di base. Il linguaggio fu cos scompo-

       COME COMUNICARE CON L'ELABORATORE                25

sto in frasi, formate da parole, formate da suoni. Allo stesso
modo, per studiare la sintassi e trovare le principali strutture
sintattiche di una lingua.
 Un approccio alternativo, la linguistica generativa, guarda al
linguaggio come a un insieme di oggetti e teorie che sono mol-
to simili agli insiemi di assiomi e alle regole di derivazione ma-
tematica. Si potr dimostrare che una frase appartiene o meno
a una certa grammatica se c' una qualche derivazione che di-
mostra che la sua struttura  in accordo con un insieme di re-
gole, come in ambito matematico si verifica la verit di una
proposizione sulla base dell'esistenza di una prova. I maggiori
successi della grammatica generativa sono stati nel campo
della sintassi. Gli strumenti utilizzati per descrivere i linguag-
gi di programmazione hanno origine in quest'approccio, in
particolare nei lavori di Noam Chomski.
 Per rappresentare le regole grammaticali di un linguaggio ci
si pu servire di particolari forme grafiche note come dia-
grammi sintattici. Una caratteristica di questi particolari dia-
grammi  quella di distinguere tra elementi terminali ed ele-
menti non terminali del linguaggio. In particolare, gli elementi
terminali sono racchiusi dentro circonferenze o ellissi, gli ele-
menti non terminali (chiamati anche categorie sintattiche)
sono racchiusi in rettangoli.
 Si esamini, ad esempio, la seguente regola grammaticale che
stabilisce come deve essere formato un identificatore (in ge-
nere, con questo termine, si intende un nome, ad esempio il
nome di una variabile o di una funzione). Questa regola
grammaticale stabilisce che un identificatore sia costituito da
lettere alfabetiche e cifre numeriche, con il solo vincolo che il
primo simbolo sia una lettera; i simboli seguenti possono esse-
re lettere o cifre. La regola, espressa con il corrispondente
diagramma sintattico,  cos descrivibile:

IDENTIFICATORE


 =-
          26                             L l!`~FORMATICA

 I blocchi lettera e cifra saranno, a loro volta, descritti
con un altro diagramma, fino ad arrivare ai simboli terminali
del linguaggio. I diagrammi lettera e <~cifra sono molto si-
mili tra loro, questo  il diagramma lettera:

    LETTERA





 Il non terminale lettera pu essere sostituito con una qual-
siasi delle lettere previste, nel diagramma cifra questo sar
vero con le cifre numeriche.
 In sintesi, i non terminali servono per descrivere il linguaggio
(sono costituenti del metalinguaggio dei diagrammi sintattici)
e devono essere sostituiti fino ad arrivare ai reali costituenti
del linguaggio, i simboli terminali.
 Per applicare la regola che definisce l'identificatore, si pu
utilizzare un albero di derivazione sintattica, come nella figura
che segue:


                         IDENTIFICATORE




              lettera       lettera        cifra




t         g          3

>~
>~
:

        COME COMUNICARE CON L'ELABORATORE                27

 Questo albero di derivazione dimostra che il nome tg3  un
identificatore ben formato;  possibile arrivare a questo nome
percorrendo le regole previste; in un primo momento sosti-
tuendo il termine identificatore con la sequenza lettera,
lettera e cifra e, successivamente, sostituendo a ciascuna
di queste categorie sintattiche la lettera o la cifra adeguata.

 Non tutti i linguaggi sono descrivibili con gli strumenti fin
qui illustrati. Tutti  linguaggi naturali (italiano, inglese, fran-
cese e tutti i linguaggi utilizzati dall'uomo) non sono ricondu-
cibili a questo tipo di descrizione, appartengono ad un'altra
classe, pi generale e con meno vincoli nella formazione delle
proprie espressioni.
 La figura che segue illustra il rapporto tra i linguaggi, nell'in-
tero universo dei linguaggi.

>(~                        ~                UNIVERSO DEI LINGUAGGI

                                 ~=
                       artificiali \ naturali




                               \~7 Y



 L'ampio universo di tutti i linguaggi  scomponibile in una
parte costituita dai linguaggi naturali e da una parte di lin-
guaggi artificiali, generati per poter comunicare con congegni
automatici e, in generale, con le macchine. Tra questi linguag-
gi artificiali trovano posto i linguaggi di programmazione, con
il compito specifico di attuare la comunicazione tra l'uomo e il
calcolatore.
Ilprogramma e i lin~aggi di programmazione

 Una volta definito l'algoritmo di soluzione per un determinato
problema,  necessario tradurlo in un linguaggio comprensibile
dall'elaboratore. La traduzione dell'algoritmo in un linguaggio
comprensibile all'elaboratore costituisce un programma (I'insie-
me di tutti i programmi per il calcolatore costituisce il software
del nostro sistema, la parte fisica della macchina  chiamata
hardware).
 Un programma pu essere scritto direttamente in ling~aggio
macchina, oppure utilizzando uno dei molti ling,uaggi di pro-
grammazione. I vari linguaggi si collocano a diversi livelli rispetto
alla logica della macchina; si distinguono solitamente in linguag-
gi a basso livello (quelli pi vicini alla macchina) e quelli ad alto
livello (pi vicini all'uomo e meno alla macchina).

 Si chiama linguaggio macchina il linguaggio proprio dell'ela-
boratore, costituito a partire da un alfabeto di soli due simbo-
li, O e 1. Due soli simboli potrebbero sembrare pochi per poter
esprimere azioni di una certa complessit in realt  possibile
ma molto scomodo e, certamente, poco simile alle modalit
umane di esprimersi.
 Ma la limitatezza dei simboli non  un limite; i primi elabora-
tori degli anni Cinquanta erano tutti programmati utilizzando
un codice con questi due soli simboli (codice binario).
 La programmazione in linguaggio macchina, pur essendo
estremamente efficace, presenta per alcuni inconvenienti. La
descrizione delle istruzioni di un programma sulla base dei due
soli simboli 0 e 1  molto lunga e laboriosa. Ogni tipo di compu-
ter possiede il proprio linguaggio macchina, dato che questo ri-
specchia fedelmente le caratteristiche fisiche dell'elaboratore.
Le istruzioni in codice binario sono di difficile memorizzazione
da parte dell'uomo.
 Attualmente, il linguaggio macchina viene utilizzato diretta-
mente solo per scrivere alcune parti di particolari programmi
che gestiscono la parte fisica della macchina, ad esempio,
quello di accensione e inizializzazione del computer (pro-
gramma di bootstrap).
Un passo avanti verso una maggiore facilit d'uso per l'uomo

 costituito dai linguaggi di tipo assembler. L'assembler  un lin-
guaggio in cui le istruzioni, formate da brevi combinazioni di let-
tere e numeri, corrispondono ciascuna ad una singola azione
eseguibile dalla macchina. La presenza di un numero maggiore
di simboli, anche alfabetici, consente di esprimere un'opera-
zione in una forma mnemonica, di pi facile utilizzo rispetto al
linguaggio macchina. L'assembler , tuttavia, un linguaggio an-
cora molto vicino alla logica della macchina (e molto meno a
quella dll'uomo) e viene usato solo quando bisogna utilizzare al
meglio le potenzialit del calcolatore.

 I linguaggi di programmazione ad alto livello sono linguaggi che
tentano di avvicinarsi il pi possibile al linguaggio e alla logica
umana. Sono costituiti da insiemi di simboli e di parole ch~ave
(parole riconosciute dal calcolatore, ciascuna con uno specifico
ruolo) e da un insieme di regole grammatica4 regole molto rigi-
de e definite in modo da evitare ogni ambiguit. Questi linguaggi
di programmazione utilizzano di solito parole e termini mnemo-
nici (spesso in lingua inglese) che corrispondono a una o pi ope-
razioni che l'elaboratore pu compiere.
 L'elaboratore dispone di un apposito programma di tradu~one
che trasforma le istruzioni, espresse in un qualche linguaggio
di programmazione, nella corrispondente sequenza in lin-
guaggio macchina.
 Il programma di traduzione pu lavorare o come interprete o
come compilatore.
 L'interprete funziona come una sorta di traduttore simulta-
neo che traduce in linguaggio macchina le istruzioni del pro-
gramma, man mano che queste devono essere eseguite.
 Il compilatore, invece, traduce prima l'intero programma,
scritto in un linguaggio di programmazione (programma sor-
gente), in un programma scritto in linguaggio macchina (pro-
gramma oggetto) e solo a questo punto, alla fine della tradu-
zione dell'intero programma, questo potr essere eseguito. I
vantaggi e gli svantaggi di queste due diverse modalit sono
legati al tipo di linguaggio a disposizione; non sempre  possi-
bile, per lo stesso linguaggio, avere a disposizione sia l'inter-
prete che il compilatore; qualora ci si trovi in questa situazio-
ne, in genere l'interprete  pi utile nella fase di messa a pun-
to del programma (si pu vedere immediatamente il risultato
         30                             L'INFORMATICA

di una singola istruzione) mentre il compilatore viene usato
nella fase finale, quando si tratta di produrre e conservare la
versione in linguaggio macchina dell'intero programma,
pronto per andare in esecuzione.
 I pi noti tra i linguaggi di programmazione ad alto livello
sono:

 - il Basic;
 - il Fortran;
- il Cobol;
- il Pascal;
- il C.

 Il Basic  un linguaggio di utilizzo generale, che non  stato
studiato per specifici campi di applicazione. Grazie alla sua
relativa semplicit si  rapidamente diffuso, soprattutto tra gli
utenti dei personal computer.
 Il Fortran  un linguaggio destinato principalmente alla ste-
sura di programmi per la risoluzione di problemi scientifici. I
dati elaborati con il Fortran sono essenzialmente numerici.
 Il Cobol  un linguaggio che viene utilizzato per realizzare
programmi per applicazioni amministrative e gestionali.
 Il Pascal  un linguaggio nato in ambito didattico che si basa
sulle regole della programmazione strutturata. Ha una larga
diffusione soprattutto in campo formativo.
 Il C  un linguaggio utilizzato in molti tipi di applicazioni di-
verse; pur essendo un linguaggio ad alto livello, consente di
accedere piuttosto facilmente ai livelli pi vicini alla logica
della macchina.

 Diversi paradigmi di programmazione

 I linguaggi fin qui descritti fanno parte di una tradizione con-
solidata e hanno caratterizzato per decenni la storia dell'in-
formatica. Questi linguaggi sono tutti basati sul paradigma
imperativo di programmazione che, pur essendo il pi diffuso,
costituisce solo una delle possibili modalit per risolvere un
problema. La distinzione pi rilevante tra le diverse modalit
riguarda il problema del controllo che consiste nello stabilire
se, e quando, eseguire una certa azione all'interno dell'algo-
ritmo risolutivo del problema.

      COME COMUNICARE CON L'ELABORATORE                31

 In generale, i linguaggi di programmazione si distinguono in
quanto portatori di uno dei fondamentali paradigmi di pro-
grammazione:

 - il paradigma imperativo (o procedurale) in cui il program-
matore si fa completamente carico del problema del controllo
e si occupa sia di che cosa si richiede dal programma sia di
come raggiungere i risultati previsti;
 - il paradigma dichiarativo in cui il problema del controllo 
demandato all'esecutore. Il programmatore specifica quindi
solo cosa si desidera dal programma e non come gli obiettivi
specificati possano essere raggiunti.

 Se i linguaggi gi citati sono di tipo procedurale, il pi noto
tra i linguaggi dichiarativi  il Prolog che, nell'ambito della
programmazione dichiarativa,  il linguaggio plU significativo
per quanto riguarda la programmazione logica, una modalit
di programmazione dichiarativa, basata essenzialmente sulla
logica matematica.
 Lo scenario attuale vede emergere sempre di pi linguaggi
basati sui diversi paradigmi di programmazione che, in qual-
che caso sono una naturale evoluzione di impostazioni gi
consolidate, in qualche altro costituiscono un differente
modo di trattare la risoluzione di problemi. Particolarmente
interessante, dalla fine degli anni Ottanta, l'approccio se-
guito dalla programmazione ad oggetti. La programmazione
ad oggetti tende a rendere maggiormente riutilizzabile il
software sviluppato per una determinata applicazione. La fi-
losofia sottesa  quella di realizzare tanti mattoncini (gli og-
getti), con i quali essere in grado di costruire facilmente pro-
grammi diversi.
 Anche la programmazione funzionale assume grande impor-
tanza per l'ottica con la quale ogni programma  realizzato.
Ogni programma  una funzione (come quelle matematiche)
che, sulla base dei dati in ingresso, produce dei risultati in
uscita. Il linguaggio pi noto nell'ambito della programma-
zione funzionale  il Lisp. Il linguaggio Lisp, utilizzato in un
contesto particolare dell'informatica, quello dell'intelligenza
artificiale,  un linguaggio con poche regole e quindi capace
di generare programmi molto compatti. Nella programma-
zione funzionale i concetti fondamentali sono quello di fun-
           32                             L'INFORMATICA

zione e di composizione di funzioni, l'espressione condizionale
e l'uso della ricorsivit.

La ricorsivit

 Il concetto di ricorsivit (o ricorsione) merita di essere appro-
fondito ulteriormente perch riveste un ruolo fondamentale
nella soluzione di problemi informatici.
 Si  gi visto, nel capitolo precedente, come la struttura ripe-
titiva consenta di ripetere un certo numero di volte determi-
nate operazioni. Uno schema alternativo a quello ripetitivo 
quello ricorsivo, basato essenzialmente sulla definizione ma-
tematica detta per induzione.
 Si esamini la seguente definizione matematica dell'oDera-
zione di somma:

 1. somma (x, 0)=x
 2. somma (x, y)= 1 + somma (x, y-1)

 In questa definizione, per definire la somma tra x e y (numeri
interi positivi), si utilizzano due regole. La regola 1 definisce
la somma tra x e il valore 0, in questo caso il risultato  x. La re-
gola 2 stabilisce come procedere per sommare due numeri
qualsiasi; come si vede, la definizione fa ricorso alla stessa
funzione somma, applicata a due valori, uno dei quali  ridot-
to rispetto al valore di partenza. La regola 1 costituisce la base
della ncorsione, la regola 2 considera il caso generale. Per me-
glio analizzare come opera la funzione appena definita, si
consideri il seguente schema di attivazione della funzione
con i valori 3 e 2. Si vuole, in sostanza, provare la funzione su
questi valori per verificare che produca il risultato atteso, 5.

        COME COMUNICARE CON L'ELABORATORE                33

 Nello schema, dopo l'attivazione dellafunzione con ivalori 3
e 2, si prova a calcolare il risultato seguendo la regola 2. Que-
sto produce il risultato 1 + somma (3,1). Il calcolo di que-
sta espressione viene sospeso perch prima deve essere calco-
lato il valore risultante della somma (3,1). Per fare questo, si
apre un ambiente pi interno, che opera con le stesse modali-
t di quello precedente. Si continua cos fino a ricadere nella
situazione descritta nella regola 1, con il secondo argomento
della funzion uguale a 0. In questo caso, si attribuisce il valo-
re del primo argomento, 3, e si chiude questo ambiente, ripor-
tando in basso a sinistra il valore della funzione nell'ambiente
corrispondente. L'avere ottenuto un valore consente, a que-
sto punto, di eseguire l'operazione rimasta sospesa nell'am-
biente precedente, di ottenere il valore per quell'ambiente e,
cos di seguito, fino ad ottenere il valore finale, 5.
 La modalit ricorsiva di risolvere i problemi, qui descritta
con un semplice esempio,  caratterizzante la programmazio-
ne funzionale in quanto il modello ricorsivo si applica in
modo naturale ad un gran numero di funzioni, ma costituisce
una modalit generale di risolvere problemi, possibile in tutti
gli ambienti di programmazione che consentono la ricorsivit.
Si tratta, di fatto, di una diversa modalit di trovare una solu-
zione, riducendo il problema in sottoproblemi pi semplici.
 Un programma ricorsivo , in genere, compatto ed elegante;
le definizioni di funzioni spesso ricalcano in modo evidente le
definizioni matematiche e il programma si analizza pertanto
in modo pi semplice. Qualche difficolt pu sorgere, per il
programmatore, per una scarsa abitudine a pensare secondo
il modello ricorsivo. Per la macchina, qualche difficolt pu
sorgere per caratteristiche fisiche non adeguate; infatti, la ne-
cessit di sospendere dei calcoli, rende indispensabile conser-
vare i dati relativi ad ogni contesto, per poterli riprendere in
un momento successivo.
3. L'architettura dell'elaboratore





La struttura logico-funzionale di un elaboratore

 L'informatica  la scienza degli elaboratori. L'elaboratore 
un esecutore di tutte le istruzioni che gli vengono fornite e,
pertanto, la sua struttura deve essere tale da consentire lo
svolgimento di questo ruolo. Quali capacit sono necessarie
in genere, ad un generico esecutore? Il primo passo, essenzia-
le, dell'attivit di un esecutore,  quello di acquisire le istru-
zioni che poi dovr eseguire; sar quindi ragionevole aspet-
tarsi che un calcolatore abbia particolari dispositivi per poter
ricevere istruzioni e comandi. Per svolgere questa funzione
un qualsiasi calcolatore ha almeno una tastiera, molto simile
alle tastiere delle macchine da scrivere. Non tutte le tastiere
sono uguali fra loro, alcune sono pi ampie e ricche di tasti, al-
tre sono pi limitate; tutte hanno comunque, sempre, almeno
i tasti con le lettere dell'alfabeto e le dieci cifre numeriche, i
simboli di punteggiatura, e un certo numero di simboli speciali
come ' * &. In generale, tutto quello che pu essere immesso
nel calcolatore attraverso la tastiera costituisce un carattere
Lettere, numeri, simboli di punteggiatura, simboli speciali;
sono quindi dei caratteri con i quali verranno comunicati i
programmi e gli altri comandi, in una forma comprensibile al
calcolatore.
 Ma, sempre nell'ambito della comunicazione tra l'uomo e il
calcolatore, ci sar un momento, altrettanto essenziale, in cui
il calcolatore dovr fornire i risultati della sua elaborazione. 
allora indispensabile un altro dispositivo che consenta di
emettere e visualizzare questi risultati. Per svolgere questa
funzione il dispositivo pi usato  certamente il video, anche
se in genere un calcolatore  dotato di altre apparecchiature
che rientrano in questa categoria, ad esempio le stampanti.

        L'ARCHITETTURA DELL'ELABORATORE                  ~S5

 Se un elaboratore  dotato di una tastiera per l'acquisizione
dei programmi, e di un video per la produzione dei risultati, di
che cos'altro avr bisogno? Ovviamente, di qualcosa che con-
senta di effettuare le operazioni previste dal suo bagaglio di
capacit; tra queste ci sar quella di saper fare le quattro ope-
razioni, e quindi ci dovr essere un dispositivo in grado di ese-
guirle. Questo dispositivo, insieme a tutti gli altri pi o meno
complessi che consentono al calcolatore di effettuare opera-
zioni, fa parte dll'unit di elaborazione. Ma ancora non basta.
Se qualcuno chiedesse a qualcun altro di eseguire una lunga
serie di operazioni, questo si potrebbe comportare in due
modi: imparare a memoria gli ordini che gli vengono dati e,
durante l'esecuzione di questi, sforzarsi di ricordare, di volta
in volta, tutti i risultati intermedi che portano al risultato fina-
le, oppure, pi ragionevolmente, prendere carta e penna e,
prima, scrivere in sequenza i passi da eseguire e, man mano,
appuntare sulla carta i vari risultati, fino al risultato finale. In
tutti e due i casi avrebbe bisogno di una funzione di memorizza-
zione svolta o dalla sua personale memoria, con qualche sfor-
zo, o dal foglio di carta sul quale ha fatto le sue annotazioni.
 Anche il calcolatore avr bisogno di memorizzare sia l'algo-
ritmo che i risultati delle operazioni; il dispositivo adatto a
questo scopo  chiamato memoria.
 E possibile, quindi, individuare la struttura logico-funzionale di
un calcolatore. Il nome logico-funzionale lascia intendere che
questa descrizione non si occupa di come il calcolatore  rea-
lizzato fisicamente, di circuiti elettrici e dispositivi fisici di va-
ria natura, ma si caratterizza solo per le funzioni che devono
essere svolte.
 Questa struttura, nota anche come modello di Von Neumann,

                       unit l ir~resso/uscda
           36                             L'INFORMATICA
 rappresentabile con lo schema della pagina precedente.

 La memoria  quel componente del calcolatore in grado di
svolgere la funzione di memorizzare: dovranno poter essere
memorizzati sia i programmi da eseguire sia i dati sui quali il
calcolatore deve operare.

 Il processore  il componente esecutore che dovr essere in
grado di eseguire i singoli passi di un programma. Il processo-
re, noto con il nome di cPu (Central Processing Unit), comuni-
ca attraverso delle linee di comunicazione sia con la memoria
centrale che con le varie unit di ingresso/uscita. Componenti
fondamentali della cPu sono:

 - unit di controllo;
 - unit aritrnetico-logica.

 L'unit di controllo organizza e gestisce l'elaborazione dei dati
e controlla il funzionamento delle altre componenti del compu-
ter; I'unit aritmetico-logica esegue i calcoli aritmetici e le ope-
razioni logiche.
 Le unit di ingresso/uscita (spesso indicate come unit di in-
put/output, spesso abbreviato in unit di I/O) hanno il ruolo di
introdurre i dati nell'elaboratore e di emetterli all'esterno;
sono unit di questo tipo la tastiera, la stampante, il video e
tutte quelle unit accessorie che hanno il ruolo di comunica-
zione tra la macchina e l'uomo che la utilizza. Tra le unit di
input, la tastiera consente di immettere dati e programmi
nell'elaboratore, oppure di formulare richieste o impartire
istruzioni alla macchina. Ma, dati e programmi possono esse-
re inseriti nell'elaboratore anche tramite altre unit di input
quali dischi magnetici, lettori ottici, ecc. Le unit di output ri-
portano i risultati delle elaborazioni nella forma desiderata
dall'utente (stampata, video, magnetica, ecc.); le pi comuni
sono il video, la stampante e le unit a dischi.

La rappresentazione delle inforrnazioni

 La comunicazione tra l'uomo e la macchina deve fare i conti
con il modo con il quale il calcolatore  in grado di rappresen-
tare le nostre informazioni. Per l'uomo, il problema della rap-

     L'ARCHITE~TURA DELL'ELABORATORE 37

     presentazione di un elemento, ad esempio di un numero, ha
     spesso coinciso con il problema della sua scrittura. Anche un
     semplice numero naturale, il numero 3, pu essere scritto in
     vari modi, gli antichi romani adottavano, per esempio, la rap-
     presentazione III.
     Nel caso di un calcolatore, rappresentare qualcosa significa re-
     gistrarla su un dispositivo di memorizzazione, con modalit e
     limiti che dipendono dalla macchina stessa. Si impone, allora,
     una riflessione su quel componente del calcolatore che viene
     utilizzato per effettuare le registrazioni, la memoria.
     E possibile pensare alla memoria come ad una cassettiera
     molto grande, nella quale  possibile inserire, uno per casset-
     to, gli elementi che ci interessano. Ma questo comporta che, per
     quanto grande sia la memoria, essa contenga necessariamente
     un numero finito di elementi (il numero dei suoi cassetti), e
     che ogni elemento contenuto nei vari elementi, abbia dimen-
     sione finita (la dimensione dei cassetti). E quindi possibile regi-
t    strare contemporaneamente solo un numero finito di dati; e cia-
     scun dato registrato non pu superare determinate dimensioni.
      Per quanto a volte sembri impossibile, l'informatica tratta
     solo quantit finite di elementi, si occupa solo di insiemi finiti,
     a differenza dell'ambito proprio della matematica che, con di-
     sinvoltura, tratta insiemi infiniti come, ad esempio, l'insieme
     di tutti i numeri naturali (0,1, 2, 3, 4...).
 Si consideri allora uno dei cassetti della memoria del calcola-
tore, che  chiamato, pi propriamente, locazione; una loca-
zione  costituita da elementi pi piccoli, ognuno dei quali,
chiamato bit, pu contenere solo uno dei possibili valori, o O o 1.
 Lo schema seguente pu rappresentare una possibile loca-
zione di 8 bit:

1  0  0 1  1  1  0  1

 Ciascun elemento sar dunque memorizzato sfruttando que-
sta modalit di rappresentazione, chiamata rappresentazione
binaria. Non sar possibile scrivere una sequenza comunque
lunga; il numero di bit contenuti in ciascuna locazione sar un
limite imposto a ciascuna locazione della memoria.
 Considerando i tipi di dati, come illustrati nel primo capito-
lo,  evidente come il tipo di dato pi semplice, il tipo boolea-
no,  rappresentabile in memoria con un solo bit. Ad esempio,
si pu associare 1 al valore vero e 0 al valore falso, (naturalmente 
si pu fare anche viceversa). Gli altri titpi di dati hanno
bisogno di ulteriore approfondimento.

 La rappresentazione dei caratteri.
Ogni carattere che  possibile immettere dalla tastiera, ha 
una rappresentazione interna costituita da una sequenza di
un numero prefissato di bit (ad esempio 8), chiamata codifica           38                             L'INFORMATICA

no,  rappresentabile in memoria con un solo bit. Ad esempio,
si pu associare 1 al valore vero e 0 al valore falso (natural-
mente, si pu fare anche viceversa). Gli altri tipi di dati hanno
bisogno di un ulteriore approfondimento.

La rappresentazione dei caratteri

 Ogni carattere che  possibile immettere dalla tastiera, ha
una rappresentazione interna costituita da una sequenza di
un numero prefissato di bit (ad esempio 8), chiamata codifica


rq~   crll Carattere ASCII Carattere ASCII Carattere ASCII

NUL
SOH
SIX
ETX
JOT
ENQ
ACK
BEL
BS
Hr
LF
VT
FF
CR
SO
Sl
DLE
DCI
DC2
DC3
DC4
NAK
SYN
ETB
CAN
EM
SUB
ESC
FS
GS
RS
US

oooooooo
oooooool
oooooolo
oooooo l l
oooooloo
ooooolol
oooool lo
ooooo l l l
oooolooo
oooolool
oooololo
oooolol l
ooool loo
ooool lol
ooool l lo
oooollll
oooloooo
oooloool
oooloolo
ooolool l
ooololoo
ooololol
ooolol lo
ooolol l l
oool looo
oool lool
oool lolo
oool lol l
oool l loo
oool l lol
oool l l lo
oool l l l l

oolooooo
oolooool
oolooolo
ooloool l
oolooloo
ooloolol
oolool lo
oolool l l
oololooo
oololool
oolololo
oololol l
oolol loo
oolol lol
oolol l lo
oolol 1 1 1
ool loooo
001 10001
ool loolo
ool lool l
ool loloo
ool lolol
001 101 10
oollolll
001 1 1000
001 1 1001
001 1 lQ10
001 1 101 1
001 1 1 100
001 1 1 101
00111110
00111111

I





@     oloooooo
A     01000001
B     01000010
C     0100001 1
D     01000100
E     01000101
F     01000110
G     01000111
H     01001000
      01001001
J     01001010
K     01001011
L     01001100
M     01001101
N     01001110
0     01001111
P     01010000
Q     01010001
R     01010010
S     0101001 1
T     01010100
Il    01010101
V     010101 10
~~~   010101 1 1
      0101 1000
      0101 1001
      0101 1010
      0101 101 1
      0101 1 100
      0101 1 101
      0101 1 1 10
      0101 1 1 1 1

o l l ooooo

a   01 100001
b   01 100010
c   01 10001 1
d   01 100100
e   01 100101
f   01 1001 10
g   01 1001 1 1

h   01 101000
i-  01 101001
    01 101010
    01 10101 1

k   01101 100
m   01101 101
n   011011 10
o   01101111
p   01 1 10000
q   01 1 10001

r   011 10010
s   01110011
t   01 1 10100
u   01 1 10101
v   01 1 101 10
w   01110111

x   01111000
y   01111001
z   01 1 1 1010
    Ol l l lnl l
    ollllloo
    olllllol
    ollllllo
DEL  01111111

  L'ARCHITETTURADELL'ELABORATORE                              39

del carattere. Sono considerati caratteri anche quelli che, an-
che se non sempre visibili, consentono di inserire i dati in una
determinata forma, ad esempio, il ritorno a capo in un testo.
Ogni carattere  dunque associato ad una particolare configu-
razione di bit, l'insieme di tutte queste informazioni costitui-
sce un codice. Il modo pi semplice per rappresentare un co-
dice  sotto forma di tabella, che consente di visualizzare l'as-
sociazione tra ciascun carattere e la sua codifica.
 Vi sono molti codici a disposizione, uno dei pi diffusi  il co-
dice ASCII (American Standard Code for Information Inter-
change). La figura nella pagina a fronte  la tabella corrispon-
dente al codice ASCII.
 Ogni volta che viene inserito un carattere dalla tastiera, un
dispositivo consente di trasforrnare il carattere immesso nella
corrispondente codifica e, viceversa, quando d-all'interno
dell'elaboratore, un carattere deve essere visualizzato. Si ope-
ra quindi secondo lo schema seguente:


                                1





. ~ ~ ..../
             ...........



La rappresentazione dei numeri interi e di quelli reali

 Da quanto precede, tutti gli oggetti utilizzabili dall'elaborato-
re sono interessati dalle limitazioni fisiche per la loro rappre-
sentazione. Per quanto riguarda i numeri interi, se si ipotizza
che un elaboratore rappresenti un numero intero con 16 bit, in
questo caso, il numero maggiore che si pu rappresentare 
1111111111111111.
 Con questa modalit non si tiene per conto del segno del
numero, che potrebbe essere positivo o negativo (si vuole rap-
presentare non solo 3 ma anche -3).
          40                             L'INFORMATICA

 Un modo migliore  allora quello di utilizzare un bit per il
segno (che potr contenere 0 se il numero  positivo e 1 se il
numero  negativo) e gli altri 15 per il valore assoluto (il nu-
mero senza il segno).
 Il numero maggiore rappresentabile sar dunque 215 (32767),
il minore -215 + 1(32767). Sar pertanto disponibile solo il se-
guente intervallo di numeri interi:

-32768                

 Quando, in seguito all'esecuzione delle singole operazioni, si
dovesse raggiungere un risultato intero non compreso in que-
sto intervallo, si verificherebbe un errore (chiamato di over-
flow) che pu essere gestito in modi diversi da ciascun elabo-
ratore. E possibile che l'errore venga semplicemente segnala-
to e venga pertanto interrotta l'elaborazione oppure che ven-
ga considerato l'intervallo dei valori interi come un insieme
circolare e, una volta raggiunto un estremo, si passi dalla
parte opposta (il numero successivo a 32767 sarebbe in questo
caso-32768). Conoscere questi limiti della macchina, e come
vengono gestiti,  essenziale nella valutazione dell'attendibili-
t dei risultati ottenuti.
 Per quanto riguarda i numeri reali, prima ancora di analizza-
re la rappresentazione della macchina,  necessario fare alcu-
ne considerazioni. Un numero reale pu essere scritto nella
forma in notazione decimale con la virgola (in ambito informa-
tico si preferisce la notazione anglosassone con il punto) o in
notazione esponenziale.
 Nella notazione decimale si trovano scritture di tipo 7.12 op-
pure - 0.195.
 Nella notazione esponenziale, il numero  rappresentato da
alcune cifre significative e dal suo ordine di grandezza, in ge-
nere preceduto dal simbolo E (esponente). Ad esempio il nu-
mero 3.5 E 3 significa 3.5 moltiplicato per 103, cio 3500.
 La rappresentazione della macchina adotter prevalente-
mente la notazione esponenziale; sar quindi necessario me-
morizzare sia le cifre significative, sia il valore dell'esponente.
 Il numero di cifre con le quali poter esprimere l'esponente,
definisce la precisione di una rappresentazione. I limiti nelle
dimensioni delle locazioni della memoria, possono portare ad

+32767

       L'ARCHITETTURA DELL'ELABORATORE                 41

una rappresentazione approssimata di un numero e anche il
risultato di una elaborazione pu risentire in vario modo di
approssimazioni effettuate nel corso dell'esecuzione delle sin-
gole operazioni. Pertanto, anche nel caso dei numeri reali,
nell'analizzare i dati prodotti dall'elaboratore,  necessario
valutare l'incidenza di eventuali approssimazioni.
4. La calcolabilit e la complessit





Problemi computabili e non computabili

 L'informatica  la scienza del calcolabile. L'informatica non si
occupa solo di architetture fisiche degli elaboratori; esiste un
ambito, quello dell'informatica teorica, che  del tutto indipen-
dente dal progresso tecnologico e che studia tutte le relazioni
che legano i concetti di calcolo, automa e linguaggio formale. I
linguaggi formali sono tutti quei linguaggi che, come i linguaggi
di programmazione, sono definiti da regole rigorose per la for-
ma delle espressioni che appartengono al linguaggio (livello sin-
tattico) e per il loro significato (livello semantico).
 Sono stati proposti vari modelli di calcolo per definire il con-
cetto di calcolabile. Uno dei pi rilevanti risale ad Alan Turing
che, nel 1936 (prima della costruzione di un vero calcolatore)
propose un modello logico di macchina di calcolo. Questo
modello, noto come macchina di Turing,  cos rappresentabi-




                                ~:1

 La macchina  costituita da un dispositivo che ha a disposi-
zione un nastro infinito, che costituisce una memoria, sul qua-
le pu leggere e scrivere simboli, spostandosi nelle due dire-
zioni, di una casella per volta. Sembra impossibile ma, un
meccanismo di questo genere,  in grado di eseguire tutti i cal-
coli eseguibili da un moderno calcolatore. Per fare un sempli-
ce esempio, per eseguire il calcolo 2+3, la macchina potr ope-
rare rappresentando il calcolo con un numero ridotto di sim-

       LA CALCOLABILITA E LA COMPLESSITA                  43

boli, ad esempio * e I; lo stato del nastro all'inizio e alla fine
del processo potrebbero essere i seguenti:
              stato iniziale del nastro
* | I | I I * I I | I | I | * |


    stato ~inale del nastro
    | * | I | I | I | I | I | * l

 Nello stato iniziale il nastro contiene una rappresentazione
simbolica dell'espressione da eseguire (per i numeri 2 e 3 vie-
ne adottata una rappresentazione simile a quella dei numeri
romani), i movimenti che la macchina compie sul nastro, leg-
gendo e scrivendo simboli, costituiscono, di fatto, una realiz-
zazione dell'operazione di somma; il nastro, cos come viene
lasciato, rappresenta il risultato.
 Ogni macchina di Turing, considerando gli stati iniziali e fi-
nali del nastro, e la sequenza degli spostamenti da effettuare,
rappresenta uno specifico algoritmo. Il concetto di algoritmo
si sovrappone pertanto a quello di macchina di Turing. Si pu
dire che un problema  calcolabile se esiste un algoritmo che
lo risolva e, per quanto appena detto, se esiste una macchina
di Turing che lo risolva.
 Esistono dei problemi per i quali non esiste nessuna macchina
di Turing che li risolva, sono i problemi non calcolabili. Lo stesso
Turing ha formulato uno dei problemi non calcolabili, noto
come problema dell'arresto: dato un generico programma e i
suoi dati di ingresso, decidere se l'esecutore si arrester o
meno. Questo problema, pur essendo risolto in molti casi
particolari, non  risolubile per tutti i casi.
 Anche assumendo altri modelli di calcolo, diversi dalla mac-
china di Turing,  stato dimostrato che tutti questi modelli
sono tra di loro equivalenti e quindi, un problema non calco-
labile secondo il modello della macchina di Turing, rimane
tale anche rispetto ad altri modelli. Questo risultato  noto
come tesi di Church, e costituisce un criterio generalmente ac-
cettato per stabilire il confine tra il computabile (calcolabile o
risolvibile con le macchine) e il non computabile.
          44                             L'INFORMATICA

 L'insieme di tutti i problemi teoricamente affrontabili si pu
quindi ripartire come nella seguente figura:


                 UNIVERSO Dl TUITI I PROBLEMI



                   Problemi~
               \ non computabili

                Problemi
              \ computabili





Complessit ed efficienza degli algoritmi

 Stabilito che i problemi computabili sono quelli per i quali
esiste un algoritmo che li risolva, questi possono essere rag-
gruppati in classi di complessit. In prima approssimazione 
possibile individuare due grandi classi: la classe dei problemi
la cui soluzione  al pi polinomiale, e quella la cui soluzione
 al pi esponenziale. Per capire meglio in che cosa consista
questa differenza, si consideri un problema per il quale siano
stati elaborati vari algoritmi risolutivi; questi algoritmi si ca-
ratterizzano, in genere, per la loro diversa efficienza.
 Per misurare l'efficienza di un algoritmo, le misure di effi-
cienza sono:

 - il tempo impiegato per eseguire l'algoritmo;
 - la quantit di memoria necessaria per l'esecuzione.

 Tra questi due criteri di efficienza il pi rilevante  senza
dubbio il tempo. Volendo misurare l'efficienza di due algorit-
mi rispetto al tempo di elaborazione, non  sufficiente far ese-
guire i programmi corrispondenti ai diversi algoritmi e con-
frontare i diversi tempi di esecuzione. Questo metodo di valu-
tazione risente infatti del linguaggio utilizzato per i program-
mi, del programma di traduzione in codice oggetto (interprete

    LA CALCOLAi31LlTA E LA cOMPLESSlTA                  45

o compilatore), delle caratteristiche del calcolatore sul quale
il programma  in esecuzione.
 Per tutte queste ragioni, per determinare il tempo di esecu-
zione viene preso in considerazione direttamente l'algoritmo
perch:

 - un algoritmo rappresenta una descrizione generale di tutto
il processo di calcolo;
- - l'algoritmo non considera tutta una serie di dettagli realiz-
     zativi, legati al particolare linguaggio di programmazione;
 - il tempo di esecuzione dell'algoritmo  indicativo del tem-
po di esecuzione dei corrispondenti programmi.

 Per determinare il tempo di esecuzione di un algoritmo che
risulti indipendente dal contesto della sua esecuzione,  ne-
cessario operare un'approssimazione sui dati del problema. Il
tempo necessario ad eseguire l'algoritmo deve essere messo
in rapporto ad una misura, generalmente indicata come di-
mensione dei dati di ingresso. Non  importante calcolare il
tempo effettivo di esecuzione dell'algoritmo, ci si pu accon-
tentare di una valutazione approssimativa, e questo  vero an-
che per quanto riguarda lo spazio di memoria occupato dal
programma corrispondente all'algoritmo analizzato.
 La misura dell'efficienza di un algoritmo, la sua complessit,
pu essere definita valutando il numero delle istruzioni ele-
mentari che vengono eseguite, in funzione della dimensione
dei dati di ingresso. Ad esempio, se l'algoritmo ha lo scopo di
sommare n numeri, la dimensione dei dati di ingresso pu es-
sere data dal numero n dei dati da sommare. Un algoritmo di
questo tipo esegue un numero di istruzioni proporzionali alla
dimensione dei dati in ingresso n; altri algoritmi, ad esempio
alcuni algoritmi di ordinamento, eseguono un numero di istru-
zioni proporzionali ad n2, altri a n3 o 2n. Dopo un'analisi dei ri-
sultati  possibile compilare la tabella riportata nella pagina se-
guente che illustra i tempi di esecuzione al variare della com-
plessit dell'algoritmo e della dimensione dei dati di ingresso,
a parit di tempo di esecuzione per n=1(0.000001 sec.).
 Dalla tabella si vede chiaramente che i valori di complessit
pi critici sono quelli esponenziali, cio quelli in cui la dimen-
sione dell'ingresso compare come esponente nel valore di
complessit. I problemi per i quali l'algoritmo risolutivo pos-
L'INFORMATICA

siede un andamento esponenziale sono di fatto non risolvibili:
in questi casi, infatti, il tempo di risposta dell'algoritmo risulta
troppo elevato (nella tabella figurano anni e addirittura seco-
li!).

COMPLESSITA
l)FI I 'Al r.()RITMn

n = 10

0.00001
secondi

 0.0001
secondi

 0.001
secondi

DIMENSIONE DEI DATI Dl INGRESSO

 n=20     n=50    n=60

0.00002  0.00005  0.0006
secondi  secondi  secondi

 0.0004
secondi

 0.008
secondi

                  0.0025   0.0036
                  secondi  secondi

                   0.125    0.216
                  secondi  secondi

 0.001      1      35.7      366
secondi  secondo   anni    secoli

 Ma, se  una questione di tempo,  possibile pensare che il
miglioramento della tecnologia possa modificare sostanzial-
mente la situazione? Purtroppo, anche supponendo di utilizza-
re un calcolatore 1000 volte pi veloce di quelli attuali, per
quanto riguarda i problemi della classe esponenziale il miglio-
ramento  del tutto trascurabile. Questa classe di problemi ri-
mane pertanto inaccessibile sia per i calcolatori attuali che
per quelli futuri.
 In conclusione, un programma pu essere eseguito da un
calcolatore solo se, di fatto, sono disponibili una memoria di
dimensioni appropriate e una sufficiente quantit di tempo.
Se l'esecuzione di un programma richiedesse quantit di me-
moria e di tempo non disponibili, esso risulterebbe inservibile,
anche se fosse scritto nel completo rispetto delle regole della
buona programmazione.





  I5. slsteml operatlvl





Che cos' un sistema operativo

 L'informatica  la scienza dell'hardware e del sof~ware. Se il
calcolatore fosse costituito solo dalla parte hardware, non sa-
rebbe praticamente utilizzabile: esso  in grado di eseguire
istruzioni scritte solo in linguaggio macchina binario, l'unico
riconosciuto dal calcolatore. Agli albori dell'informatica, tut-
tavia, la situazione si presentava esattamente cos: l'utente del
calcolatore era costretto a lavorare solo in linguaggio macchina
e ad occuparsi direttamente di un'infinit di problemi legati al
suo specifico hardware. Il programmatore introduceva ma-
nualmente le istruzioni in codice macchina tramite una serie
di interruttori a due posizioni, corrispondenti a 0 e 1. Le per-
sone che avevano a che fare con l'informatica erano necessa-
riamente poche e molto esperte.
 Fortunatamente, all'inizio degli anni Cinquanta, ci si rese con-
to di come fosse conveniente arricchire l'hardware con program-
mi in grado di consentire all'utente di utilizzare il computer in
modo pi semplice, facilitando l'interazione uomo-macchina.
Nacquero, allora, i primi sistemi operativi.

Successive ~enerazioni di sistemi operativi

 La prima generazione di sistemi operativi utilizzava schede e
nastri perforati per l'immissione dei dati e dei programmi e il
lavoro era organizzato secondo una modalit chiamata batch
o elaborazione a lotti. Con questa modalit, ancora oggi uti-
lizzata in alcuni settori, i blocchi di programmi vengono cari-
cati uno per volta in memoria e non viene consentita alcuna
interattivit, cio nessun intervento dell'utente durante la
fase di elaborazione. L'utente, una volta inserito il suo pro-
gramma in un blocco di lavoro, attende senza intervenire i ri-
sultati che vengono prodotti. Durante l'immissione dei dati, la
cPu rimane inattiva, con grave spreco di potenza di calcolo.
 Successivi sistemi operativi tendono a limitare questo incon-
veniente, consentendo alla cPu di elaborare le informazioni
mentreviene effettuata l'introduzione e/o la stampa dei dati. I si-
stemi operativi di questa seconda generazione adottano la tecni-
ca.della multiprogrammazione, owero la contemporanea pre-
senza in memoria principale di pi programmi. Questa modalit
 spesso congiunta con la tecnica della suddivisione di tempo
(~irne-sharalg): i programmi vengono trattati come se fossero in-
seriti in una coda circolare e a ciascuno di essi viene assegnato ci-
clicamente un certo tempo di elaborazione (quantum); alla fine
del tempo a sua disposizione il programma perde il diritto all'uso
della cPu che viene assegnata al programma successivo.
 La terza generazione di sistemi operativi  caratterizzata
dallo sviluppo di sistemi di grosse dimensioni, in grado di sod-
disfare le esigenze di molti utenti che contemporaneamente
accedono alle risorse disponibili attraverso postazioni con
terminali, anche fisicamente lontane dalla collocazione del
grande calcolatore.
 Nei sistemi degli anni Settanta, considerati quelli della quar-
ta generazione, comincia a manifestarsi la filosofia dell'infor-
matica distribuita, resa possibile dal contemporaneo abbassa-
mento del costo dell'hardware e quindi dalla diffusione sem-
pre pi capillare di piccoli sistemi in tutti gli ambienti di lavo-
ro, nei servizi, nelle aziende in genere. L'informatica distri-
buita consente di distribuire potenza di calcolo e risorse;
eventualmente, sistemi piccoli e medi vengono collegati tra
loro in un sistema a rete, consentendo lo scambio delle infor-
mazioni. Questa sempre maggiore diffusione dell'uso di mezzi
informatici porta allo studio e allo sviluppo di interfacce sem-
pre pi vicine alla modalit umana di lavoro: il colloquio tra
utente e sistema non si svolge pi digitando sulla tastiera co-
mandi sintetici e di difficile memorizzazione ma attraverso
l'uso di rappresentazioni grafiche, dette icone, e di menu che
sempre pi tengono conto dell'utilizzo del sistema da parte di
una classe di utenti sempre pi vasta e quindi sempre pi di-
stanti dalla logica interna della macchina. Alla tradizionale
tastiera si affianca sempre di pi il mouse, uno strumento che,
come un dito aggiuntivo, consente di indicare un'icona o un
punto dello schermo e di procedere cos, semplicemente, all'at-
tivazione di una nuova operazione. Il modo di presentarsi dei
nuovi sistemi operativi consente, pertanto, di svolgere tutte le
operazioni nel modo il pi possibile immediato e semplice.
 In presenza di pi di una cPu, i sistemi di elaborazione sono
chiamati sistemi concorrenti. In questo caso l'elaborazione di
istruzioni pu awenire, nello stesso istante, ad opera delle di-
verse cPu, consentendo l'esecuzione d i processi paralleli (il ter-
mine processo verr precisato nel corso d el capitolo). In questi
sistemi risulta modificata sia l'architettura dell'hardware, per
la presenza di pi processori, sia il software, che deve tener
conto dell'attivazione contemporanea di pi processi.
 La quinta generazione dei sistemi operativi, solo in minima
parte gi realizzata, dovrebbe approfondire sempre di pi la vi-
cinanza all'utente umano, operando su pi fronti contempo-
raneamente: da una parte l'architettura di Von Neumann po-
trebbe essere affiancata da calcolatori con pi processori cen-
trali, portando ad un maggiore sviluppo dell'elaborazione pa-
rallela, dall'altra le modalit di interazioni con l'utente
faranno sempre pi ricorso alle tecniche di multimedialit
che consentono di utilizzare in modo sempre pi esteso suoni,
immagini, filmati e la stessa voce umana.
 Ogni sistema operativo, costituito dall'insieme dei componenti
software che si collocano tra l'hardware e i programmi
dell'utente, deve essere in grado di soddisfare due diversi tipi
di esigenze:

 - consentire all'utente di utilizzare il sistema in modo sem-
plice e veloce;
 - gestire in modo ottimale le risorse del sistema.

 Per questo,  evidente che esistono due punti di vista per consi-
derare un sistema operativo: il sistema operativo visto dall'uten-
te e il sistema operativo visto dal progettista del sistema.

n sistema operativo visto dall'utente

 Dal punto di vista dell'utente, il sistema operativo deve esse-
re in grado di evitare all'utilizzatore l'uso diretto delle risorse
del sistema, fornendogli tutta una serie di servizi, quali la pos-
sibilit di eseguire un pr~ogramma controllandone tutte le fasi
fino alla terminazione. E inoltre importante che il sistema sia
in grado di gestire in modo efficiente le operazioni relative all'in-
serimento e all'uscita dei dati, e quelle relative alla gestione delle
informazioni utilizzate o prodotte dal programma. In caso di er-
rori, sia di tipo hardware che di tipo software, il sistema deve es-
sere in grado di intervenire, o per consentire la prosecuzione
dell'elaborazione, o per emettere opportuni segnali diagnostici.
 L'utente vede il suo sistema sostanzialmente diviso in due
parti: il sistema operativo vero e proprio e l'insieme dei pro-
grammi applicativi: dal suo punto di vista l'organizzazione di
un sistema operativo si pu rappresentare come in figura:





       1 interprete /--~\
       / Comandi / PrOgrammi

               j sistema (~)


                \~plicativ~/ j





 Il livello al quale l'utente accede direttamente  l'interprete
dei comandi. L'interprete comandi, chiamato anche shell,
mette a disposizione dell'utente una serie di comandi attra-
verso i quali l'utente accede ai programmi di sistema o ai pro-
grammi applicativi. I programmi di sistema consentono di otte-
nere informazioni generali sul proprio programma, di attiva-
re traduttori di un linguaggio, di effettuare varie operazioni
sugli archivi disponibili. I programmi di sistema, per svolgere
le operazioni richieste, attivano il nucleo, cio quella parte del
sistema operativo che pi direttamente si occupa di gestire i
diversi componenti hardware.

n sistema operativo visto dal progettista

 Dal punto di vista del progettista, il concetto pi importante
diventa ilprocesso. Con il termine processo si intende un pro-
gramma visto nella sua esecuzione, in modo dinamico piutto-
sto che statico. Sono pertanto considerate, in quest'ottica, le
risorse che il processo utilizza (quelle che sono state indicate
dal programma, ad esempio aree di memoria per le variabili)
e tutto qello che succede nel sistema durante l'esecuzione
del programma corrispondente.
 Nel suo evolversi, un processo passa attraverso stati diversi, a
seconda che le istruzioni del programma corrispondente si
trovino in esecuzione sulla cPu o se, invece, siano in esecuzio-
ne, da parte della cPu, operazioni relative ad altri processi.
 Un processo  quindi caratterizzato da una serie di cambia-
menti di stato; se il sistema ha solo un programma in memoria
principale (uniprogrammazione), l'unico processo esistente
alterner fasi di esecuzione a stati di attesa. Pi interessante 
invece la situazione in un ambiente di multiprogrammazione;
in questa situazione, diversi programmi si trovano in memoria
contemporaneamente, ciascuno dar origine a un diverso
processo che contender agli altri processi l'uso della cPu.
 La logica con la quale i processi otterranno l'uso della cPu
costituisce una strategia specifica che varia secondo le scelte
fatte dal progettista; in tutti i casi i processi devono avanzare
in modo abbastanza uniforme,  quindi necessario che cia-
scun processo alterni istanti di uso della cPu con altri nei quali
rimane in attesa, perch la cPu  stata assegnata ad un altro
processo.



 -~ =
 Ciascun processo, pertanto, cambia continuamente di stato
secondo lo schema riportato nella pagina precedente.
 Gli stati di creazione e di terminazione rappresentano rispet-
tivamente il momento in cui il processo viene creato (e quindi
noto al sistema con tutta una serie di informazioni che lo iden-
tificano), e quando, al contrario, termina e viene successiva-
mente eliminato. Gli stati pi significativi, che rappresentano
la maggior parte di vita del processo, sono quello di pronto, di
esecuzione e di attesa. Nello stato di pronto il processo  po-
tenzialmente in grado di andare in esecuzione (ad esempio,
ha tutte le risorse che gli servono) ma aspetta che gli venga as-
segnata la cPu che, evidentemente,  impegnata con un altro
processo. Nello stato di esecuzione, il processo ha la cPu a di-
sposizione e sono in esecuzione le istruzioni del programma
corrispondente. Da questo stato, il processo pu tornare nello
stato di pronto, secondo la politica di condivisione della cPu
adottata (ad esempio, ha terminato un tempo prefissato) op-
pure, se richiede un I/O, viene messo in stato di attesa che le
operazioni richieste vengano completate, e la cPu viene asse-
gnata ad un altro processo. Dallo stato di attesa il processo
transita nuovamente nello stato di pronto.
 Il sistema, pertanto,  visto dal progettista secondo una strut-
tura a livelli di questo tipo:



                       / programml      \
                        /applica~      \


                           /processi ~

(~cleo(~)





 In ogni livello  possibile intervenire con una modalit e un
linguaggio propri di quel livello; ciascun livello  in grado di
sfruttare tutte le opportunit offerte dal livello sottostante. Il
livello dei processi include tutti i processi utenti (attivati da un
programma dell'utente) ma anche i processi propri del siste-
ma, i programmi di gestione dell'VO, quelli di gestione della
memoria centrale e quelli per le memorie secondarie.

            La gestione della memoria centrale

 Una delle funzioni principali del sistema operativo  quella
relativa alla gestione della memoria centrale, affidata ad un par-
ticolare componente del sistema operativo, il gestore della
memoria. La situazione si presenta in modo diverso se si trat-
ta di un sistema in uniprogrammazione o in multiprogram-
mazione; nel primo caso la gestione della memoria risulter
relativamente semplice, nel secondo sar necessario ricorre-
re a tecniche pi sofisticate e complesse.
 Nel sistema uniprogrammato la memoria centrale  in gene-
re cos suddivisa:


                           zona occupata
                       dal sistema operativo




                           zona occupata
                                dal
                          programma utente





                            zona libera
          54                             L'INFORMATICA

 Una zona della memoria  riservata a quella parte del siste-
ma operativo che deve risiedere necessariamente in memoria,
un'altra zona  riservata al programma utente, una terza zona,
se non viene utilizzata dal programma, rimane libera. Se il
programma utente richiede uno spazio di memoria pi grande
di quello disponibile, viene adottata una tecnica chiamata degli
overlay: il programma  suddiviso in parti e vengono caricate
in memoria di volta in volta solo quelle parti del programma
necessarie all'avanzamento dell'elaborazione.
 Nei sistemi in multiprogrammazione, la zona della memoria
riservata al programma utente deve essere suddivisa in parti
da assegnare ai vari processi. Si adottano tecniche diverse per
questa suddivisione della memoria. La tecnica pi semplice 
quella a partizionifisse: la memoria viene suddivisa in un nu-
mero predefinito di partizioni, ciascuna con una determinata
dimensione. Quando un processo richiede una parte di me-
moria di una certa dimensione, il gestore della memoria asse-
gner al processo una partizione libera di dimensione uguale
o maggiore di quella richiesta. Con questa tecnica  possibile
che molto spazio in memoria venga sprecato perch la parte
di partizione non utilizzata dal processo, ma comunque ad
esso assegnata, non pu essere assegnata ad un altro processo
e risulta quindi inutilizzata. Le strategie per l'assegnazione
della partizione seguono vari algoritmi tendenti tutti ad otti-
mizzare lo spazio in memoria e a limitare il pi possibile il
problema dello spreco di memoria. A fronte di questi limiti, la
tecnica delle partizioni fisse ha il vantaggio di essere molto ve-
loce e di semplice realizzazione.
 Per owiare ai limiti della tecnica a partizioni fisse si pu uti-
lizzare la tecnica a partizioni variabili. Con questa modalit, le
partizioni hanno esattamente le dimensioni richieste da cia-
scun processo, partendo da una situazione iniziale di memo-
ria non suddivisa. Dopo un certo periodo di attivit, quando i
processi rilasceranno di volta in volta le loro aree di memoria,
si creeranno delle partizioni libere di dimensioni tali da poter
essere assegnate o, viceversa, di dimensioni troppo piccole da
poter essere utilizzate. Si potrebbe creare una situazione di
frammentazione della memoria che ha bisogno di una riorga-
nizzazione degli spazi e di un periodico ricompattamento.

         I SISTEMI OPERATIVI                           55

Questa tecnica risulta pi efficiente di quella precedente, an-
che se ha bisogno di algoritmi non banali di gestione.
 Le tecniche di gestione della memoria centrale non finisco-
no qui, non  possibile affrontarle tutte; in tutti i casi  sempre
presente la necessit di soddisfare l'esigenza di un uso ottima-
le della memoria, coniugata ad una modalit di gestione che
consenta di ottenere quanto richiesto dai processi in tempi ac-
cettabili. L'una o l'altra tecnica di gestione vengono adottate
dal progettista del sistema operativo, valutando l'impatto di
ciascuna tecnica, anche in relazione agli altri componenti del
sistema.
6. Gli archivi





Dall 'archivio al file

 L'informatica  la scienza delle informazioni. La gestione
delle informazioni  senza dubbio il ruolo fondamentale svol-
to da un sistema di elaborazione. Le informazioni, in genere,
sono raggruppate in archivi; con il termine archivio si intende
l'insieme di tutte le strutture che contengono le informazioni
necessarie in un certo contesto.
 In molte situazioni quotidiane gli archivi sono presenti in va-
rie forme, spesso ancora solo sotto forma cartacea ma, co-
munque, il loro uso  molto diffuso; biblioteche, uffici anagra-
fici, archivi sanitari sono tutti esempi di archivi di uso comune.
Non sempre la gestione delle informazioni con i metodi tradi-
zionali risulta soddisfacente, gi da molti anni un numero sem-
pre pi grande di settori lavorativi si sta orientando ad affiancare
o a sostituire gli archivi cartacei con gli strumenti informatici.
 Il passaggio da un archivio cartaceo ad un archivio informa-
tico costituisce un cambiamento non sempre semplice e, a vol-
te, attuato in modo non corretto.
 L'archivio informatico deve possedere tutte le funzionalit
proprie di un archivio cartaceo, deve aggiungere molto in ter-
mini di velocit di utilizzo dell'archivio e, soprattutto, deve
consentire operazioni di difficilissima effettuazione con me-
todi e strumenti non informatici, in tempi accettabili. Nel pas-
saggio dall'archivio cartaceo a quello informatico devono es-
sere superati gli eventuali limiti esistenti nell'organizzazione
dell'archivio cartaceo, per non rischiare un sottoutilizzo o un
degrado delle prestazioni dell'intero sistema.
 Il termine archivio diventa, in ambito informatico, un file.
Quando si tratta di file, ci si riferisce necessariamente a infor-
mazioni che risiedono su memorie di massa, cio Sll memorie

permanenti collegate al sistema, in grado di contenere un nu-
mero molto grande di informazioni, in genere i dischi.
 Come per i sistemi operativi in generale,  possibile analizzare
la gestione delle informazioni considerando sia il punto divista
dell'utente del sistema, che avr la necessit di svolgere una
lunga serie di operazioni relative alle proprie informazioni
(creare un archivio, rintracciare particolari dati, cancellare
elementi, ordinare l'archivio secondo particolari criteri e cos
via), sia dal punto di vista del progettista del sistema, analiz-
zando con maggiore precisione come sono organizzate le in-
formazioni nel sistema stesso.
 In realt, l'utente ha una visione del problema della gestione
dei file relativa solo al modo di effettuare le operazioni che lo
riguardano direttamente; esiste infatti uno specifico compo-
nente del sistema operativo, ilfile system, che ha il compito di
gestire tutti i file sul versante pi vicino all'hardware della mac-
china. Ad esempio, il file system si occuper di reperire lo spa-
zio necessario per le informazioni da registrare, mentre il
compito dell'utente sar solo quello di indicare che vuole re-
gistrare determinate informazioni.
 L'organizzazione degli archivi pu essere vista a vari livelli; dal
livello pi basso, la gestione dei dispositivi fisici, a quello riguar-
dante l'utente finale. E possibile schematizzare cos le visioni:

                LIVELU Dl IMPLEMENTAZIONE DEGLI ARCHIVI
                             utente finale

                             applicazione

                               archivio

                        organizzazione dei dati

                              file system

                         gestione dispositivi

                                   I
                                 n ~ Q
 Man mano che si sale di livello, la visione dell'archivio sar
sempre pi astratta e lontana dalla reale memorizzazione fisica.
 Una delle pi frequenti operazioni che l'utente, da parte sua,
 interessato a svolgere,  quella di conoscere tutte le infor-
mazioni relative agli archivi esistenti, per esempio su un deter-
minato disco. Per fare questo, il file system mette a disposizio-
ne dell'utente un insieme di informazioni organizzate spesso
in una struttura ad albero, la directory. La figura seguente po-
trebbe illustrare come i dati sono collocati in un certo disco:





~3

                                 ~\





                        prme | | seconde |

                            O directory

                                file





 Le informazioni sono ripartite in modo da consentire una
loro suddivisione logica (i dati sono raggruppati secondo un
determinato criterio) e la struttura ad albero consente una
maggiore efficienza rispetto alle operazioni da effettuare.
Nell'esempio della figura, dal punto di partenza (radice
dell'albero)  possibile accedere ad un file e a due sotto-direc-
tory, ciascuna delle quali contiene due file. In questa organiz-
zazione,  possibile che file diversi, sotto diverse sotto-direc-
tory, abbiano nomi uguali: questo non crea confusioni perch
il nome completo del file  dato dal suo nome preceduto da
quello della sua sotto-directory; in generale,  dato da tutti i
nomi (di sotto-directory) che si incontrano dalla radice fino al
file. Nell'esempio, esistono due file di nomeprime ma corri-
spondono a due archivi diversi, uno di nome classilprime e l'al-
tro di nome docentilprime (il simbolo \ separa il nome della sotto-
directory da quello di un file o di un'altra sotto-directory).
 Come  costituito un file al suo interno? I file pi semplici da
trattare sono quelli nei quali ogni elemento  di tipo semplice,
ad esempio un carattere. I file di testo, quelli che vengono creati
con un semplice sistema di scrittura, sono file di caratteri.
 In un file di tipo pi complesso, ogni elemento del file deve
poter contenere informazioni di tipo diverso, logicamente
correlate. In un ambito lavorativo potr esistere un file conte-
nente tutte le informazioni relative ai dipendenti, o un altro
contenente tutti i dati delle fatture pagate dall'azienda. In
questi casi, la singola unit di informazione del file  il record .
Il numero dei record in un file determina la lunghezza del file.

                               Fll F



                    record     record




      Mario Rossi | via Roma, 13 | 234567 |

       nome indirizzo telefono

 Considerando questa figura  possibile illustrare l'organiz-
zazione di un file. I singoli elementi del file sono dei record,
tutti con la stessa struttura. Un record  suddiviso in campi.
Ogni campo ha un nome e contiene una parte dell'informazione,
individua un attributo dell'oggetto. Nell'esempio, ciascun record
del file  suddiviso in tre campi: nome, indirizzo e telefono.
 Se un campo  utilizzato per selezionare un record dell'archi-
vio, viene ad assumere il ruolo di chiave. Ad esempio, in una
operazione del tipo stampare tutti i dati relativi all'utente
con numero di telefono 234567, il campo telefono ha ruolo
di chiave.
 La chiave pu essere di due tipi:

 - chiave primaria:  una chiave che individua al pi una regi-
strazione fra quelle contenute nell'archivio; il suo valore pu
essere posseduto da una sola registrazione;
 - chiave secondaria: quando ad un valore di chiave corrispon-
dono pi registrazioni.
 Nella tabella che segue, il campo matricola svolge ruolo di
chiave primaria (esiste un solo record con un certo valore)
mentre il campo nome e il campo data di nascita sono entram-
bi chiavi secondarie (esistono record con valori uguali nel
campo nome e cos pure nel campo data di nascita).


MATRICOLA        NOME       DATA NASCITA
 53701      Paolo Bianchi     10/3/50
 48256      Giovanni Rossi
 12350
 78113
 85245        Franco Ics

Paolo Bianchi
 Carlo Neri



Operazioni sugli archivi

5/11/40
7/12/20
18/5/35
5/1 1/40



 Sui file  possibile eseguire varie operazioni, alcune coinvol-
gono il file nella sua globalit, altre consentono di operare a li-
vello di singoli record. Le operazioni che coinvolgono global-
mente il file sono quelle che consentono:

 Creazione di un archivio vuoto. Consente di attribuire un i-
dentificatore (il nome) ad un file che da quel momento viene
riconosciuto dal sistema.
 Apertura di un file. Consente di predisporre il file all'esecu-
zione di qualsiasi operazione. E l'operazione che, tranne per
la creazione, deve precedere tutte le altre. Con questa opera-
zione viene resa disponibile una parte di memoria principale
(buf~er) nella quale transitano, un po' allavolta, le varie infor-
mazioni registrate sul file.
 Chiusura di un file. Consente di terminare le operazioni che si
stavano svolgendo sul f;le. Il buffer associato al file viene reso
disponibile per altri usi.
 Eliminazione di un file. Con questa operazione viene can-
cellato il file e il suo identificatore; il file non  pi ricono-
sciuto dal sistema.

 Oltre a queste operazioni, da considerarsi basilari per la ge-
stione di un file, le seguenti sono ancora operazioni che coin-
volgono l'intero file:

 Scansione del file. Con questa operazione  possibile scorre-
re tutti gli elementi del file.
 Ordinamento del file. E possibile posizionare gli elementi del
file secondo un ordine prescelto, ad esempio l'ordine alfabeti-
co. Deve essere scelta preliminarmente la chiave sulla quale
gli elementi devono essere ordinati.
 Fusione di due file. Quest'operazione coinvolge almeno due
file e consente di unificare in un unico file le informazioni pro-
venienti dai due file di origine.
 Le operazioni che possono interessare solo una parte degli
elementi del file sono operazioni relative all'aggiomamento
delle informazioni presenti o alla ricerca di elementi con de-
terminate caratteristiche.
 Le operazioni di aggiomamento possono essere:

 Aggiomamento per inserzione. Questa operazione viene ef-
fettuata per inserire un nuovo elemento nel file. L'aggiorna-
mento pu essere un semplice inserimento in coda, cio alla
fine del file; in questo caso  sufficiente scorrere tutto il file e
aggiungere il nuovo elemento con una semplice operazione di
scrittura sul file, oppure pu essere fatto rispettando un qual-
che criterio, ad esempio mantenendo un ordinamento gi
presente nel file.
 Aggiornamentopercancellazione. E l'operazione che consen-
te di eliminare un determinato elemento. La lunghezza del
file risulta modificata se si attua una vera e propria cancella-
zione (cancellazione fisica). A volte pu risultare pi con-
veniente, in termini di tempo, eliminare l'elemento conno-
tandolo in un particolare modo; in questo caso, la lunghezza
del file, e quindi lo spazio occupato, non varia con la cancel-
lazione dell'elemento (cancellazione logica).
 Aggiomamento per modifica. La modifica di un elemento in
un file consiste nel sostituire determinate informazioni pre-
senti in uno o pi campi del record (al limite l'intero record)
con altre fornite dall'utente; ad esempio il campo stato civi-
le di un record di tipo anagrafico pu essere variato da celi-
be a coniugato.

 Le operazioni di ricerca possono essere effettuate per posi-
zione oper ch~ave: nella ncerca per posizione si vuole accede-
re ad un elemento che si trova in una determinata posizione,
nella ricerca per chiave si vuole accedere ad un elemento che
contenga una certa chiave. Se la chiave  primaria, l'elemento
ricercato sar unico, altrimenti saranno evidenziati pi ele-
menti con quello stesso valore di chiave.
 L'insieme di tutte le procedure che consentono la realizza-
zione delle operazioni analizzate costituiscono un sistema di
gestione di un archivio.

Tipi di organizazione di un file e metodi di accesso

 Per la determinazione della struttura del file  necessario
considerare la tipologia degli elementi da memorizzare e qua-
le tipo di organizzazionefisica  pi conveniente realizzare sul-
la base del tipo di elaborazione da effettuare e dei supporti fi-
sici a disposizione (dischi, nastri, ecc.). I possibili tipi di orga-
nizzazione sono:

 - sequenziale;
 - casuale;
 - mista (con indice).

Organizzazione sequenziale
 L'organizzazione sequenziale  tale se sono presenti i seguenti
vincoli:

 - per ogni record del file, escluso l'ultimo,  definita un'ope-
razione di accesso ad un altro record designato come successi-

vo;
 - non esistono strutture dati ausiliarie associate al file che
possano agevolare le operazioni di ricerca.

 Nell'ambito dell'organizzazione sequenziale, tuttavia, i me-
todi di accesso, cio i metodi con i quali  possibile raggiunge-
re un singolo elemento del file, possono essere rispettivamen-
te di tipo sequenziale e di tipo diretto.
 Nell'accesso sequenziale, per accedere ad un record,  neces-
sario accedere a tutti quelli precedenti. Questo tipo di accesso
pu essere necessario per varie ragioni:

 - le caratteristiche del supporto non consentono un tipo di
accesso diverso (ad esempio, un nastro);

- i record del file non hanno tutti la stessa lunghezza;
 - i vari elementi del file sono memorizzati fisicamente in
modo non contiguo.

 L'accesso diretto permette di evitare di scorrere tutti gli ele-
menti del file, fino ad arrivare all'elemento cercato, ma consen-
te di raggiungerlo direttamente. Il tempo impiegato per effet-
tuare quest'operazione  costante per ogni elemento, non di-
pende guindi dalla posizione nella quale si trova l'elemento
stesso (il primo o l'ultimo elemento vengono raggiunti nello
stesso tempo). Naturalmente, questo tipo di accesso, in genere
pi conveniente per molte applicazioni, ha bisogno di un sup-
porto adeguato (il nastro  escluso).
 Nell'organizzazione sequenziale le possibili operazioni si
svolgono con differenti modalit a seconda del tipo di acces-

so.
 Per quanto riguarda la ricerca di un elemento, nel caso
dell'accesso sequenziale  necessario ricorrere ad una ricerca
che prevede la scansione di tutto il file, elemento per elemen-
to. In questa situazione il tempo di ricerca dipende dalla posi-
zione dell'elemento nell'ambito dell'archivio: se un elemento
si trova all'inizio dell'archivio sar raggiunto molto presto, al-
trimenti il tempo di ricerca aumenter man mano, fino a tro-
vare l'elemento cercato.
 Nel caso dell'accesso diretto la ricerca pu essere fatta in
modo pi veloce se gli elementi sono collocati nel file secondo
qualche ordinamento. In questo caso  possibile adottare la ri-
cerca binaria, altrimenti deve essere effettuata una ricerca
completa.
 La ricerca binaria consiste nell'accedere inizialmente all'ele-
mento centrale dell'archivio; se l'elemento da cercare  mino-
re di quello trovato, si passa a considerare, da questo punto in
poi, solo la prima parte del file (l'elemento da cercare  neces-
sariamente in questa parte, perch l'archivio  ordinato), al-
trimenti si cerca nella seconda parte. In entrambi i casi si pro-
cede come all'inizio, con l'accesso all'elemento centrale e pro-
seguendo quindi con la stessa tecnica. Il processo si interrom-
pe quando l'elemento viene trovato o quando si determina
che non  presente nell'archivio.
 Il metodo della ricerca binaria  fondamentale nell'ambito
dell'algoritmizzazione; per fare un esempio di questo meto-
do, si supponga di dover cercare nel seguente archivio, ordi-
nato rispetto al primo campo, l'elemento con valore 49:

                               2 _ _





 Volendo effettuare la ricerca binaria sul file indicato, il primo
accesso al file porter a raggiungere l'elemento con valore 21
nel primo campo; a questo punto, poich l'elemento cercato 
maggiore di quello trovato, si passa a considerare solo la se-
conda parte degli elementi, riapplicando lo stesso metodo. Il
prossimo elemento sar quello con valore 40, poi quello con
valore 51 e, infine, si raggiunger proprio l'elemento con valore
49.
 Per quanto riguarda l'inserimento di un nuovo elemento nel
file, sia in caso di accesso sequenziale sia in caso di accesso di-
retto, l'inserimento awiene alla fine del file, aggiungendo in
fondo il nuovo elemento. Se il file  ordinato, e l'inserimento
deve mantenere l'ordinamento degli elementi, l'inserimento
viene effettuato utilizzando un altro file sul quale riscrivere
tutti gli elementi del file di partenza e, al posto giusto, il nuovo
elemento da inserire. Per ottenere la modifica del file di par-

                                           l

tenza, gli elementi del nuovo file devono essere copiati nel file
iniziale.
 Solo nel caso di accesso diretto, se il file  suddiviso in parti
(pagine),  possibile predisporre per ogni parte del file un
nuovo file ad essa associata che contenga l'elemento da inse-
rire (area di trabocco).
 Per le operazioni di cancellazione e di aggiornamento, i due
tipi di accesso consentono modalit molto diverse: in caso di
accesso`sequenziale  necessario riscrivere tutto il file, per en-
trambe le operazioni; nell'accesso diretto si coinvolge solo il
record sul quale  prevista l'operazione. La cancellazione 
spesso solo di tipo logico, si interviene con la cancellazione fi-
sica solo periodicamente, dopo un certo numero di cancella-
zioni logiche.

Organizzazione casuale

 L'organizzazione casuale  preferibile quando tutte le elabo-
razioni richieste riguardano un solo record alla volta, cio
quando si tratta di effettuare operazioni locali. Questo tipo di
organizzazione  possibile solo in presenza di un supporto che
consenta l'accesso diretto.
 Nell'organizzazione casuale, la ricerca di un record nel file
pu awenire:

 - per posizione (file relativo);
 - per chiave (organizzazione hash).

 Nel file relativo l'accesso al record si ottiene con una opera-
zione di seek: quest'operazione consente il posizionamento
sull'elemento del file di posizione data. Dopo il posiziona-
mento  possibile effettuare operazioni di lettura, scrittura,
modifica.
 Nell'organizzazione per chiave, detta anche hash, la memo-
rizzazione, e la successiva ricerca di un elemento, avviene at-
traverso una funzione di trasformazione secondo il seguente
schema:

    chiave     > | funzione di trasforrnazione | > indirizzo

   Dato il valore della chiave, la funzione di trasformazione,
          ~l~                             L-INFORMATICA

applicata alla chiave, produce un valore che costituisce l'indi-
rizzo della locazione dove l'elemento dovr essere memorizzato.
 I problemi relativi alla gestione hash sorgono quando, appli-
cando la funzionc di trasformazione su chiavi diverse, si ottie-
ne uno stesso indirizzo. Non essendo possibile memorizzare
nelle stessc locazioni elementi diversi, si deve affrontare
questo prol-lema, noto come collisione. La gestione delle
collisioni de~c consentire di memorizzare l'elemento che
ha colliso (e stato generato un indirizzo gi occupato da un
aitro clemento) in un altro indirizzo disponibile per l'archi-
vio: la nl(~ lit~i di memorizzazione deve essere veloce e deve
r ot~r c~crc ri;lpplicata anche in fase di recupero dell'elemento.

o~a~ a~ione ~nista (sequenziale con indice)

 ~!~ll or~ izz;lzione sequenziale con indice, il file dei dati
(cl~ m;l~ u~ ~tO contestofi/eprima7io)  organizzato in bloc-
chi cl-i.ull.lti /~ e, ciascuna delle quali contiene un certo nu-
mcro ~li r~ tr.lzioni solitamente ordinate rispetto alla chiave.
 L..~ chi.l; ~ pi ;llt~ di ciascuna delle pagine del file primario 
riport~t;l in unJile indice, secondo lo schema seguente:





                               \ AC |





FILE INDICE
                  FILE PRIMARIO

           GLI ARCHIVI                               67

 In un'organizzazione di questo tipo, le operazioni di ricerca
o inserimento di un elemento awengono consultando inizial-
mente il file indice e, da questo, accedendo direttamente alla
pagina nella quale deve essere effettuata l'operazione. In si-
tuazioni molto complesse,  possibile prevedere una gestione
degli indici a pi livelli.
7. Basi di dati





Sistema digestione di una base di dati

 Una base di dati  un archivio integrato di dati, controllato
da un sistema di gestione.
 Le basi di dati costituiscono lo strumento da utilizzare quando
le informazioni da considerare in un determinato contesto
(azienda commerciale o di servizi, banca, scuola, ecc.) sono in
numero molto consistente e, soprattutto, risulta conveniente
poter correlare tra loro queste informazioni, in modo da otte-
nere informazioni derivanti dalla struttura stessa della base di
dati. Una base di dati (in inglese database) indica sia un archi-
vio di dati preparato tramite un computer, sia tutto il corredo
di moduli soft~vare che consentono la costruzione e l'uso di
questi archivi.
 Il sistema di gestione di una base di dati consente di:

 - creare archivi di dati con la struttura desiderata (per esem-
pio, lo schedario automatizzato di una biblioteca);
 - memorizzare su disco i dati dell'archivio;
 - aggiornare e modificare con facilit i dati inseriti;
 - reperire velocemente le informazioni, tramite ricerche in-
crociate su pi chiavi d'accesso.

Dato e informazione

 Per poter analizzare meglio le caratteristiche di una base di
dati,  necessario precisare il significato di alcuni termini ri-
correnti in questo contesto. Innanzi tutto, occorre fare una di-
stinzione tra i termini dato e infomtazione.

 Dato:  la rappresentazione di un'informazione ottenuta per
mezzo di alcune caratteristiche dell'informazione stessa.

 I~lfo~mazione:  l'incremento di conoscenza che pu essere
acquisita dai dati.

 Come si pu notare, le due definizioni sembrano rincorrersi
tra loro;  possibile chiarire con un esempio. Supponiamo di
trovarci di fronte a questi dati, in organizzazione sparsa:

                       14.30
                 Genova
        18.12
                            14.00
Napoli               14.05

          10.18              Bologna

 Roma


15.05
    7.00

16.00



 Che cosa significano questi nomi e numeri? Essi costituisco-
no dati, ma questi dati non sono utili (non danno informazio-
ne) se non si fornisce una chiave di interpretazione che con-
senta di comprendere il loro significato, cio i fatti che essi co-
dificano.
 Se, invece, gli stessi dati vengono organizzati in qualche
modo, ad esempio sotto forma di tabella, come nell'esempio
che segue, il loro significato risulta subito chiaro: solo in que-
sto caso, con una chiave di interpretazione, i dati costituisco-
no informazione.

partenza da  alle ore  arrivo a
Genova       7.00      Roma
Firenze      14.00     Bolo~na
Bolo~na      10.18     Roma
Roma         16.00     Napoli

 alle ore
 13.00
 15.05
 14.30
_ 18.12

 Si definisce schema di una struttura il modello o l'ossatura
della struttura stessa, mentre si definisce ista~lza o esemplare,
uno schema nel quale sono inseriti particolari valori. Nell'esem-
pio della tabella precedente, lo schema  costituito dalla tabella
vuota, con solo l'intestazione di ogni colonna (partenza da, ecc.)
mentre la tabella riempita, con quei particolari valori, costituisce
un'istanza dello schema.
 Lo schema fornisce la clliave di intcrpretazione e rappresen-
ta il dato dal punto di ~ a i~ iollo/(~.
 I valori particolari inseriti nella tabella costituiscono il dato dal
punto di vista estensionale, valori che, in un'altra situazione, pos-
sono cambiare, nell'ambito dello stesso schema intensionale.

Schema logico dei dati

 Il concetto di schema, esteso a tutti i dati presenti nella base di
dati, consente di definire lo schema logico dei dati. Non  neces-
sario che ogni utente del sistema sia a conoscenza dell'intero
schema logico, molto pi frequente  la situazione che con-
sente ad ogni utente di intervenire sulla base di dati attraverso
un sottoschema, relativo alla sua applicazione e alle sue com-
petenze. La base di dati, come mostra la figura che segue, si
presenta pertanto secondo diversi livelli di astrazione: nel li-
vello esterno opereranno i vari utenti, ciascuno avendo a dispo-
sizione una visione parziale della base di dati attraverso uno
specifico sottoschema; il livello logico sar costituito dalla orga-
nizzazione logica dei dati, attraverso lo schema generale; il livel-
lo fisico sar quello dei supporti flSiCi di memorizzazione.

utente 1 [=
utente 2 =~\~



 utente 3 ~,;~


 utente 4


 livello esterno

       livello logico  livello fisico
Livelli di astrazione

base di
  dati
  fisica
  l





 In molte applicazioni informatiche si trovano numerosi dati
con la stessa interpretazione; tutti i dati con la stessa interpre-
tazione costituiscono una categoria. In generale le categorie
sono relativamente poche rispetto al gran numero dei dati.
 Pu invece accadere, in ambiti limitati, che le categorie siano
in numero molto grande e i dati un numero molto ridotto: in
questo caso le applicazioni ricadono principalmente nella sfe-
ra chiamata dell'intelligenza artificiale e dei sistemi esperti.
 Uno schema, cos com' stato definito, identifica pertanto una
struttura dei dati attraverso:

 - le categorie in cui sono ripartiti i dati;
 - lepropriet di ogni categoria;
 - le relazioni (o associazioni) tra le varie categorie.

 Un insieme di dati organizzati in accordo ad un certo schema
S  detto occorrenza di una base di dati o anche istanza o esten-
sione dello schema S.
 Tutte le operazioni attraverso le quali  possibile accedere o
modificare i dati di una base di dati sono funzioni che trasfor-
mano lo stato della base dei dati.
 Considerando l'insieme delle regole necessarie alla genera-
zione degli schemi e l'insieme delle operazioni che consento-
no la manipolazione della base dei dati, tutto questo d luogo
ad un modello dei dati.
 Le regole per la generazione degli schemi costituiscono un
vero e proprio linguaggio per la des-crizione dei dati (chiama-
to DDL) cos come un vero e proprio linguaggio  utilizzato per
la manipolazione dei dati (chiamato DML). L'insieme di questi
due linguaggi costituisce buona parte del sistema di gestione
di una base di dati (chiamato DBMS). Il sistema di gestione di
una base di dati  quindi dato dall'insieme dei moduli softwa-
re che sono necessari per la creazione, la gestione e il reperi-
mento dei dati in una base di dati.
 La figura che segue illustra come il sistema di gestione della
base di dati si interpone, con tutte le sue funzioni, tra l'utente
e la base fisica dei dati.





            base di dati                     utente

DBMS

DBMS sistema di gestione di una base di dati
DDL linguaggio di descrizione dei dati
DML linguaggio di manipolazione dei dati
Caratterishche di un sisfema di gestione di una base di dati

 Un sistema di gestione di una base di dati deve possedere al-
meno i seguenti requisiti:

 Indipendenza dei programmi applicativi dai dati. L'indipenden-
za dei programmi dai dati deve essere consentita a due livelli:
indipendenza dalla struttura fisica dei dati e indipendenza
dalla struttura logica dei dati. Per quanto riguarda l'indipen-
denza dalla struttura fisica dei dati, essa consiste nella possibi-
lit, data dal linguaggio di manipolazione dati, di utilizzare
dati con diversa struttura fisica, senza mai intervenire su di
essa. Una modifica della struttura fisica dei dati non deve avere
come conseguenza la modifica dei programmi che utilizzano
la base dei dati.
 L'indipendenza dalla struttura logica dei dati  legata alla
possibilit, per il singolo utente, di lavorare con un particolare
sottoschema, senza intervenire, e senza conoscere, la struttu-
ra logica globale dell'intera base di dati. D'altra parte, deve
essere possibile modificare lo schema logico senza dover mo-
dificare i programmi non interessati alla modifica.

 Indipendenza daU'hardware. Tutte le operazioni consentite
dalla base dei dati devono essere totalmente indipendenti
dall'hardware utilizzato, i supporti di memorizzazione non
devono essere mai trattati direttamente e la loro diversit non
deve intervenire a modificare la struttura della base di dati.

 Possibilit di rappresentare relazioni complesse tra i dati. Le
relazioni fra i dati esistenti nella realt sono in genere di tipo
complesso. Il sistema deve consentire di rappresentare e re-
perire queste relazioni in modo efficiente, cos come richie-
sto dalle applicazioni reali.

 Non ridondanza dei dah. Un base di dati contiene dati comu-
ni ad applicazioni diverse. E preferibile che lo stesso dato ven-
ga rappresentato una solavolta, e che tutte le applicazioni fac-
ciano riferimento a quell'unico dato, eventualmente modifi-
candolo. In caso contrario,  possibile che applicazioni diver-
se creino situazioni di inconsistenza tra i dati (ad esempio, in
un archivio anagrafico, se l'indirizzo di un utente  registrato

in pi punti dell'archivio, potrebbe succedere che una modifi-
ca venga effettuata solo su una di queste registrazioni e non
sulle altre, rendendo l'informazione inconsistente; quale sar
quella corretta?).

 Sicurezza dei dati. In una base di dati  necessario garantire
due forme di sicurezza: la sicurezza da accessi non autorizzati
e la sicurezza da errori derivanti da malfunzionamenti hard-
ware o errori accidentali. Per quanto riguarda il primo punto,
 ormi opinione diffusa, a tutti i livelli, che la raccolta e la
consultazione di informazioni costituiscano un'attivit molto
delicata e che quindi debbano esistere adeguati sistemi di pro-
tezione che garantiscano la riservatezza dei dati. Per quanto
riguarda la sicurezza da errori di vario tipo, deve essere garan-
tito che nessun utente n un malfunzionamento del sistema
possano alterare irrimediabilmente la base di dati.

 Il rapporto tra i vari concetti fin qui affrontati  ben espresso
dalla figura che segue:



      di ~                 modello
     dati J              logico dei dati J



    descrive\      / tradotto in




ge~
  dal

schema



   utilizzato
La progettazione concettuale

 Per poter definire una base di dati bisogna inizialmente ope-
rare un'operazione di astrazione sulla realt; in questa attivit
 essenziale semplificare al massimo la quantit di informa-
zioni deducibili dalla situazione reale, estraendo soltanto
quelle caratteristiche che rivestono un ruolo certo nella base
di dati che si vuole realizzare. Si awia in questo modo la pro-
gettazione concettuale della base di dati, quell'attivit che mira
a cogliere e rappresentare in modo semplice ed efficace gli
aspetti della realt interessanti ai fini informativi. Un modello
di progettazione concettuale  di tipo entit-attributo.
 Le entit sono le classi di oggetti o persone del mondo reale,
distintamente identificabili, implicate nell'applicazione. Ogni
entit  caratterizzata da un insieme di propriet (attributi).
Uno specifico oggetto di una classe di entit  un'occorrenza
di quella entit.
 Le relazioni tra entit costituiscono le associazioni.

 cod. fisc.
cognome--
nome----

 liV~,III~ _

dipendente ~

    \
       non docente ~ attivit





  sezione
- ordine





- matricola
- cognome
  nome

 La realt spesso si presenta come un insieme di entit con-
nesse da attributi.
 Il modo pi espressivo per definire una progettazione con-
cettuale  quello attraverso uno strumento grafico che visua-
lizzi le entit, gli attributi di ciascuna entit, le relazioni esi-
stenti tra le entit.
 Lo schema riportato nella pagina a fronte costituisce la rap-
presentazione dell'organizzazione di una scuola.
 In quest'esempio le entit individuate sono dipendente, do-
cente, non docente, classe, studente: ognuna di queste entit 
caratterizzata da una serie di attributi che consentono di di-
stinguere occorrenze diverse della stessa entit.

Classificazione dei tipi di basi di dati

 Sono state progettate basi di dati di diverse tipologie, ciascu-
na con un diverso modello logico dei dati. I tipi di modelli, al-
meno per quanto riguarda le prime realizzazioni di basi di dati,
sono stati classificati come gerarchici, reticolari, relazionali.
 Il modello gerarchico utilizza strutture dei dati ad albero; le
informazioni, contenute nei nodi dell'albero sono costituite da
record raccordati tra loro da archi che definiscono le relazioni
tra i dati. Le basi di dati gerarchiche hanno il pregio di essere re-
lativamente semplici da definire e di comprensione immediata.
Il modello reticolare costituisce un'evoluzione del modello
gerarchico; utilizza prevalentemente il tipo di dato a lista e
questo consente di ridurre il rischio di ridondanza dei dati,
proprio del modello gerarchico. Tuttavia, la realizzazione di
un modello reticolare pu risultare meno semplice rispetto a
quello gerarchico.
 Il modello relazionale  un modello basato sulle diverse rela-
zioni che legano gli elementi dei file. Il procedimento di ricer-
ca consiste nella costruzione di relazioni o, pi in generale, di
insiemi di relazioni. Questo modello elimina le ridondanze di
dati;  possibile ricercare i dati attraverso gli operatori logici
and, or, not, anche composti tra loro. Qualche difficolt pu
sorgere per la rappresentazione dei dati con molte relazioni.
 Non sempre una base di dati si presenta con peculiarit ben
definite, molte delle ultime realizzazioni presentano aspetti
misti, con caratteristiche di modelli diversi.
8. Ambienti applicativi





Le applicazioni pi diffuse

 Le innumerevoli applicazioni informatiche costituiscono il
settore pi appariscente e pi noto dell'informatica. Pro-
grammi applicativi vengono sviluppati per soddisfare le esi-
genze pi svariate, ciascuno di essi costituisce un vero e pro-
prio ambiente, con propri oggetti, strumenti, modalit di uti-
lizzo. Uno dei principali settori di attivit in cui vengono rea-
lizzate applicazioni informatiche  quello del lavoro d'ufficio
nel quale vengono sempre pi utilizzati specifici programmi
applicativi, destinati ad automatizzare le principali attivit
amministrative e burocratiche.
 In genere, si indica con software applicativo l'insieme dei pro-
grammi che permettono all'elaboratore di svolgere dei com-
piti ben precisi, come effettuare calcoli, scrivere documenti e
relazioni, archiviare dati, ecc. I programmi applicativi posso-
no essere scritti dallo stesso utente, oppure possono essere
commissionati a programmatori, oppure, pi semplicemente,
possono essere acquistati gi pronti.
 I programmi applicativi possono soddisfare le pi svariate
esigenze:

- la gestione della contabilit di una azienda;
- la scrittura di testi e di documenti;
- la realizzazione di disegni industriali o artistici;
- la composizione di brani musicali;
- la gestione delle merci di un magazzino;
- la progettazione di nuovi macchinari;
- lo studio in autoistruzione;
ecc.

Alcuni, tra i programmi applicativi, hanno acquisito una dif-

fusione e importanza particolare. Oltre alle basi di dati, gi il-
lustrate,  necessario ricordare:

- word processor (elaboratore di testi);
- fogli elettronici;
- programmi di grafica.

Word processor

 Tra le applicazioni pi estese dell'elaboratore va certamente
collocato il suo uso come elaboratore di testi, attraverso pac-
chetti software chiamati word processor.
 L'elaboratore viene utilizzato come strumento per la scrittu-
ra, non solo come se si avesse a disposizione una macchina da
scrivere, ma piuttosto come un potente strumento per orga-
nizzare e conservare i propri dati.
 I vantaggi che derivano dall'uso di questa modalit di scrittura
sono molteplici:

 -  possibile effettuare un numero infinito di modifiche e cor-
rezioni invisibili del testo, che risulta sempre pronto per es-
sere stampato in modo perfetto (viene eliminata l'eventuale
fase di stesura a mano del testo e la successiva ricopiatura);
 -  possibile manipolare la parte tipografica di un testo mo-
dificando i tipi di caratteri, l'impaginazione e inserendo even-
tualmente parti grafiche o tabellari;
 -  possibile conservare i testi per riprenderli in un secondo
tempo;
 - l'archiviazione dei documenti registrati su supporti magne-
tici richiede meno spazio rispetto ad un supporto cartaceo;
 - un testo elaborato con il computer pu essere inviato attra-
verso reti locali o geografiche ad altri elaboratori.

 L'uso di un word processor risulta molto semplice anche per
i non esperti di calcolatori: in breve tempo  possibile acquisi-
re dimestichezza con le modalit di scrittura proprie del siste-
ma a disposizione, essere in grado di memorizzare il proprio
testo o ricercare e riprendere uno gi memorizzato.
 I vantaggi derivanti dall'uso di un sistema di scrittura risulta-
no talmente evidenti che nessuno, anche dopo una limitata
esperienza, potrebbe pi pensare di tornare ad una normale
macchina da scrivere.
 Il tema di come la scrittura elettronica possa influenzare la
produzione scritta costituisce materia per un dibattito aperto
ormai da parecchi anni ma ancora fertile di nuovi contributi,
man mano che l'uso del word processor si va diffondendo in
modo capillare non solo tra gli addetti ai lavori (scrittori, gior-
nalisti, ecc.) ma tra strati sempre pi ampi della popolazione
Anche l'ambito formativo e scolastico ne viene necessaria
mente investito: sono molteplici gli studi che analizzano gli ef-
fetti dello strumento sia nella fase iniziale della produzione
scritta, sia in momenti successivi della formazione. E possibile
ipotizzare che lo strumento favorisca la disponibilit allo scri-
vere, creando una sorta di trampolino per superare il cosid-
detto blocco della pagina bianca. Le possibilit di scompor-
re il proprio testo, di duplicare e spostare parti, creano una
sorta di possibilit di manipolazione fisica del testo che con-
sente di provare un effetto di maggiore libert e creativit ri-
spetto ad una situazione con carta e penna.

Fogli elettronici

 In molti settori, specie di tipo economico o scientifico,  ne-
cessario trattare contemporaneamente molte variabili corre-
late fra loro. Un foglio elettronico, che in genere si presenta
sotto forma di un grande foglio con righe e colonne, consente
di inserire dati e di fare tutta una serie di calcoli, facendo va-
riare di volta in volta una o pi tra le variabili presenti. Oltre a
rendere pi rapide determinate operazioni di calcolo, con-
sente di indagare sull'andamento di un sistema che viene rap-
presentato con un apposito modello matematico e consente
pertanto di svolgere delle conseguenti attivit di tipo decisio-
nale.
 Tutti i fogli includono la possibilit di rendere i dati in forma
grafica, secondo diverse modalit.
 I fogli elettronici pi recenti sono spesso inglobati in un pac-
chetto software che consente delle prestazioni integrate di va-
rio tipo, dal sistema di scrittura, al data base, al foglio elettro-
nico.

Programmi di grafica

 I programmi di grafica consentono di disegnare sullo scher-
mo dell'elaboratore e di produrre poi le relative stampe. Con
questi programmi  possibile effettuare sia disegni di tipo
geometrico che disegni a mano libera, operando con una
grande quantit di strumenti messi a disposizione dal pro-
gramma: pennelli, barattoli di vernice, semplice matita.
 Le applicazioni grafiche, sempre pi diffuse e appariscenti,





   -

 un tipica ~inestra~ di un programma di grafica.
sono culminate, in questi ultimi anni, nelle applicazioni della
cosiddetta realt vi7tuale.
 Questo settore, pur non essendo costituito da tecnologie vera-
mente innovative, associa tra loro pi settori tecnologici con-
solidati e, sfruttando pienamente i risultati ottenuti nella gra-
fica tridimensionale, costituisce un'applicazione informatica
di un certo interesse e, secondo alcuni, ricca di implicazioni
anche sociali.
 Molto note sono le applicazioni grafiche che danno origine
alle figurefrattali. E questo uno dei campi pi spettacolari di
applicazione della ricorsivit; semplici programmi ricorsivi
sono in grado di generare figure complesse tutte basate sulla
ripetizione, con diversi parametri, di poche figure di base.
 Ma la grande diffusione delle tecnologie basate sulle imma-
gini ha prodotto molti cambiamenti anche nel settore della ri-
cerca matematica. Il computer  diventato uno strumento che
permette esperimenti matematici che aprono prospettive del
tutto nuove. Nella matematica applicata il computer serve per
calcolare una risposta approssimata, quando la teoria non  in
grado di darne una esatta, ma in nessun modo la teoria viene
a dipendere dal computer per le sue conclusioni; al contrario,
i due metodi, teorico e algoritmico, sono come due punti di vi-
sta indipendenti dello stesso oggetto (Davis e Hersh, The
mathenlatical experience, 1981). Man mano che strumenti e
programmi informatici diventano pi sofisticati, di pari passo
aumentano la profondit e la rilevanza delle applicazioni del-
la grafica computerizzata ai problemi matematici. Il calcola-
tore sta costringendo i matematici a riconsiderare la natura
stessa della dimostrazione. Per ottenere certe dimostrazioni
negli ultimi anni sl sono dovute eseguire masse enormi di cal-
coli, sicch nessun essere umano pu verificare queste cosid-
dette dimostrazioni al calcolatore; solo altri calcolatori sono in
grado di farlo. In questi ultimi anni il calcolatore grafico ha
consentito di dimostrare risultati per nulla banali in matema-
tica, utilizzando le capacit grafiche di un computer i mate-
matici sono riusciti a comprendere in che modo fosse possibi-
le trovare una dimostrazione analitica delle propriet della fi-
gura che si potevano vedere solo su di uno schermo. Il compu-
ter  servito da guida nella costruzione di una dimostrazione
form~le, ha fornito 11110 stnlmento che ha consentito di esplo-
rare a fondo il problema. Inoltre, ha permesso di avere una com-
prensione cos approfondita delle caratteristiche di un esempio,
da consentire la costruzione di un'infinit di nuovi esempi.

Ipertesto

 L'ipertesto  un soft~vare che organizza in modo non lineare
un'informazione testuale. Siamo abituati a trattare le informa-
zioni secondo una modalit lineare, un libro o un giornale
hanno le informazioni trattate e visualizzate in sequenza,
un'informazione  in relazione solo ed esclusivamente con
quella che la precede e con quella che la segue. L'ipertesto, in-
vece, consente che una certa unit informativa risulti connes-
sa con un'altra unit. Elementi fondamentali di un ipertesto
sono le unit di informazione, i collegamenti esistenti tra le
varie unit, le rappresentazioni dei nodi e dei legami tra loro,
le modalit di passaggio da un'unit all'altra.
 Elemento principale  il nodo inforrnativo. Il nodo  l'unit di
informazione che costituisce un blocco autosufficiente, sia dal
punto di vista linguistico che da quello comunicativo. Un
nodo pu esser composto da un singolo vocabolo, da una fra-
se, o anche da pi frasi. Nell'ambiente dell'ipertesto un nodo
deve essere caratterizzato in modo evidente, in genere  rico-
noscibile perch assume un particolare colore, o  caratteriz-
zato da un simbolo grafico, un'icona.
 I collegamenti tra le varie unit sono assicurati attraverso
collegamenti (link) tra un nodo di partenza e un nodo di arri-
vo. Questi legami sono quelli che realizzano effettivamente la
non linearit dell'informazione, consentendo all'utente di
muoversi e navigare con una semplice pressione (clic) del
mouse. Il termine navigazione  usato proprio per esprimere
la possibilit di spostarsi da un punto all'altro nell'ambiente
informativo. I legami devono essere riconoscibili e semplici da
attivare e devono essere caratterizzati da una elevata libert
nella scelta delle direzioni di navigazione.
 Un ipertesto deve essere caratterizzato da una elevata liber-
t nella scelta delle direzioni di navigazione e deve prevedere
strumenti di navigazione articolati, con il compito di dirigere
la consultazione, correggere errori di navigazione o annullare
il percorso seguito.
          82                             L'INFORMATICA

 In genere nell'ipertesto  presente uno speciale nodo infor-
mativo, contenente il disegno della mappa dei legami, o dei
legami principali esistenti tra i nodi. Con queste mappe l'uten-
te pu ricostruire la posizione occupata in un certo istante, op-
pure individuare il nodo in cui desidera posizionarsi.
 Tra gli strumenti per la navigazione nell'ipertesto, il back-
tracking  uno strumento di navigazione che permette di ri-
percorrere a ritroso il percorso seguito fino a quel momento;
deve inoltre essere sempre possibile riprendere il percorso
dal punto iniziale.
 Spesso il termine ipertesto  accostato a quello di ipermedia.
L'ipermedia  la tecnologia informatica che consente di orga-
nizzare in modo non lineare informazioni provenienti da pi
media (testi scritti, testi orali, immagini statiche, disegni, gra-
fici, dipinti, immagini in movimento, suoni e musiche). La dif-
ferenza pi evidente tra ipermedia e ipertesto  quindi nella
pi ampia tipologia di codici linguistici che l'ipermedia  in
grado di ospitare.
 Molti esempi di ipertesti e di ipermedia sono ormai disponi-
bili, la loro applicazione trova ampio spazio in tutto il settore
educativo e formativo, in quanto costituisce una diversa mo-
dalit di presentazione della conoscenza. La valenza formati-
va di questo software potr essere realmente valutata solo
dopo un'esperienza significativa e un'accurata analisi dei ri-
sultati. Al momento, le esperienze di uso di iDertesti Der la
formazione, sono ancora in fase iniziale.

 L 'intelligenza artificiale e i sistemi esperti

 Con il termine intelligenza artificiale si identifica quel settore,
nell'ambito dell'informatica, che studia i fondamenti teorici,
le metodologie e le tecniche che permettono di progettare
hardware e software capaci di consentire all'elaboratore delle
prestazioni che, ad un osservatore comune, sembrerebbero di
pertinenza esclusiva dell'intelligenza umana.
 Settori tipici dell'intelligenza artificiale sono quelli riguar-
danti i sistemi di visione, il riconoscimento vocale, i sistemi di
apprendimento.
 Le applicazioni dell'intelligenza artificiale sono molteplici;
tra le pi significative si collocano i sistemi esperti.

AMBIENTI APPLICATIVI

 Un sistema esperto  un programma in grado di fornire una
consulenza su un determinato settore di conoscenza. Le pre-
stazioni sono paragonabili a quelle che possono essere fornite
da un esperto umano. Il sistema  in grado di accettare delle
domande corredate da alcune informazioni in ingresso e di
generare delle risposte attingendo ad una base dati molto ar-
ticolata, base di conoscenza, relativa al settore specifico.
 Lo schema seguente illustra i principali componenti di un si-
stema esperto:


 esperlo uman


base delle
conoscenze

    \





conclusioni
(soluzioni del
caso in esame)

                             utente ~


richiesta e ottenimento
di informazioni
sul caso in esame



                               risolutore dei problemi
             (motore inferenziale)



giustificazioni del
comportamento
nell'ottenimento della
conclusione


Componenti di un sistema esperto (Archer e Westmore, I sistemi esperti e le loro pro-
spettive, 1985).

 La base della conoscenza viene costituita grazie all'apporto di
esperti della materia che mettono a disposizione la loro espe-
rienza in un particolare settore, in termini di conoscenze e di
comportamenti. Il motore inferenziale  una sorta di algoritmo
in grado di dedurre risposte, in genere su metodi proba-
bilistici, in base a determinate richieste dell'utente del siste-
ma.
 Il sistema fornisce pertanto un comportamento intelligen-
te ed  inoltre in grado di giustificare passo per passo la ri-
sposta data, sulla base delle informazioni in suo possesso, im-
magazzinate nella base di conoscenza.
 Esistono sistemi esperti per la diagnosi di malattie, per la
progettazione di hardware, per la pianificazione di esperi-
menti scientifici.
 Gli anni Ottanta sono stati caratterizzati da grandi entusia-
smi per la tecnologia dei sistemi esperti, purtroppo anni pi
recenti hanno dimostrato quanto siano costosi sistemi esperti
realmente tali, e i prodotti in uso sono necessariamente limi-
tati ad ambiti molto ridotti e circoscritti.

Conclusioni





 Il mondo dell'informatica  in continua evoluzione e conti-
nua ad investire capillarmente la vita di ciascuno. Le difficolt
maggiori in alcuni settori di interesse dell'informatica, tuttavia,
riguardano la complessit dell'uomo come essere pensante e
come esecutore di azioni. La capacit umana di utilizzare in
modo estremamente flessibile un'enorme base di conoscenza,
pur in contesti molto differenti, costituisce un modello di in-
telligenza non ancora minimamente eguagliabile da una mac-
china. Se le ricerche nell'ambito dell'informatica andranno
pertanto di pari passo con quelle relative alla mente umana, i
risultati conseguiti potranno riguardare campi sempre pi va-
sti e vicini alle reali esigenze delljuomo.
 Ma, forse, il cercare di raggiungere con una macchina l'intel-
ligenza umana , complessivamente, una strada sbagliata:
l'elaboratore ha una sua intelligenza specifica (sa mantenere
in memoria tutti i dati o fare rapidamente determinate elabora-
zioni, meglio dell'uomo). Le macchine dovrebbero essere usa-
te solo per fare meglio ci che all'uomo risulta pi difficile.
Le tappe fondamentali dell'informatica





Generazioni di
 calcolatori

     1944
primo computer
    Mark 1

  1946- 1954
    prima
 generazione

 1955 - 1964
   seconda
 generazione

 1965 - 1974
    terza
 generazione

 1975 - 1980
    quarta
 generazione

1980 - a oggi
    quinta
 generazione

     Caratteristiche
       tecnologiche
  rel elettromagnetico



  calcolatori a valvole



  transistor, memorie di
ferrite, dischi magnetici


circuiti integrati a bassa
   e media integrazione


     circuiti ad alta
  integrazione, memorie
     a semiconduttore
   cir ti. a molto alta
   mtegrazlone, memone
cd-rom, calcolatori con
pi processori centrali

   Caratteristiche del
        soft~vare

     predisposizione
 manuale dei circuiti di
         calcolo

   linguaggio macchina,
  linguaggi assemblativi


linguaggi ad alto livello,
       librerie di
     sottoprogrammi,
    elaborazione batch

   multiprogrammazione,
  sistemi operativi per
   multiprogrammazione,
 informatica distribuita

   sistemi concorrenti,
sistemi operativi iconici


 sistemi esperti, realt
 virtuale, multimedialit

Glossario





Albero: struttur dati costituita da un elemento, detto radice, e da un insie-
  me di sottoalberi, anch'essi alberi.
Algoritmo: insieme di operazioni che, eseguite in un certo ordine, consen-
  tono di ottenere la soluzione di un problema in un numero finito di
  passi.
And: operatore logico.
Archivio: raccolta di dati memorizzati e organizzati in modo da consentir-
  ne il reperimento, l'analisi e la modifica.
Array: dato strutturato costituito da un numero finito di elementi, tutti
  dello stesso tipo.
ASCII: codice alfanumerico.
Assembler: linguaggio di programmazione di tipo simbolico.
Attributo: propriet elementare di un'entit.
Automa: una macchina (fisica o astratta) che esegue algoritmi.

Base di conoscenza: insieme di informazioni che consentono, in un siste-
   ma esperto, di fare deduzioni su uno specifico dominio.
Base di dati: un sistema integrato di archivi e di operazioni eseguibili su di
   essi.
Basic: linguaggio di programmazione ad alto livello.
Bit: unit minima di informazione.
Bootstrap: programma residente in memoria che consente di caricare il si-
  stema operativo all'accensione del calcolatore.
Byte: raggruppamento di otto bit contigui.

C: linguaggio di programmazione ad alto livello.
Calcolatore: macchina in grado di eseguire istruzioni aritmetiche e logi-
  che.
Campo: elemento di un record.
Carattere: un simbolo a cui  associato un elemento del codice.
Cd-rom: compact disk, supporto di memorizzazione a sola lettura.
Chiave: campo di record usato per identificare un elemento.
Coda: struttura di dati gestiti con la modalit il primo che entra  il pri-
  mo che esce.
Codice alfanumerico: codice per la rappresentazione di un alfabeto di
  simboli alfabetici, numerici, segni di interpunzione, simboli speciali.
Codice binario: codice costruito utilizzando un alfabeto di due soli simboli.
Codifica: la traduzione di un algoritmo in un linguaggio di programma-
  zione.
Compilatore: programma che traduce un programma scritto in un lin-
  guaggio ad alto livello in uno equivalente scritto in linguaggio macchi-

Complessit computazionale (di un algoritmo): numero delle istruzioni ele-
  mentari che vengono eseguite, in funzione della dimensione dei dati di in-
  gresso.
Computer: v. calcolatore.
CPU: unit centrale di elaborazione.

Dato: rappresentazione formale di un'informazione.
Dato semplice: dato elementare, non ulteriormente scomponibile.
Dato strutturato: dato definito a partire da dati semplici o da altri dati gi
  definiti.
DBMS: sistema di gestione di una base di dati.
Duagramma Nassi-Schneidermann: rappresentazione grafica di una strut-
  tura algoritmica di controllo.
Diagramma sintattico: rappresentazione grafica di regole grammaticali.
Directory: insieme di informazioni riguardanti il contenuto di un disco, or-
  ganizzate spesso in una struttura ad albero.
Disco: supporto di memoria secondaria ad accesso diretto.

Elaboratore: v. calcolatore.
Enht: classi di oggetti o persone del mondo reale, distintamente identifi-
  cabili, implicate in un'applicazione.

File: archivio.
Foglio elettronico: softvare applicativo nel quale i dati sono organizzati
  prevalentemente in forma tabellare.
Fortran: linguaggio di programmazione ad alto livello.

Grafo: struttura di dati non lineare composta da nodi e archi.
Grammatica: sistema formale costituito da un insieme di simboli termina-
  li, da un insieme di simboli non terminali, da un assioma e da un insie-
  me di regole che consentono di generare tutte le stringhe di un deter-
  minato linguaggio.

Hardware: l'insieme dei componenti fisici di un elaboratore.
Hash: modalit di organizzazione di un archivio che prevede l'individua-
  zione di un indirizzo di memoria attraverso una funzione di trasforma-
  zione di chiave.

Icona: immagine rappresentativa di un'operazione da compiere.
Indice: in un array l'indicatore di posizione di un singolo elemento, nel
  contesto degli archivi, un particolare file contenente, in un qualche or-
  dine, solo le chiavi di un archivio pi ampio, al quale rimanda
Indirizzo di memoria: numero binario che identifica la posizione di una lo-
  cazione di memoria.
Informatica: insieme delle discipline e delle tecniche di elaborazione
  automatica dei dati.
Inforrnazione: interpretazione di un dato.
Input: ingresso.

Intelligenza artificiale: settore dell'informatica che tratta di metodi e tecni-
  che informatiche tendenti a produrre dalla macchina prestazioni simili
  a quelle umane.
Interattivo:  detto di un programma che consente un dialogo tra utente
  ed elaboratore.
Interprete: programma che consente di tradurre ed eseguire un program-
  ma scritto in un linguaggio ad alto livello.
  o: ingresso e uscita.
Ipertesto: software che organizza in modo non lineare un'informazione te-
  stuale.
Istruzione: azione o operazione da compiere.
Iterazione: una delle tre strutture algoritmiche fondamentali.

Linguaggio artificiale: linguaggio formale definito per un determinato sco-
   po.
Linguaggio di programmazione: linguaggio artificiale utilizzato per scrive-
   re programmi che devono essere eseguiti da un calcolatore.
Linguaggio formale: insieme di stringhe costruibili con un determinato al-
   fabeto e definite attraverso regole grammaticali.
Linguaggio macch'na: linguaggio binario usato direttamente dalla cPu.
Lisp: linguaggio di programmazione ad alto livello.
Lista: struttura di dati lineare costituita da elementi tutti dello stesso tipo.

Macch'na di Turing: modello logico di calcolo.
Memoria: dispositivo di registrazione dei dati.
Memoria di massa: memoria ausiliaria per la memorizzazione permanen-
  te dei dati.
Modello di Von Neurnann: modello logico-funzionale di un elaboratore.
Mouse: dispositivo di puntamento.
Multiprogrammazione: tecnica che consente di mantenere contempora-
  neamente in memoria centrale pi programmi tra loro indipendenti.

Nastro magnetico: supporto fisico di memorizzazione ad accesso sequen-
  ziale.
Not: operatore logico.
Nucleo: componente del sistema operativo.

Or operatorelogico.
Output: uscita.
Overflow: trabocco.

Paradigma di programmazione: modalit di soluzione di un problema.
Partizione di memoria: una parte di memoria suddivisa.
Pascal: linguaggio di programmazione ad alto livello.
Periferiche: dispositivi di ingresso e/o uscita dei dati.
Pila: struttura di dati gestiti con la modalit l'ultimo che entra  il primo
  che esce.
Procedura: porzione di algoritmo che risolve un sottoproblema.
Processo: programma in esecuzione.
Processore: esecutore di operazioni.
Programma: algoritmo espresso in un linguaggio di programmazione.
                90                                GLOSSARIO

Prolog: linguaggio di programmazione ad alto livello.

Record: dato strutturato che consente di aggregare dati di tipo diverso.
Ricorsivit: possibilit di una procedura o di una funzione di richiamare
  se stessa al suo interno.
Ridondanza: ripetizione di un dato, eliminabile senza perdita di informa-
  zione.
Risorsa: componente hardware o software gestita dal sistema operativo.

Schema logico (di una base di dati): descrizione degli oggetti di un'appli-
  cazione in un modello logico di base di dati.
Selezione: struttura algoritmica fondamentale.
Sequenza: struttura algoritmica fondamentale.
Sistema esperto: software in grado di fornire una consulenza su un deter-
  minato settore di conoscenza.
Sistema operah'vo: insieme dei componenti software che consentono di ge-
  stire le risorse del sistema e che ne consentono all'utente un semplice
  utilizzo.
Software: programma o insieme di programmi.
Software applicativo: programma rivolto a una specifica applicazione.
Stampante: unit periferica per la stampa.
Stringa: sequenza di caratteri o di elementi di un alfabeto.
Struthura d dah: organizzazione specifica di un insieme di dati.
Struthure di controllo: strutture algoritmiche.

Tastiera: unit di input dei dati.
Tavole di verit: tabelle che definiscono gli operatori logici.
Teorema di Bohm-Jacopini: teorema che asserisce che un algoritmo 
  sempre definibile tramite le sole strutture fondamentali di controllo.
Tesi di Church: tesi che asserisce che tutti i modelli di calcolo sono tra di
  loro equivalenti per quanto riguarda la computabilit o la non computa-
  bilit.
Time-sharing: tecnica di ripartizione del tempo di cPu ai processi in ese-
  cuzione.
Tipo ooleano: tipo di dato semplice costituito da due soli valori, vero e
  falso.
Tipo di dato: insieme di valori e insieme di operazioni su di essi.
Top-down: metodologia di programmazione dal generale al particolare.

Unit di controllo: unit che coordina e controlla i vari dispositivi del si-
  stema.
Unit logico-aritmehica: unit che svolge le operazioni logiche e aritmeti-
  che.

Vettore: v. array.

Word processor elaboratore di testi.

fine.