Home

Federica EU

1/25

Sergio Scippacercola » 2.Le principali strutture dei dati

Caratteristiche dell’informazione

Ogni informazione è caratterizzabile mediante il “tipo, valore ed attributo”.

Definizioni:

Tipo è l’insieme degli elementi su cui si effettua la scelta dell’informazione;
valore è lo specifico elemento scelto dall’insieme Tipo;
attributo (o variabile o categoria) è un nome mnemonico abbreviato del Tipo.

Ad esempio, Roma è un nome di città che ha per tipo “insieme dei nomi di città”, può avere come attributo “NOME-DI-CITTA” o semplicemente “CITTA”. Roma, Napoli, Milano sono dei possibili valori. Un numero intero ha per tipo “insieme dei numeri interi”, attributo “INTERO” e per valore uno specifico numero ad es. 45 o 3543.

Dati privi di organizzazione

Ai fini di una qualsiasi elaborazione, i dati devono essere organizzati e classificati.

Gli esempi a lato mostrano dati che, volutamente messi in disordine indicano che se restano disorganizzati e disordinati, non potranno essere elaborati.

Si definiscono:

dati semplici o elementari i dati costituiti solo da cifre o numeri o caratteri dell’alfabeto come, ad esempio, quelli indicati nella figura a lato.

Dati privi di organizzazione e classificazione.

Dati organizzati per riga – Aggregati di dati elementari

Si definiscono:

dati aggregati i dati costituiti da più dati elementari (cfr figura a lato)

Ad esempio sono aggregati di dati elementari un insieme di lettere (ad es. BUCCI) un insieme di cifre (ad es. 876543 o 081) etc.

Dati aggregati i dati costituiti da più dati elementari

Dati strutturati

Si definiscono:

dati strutturati i dati costituiti da dati elementari aventi una struttura o modello o schema di aggregazione

Ad esempio sono strutturati i dati organizzati secondo lo schema:

Cognome; nome

Prefisso telefonico ; numero di telefono

Sono, altresì, strutturati, perché rispettano precisi schemi, le strutture di dati dette vettori e matrici.

Dati costituiti da dati elementari aventi una struttura o modello o schema di aggregazione

Dati elementari

Tra i dati elementari si definiscono il:

Tipo reale
Tipo intero
Tipo carattere
Tipo booleano

Il tipo reale è un sottoinsieme finito dell’ insieme dei numeri reali. Le operazioni su numeri di tipo reale producono come risultato un numero di tipo reale.

Il tipo intero è un sottoinsieme finito dell’ insieme dei numeri interi. Su elementi di questo tipo si possono eseguire le quattro operazioni aritmetiche purché il risultato sia ancora un numero intero ed appartenga all’intervallo di definizione.

Si definisce tipo carattere l’ insieme dei simboli usati per la scrittura tradizionale mediante mezzi meccanici e cioè è formato da tutto il set di caratteri dell’ alfabeto inglese esteso ai simboli delle cifre e dei segni speciali: A,B,C,…., Z 0, 1, 2,…9,?,’,^,*,…

Il tipo booleano è un insieme i cui elementi sono valori booleani: (VERO, FALSO), spesso indicati in inglese con (T, F); (SI e NO); (1 e 0). Su dati di tipo booleano si possono effettuare delle operazioni booleane o logiche che vengono chiarite di seguito.

Algebra di Boole

L’algebra booleana, dal nome del matematico inglese George Boole, fa ricorso a notazioni algebriche convenzionali per rappresentare relazioni di tipo logico come se fossero relazioni di tipo matematico. Boole considerò un insieme I costituito da solo due elementi (1 e 0) e definì le seguenti operazioni: somma logica, prodotto logico e negazione.

L’insieme I con le tre operazioni logiche costituisce l’Algebra rudimentale di Boole. Tale struttura algebrica fu adottata per lo studio della logica delle proposizioni e solo molti anni dopo, nel 1936, Shannon propose di applicarla alle reti di interruttori ed ai circuiti a relé perché caratterizzati da solo due stati di funzionamento (aperto, chiuso).

Nelle tabelle seguenti sono elencate le tre operazioni logiche fondamentali su valori booleani (0,1) e (V,F). Si definisce valore booleano un valore di un insieme di elementi binari (0,1) o (V,F) o (Vero, Falso) etc.

George Boole (en.wikisource.org)

Somma logica con valori 0 e 1

Somma logica con valori F e V

Prodotto logico con valori 0 e 1

Prodotto logico con valori F e V

Negazione o complementazione

Algebra di Boole

Le principali applicazioni dell’Algebra di Boole sono:

la Logica delle proposizioni perchè è possibile associare ad ogni proposizione una condizione di verità o falsità;

le Reti di interruttori ed ai circuiti a relé perché caratterizzati da due stati di funzionamento (aperto, chiuso).Infatti, associando ad un interruttore aperto il valore 0 e, ad un interruttore chiuso il valore 1, si possono realizzare operazioni logiche booleane utilizzando insiemi di interruttori collegati in serie o in parallelo.

Dati strutturati: Grafo, schema ed esemplare

I dati strutturati sono un insieme di dati elementari aventi tra loro un legame o una relazione.

Spesso tali dati sono descritti mediante un grafo (cfr figura a lato):

se nei nodi sono riportati gli attributi il grafo prende il nome di schema;
se nei nodi sono, invece, riportati i valori assunti dalle rispettive variabili (attributi), il grafo prende il nome di esemplare.

Per un singolo schema si possono produrre infiniti esemplari.

Esempio di grafo, schema ed esemplare

Dati strutturati: la Tabella

Si definisce Tabella un insieme finito di: n coppie di valori (x,y) con x appartenente ad X ed y appartenente ad Y che corrispondono all’applicazione: y=f(x), dove x è anche detta “chiave” della Tabella. Infatti mediante la x è possibile ottenere il valore corrispondente di y. Sia x che y possono essere di qualsiasi tipo. Possono anche crearsi tabelle con vettori. Si tiene a far presente che la y può rappresentare un gruppo di elementi e non un solo elemento. Ad esempio se il codice dipendente è chiave (x), gli altri attributi (cognome, nome, data di nascita) rappresentano la “y“.

Le operazioni che si possono effettuare su una Tabella di n elementi sono: ricerca, inserimento e cancellazione.

L’ operazione di ricerca consiste nel fornire una x* ed ottenere la corrispondente y=f(x*).
L’ operazione di inserimento consiste nel fornire una coppia (x*, y*) ed aggiungerla in coda alla tabella che conterrà n+1 elementi dopo l’inserimento.
L’operazione di cancellazione di un elemento x*, si attua fornendo un x* e viene eliminata la coppia (x*, y*) e la tabella conterrà n-1 elementi. Le Tabelle sono molto usate dai compilatori e in tutti i casi dove non è possibile creare corrispondenze mediante formule matematiche.

Esempio di tabella con chiave il codice

Dati strutturati: vettore, matrice.

Si definisce tipo vettore (o array) (Fig. 2) un insieme ordinato di n dati elementari componenti. Al tipo vettore è associato un indice che indica la posizione dell’elemento nel vettore [ad. es. V(i)].

Si definisce tipo vettore bidimensionale (o array bidimensionale o matrice) un vettore monodimensionale i cui elementi sono vettori monodimensionali. Nel caso dei vettori bidimensionali essi posseggono due indici per indicare rispettivamente la riga e la colonna di appartenenza dell’elemento della matrice [es. A(i,j)].

Il vettore consente di considerare come un unico dato più dati di tipo eguale.

Quindi un vettore contiene elementi dello stesso tipo (numeri interi o numeri reali o tutte lettere):

V(1)=36 V(2)=76; V(1)=8,81 V(2)=98,87; V(1)=H V(2)=I V(3)=L.

Dati complessi: Le immagini

Sono dati complessi le immagini, i suoni, le immagini con suoni (animazioni).

Bitmap

Esemplifichiamo la prima di queste tecniche: per semplicità consideriamo una immagine bidimensionale di una figura irregolare di colore nero. La figura irregolare si può ricondurre al quadrato fondamentale con vertici (0,0), (0,1), (1,0), (1,1) come è schematicamente indicato in Figura. Il quadrato fondamentale lo si può suddividere in un reticolo regolare formato da righe e colonne equidistanziate. In Figura sono indicate otto righe ed otto colonne. Si ottengono 8×8 quadratini tutti di uguale dimensione. Ogni singolo quadratino viene detto pixel (picture element). Si associa agli 8×8 quadratini una matrice A di dimensione 8×8 il cui elemento generico:

a_ij = 0 se il quadratino (i,j) non contiene la figura
a_ij = 1 se il quadratino (i,j) contiene la figura in modo prevalente (più del 50%).

L’immagine è di fatto digitalizzata ma con una definizione abbastanza scadente (che viene detta risoluzione bassa). Si usa il termine di risoluzione per indicare il numero totale di pixel utilizzati nel procedimento. Per valutare la risoluzione si può anche indicare il numero totale di righe orizzontali e verticali (8×8 in Figura) o i DPI=Dot per Inch.

Immagine nel quadrato fondamentale (a sinistra). Griglia regolare sovrapposta al quadrato fondamentale (a destra)

Codifica pixel con colori

Se la figura è colorata bisogna rappresentare anche i colori per cui ad ogni pixel deve essere associato anche il colore. In tal caso ogni pixel invece di essere associato ad un bit zero o uno deve essere associato al codice del colore. Se, ad esempio, si vogliono rappresentare sedici tonalità di colore si ha bisogno di quattro bit per ogni pixel per cui l’ elemento generico a_ij della matrice A diventa:

a_ij = 0000 se il quadratino (i,j) non contiene la figura

a_ij ≠ 0000 se il quadratino (i,j) contiene la figura in modo prevalente, inoltre a_ij = XXXX dove con XXXX è genericamente indicata la codifica in binario di una delle sedici tonalità del colore.

Quindi un’immagine di tipo bitmap è costituita da una matrice di punti, ciascuno caratterizzato dal suo colore e intensità luminosa;nella visualizzazione sullo schermo, ad ogni punto corrisponde un pixel. Ciò comporta un notevole dispendio di memoria, infatti per una immagine di 800 x 600 pixel, tenuto conto che l’informazione relativa al colore è codificata con 24 bit, cioè tre byte per ogni pixel, occorrono circa 1,5 Mbyte di memoria. Questa tecnica di memorizzazione è generalmente usata per le fotografie ed i disegni artistici; presenta lo svantaggio che la dimensione dell’immagine visibile è proporzionale al numero di punti memorizzati, pertanto la possibilità di ottenere ingrandimenti è limitata dal fatto che, ingrandendo l’immagine, i punti cominciano a divenire visibili ed appaiono come piccoli rettangoli, mentre i contorni assumono un aspetto ’seghettato’. I file di tipo bitmap compressi più comuni, perché correntemente utilizzati sul web, sono quelli con estensione .jpg, .gif e .png.

Grafica vettoriale

CAD

La grafica vettoriale ha il vantaggio di consentire il ridimensionamento dell’immagine, senza perdite nella risoluzione e di poterla ruotare per visualizzarla secondo diversi punti di vista, inoltre si può modificare l’ombreggiatura e la trasparenza delle diverse parti dell’oggetto rappresentato. Questa tecnica è utilizzata in particolare nella progettazione assistita da computer (CAD = Computer Aided Design) in quanto consente di esaminare e provare tutti gli aspetti costruttivi ed estetici di un oggetto da produrre, anche molto complesso come può essere un automobile, prima di costruire qualsiasi prototipo reale.

I suoni

Il procedimento di digitalizzazione del suono viene detto campionamento.

Il suono emesso da una sorgente S si propaga in un mezzo (aria, acqua, etc.) con onde sonore, che partono dalla sorgente ed investono il ricevente in un punto R. Un’onda sonora è un’onda di pressione variabile e misurabile nel tempo dove si trova il ricevente R. L’onda sonora è di tipo analogico (continua) e può essere descritta in funzione del tempo come è rappresentato nel grafico.

Il campionamento consiste nel segmentare l’onda analogica ricevuta da R in un insieme discreto a intervalli costanti. Si definisce frequenza di campionamento la misura del numero di campioni considerati nell’ unità di tempo.

Si definisce frequenza di campionamento la misura del numero di campioni considerati nell’ unità di tempo

I suoni

Diagramma dell’intensità della pressione di una onda sonora (in ordinata) percepita dal ricevente R al passare del tempo T (in ascissa)

I suoni II

Definita la scala con cui rappresentare i valori di pressione dell’aria si può assegnare un numero a ciascun segmento discreto dell’onda sonora continua. La sequenza di bit dei numeri identificati costituisce la rappresentazione digitale del fenomeno analogico del suono.

Anche l’asse delle ordinate deve essere quantizzato cioè discretizzato e, quindi, si devono indicare i livelli di intensità su otto, sedici, trentadue o più bit. Nel caso del suono si deve discretizzare sia il tempo, sia l’intensità ottenendo una successione di valori in binario che rappresentano il suono discretizzato.

Occupazione di memoria

Per assicurare la fedeltà della riproduzione del suono, occorre che i campioni siano misurati a brevissimi intervalli di tempo. Per esempio un CD musicale, viene prodotto a partire da una sequenza di bit generata da 44.000 campioni al secondo, misurati su ciascuno dei canali audio; tenuto conto che ogni campione è espresso da un numero a 16 bit, si vede che per memorizzare un minuto di musica stereofonica ad alta fedeltà in formato digitale, occorrono circa 10 Mbyte; questo elevato fabbisogno di memoria rende conveniente il ricorrere ad algoritmi di compressione.
I file audio compressi con l‘algoritmo mp3 (hanno appunto l’estensione .mp3) occupano approssimativamente un decimo dello spazio di memoria del file originale; i file audio di Windows hanno l’estensione .wav.
Con il computer oltre che riprodurre la musica, precedentemente memorizzata in file audio, si possono anche comporre brani musicali, mediante un sintetizzatore, che è uno strumento elettronico in grado di riprodurre i suoni di una intera orchestra e di creare effetti sonori originali. Per pilotare strumenti musicali elettronici, si utilizza un tipo di interfaccia specifico, detto MIDI (Musical Instrument Digital Interface). Nei file audio tipo MIDI (che hanno estensione .mid), i dati memorizzati non sono dei suoni campionati, ma i comandi necessari a riprodurre le note, con intensità e timbro di ciascuna, che vengono inviati al sintetizzatore, per riprodurre i suoni desiderati. Come conseguenza i file .mid occupano uno spazio molto più ridotto dei file .wav a parità di durata del brano musicale.

Algoritmi di compressione

Digitalizzare, cioè convertire in formato binario le informazioni contenute nelle immagini e nei suoni, per poterli poi conservare e riprodurre fedelmente, richiede un elevato fabbisogno di memoria. Per ridurre tale fabbisogno, si ricorre a specifiche tecniche di compressione dei dati.
La compressione dei dati può essere fondamentalmente di due tipi: ‘lossy‘, cioè con perdita di dati, perché la successiva decompressione non riprodurrà esattamente l’originale oppure ‘lossless‘, quando la decompressione ripristina esattamente l’originale. La compressione lossy è preferita, perché è più efficiente e la perdita di dati nella riproduzione audio/video non è generalmente percepita dallo spettatore/ascoltatore ovvero la qualità risultante è adeguata allo scopo prefisso.
Per esempio nel caso di una immagine, invece di memorizzare tutti i pixel di una zona dall’aspetto uniforme, si memorizza un singolo pixel ed il numero di pixel uguali che lo seguono; inoltre si riduce il numero di sfumature di colore che saranno riprodotte sullo schermo.Nel caso dei suoni la compressione è ottenuta rinunciando a memorizzare i dati relativi ai suoni di frequenza più bassa o più elevata di quella percepibile dall’ascoltatore medio e quelli relativi ai suoni che non sarebbero percepiti, perché sovrastati da altri contemporanei e più intensi. Tale tecnica è ad esempio usata dal diffusissimo algoritmo di compressione mp3.