| << |  <  |  >  | >> |

Indice

  9 Prefazione
 11 Ringraziamenti

    Metodi informazionali


 15 1.   Operazioni e Algoritmi

    1.1. Classi, sequenze e relazioni, 15
    1.2. Operazioni, funzioni e predicati, 17
    1.3. Strutture, calcoli e algoritmi, 21
    1.4. Esercizi proposti, 24

 26 2.   Espressioni e Comandi

    2.1. Espressioni e calcoli di valutazione, 26
    2.2. Lambda espressioni e condizionali, 29
    2.3. Combinatori e comandi, 31
    2.4. Esercizi proposti, 34

 37 3.   Istruzioni e Programmi

    3.1. Spazi di dati e tipi di calcoli, 37
    3.2. Programmi, macchine e automi, 40
    3.3. Programmi a registri, 42
    3.4. Linguaggi procedurali, 46
    3.5. Esercizi proposti, 48

 50 4.   Circuiti e Macchine

    4.1. Funzioni booleane e circuiti, 50
    4.2. Macchina von Neumann e ciclo di esecuzione, 52
    4.3. Esercizi proposti, 54

 56 5.   Dati e Tipi

    5.1. Grafi e alberi, 57
    5.2. Stringhe, vettori e liste, 60
    5.3. Memorie indirizzabili e sequenziali, 63
    5.4. File, record e puntatori, 64
    5.5. Esercizi proposti, 66

 68 6.   Simboli e Codici

    6.1. Caratteristiche dell'informazione digitale, 68
    6.2. Misure informative e codici, 72
    6.3. Codice ASCII e UNICODE, 76
    6.4. Codici istantanei e algoritmo di Huffmann, 77
    6.5. Compressione, trasmissione e sicurezza, 79
    6.6. Esercizi proposti, 81

 83 7.   Linguaggi e Automi

    7.1. Linguaggi e operazioni su linguaggi, 83
    7.2. Automi a stati finiti ed espressioni regolari, 85
    7.3. Grammatiche di Chomsky, 87
    7.4. Calcolabilità, semidecidibilità e decidibilità, 91
    7.5. Macchine di Turing e Tesi di Church, 93
    7.6. Indecidibilità e complessità di calcolo, 97
    7.7. Esercizi proposti, 102

104 8.   Risorse e Interfacce

    8.1. Funzioni di un sistema operativo, 104
    8.2. Filesystem e linguaggio di comandi, 108
    8.3. Livelli di programmazione, 111
    8.4. Applicazioni e interfacce grafiche, 113
    8.5. Unix e Linux, 116

119 9.   Reti e Servizi

    9.1. Servizi e protocolli, 119
    9.2. Ipertesti e formati, 121
    9.3. Accesso e uso di servizi fondamentali, 122
    9.4. Standard e complessità, 123

    Appendici

129 A. Laboratorio di Linux

       a cura di D. Botturi, F. Fontana e G. Pravadelli

130 A.1.   Primi passi con Linux
    A.1.1. Preliminari, 130
    A.1.2. L'accesso al sistema, 132
    A.1.3. I primi comandi, 133
    A.1.4. L'esecuzione dei programmi, 137
    A.1.5. Il manuale, 140

142 A.2.   Il filesystem di Linux
    A.2.1. Concetti di base del filesystem, 143
    A.2.2. Il Virtual File System, 150

151 A.3.   Comandi shell su file testuali e text editing di
           base
    A.3.1. Redirezionamento dei flussi standard, 152
    A.3.2. Archiviazione di file, 153
    A.3.3. Comandi per l'editing elementare di testi, 155
    A.3.4. Editing di testi da shell, 162

164 A.4.   La Shell
    A.4.1. Quali shell?, 165
    A.4.2. Programmare la shell, 166
    A.4.3. Costrutti del linguaggio di shell, 170

175 A.5.   Servizi client/server di base
    A.5.1. Comunicazioni via rete tra host, 176
    A.5.2. Protocolli client/server, 176
    A.5.3. Accesso a risorse remote, 177
    A.5.4. Condizioni basilari per la connettività, 179
    A.5.5. Servizi di base, 181
    A.5.6. Evoluzioni dei servizi di base, 185

188 A.6.   Strutture e uso dei comandi multimediali
    A.6.1. Visualizzazione, gestione e stampa di documenti,
           190
    A.6.2. Manipolazione di immagini, 194
    A.6.3. Ascolto di audio, 194
    A.6.4. Rappresentazione di sequenze video, 196

197 A.7.   Internet
    A.7.1. Le Principali Applicazioni, 199
    A.7.2. I Tipi di Connessione, 199
    A.7.3. La Navigazione del World Wide Web, 200
    A.7.4. La Posta Elettronica, 205

208 B. Esercizi di riepilogo


219 Bibliografia

 

| << |  <  |  >  | >> |

Pagina 9

Questo testo intende presentare i concetti di base dell'informatica in modo da porre in primo piano l'aspetto scientifico di tale disciplina.

Se è vero che gli aspetti tecnologici hanno un ruolo determinante nello sviluppo di nuovi modelli concettuali, è tuttavia altrettanto vero che nessuna tecnologia di lungo periodo può essere concepita al di fuori di modelli teorici solidi. Quello che spesso risulta difficile, nel trasmettere i concetti di base dell'informatica, è l'elaborazione di un linguaggio che sia indipendente dalle forme contingenti con cui questi concetti si ritrovano nella pratica usuale. È quindi una sfida non indifferente definire un percorso concettuale semplice, ma al tempo stesso non banale o fuorviante, in cui, in una struttura coerente, gli attori principali di tale disciplina risultino organizzati nella loro essenza, spogliati dalle vesti delle molte rappresentazioni con cui, a ritmo spesso vorticoso, sono costretti a esibirsi nel proscenio del «mercato informatico».

La valenza concettuale di algoritmi e linguaggi è talmente forte da essere alla base della cultura scientifica a un livello preliminare rispetto alla stessa nozione di dimostrazione che stigmatizza l'idea di rigore formale delle scienze esatte. L'automa che nella triade algoritmo-linguaggio-automa è l'ultimo arrivato ha anche ridisegnato i ruoli che le nozioni precedenti avevano nel quadro concettuale prenovecentesco. Far capire l'essenza di tali concetti e il loro legame con i concetti delle altre discipline scientifiche è un dovere degli studiosi di informatica e un diritto di chi desidera avere coordinate di riferimento che non siano solo gerghi tecnici tarati su esigenze di commercializzazione o semplicemente di descrizione superficiale.

I manuali di base dell'informatica si differenziano enormemente da quelli delle altre discipline sorelle quali matematica e fisica, i quali hanno avuto un tempo di decantazione ben più lungo e non hanno sofferto dell'impellenza tecnologica dovuta alla contrazione dei ritmi dell'ultimo secolo. Vi è spesso una implicita confusione tra manuale scientifico e manuale di istruzioni. È come se si pretendesse di spiegare l'elettromagnetismo utilizzando un tester per la misura di tensioni e correnti. Ovviamente l'uso di tali strumenti aiuta spesso a comprendere i concetti fisici, tuttavia la loro essenza è radicata nei costrutti teorici fondamentali di grandezza, equazione, dimensione, sistema di riferimento, legge fisica, princìpi di conservazione...

Riuscire a usare un computer per elaborare un documento è una cosa utilissima, ma non è informatica nel senso scientifico di tale termine, come non è fisica sapere progettare e realizzare un impianto di illuminazione o sapere assemblare componenti per costruire una radio. Ed è fondamentale ribadire che di contenuto scientifico l'informatica ne ha da vendere.

Se l'informatica non avesse avuto alle spalle un arsenale ricco di costrutti teorici la tecnologia non avrebbe potuto produrre quello che oggi è sotto gli occhi di tutti. Ma tali concetti affondano le loro radici in questioni di logica matematica, di matematica discreta, di teoria dell'informazione: cosa è un calcolo? come si rappresenta? come si realizza? come si analizza? come si valuta? Cosa è un dato? come si strutturano i dati ai fini di un certo calcolo? Come si misura l'informazione? Nessuno oggi confonde i problemi fondamentali delle equazioni di moto con quelli tecnici di realizzazione di veicoli. Tuttavia, dietro la chiarezza di stile e di contenuti della matematica e della fisica di base vi è stato il lavoro di generazioni di scienziati che si sono posti il problema dei percorsi concettuali delle loro discipline.

Oggi uno sforzo analogo è necessario in informatica, ove i problemi di confusione e di travisamento hanno anche un motivo più profondo, che non è solo quello di una disciplina giovane, o quello delle interferenze socioeconomiche. Infatti «informazione», «linguaggi», «algoritmi» come «oggetti» di studio interferiscono con se stessi come «strumenti» di studio, in una maniera più sottile rispetto a quanto non possa avvenire nello studio di equazioni differenziali. E spesso la confusione concettuale delle esemplificazioni è inerente a una confusione tra il linguaggio che si usa e quello che si studia. Il profilo che segue nasce dalla consapevolezza di tali difficoltà, ma anche dalla volontà di tentare e sperimentare la ricerca di un semplice «syllabus concettuale» collegato anche a una prima attività di laboratorio.

| << |  <  |  >  | >> |

Pagina 34

Sia S l'insieme delle configurazioni di uno spazio di dati (nozione che sarà precisata più avanti).

Diciamo comando un'espressione C che denota una funzione fc da S in S. L' esecuzione di un comando C in una configurazione s dello spazio dei dati produce la trasformazione della configurazione s in fc(s).

Una macchina (di calcolo) è un'entità fisica i cui stati S corrispondono a configurazioni di uno spazio di dati e che è in grado di eseguire dei comandi.

Indicheremo con [M:C] la funzione associata all'esecuzione del comando C da parte della macchina M.

Si parla più propriamente di automa come macchina astratta, ovvero definita a prescindere dalla sua realizzazione fisica.

| << |  <  |  >  | >> |

Pagina 40

Un comando può essere determinato componendo vari comandi. Tuttavia, piuttosto che impartire a un esecutore i comandi uno dopo l'altro, aspettando ogni volta che un comando venga eseguito prima di impartire il comando successivo, è più conveniente in molti casi concepire espressioni che individuano una serie di comandi e un ordine di applicazione di tali comandi. Si perviene in tal modo alla nozione di programma.

Sia C l'insieme dei comandi eseguibili da una macchina M, e sia S l'insieme degli stati di M.

Un programma P per una macchina M è un'espressione che specifica una funzione parziale fp da S in C. L'esecuzione di un programma P da parte di M in uno stato s produce una sequenza di stati, possibilmente infinita, detta computazione di P da parte di M:

[...]

Un programma è articolato in una sequenza di istruzioni:

(I1, I2, ..., In).

Sebbene le istruzioni siano collegate ai comandi, tuttavia è bene distinguere tra le prime e i secondi, in quanto le istruzioni corrispondono a unità di composizione del programma, ma non è detto che vi sia una corrispondenza uno a uno tra le istruzioni e i comandi eseguiti da un programma. Infatti le istruzioni determinano i comandi da eseguire, ma alcune istruzioni, dette imperative, specificano direttamente un comando; altre, dette di controllo, determinano, in base a certe condizioni, se, come e dove continuare nella computazione.

Inoltre, una stessa istruzione può specificare più volte un comando da eseguire e l'ordine della sequenza temporale di esecuzione dei comandi può non coincidere con l'ordine di comparsa delle istruzioni relative.

Una macchina a programma è una macchina (di calcolo) in grado di acquisire dall'esterno un programma e di eseguirlo.

Un linguaggio di programmazione è determinato da un insieme di regole con cui si costruiscono i programmi eseguibili da una macchina M. Più astrattamente possiamo semplicemente dire che un linguaggio di programmazione L(M) è l'insieme dei programmi eseguibili da una macchina a programma M.

Un programma è in definitiva la specifica di un algoritmo eseguibile da una macchina a programma, che in tal senso è in grado di «capire» e realizzare gli algoritmi espressi dai programmi scritti nel proprio linguaggio di programmazione.

| << |  <  |  >  | >> |

Pagina 44

In questo scenario si concentra il nucleo di sviluppo di tutta l'informatica. Problemi e algoritmi sono antichi quanto la matematica, tuttavia ciò che ne ha completamente ridefinito i ruoli e la dinamica interna sono stati gli automi, concepiti e costruiti a partire dalla metà del Novecento, e i linguaggi di programmazione, che si sono rivelati intermediari essenziali tra automi e algoritmi.

Infatti l'algoritmo, in quanto metodo risolutivo definito dall'uomo, necessita di essere «tradotto» entro un linguaggio comprensibile all'automa di calcolo, come programma da esso eseguibile. Ma spesso tale traduzione si articola in vari livelli intermedi, attraverso una gerarchia di programmi complessa e articolata, prima di arrivare al programma finale eseguito dall'automa. Il metodo che si utilizza al riguardo è basato sulla nozione di macchina astratta costruita a partire da un'altra macchina.

Infatti, una macchina M può essere realizzata a partire da una macchina «più semplice» M' non appena i programmi di L(M) siano tradotti in opportuni programmi di L(M').

| << |  <  |  >  | >> |

Pagina 56

Dati e Tipi

Un dato è una qualsiasi entità a cui si attribuisce una funzione informativa. Una tale spiegazione è però circolare. Infatti, cosa è un'informazione? È quanto viene veicolato da un dato. In definitiva le due nozioni si postulano in modo reciproco.

Come l'energia si manifesta nel passaggio di materia o nel cambiamento di «forme» della materia, anche l'informazione si manifesta nel passaggio da un dato a un altro, o da una rappresentazione in termini di certi dati a quella in termini di altri dati.

Allora ciò che risulta essenziale nella nozione di dato è proprio il concetto di trasformazione del dato in altro dato e quindi ancora il concetto di operazione. In definitiva i dati sono caratterizzati essenzialmente dalle operazioni a essi applicabili. In tal senso un insieme di dati è caratterizzato da un tipo definito come modello predicativo su un dominio di elementi detti appunto dati.

I sistemi numerici sono, in prima approssimazione, esempi di tipi di dati. Tuttavia i dati devono avere anche una natura «effettiva» cioè devono essere rappresentabili tramite entità fisiche.

Quando i dati sono concepiti, piuttosto che come elementi singoli globalmente considerati, come entità con una articolazione interna, allora ciascun dato è concepibile come una struttura che dicesi appunto struttura dati e che, per la natura fisica di dato, deve essere finita, ovvero costituita da un dominio finito e da un numero finito di relazioni su tale dominio. Quindi, ancora una volta, anche se a un livello diverso, è essenziale usare il concetto di modello predicativo, in questo caso come «forma» di organizzazione dei dati.

| << |  <  |  >  | >> |

Pagina 68

Simboli e Codici

Come per tutte le nozioni fondamentali, è impossibile dare subito una definizione univoca e semplice di informazione.

Il concetto di informazione è legato intimamente a quelli di azione, comunicazione, forma, struttura, ordine, complessità, significato, conoscenza, segno, simbolo, dato, segnale, messaggio, codice, rappresentazione, deduzione. Varie teorie tese a definire rigorosamente l'informazione si sono di volta in volta ricondotte a connotare l'informazione in relazione a taluno di tali concetti. Inoltre, spesso l'informazione si precisa in termini del contesto a cui si riferisce: informazione numerica, statistica, qualitativa, simbolica, biologica, linguistica, artistica. Tutto ciò indica la vastità di orizzonti entro cui si colloca un concetto talmente pervasivo. Il XX secolo è in un certo senso l'èra dell'informazione, su cui si sono basate e sviluppate le discipline emergenti del secolo: la biologia molecolare e l'informatica, che hanno dimostrato una sorprendente analogia nel tipo di strutture di base su cui sono fondati i loro processi fondamentali.

6.1. Caratteristiche dell'informazione digitale

Come si è già detto un dato è un'entità fisica a cui è attribuibile un valore informativo, prescindendo dalla sua natura discreta o continua, quantitativa o qualitativa. Tuttavia, la nozione di dato più direttamente collegata al concetto di calcolo presenta due aspetti: l'aspetto discreto e quello quantitativo. L'informazione convogliata da tali dati si dice anche digitale ed è in tal senso sempre riconducibile a una stringa di simboli (cifre, caratteri, segni, lettere, engrammi, grafemi,fonemi...), ovvero elementi di un insieme finito detto alfabeto. La codifica di un dato è a sua volta suscettibile di ulteriore codifica, ovvero la codifica di un dato è a sua volta un dato.

L'informazione discreta associata a una stringa è digitale, in opposizione all'informazione analogica di un'immagine presa nella sua globalità, di un suono, o in generale una grandezza continua esprimibile con numeri reali o funzioni a valori reali.

| << |  <  |  >  | >> |

Pagina 104

Risorse e Interfacce

Se riconsideriamo lo schema di una macchina von Neumann (figura 4.2) vediamo che essa è composta di varie parti collegate, sotto il controllo di una unità centrale. Queste parti sono risorse in grado di svolgere delle funzioni. Tuttavia, anche i programmi memorizzati in memoria secondaria sono delle risorse e gli stessi dati sono delle risorse. In tal senso una risorsa è una qualsiasi entità che svolge un ruolo in un processo di elaborazione dell'informazione. La distinzione classica in hardware e software si riferisce alla fisicità o meno delle risorse. L'unità centrale, quella di elaborazione, le varie memorie (ROM, RAM, Flash, Cache, IDE, EIDE, Floppy, SCSI, CD...), le unità di ingresso/uscita, e le varie periferiche (devices) costituiscono l'hardware del sistema, mentre i programmi costituiscono il software.

Tuttavia, ciascuna risorsa ha un suo modo d'uso e un suo livello nella gerarchia di macchine che si sviluppa a partire dalla macchina di base (CPU, ALU, ROM, RAM, Bus). Si pone quindi il problema di coordinare tali risorse e di renderle utilizzabili da parte degli utenti, in modo efficiente ed evitando che ogni utente debba conoscere i dettagli specifici del funzionamento di tutte le risorse.

8.1. Funzioni di un sistema operativo

Un sistema operativo è un insieme di programmi coordinati che gestisce le risorse di una macchina e la sua interazione con gli utenti.

| << |  <  |  >  | >> |

Pagina 115

Nella programmazione a oggetti un tipo di oggetto detto anche classe è caratterizzato da una serie di attributi di tipi prefissati e da certi metodi (operazioni) in essa definiti. Un oggetto della classe è individuato da un nome che ne caratterizza la sua identità e da uno stato determinato dal valore dei suoi attributi, variabile nel tempo. Quindi un oggetto si crea, si osserva e si modifica. La modificazione di un oggetto avviene secondo i metodi definiti nella sua classe producendo certi effetti sullo stato dell'oggetto. Tuttavia i metodi sono caratterizzati da una specifica pubblica, o interfaccia, che ne esprime astrattamente gli effetti senza indicare come questi sono ottenuti e da una specifica privata, cioè un' implementazione che dice come realizzarli. Questo implica che un oggetto e i suoi metodi possono essere utilizzati anche senza conoscerne l'implementazione. Avviene quindi qualcosa di analogo al caso di una teoria assiomatica che descrive una funzione senza specificare come essa possa essere calcolata da uno specifico automa. Questa visione astratta consente una facile componibilità di moduli programmativi per realizzare comportamenti complessi. Caratteristiche intimamente legate alla natura astratta degli oggetti sono l'ereditarietà, la specializzazione e la generalizzazione. Ovvero, data una classe di oggetti si può definire una sua sottoclasse che ne costituisce una specializzazione, semplicemente aggiungendo altri attributi e metodi a quelli della classe originale, in modo che le caratteristiche della classe originale vengano ereditate dalla sottoclasse. Inversamente, una classe di oggetti può essere generalizzata semplicemente eliminando delle caratteristiche particolari e rendendola appunto di tipo più generale. Altre caratteristiche di più recente introduzione hanno aggiunto altre prospettive importanti collegate alla comunicazione tra oggetti e alla loro mobilità in uno spazio in cui anche i canali di comunicazione non sono fissi, ma si riconfigurano nel tempo.

| << |  <  |