Informatica - Appunti

Esame di informatica generale – lezioni prof. Vanni – a.a 2005-06

La parola "informatica" deriva dalla fusione di due termini: informazione e automatico. E significa, appunto, informazione automatica. In altri termini, l'informatica è interessata all'informazione e a processi o procedimenti automatici. Come primo approccio possiamo dire che essa è l'insieme delle tecniche e dei metodi relativi all'elaborazione, alla trasmissione, alla conservazione e alla rappresentazione delle informazioni in modo automatico.

L'informazione e la comunicazione

La parola "informazione" significa dar forma a idee e concetti. Quando ci informiamo, l'informazione la ricerchiamo attraverso un sistema di comunicazione. Comunicazione vuol dire: mettere in comune. Per avviare un processo di comunicazione devono esistere almeno due elementi che devono entrare in comunicazione fra di loro: uno che funge da comunicatore e un altro che funge da destinatario. La comunicazione può anche avvenire tra un individuo ed una macchina. Inoltre, possono comunicare fra loro anche macchine e macchine.

Nell'ambito di un sistema di comunicazione, affinché la trasmissione dell'informazione sia efficace, è necessario che comunicatore e destinatario usino lo stesso codice comunicativo. Si presuppone, inoltre, che debba esistere un messaggio da veicolare. Un altro elemento base affinché la comunicazione diventi efficace è che sia il comunicatore che il destinatario utilizzino lo stesso mezzo, lo stesso canale di comunicazione. È chiaro che più ampio è il canale, maggiore è la quantità di dati che possiamo trasmettere nell'unità di tempo.

Un altro elemento da prendere in considerazione è che durante un processo di comunicazione è necessario eliminare o ridurre quanto più possibile il rumore che si inserisce nel canale, rumore che può ostacolare la comunicazione.

Il modello di Shannon

Il modello presentato è il modello di Shannon della teoria dell'informazione, esso risale al 1948 e fu proposto dall'autore in chiave matematica.

Riepilogo: La teoria dell'informazione prende in considerazione il processo di trasmissione delle informazioni da un elemento A, chiamato "comunicatore", a un elemento B, chiamato "destinatario" della comunicazione. La comunicazione viene veicolata attraverso un messaggio. Questo messaggio deve essere codificato in un codice comunicativo comune, veicolato attraverso un canale di comunicazione e su questo canale devono trovarsi entrambi i protagonisti del processo di comunicazione. Inoltre, questo canale deve essere esente da rumore di fondo.

Un aspetto importante della teoria dell'informazione di Shannon è quello della "misura dell'informazione": dobbiamo stabilire, quindi, un'unità di misura. L'unità base di misura dell'informazione è "la più piccola tra due scelte equiprobabili". L'unità minima base di misura dell'informazione è il BIT. BIT è una forma contratta, un acronimo del termine inglese "binary digit" cioè di "cifra binaria".

Informazione ed entropia

In natura ogni corpo lasciato a sé ha una sua struttura fisica, una sua struttura ben precisa, un suo equilibrio, un suo ordine, ma questo ordine tende nel tempo per natura a trasformarsi in disordine. Qualsiasi corpo in natura tende all'entropia. L'entropia è la tendenza naturale di un corpo verso la disorganizzazione. Ma l'informazione consiste in un processo inverso. In questo fenomeno si va dal disordine verso l'ordine. Più diamo informazioni, maggiore è l'organizzazione che si viene ad avere.

Shannon non ha fatto che riprendere quella che era la formulazione matematica data nel Secondo Principio della Termodinamica, riportandola con il segno meno, per indicare che il processo dell'informazione è un processo inverso a quello dell'entropia.

Parametri fondamentali dell'informazione

Tre sono i parametri fondamentali che caratterizzano l'informazione:

• Tipo
• Valore
• Attributo

Il tipo è l'insieme degli elementi tra i quali viene operata la scelta. Il valore corrisponde al particolare elemento scelto. L'attributo è il significato attribuito all'elemento scelto. Ad esempio, se diciamo: "Maria è un'allieva del Corso di Informatica.", in questo caso il tipo rappresenta il nome di persona "Maria" e se tra i nomi di persona si sceglie "Maria", il singolo nome scelto è il valore; Maria come "allieva del Corso di Informatica" è l'attributo.

Calcolatori e processi di elaborazione

Quando usiamo il termine "calcolatore", cosa vogliamo indicare? Vogliamo indicare che le macchine in questione sono macchine in grado di eseguire dei calcoli. L'esecuzione dei calcoli presuppone l'esistenza di un insieme di procedure. Queste procedure consistono nella trasformazione dei dati iniziali in risultati finali. Le macchine, a differenza dell'uomo, mancano di apprendimento. L'elaboratore, ogni volta che lo accendiamo, è unatabula rasa, cioè non ha nessuna conoscenza, quindi, ogni volta che vogliamo che esso svolga un processo di elaborazione, gli dobbiamo fornire necessariamente tutto il set di istruzioni su come svolgere questo processo, su come trasformare questi dati iniziali in risultati finali. Le procedure da fornire le dobbiamo offrire nei minimi particolari. Ciò che dobbiamo fornire all'elaboratore per fargli eseguire un processo di elaborazione si chiama "programma".

Hardware e software

Da qui distinguiamo due parti dell'elaboratore:

• La prima è l'hardware (l'insieme dei componenti fisici che costituiscono un elaboratore). Esso è la parte tangibile della macchina.
• La parte immateriale, non tangibile, che costituisce il programma che di volta in volta diamo alla macchina la chiamiamo "software". Essa contiene tutte le informazioni che trasferiamo sulla macchina. (Ricordiamo a proposito che le informazioni sono immateriali).

Il processo di elaborazione

Dobbiamo chiarire che cosa intendiamo per "processo di elaborazione". Facciamo l'esempio della preparazione di una torta. Per preparare una torta si ha bisogno degli ingredienti e della ricetta ossia dell'insieme di istruzioni fornite in modo tale da applicare queste procedure per raggiungere quel risultato finale che è la torta. X = {x₁, x₂, x₃, …, x_n}. Nella preparazione di una torta, X è l'insieme dei dati. Attraverso un processo di elaborazione l'insieme X è trasformato in un insieme Y che rappresenta il risultato. Ad esempio, nella preparazione di una torta, manipolando i vari ingredienti otteniamo la torta Y: Y dipende da X. Quello che abbiamo appena espresso è il concetto di "funzione".

Il processo di elaborazione, cioè la trasformazione di dati iniziali in risultati, dipende dalle regole di trasformazione che applichiamo. Se cambiamo, infatti, gli ingredienti applicando ad essi le procedure esecutive, muterà il risultato. Ma se sugli stessi ingredienti applichiamo procedure differenti, il risultato muterà egualmente. Il risultato, quindi, dipenderà sia dalla variazione dei dati sia dalla variazione delle procedure. F non è altro che il programma che dobbiamo dare alla macchina affinché la macchina acquisisca le modalità con cui deve trasformare i dati per ottenere poi un risultato.

Il teorema di Gödel e le regole di trasformazione

C'è un problema: possiamo avere dei dati ma questi dati non necessariamente ci porteranno a un risultato. Questo avviene quando non siamo in grado di trovare delle regole di trasformazione. Si pensi che ci sono dei problemi logicamente esatti che però non sono risolvibili perché non siamo in grado di trovare delle regole di trasformazione in un risultato. Questo è una teoria fondamentale nell'ambito matematico che viene chiamato "teorema di Gödel" il quale dice che ci sono problemi logicamente esatti, ma non risolvibili perché non siamo in grado di trovare delle relazioni risolutive. Quello che noi dobbiamo studiare è come si costruiscono queste regole.

Teoria dell'algoritmo e sue proprietà

Il concetto di algoritmo nasce nell'ambito della matematica nell'VIII sec. d.C. ed è stato poi ripreso nell'ambito informatico subendo un'evoluzione, in quanto, negli anni '30, si è provveduto ad elaborare una "teoria degli algoritmi". Questo concetto nasce nella cultura araba ad opera di un matematico-astronomo arabo Abu Abdallah Muhammad Ibn Musa al-Juarizmí, cioè nativo di una località chiamata all'epoca al-Juarizmi. La parola "algoritmo" è infatti un'espressione latinizzata della località araba al-Juarizmi. Nella cultura occidentale questo concetto è stato introdotto da un matematico pisano di nome Leonardo Pisano, conosciuto come Fibonacci, il quale scrisse un'opera famosa intitolata "Liber abaci" dove riporta quelli che sono stati gli studi condotti da questo matematico arabo.

Che cosa intendiamo per algoritmo? L'insieme delle procedure di calcolo che vengono messe in atto per risolvere un problema. Un algoritmo per poter essere funzionale deve presentare delle proprietà.

• Una prima proprietà è che il numero delle istruzioni deve essere finito e queste istruzioni devono presentare un'istruzione iniziale (istruzione di start, di partenza) e una finale (istruzione di stop).
• Le istruzioni devono essere poste in modo chiaro, senza nessuna forma di ambiguità e devono essere poste in modo univoco. La macchina non apprende, ogni volta che inizia un processo di elaborazione è come se lo iniziasse per la prima volta. Dobbiamo, quindi, essere molto espliciti quando diamo le istruzioni alla macchina, cioè quando scriviamo l'algoritmo esecutivo per la prima volta.
• Alla macchina dobbiamo dare tutte le procedure nei minimi particolari senza nessun salto e senza alcuna forma di ambiguità.

Di fronte a un'istruzione non ben esplicitata la macchina non è in grado di procedere. Le macchine non apprendono e non hanno nessun grado di intelligenza. Quando siamo di fronte ad una macchina dobbiamo pensare che abbiamo a che fare con il più grande stupido possibile.

• Quando costruiamo algoritmi procedurali per le macchine dobbiamo tener presente queste regole di base:
• Le istruzioni devono essere fornite in numero finito, cioè ogni istruzione deve avere un inizio ed una fine.
• Le istruzioni devono essere poste in modo sequenziale rispettando una cronologia
• Le istruzioni devono essere date in modo ed univoco chiaro senza nessuna forma di ambiguità.

Macchine dedicate e macchine generiche

Generalmente quando parliamo di elaboratori, di computer abbiamo a che fare con macchine generiche. Tutte le macchine di cui disponiamo le possiamo descrivere in due tipologie: macchine generiche e macchine dedicate (macchine che svolgono sempre lo stesso processo).

Una macchina dedicata è la lavatrice perché svolge sempre lo stesso compito, quello di lavare la biancheria. È una macchina che è progettata per assolvere quest'unica funzione. Queste macchine sono costruite con un programma che è detto "programma fisso". Sono macchine sequenziali: la lavatrice esegue un algoritmo che è sempre lo stesso.

Le macchine generiche sono invece macchine che hanno un hardware, un insieme di componenti i quali ci consentono di svolgere un qualsiasi processo di elaborazione. In queste macchine ogni volta dobbiamo fornire alla macchina l'algoritmo esecutivo che consente di fargli svolgere quel particolare processo di elaborazione.

Negli anni '30 si cominciò a studiare, da parte dei matematici, come fosse possibile costruire una macchina in grado di risolvere un qualsiasi problema. Generalmente le macchine che venivano costruite fino a quell'epoca erano delle macchine specializzate nella risoluzione di alcuni tipi di problemi, l'interesse dei matematici degli anni '30 tra cui in grande matematico inglese, Alan Turing si incentrano su quelle che sarebbero dovute essere le caratteristiche che avrebbe dovuto possedere un risolutore automatico di algoritmi., cioè una macchina in grado di svolgere qualsiasi problema.

Una macchina generica per essere operativa deve essere specializzata. Ogni volta che diamo le istruzioni a questa macchina generica, la specializziamo. Ad esempio se un utente ha necessità di scrivere un documento, che cosa ha bisogno di fornire alla macchina? Deve fornire alla macchina tutte le istruzioni che facciano in modo che la macchina diventi una macchina da scrivere. Generalmente noi lanciamo il programma Word; attraverso questo programma possiamo far sì che la macchina diventi macchina da scrivere e consenta all'utente di scrivere il documento. Così anche se un utente ha necessità di fare un disegno o un collegamento internet, ha bisogno di dare le istruzioni idonee alla macchina, di specializzarla come una macchina per far disegni oppure di renderla una macchina in grado di collegarsi ad internet. Il concetto di "macchina generica" è un concetto fondamentale. Alan Turing descrive quello che è l'automa generalizzato; ci parla di questa macchina teorica e di quali dovrebbero essere i requisiti che dovrebbe possedere questa macchina teorica, questa macchina in grado di risolvere qualsiasi tipo di problema. L'unica difficoltà è quella di descrivere in modo dettagliato ogni procedura, di dire alla macchina come arrivare alla risoluzione di un problema. Quest'approccio è nato da quelli che sono gli studi su quelli che sono i processi che mettiamo in atto quando risolviamo i problemi.

La risoluzione dei problemi

Per risolvere un problema di che cosa abbiamo bisogno? Abbiamo bisogno di dati. Questi dati ci vengono forniti all'esterno e li trasferiamo al nostro interno. Se li abbiamo scritti su un pezzo di carta o sulla lavagna li trasferiamo al nostro interno. Leggiamo su un pezzo di carta questi dati utilizzando un organo di senso, la vista, che ci consente di introdurli nella nostra mente, impegnando il cervello (l'hardware) e di trasferirli all'interno scrivendoli nella nostra memoria. Noi siamo dotati di due tipi di memoria, quella a breve termine e quella a lungo termine. La memoria a breve termine perde facilmente il suo contenuto. Sappiamo come far rimanere i concetti nella mente: far sì che la conoscenza passi dalla memoria a breve termine, che perde facilmente il contenuto, nella memoria a lungo termine, che è quella memoria dove il contenuto rimane nel tempo. I dati li scriviamo nella nostra memoria e li lavoriamo.

Generalmente come codifichiamo le informazioni? Utilizzando un alfabeto. Costruiamo delle frasi; queste frasi debbono essere organizzate in modo corretto rispettando quelle che sono delle regole sintattiche. In questo modo abbiamo rappresentato mediante dei simboli, che sono i simboli alfabetici, l'informazione. Nella nostra mente, però, l'immagine che si forma nella nostra retina viene trasferita, attraverso delle terminazioni nervose, trasformata sotto forma di impulsi elettrici, che passano – attraverso il nervo ottico – e vengono registrati nella nostra memoria.

Che cosa abbiamo notato? Che c'è stato prima un momento di codifica, utilizzando simboli alfabetici o caratteri alfabetici. Successivamente c'è stata una transcodifica, cioè un passaggio da questo codice simbolico in un codice elettrico. L'operazione di transcodifica è il passaggio da un codice ad un altro codice comunicativo.

Elaborazione e programmazione

Come avviene l'elaborazione? L'elaborazione avviene perché questi dati vengono trasformati secondo certe regole. Generalmente noi disponiamo solo sommariamente di regole; ma la maggior parte delle operazioni da fare le abbiamo apprese nel tempo, perché siamo organismi dotati di intelligenza. Passiamo alle macchine. Le macchine non apprendono e, allora, quando dobbiamo far svolgere un processo di elaborazione alla macchina, dobbiamo esplicitare tutte le istruzioni necessarie per lo svolgimento del processo di elaborazione. Qui sta la grossa difficoltà nel programmare le macchine, cioè nel dover esplicitare nei minimi particolari tutte le operazioni che la macchina deve poter svolgere. Perché la macchina, in caso di difficoltà, non è in grado di ricordare come ha fatto la volta precedente o come ha fatto in casi analoghi.

Nel 1946-47 queste teorie hanno consentito la costruzione del primo elaboratore moderno. Lo studio dell'automa infinito di Turing risale al 1936. Se vogliamo che questa macchina sia un risolutore di problemi essa deve essere in grado di eseguire un algoritmo che, per proprietà sua, deve essere finito.

Origini dell'informatica

L'informatica nasce da due ambiti di studio: dalla teoria dell'informazione e dagli studi sulla trasformazione dell'informazione in modo automatico, cioè dell'approccio con la teoria degli automi. L'informatica rappresenta l'elaborazione, la conservazione, la trasmissione, la rappresentazione delle informazioni in modo automatico. La teoria dell'informazione e la teoria degli automi sono i due pilastri su cui essa si regge.

Questo concetto di "macchina generica" è perfezionato dieci anni dopo da Von Neumann, che getta le basi di quella che è la macchina reale. Bisogna fare una premessa sul perché dell'interesse, in questo periodo nei confronti del calcolo automatico. Negli anni '40 nasce una disciplina, la cibernetica il cui fondatore è Norbert Wiener. L'elemento di base della cibernetica è l'informazione. La cibernetica aveva intenzione di studiare tutti i sistemi autoregolati.