Appunti necessari per esame di informatica

INFORMATICA - 2 Cfu

1. Introduzione all’Informatica – principali strutture dei dati

La parola INFORMATICA è l’acronimo di due parole: INFORmazione e autoMATICA.

La principale caratteristica dell’Informatica è la trasformazione (o elaborazione) di informazioni in modo automatico

cioè senza il diretto e continuo intervento dell’uomo.

INFORMATICA viene anche indicata come :

• Informatics

• Informatique

• Information processing

• Electronic Data Processing

• Computer Science

• IT o Information Technology o Tecnologia dell’ informazione

ICT (Information and Communication Technologies) indica l’insieme dei metodi e delle tecnologie che

realizzano sistemi di elaborazione, trasmissione e ricezione di informazioni

Definizione di Informatica

L’ Informatica è l’insieme delle discipline e delle tecniche che hanno per obiettivo:

• la raccolta, l’organizzazione ed il trattamento automatico delle informazioni mediante macchine (gli elaboratori);

• i procedimenti automatici speciali (i programmi) per la trasformazione delle informazioni.

Bisogna sottolineare che è indispensabile una fase di raccolta, di organizzazione e di “trattamento” delle informazioni iniziali

per renderle idonee alla elaborazione.

E’ inoltre indispensabile sviluppare o utilizzare dei procedimenti automatici (i programmi) che siano in grado di “trasformare”

le informazioni iniziali in informazioni finali cioè i risultati del programma.

Eventi del 1600-1800

Gli elaboratori elettronici sono il risultato di varie invenzioni sia per quanto riguarda i componenti delle macchine sia per

quanto riguarda la programmazione sia per le teorie che sono alla base dell’ Informatica. Nel seguito, si tenta di tracciare una

breve storia sugli eventi prodromici degli elaboratori, anche se è estremamente difficile riportare tali eventi in modo completo

e preciso per la incertezza delle fonti e della datazione.

1. Il primo evento che riportiamo è la progettazione del riporto automatico su macchina digitale. Nel lontano 1642 il

francese Blaise Pascal, a soli diciannove anni, inventò una macchina in grado di addizionare numeri a dodici cifre. Tale

macchina, chiamata in onore del suo inventore “pascalina”, è composta da ingranaggi affiancati che ruotano durante

l’esecuzione di un’addizione. Su ogni ingranaggio sono rappresentate le cifre da 0 a 9. La macchina funziona come

un’abaco cinese ma, mentre per l’abaco cinese il riporto di un’addizione si effettua “manualmente”, la pascalina effettua il

riporto dell’addizione mediante un’opportuna leva inserita tra due ingranaggi successivi.

Il sistema binario

Il secondo evento notevole accade nello stesso secolo (1600) da parte di Gottfried Leibnitz che crea il sistema

binario costituito, a differenza di quello decimale, dalle combinazioni di due sole cifre (zero e uno).

Il sistema binario, insieme agli sviluppi della teoria binaria del matematico George Boole sarà ben tre secoli dopo

l’alfabeto degli attuali elaboratori.

Lo stesso Leibnitz perfezionò la “pascalina” rendendola in grado di eseguire moltiplicazioni realizzate da addizioni

ripetute.

Il binario

Un insieme binario è un insieme composto da due cifre (cifra zero o uno) o da due monosillabi (si oppure no) o da due

segni geometrici (punto e linea) oppure dal colore (bianco e nero), etc. cioè un insieme binario ha due soli elementi come

quelli rappresentati nella figura accanto.

Con il termine BIT che è l’acronimo di BInary digiT si indica uno dei due elementi dell’insieme binario.

BIT, quindi, è Il termine inglese per indicare una cifra binaria cioè una “informazione binaria” .

Alcuni insiemi binari

Primo esempio di traduzione del linguaggio umano in codici registrati su schede perforate

1

Il terzo evento notevole da richiamare accadde intorno al 1804 ed è il primo esempio di traduzione del linguaggio

umano in codici registrati su schede perforate.

Il meccanico francese Joseph Marie Jacquard inventò un dispositivo che automatizzava i processi di orditura dei tessuti.

Per noi è stato il primo esempio di registrazione delle ISTRUZIONI su un apposito cartoncino.

La lettura della scheda avviene mediante una matrice di aghi perpendicolare alla scheda:

dove c’è un foro passa l’ago che seleziona il filo da tessere. Una successione di schede rappresentano il disegno da

realizzare.

Esemplare di scheda con fori che rappresentano una parte di un disegno da realizzare con un processo di orditura

Babbage

Il quarto evento è’ dovuto, intorno al 1833, al matematico inglese Charles Babbage che progettò ma non potè realizzare

per l’inesistenza di una idonea forma di energia il primo calcolatore numerico automatico di tipo meccanico: la macchina

analitica (ANALYTICAL ENGINE). La macchina analitica era suddivisa in quattro sottounità: una sottounità deputata alla

raccolta dei dati, un’ altra a trasferire i dati in una terza (detta “mulino”) dove si eseguivano le operazioni i cui risultati erano

rappresentati nella quarta unità. Schematicamente: Raccolta dati -> Trasferimento dati -> MULINO -> RISULTATI.

Il progetto con il suo schema si è, invece, dimostrato molto attuale per la giusta individuazione dei sottosistemi componenti.

Il grande merito di Babbage è stato di aver inventato il controllo automatico cioè la possibilità di far eseguire operazioni

con un programma specificamente predisposto.

Babbage, invece, inventò e realizzò, sulla falsariga della pascalina, una macchina in grado di produrre tabelle matematiche

(in figura).

Primo esempio di dati codificati registrati su un supporto

E passiamo ad un altro importante evento: la prima volta che le informazioni vennero registrate con un codice (IL

CODICE HOLLERITH) su un supporto.

Nel 1850 l’ingegnere Hermann Hollerith, inventore statunitense, sulla falsariga della applicazione di Jacquard citata, adottò

una particolare codifica (codifica Hollerith) per registrare dati su schede meccanografiche e per immetterli in macchine che

potevano contabilizzare i dati registrati.

Nel 1890 tale metodo fu adottato per eseguire il Censimento della popolazione degli Stati uniti d’ America. I dati relativi ai

caratteri dei componenti il nucleo familiare (cognome, nome, data di nascita, etc.) venivano registrati bucando, secondo

un’opportuna codifica appositi cartoncini (le schede meccanografiche). La figura in alto riporta il codice Hollerith con la

corrispondenza dei simboli con i fori. La scheda era suddivisa in zone (campi) di prefissata ampiezza. In ogni campo era

registrato un dato. Scheda perforata con il codice Hollerith

Eventi del 1900

Tra il 1930 ed il 1945 tre americani (H. Aiken, J. Atanasoff e G. Stibitz ed un tedesco (K. Zuse) riescono a realizzare i primi

prototipi di elaboratori:

• Aiken inventò il MARK I: macchina elettromeccanica a relé concettualmente simile al progetto di Babbage. Si ricorda che il

relè (cfr figura a lato) è un dispositivo dotato di contatti elettrici che vengono azionati per mezzo di un elettromagnete

quando la bobina viene percorsa dalla corrente.

• Atanasoff creò il primo calcolatore elettronico non a relè.

• Stibitz produsse una macchina a relé ma in grado di elaborare secondo la codifica binaria, anche le cifre decimali.

• Zuse inventò una serie di macchine a relé (Z1, Z2 e Z3) con uso di numeri registrati con la virgola mobile. La virgola mobile è

una particolare forma di rappresentazione dei numeri reali. La rappresentazione in virgola mobile consiste nel

±x

rappresentare qualsiasi numero reale R nella forma: R = ±M ?b . Dove M viene detta mantissa di m cifre, b è la base del

sistema di numerazione adottato, x è l’esponente, detto caratteristica ed indica di quanti posti deve essere spostata la virgola

+1 -2

per ottenere R. Ad esempio: R=+5,24 = +0,524 x10 ; R = -0,0048 = -0,48 x10

2 Schema di relé. (relè aperto/relè chiuso): può memorizzare due valori binari.

Alan Turing (1912-1954)

Alan Turing è il vero progettista di uno schema di elaboratore ed è riconosciuto uno dei padri dell’Informatica poiché inventò

una macchina teorica considerata fondamentale nella teoria della “computabilità” cioè per verificare se un problema è

risolubile con un elaboratore oppure no.

Turing, matematico e logico inglese, imparò a leggere in tre settimane. Si laureò a 22 anni a Cambridge in Meccanica

quantistica.

Nel 1934 descrisse lil progetto della sua “macchina” . Durante la II guerra mondiale riuscì a decifrare il codice segreto della

macchina cifrante tedesca di nome ENIGMA.

Partecipò al progettò Colossus (primo computer elettronico digitale programmabile).

Arrestato nel 1952 fu condannato ad una severissima pena. Si suicidò nel 1954.

Schema della macchina di Turing

Lo schema funzionale della macchina di Turing (Figura a lato) prevede:

• un’unità di memoria esterna fatta da un nastro illimitato nei due sensi e suddiviso in tante celle vuote o contenenti un solo

simbolo c (ad es. 0 o 1) di un alfabeto detto “alfabeto esterno”. Su tale unità risiedono le informazioni “lette” o “scritte” dalla

i

macchina;

• un’unità di controllo con memoria in cui è posto un programma finito; l’ unità di controllo è fornita di un dispositivo in grado

sia di spostare il nastro a destra (D), a sinistra (S) o lasciarlo fermo (F) sia di leggere e/o scrivere in una qualsiasi delle celle

del nastro un simbolo dell’alfabeto esterno;

• Ø un’unità di memoria interna in grado di conservare i simboli s , s , … s che costituiscono l’alfabeto interno (ad es. A, B, C,

0 1 k

s etc. … detti stati della macchina);

0

• Ø un’unità logica che ha due ingressi e tre uscite. L’unità riceve in ingresso una coppia di valori (s , c ) e produce, in uscita,

i i

una terna di valori (s , c , m ) dove m indica (D,S,F) cioè uno dei tre simboli di movimento (destra, sinistra, fermo).

j j j j

Schema della macchina di Turing

La macchina di Turing può eseguire solo un tipo di operazione che produce tre azioni:

1 il carattere c viene scritto nella memoria esterna al posto di c ;

j i

2 il carattere s viene scritto nella memoria interna rimpiazzando s ;

j i

3 m (D,S,F) è registrato nella memoria di controllo e tale movimento viene eseguito dall’unità di controllo prima della lettura

j

della stessa o altra cella.

Per realizzare un programma si crea una matrice (matrice funzionale) con tante righe quanti sono i simboli dell’ alfabeto

esterno e tante colonne quanti sono i simboli dell’alfabeto interno (stati della macchina).

La macchina legge un simbolo c e lo invia all’unità logica insieme al simbolo s scritto nella memoria interna. In base alla

i i

matrice funzionale viene determinata quale terna (s , c , m ) produrre in uscita. Il simbolo s viene scritto nella memoria

j j j j

interna, il simbolo c viene scritto sul nastro al posto del simbolo precedente e l’unità di controllo esegue il movimento m .

j j

3 Schema di matrice funzionale

ESEMPIO: sostituisci 0 con 1 ed 1 con 0 Schema della macchina di Turing

Operazioni per invertire O con 1 e 1 con 0 sulla memoria

Hardware, Algoritmo, Software

E’ stato evidenziato quali sono stati gli sviluppi delle macchine per elaborare i dati. E’ necessario ora precisare che le

macchine devono essere istruite sul problema specifico da risolvere e bisogna differenziare la “macchina” dal “problema da

risolvere”.

Hardware è la macchina intesa come insieme di componenti meccanici, elettrici, elettromeccanici ed elettronici.

Per poter effettuare un’elaborazione dei dati, definito il problema, è necessario sviluppare un algoritmo e poi tradurre questo

algoritmo in una serie di istruzioni (programma) che devono essere eseguite dalla macchina di elaborazione. Si intende per

ALGORITMO uno schema o procedimento sistematico di calcolo cioè l’insieme ordinato delle fasi logiche che

conducono alla soluzione di un problema (ovvero di problemi di una stessa classe) trasformando i dati iniziali a

disposizione.

Software è l’insieme dei programmi contenenti istruzioni per risolvere un problema.

• si definisce Istruzione o comando ogni singola operazione.

• si definisce Programma di calcolo o semplicemente programma la successione delle istruzioni scritte in uno specifico

linguaggio.

Modello di elaborazione manuale (non automatica) Schema di elaborazione manuale di un insieme di istruzioni

scritte su un foglio e dati da elaborare scritti su un altro foglio

(modello "penna-carta")

4

Esempio di algoritmo

Per meglio chiarire le differenze tra algoritmo e software, supponiamo di voler risolvere un’equazione di primo grado ad

una sola incognita del tipo ax+b=0 e di poter disporre di un uomo che abbia una calcolatrice e che, quindi, possa eseguire i

calcoli senza però sapere come si risolve un’equazione di primo grado. L’operatore può disporre di penna, carta per scrivere

e di una calcolatrice per eseguire i calcoli.

Poiché non sa come risolvere l’equazione è necessario elencare minuziosamente tutte le operazioni che, dai dati iniziali (i

coefficienti a e b) portano ai risultati cioè al valore della radice (x). Se il coefficiente a è diverso da zero, la formula risolutiva

che conduce al calcolo della radice è: x=-b/a

Il procedimento porta a raccogliere, organizzare e trattare i dati e le operazioni nel modo seguente. Si predispone un

FOGLIO DATI DI INGRESSO, un FOGLIO RISULTATI INTERMEDI, un FOGLIO ISTRUZIONI ed un FOGLIO DATI DI

USCITA (cfr. figura a lato). Sul FOGLIO DATI DI INGRESSO, nell’ipotesi che l’equazione da risolvere sia 2x-10 = 0, si

scrivono due etichette (attributi) e i valori dei coefficienti a,b ad esempio 2 e -10. Il FOGLIO ISTRUZIONI dettaglia le

istruzioni da eseguire. Il FOGLIO DATI DI USCITA è predisposto solo con l’etichetta X= .

Schema del "modello penna-carta"

Sul FOGLIO ISTRUZIONI sono dettagliate le seguenti istruzioni:

1 Inizio

2 Leggi i valori associati ad A e B e scrivili su R.I.

3 Moltiplica per -1 il valore associato a B ed il risultato scrivilo a fianco alla voce C

4 Dividi il valore associato a C per il valore associato ad A ed il risultato scrivilo a fianco alla voce X su R.I.(risultati intermedi)

5 Riporta il valore associato ad X sul FOGLIO DATI DI USCITA

6 Fine

Con riferimento al problema illustrato, la formula risolutiva dell’ equazione di primo grado è un algoritmo ed il programma è

rappresentato dalle ISTRUZIONI (1 a 6) dettagliate nel FOGLIO ISTRUZIONI. Come si può immediatamente notare il

programma è scritto in lingua italiana e può essere comprensibile solo da parte di un “operatore umano”.

Foglio dati di ingressi Foglio risultati intermedi

Alcune applicazioni dell’Informatica

Si riportano alcuni ambiti delle principali applicazioni dell’Informatica: Economico-commerciale, industriale, in casa, per la

didattica, per la formazione professionale, nello spettacolo, nelle arti, nelle scienze, in ingegneria, in matematica, nei sistemi

informativi, nella navigazione, etc.

• Elaborazione delle transazioni

• Telelavoro

• Editoria elettronica (desktop publishing)

• Analisi finanziarie

• CAD (Computer aided design) progettazione

• CAM (Computer aided manufacturing) produzione virtuale

• Cinema, musica, animazioni, sport, animazioni, ecc.

• Cataloghi, consultazioni, ricerche, acquisti

• Operazioni bancarie, giochi

Discipline alla base delle applicazioni informatiche

A conclusione della lezione introduttiva, si evidenziano con le figure a fianco le discipline che sono alla base delle

applicazioni informatiche.

5

Nella figura in alto sono indicate le relazioni che intercorro tra la Psicologia, la Logica e la Matematica discreta per la

progettazione degli Algoritmi.

Nella figura in basso, sono indicate le principali materie come la Fisica e la Matematica che sono alla base della

costruzione del hardware dei sistemi di elaborazione. Infine, è sottolineata l’importanza della Linguistica che, con i suoi

linguaggi formali, contribuisce alla progettazione dei programmi.

Psicologia, Logica e Fisica, Matematica e

Matematica discreta alla Linguistica alla base delle

base della applicazioni applicazioni informatiche

informatiche

3 – Dall’analogico al digitale

Sistemi di numerazione posizionali e non

Viene definito sistema di numerazione o numerazione l’insieme delle regole e dei simboli per rappresentare i numeri.

Assumono particolare caratteristica i sistemi di numerazione detti posizionali.

La numerazione romana, ad esempio (cfr figura per i suoi simboli principali), non è un sistema di numerazione posizionale

perché il valore di ogni cifra dipende sia dalla sua posizione nell’ambito del numero ma anche da più di una regola.

Esempio: IV è diverso da VI ed assumono due valori differenti: cioè il valore è differente se la cifra I si trova a sinistra o a

destra di una cifra più grande Alcuni simboli della numerazione romana (non posizionale)

Sistemi Posizionali

Per i sistemi posizionali si definisce base il numero dei simboli diversi che si possono utilizzare. La base della

numerazione in cui è espresso il numero è indicata in basso a destra; quando si omette la base si intende in base 10.

Sistema posizionale significa, che ogni numero &egra