Appunti completi Fondamenti di informatica

Fondamenti di informatica

L'informazione è ciò che viene comunicato, e serve per diminuire l'incertezza riguardo un insieme di possibilità. L'informatica è la scienza che si occupa del trattamento automatico dell'informazione. Le informazioni possono essere rappresentate in due modalità:

Rappresentazione analogica

Con la rappresentazione analogica le proprietà scelte del fenomeno (le grandezze) sono omeomorfe alla forma della rappresentazione, ossia l'informazione può essere manipolata manipolando la sua rappresentazione. Le grandezze sono rappresentate in modo continuo, ma l'ampia possibilità di manipolazione fa sì che le informazioni possano subire cambiamenti non voluti (errori).

Rappresentazione discreta o numerica

Con la rappresentazione discreta o numerica le grandezze sono rappresentate in modo approssimato da un insieme di rappresentazioni distinte. L'approssimazione è voluta e permette di limitare la possibilità di manipolazione, e quindi di rilevare e correggere automaticamente gli errori. Per esempio, il disco di vinile è una rappresentazione analogica di segnali audio, ma dato un disco non si può capire se le informazioni finali siano come quelle iniziali o abbiano subito una manipolazione.

Codifica dell'informazione

La codifica è il procedimento che permette di passare dal concetto di informazione alla sua rappresentazione. Il simbolo è l'unità fondamentale della rappresentazione. La codifica è l'uso di un codice, ossia un insieme di simboli che permette la rappresentazione dell'informazione, scelte da un alfabeto, l'insieme di tutti i simboli possibili. Caratteristica di un alfabeto è la cardinalità, la presenza di un preciso numero di elementi. I simboli sono usati in sequenze di lunghezza definita, dette parole codice o stringhe. Le regole che stabiliscono se una parola codice sia parte o meno di una codifica costituiscono il linguaggio.

Il numero di parole codice differenti con lunghezza data da un alfabeto composto da n simboli distinti, ossia con cardinalità, è lⁿ. La codifica è tale che a ciascuna parola codice, sequenza di simboli, corrisponda uno ed un solo valore, ma ad un valore possono corrispondere una o più parole codice (è una funzione suriettiva). Pertanto, la lunghezza deve essere tale che lⁿ ≥ m, ossia il numero di parole codice deve essere maggiore o uguale al numero di valori diversi rappresentabili. La prima lunghezza tale che n ≥ m è detta lunghezza minima.

Ridondanza

Nel caso in cui si parla di ridondanza, caratteristica che può essere utile per la prevenzione di errori poiché se non tutte le configurazioni possibili vengono utilizzate per la rappresentazione, la variazione di una parola chiave può essere rilevata quando non presenta un valore associato.

Rappresentazione digitale

Una rappresentazione discreta ampiamente usata è quella digitale, che permette una automazione della correzione di errori, e tra le digitali numeriche la rappresentazione binaria è la più diffusa. Essa si basa su un alfabeto con cardinalità due, avente quindi due simboli, convenzionalmente con forma 0 e 1. Entrambi i simboli sono detti bit, termine che deriva da binary digit.

Nei moderni calcolatori si utilizza una codifica a lunghezza fissa di 8 bit, ossia di un byte, che permettono di rappresentare ciascuno 256 valori diversi. Nel caso in cui i valori da rappresentare siano maggiori, allora si individua il numero di byte tale che 2^b ≥ m.

Rappresentazione dei testi e gli standard

Un esempio di applicazione della rappresentazione binaria è la rappresentazione dei testi, dove ogni simbolo è correlato ad una parola codice con lunghezza fissa formata da simboli binari (bit). La lunghezza minima affinché la rappresentazione binaria sia corrisposta a 26 valori diversi, il numero di lettere dell'alfabeto, è 5, poiché 2⁵ = 32, mentre 2⁴ = 16 < 26. Ma considerando anche le maiuscole, così come i numeri e altri simboli di punteggiatura, la lunghezza minima diventa maggiore. Vi sono anche altri simboli che non rappresentano graficamente nulla, ma sono usati per la tabulazione o forniscono determinati comandi.

Lo standard ASCII utilizza 7 bit, mentre la versione estesa di questa, così come lo standard EBCDIC, utilizzano 8 bit, ossia un byte, che permettono quindi di rappresentare 256 simboli differenti. Avere uno standard è importante affinché sistemi diversi comunichino tra loro. Lo standard UNICODE considera invece simboli di alfabeti diversi da quello anglosassone, e deriva da un processo di ricerca congiunta tra le nazioni. La codifica descritta dallo standard UNICODE non è più a lunghezza fissa, ma varia entro determinate lunghezze di byte. UTF-8 ad esempio usa da 1 a 4 byte per carattere, che sono codificati in parole da 8 bit. È lo standard UTF-16 ad essere utilizzato internamente da Windows e MacOS. Certi standard però non sono stati unanimemente decisi, ma per la loro popolarità sono divenuti degli de facto standard, nonostante possano non essere ottimali, il costo e la difficoltà di cambiarne uno all'unisono sono considerati maggiormente.

Ottenere segnali analogici e digitali

I sensori trasformano grandezze fisiche di interesse in, solitamente, segnali elettrici; questa trasformazione è analogica, poiché il segnale elettrico si muove in analogia con la variazione della grandezza fisica interessata. Per trasformare un segnale analogico in uno digitale si opera su di esso un campionamento, o quantizzazione. La quantizzazione deve tenere conto della relazione inversa tra qualità del formato digitale e peso dell'informazione.

Gli audio

Un segnale audio è un insieme di frequenze sonore, quindi è analogico e pertanto campionabile lungo vari assi orizzontali.

Codifica delle immagini

Anche un'immagine è un insieme continuo di informazioni, perché è un insieme di frequenze elettromagnetiche. Il campionamento in questo caso avviene secondo assi orizzontali e verticali che individuano un reticolo di punti detti pixel, termine che deriva da picture element. È possibile considerare ciascun pixel come pari ad un bit, ma in questo modo si ottiene un'immagine esclusivamente in bianco e nero. Associando più bit a ciascun pixel, invece, si ottiene una rappresentazione monocromatica più fedele; usando 8 bit/pixel si ottiene un'immagine a 256 livelli di grigio. Per immagini a colori invece si associano a ciascun pixel insiemi di bit diversi, ciascuno che descrive un'intensità cromatica diversa; con lo standard RGB, si utilizzano 8 bit per tre colori diversi, rosso, verde e blu, quindi 24 bit, ottenendo un peso complessivo dell'immagine relativamente notevole.

L'associazione di bit a pixel fornisce immagini digitali denominate bitmap. I bitmap possono essere rappresentati secondo diversi formati di file (TIFF, GIF, JPEG, BMP …), così come secondo diverse risoluzioni (densità di pixel), che possono comportare pesi diversi e numero di colori rappresentabili altrettanto differenti. In un'immagine si considerano anche diverse forme di compressione, ossia di riduzione della quantità di dati occupata, mediante tecniche che vanno a rimuovere informazioni utili (lossy), o che vanno a rimuovere informazioni superflue (lossless).

Filmati

Un filmato è una sequenza di immagini che sono proiettate a velocità tale che l'occhio non sia in grado di identificarla come una sequenza discreta. Il framerate di un video è il numero di frame, ossia immagini, per secondo.

Compressione MPEG

Per i filmati, così come per gli audio, è possibile introdurre un primo tipo di compressione, che considera unicamente i segnali che variano, e non segnali ripetuti, permettendo di risparmiare sulla quantità di dati. Questa tecnica è adottata nello standard MPEG (Moving Picture Expert Group).

Sistemi di numerazione

La rappresentazione forse più importante è quella dei numeri. Un sistema di numerazione è un insieme di cifre e regole che assegnano ad ogni sequenza di cifre un valore numerico. Sono classificati in sistemi posizionali e non, ossia dove la posizione di una cifra ne fa cambiare il valore associato o meno.

Nei sistemi posizionali in base si utilizza la numerazione posizionale pesata, ossia dove un valore è espresso come la sommatoria del prodotto tra ciascuna cifra ed una base costante elevata a potenza con esponente pari alla sua posizione. In un sistema del genere in base b servono b simboli per rappresentare i diversi valori compresi tra 0 e b − 1. Il valore trovato è espresso in decimale, quindi questo corrisponde ad un metodo generale per la conversione da una base non decimale ad una decimale.

È da notare che nel passaggio da una base all'altra alcune proprietà dei numeri non si conservano, ad esempio un numero periodico in una base può non esserlo in un'altra. Per la conversione da una base decimale ad una non decimale, invece, considerando che N può essere intero o frazionario, si distinguono due procedimenti diversi ma logicamente uguali.

Dato quindi N = c_l ⋅ b^l + c_l−1 ⋅ b^l−1 + ... + c₁ ⋅ b¹ + c₀ ⋅ b⁰ + c₋₁ ⋅ b⁻¹ + c₋₂ ⋅ b⁻² + ..., la parte frazionaria è quella da c₋₁ ⋅ b⁻¹ in poi, mentre in precedenza vi è la parte intera. Per convertire la parte intera di un valore, si operano consecutive divisioni tra il valore da convertire o il quoziente intero di tali divisioni e la base, ed il resto (ossia la parte frazionaria del quoziente) di ciascuna divisione corrisponde ad una cifra del valore nella nuova base, da destra verso sinistra. Per convertire la parte frazionaria di un valore invece si effettuano prodotti, e la parte intera a ciascun prodotto corrisponde ad una nuova cifra da apporre da sinistra verso destra.

Errori di overflow e underflow

Con la rappresentazione numerica è necessario considerare alcuni aspetti pratici. In sistemi di calcolo a precisione finita, che è sempre il caso con i calcolatori perché lo spazio di archiviazione è limitato, le operazioni possono causare errori quando il risultato non appartiene all'insieme dei valori rappresentabili. Quando un valore eccede il più grande valore rappresentabile, o è inferiore al minimo, si verifica un overflow. Se invece un valore è troppo piccolo per essere memorizzato completamente, può verificarsi un underflow ed il valore è espresso come nullo, poiché è approssimato al valore più piccolo esistente, lo 0.

Esempio: Per una calcolatrice con soli tre cifre, in grado di rappresentare unicamente numeri interi compresi tra 0 e +999, 730 + 510 e 2 : 3 danno rispettivamente errori di overflow e underflow. Nonostante gli operandi possano essere rappresentati, per il risultato in entrambi non può avvenire altrettanto.

Gli errori di overflow e underflow fanno sì che l'algebra a precisione finita non possa rispettare sempre due delle proprietà fondamentali: la proprietà associativa e quella distributiva; l'ordine in questo caso può determinare la validità delle operazioni. L'insieme dei numeri rappresentabili può essere considerato come un sistema periodico, dove il numero più alto rappresentabile è adiacente a quello più basso; gli errori di overflow, quindi, consistono nel passaggio di questa soglia, in un verso o in un altro.

Sistema binario

La rappresentazione numerica nei calcolatori avviene, come ogni altra informazione, mediante il sistema binario. Per questo motivo, l'intervallo di definizione dell'algebra a precisione finita di un calcolatore dipende dal numero di byte associato alla rappresentazione. I valori numerici rappresentati da un insieme di bit dipendono dal valore posizionale di ciascuno. La posizione meno significativa (LSB, Least Significant Bit) è quella a destra, mentre quella più significativa (MSB) è quella a sinistra. A partire dalla posizione meno significativa, si associa un peso con valore 0, che è incrementato di 1 ad ogni posizione. Il valore in una determinata posizione è quindi moltiplicato per 2 (la base) elevato al rispettivo peso, ed il valore rappresentato è pari alla somma di tutti i prodotti. Un byte può rappresentare 2⁸ = 256 valori diversi; quindi, si possono gestire gli intervalli di numeri [0,255], poiché incluso lo 0 sono 256 valori, oppure considerando numeri negativi si possono rappresentare valori nell'intervallo [−127,128].

Operazioni su numeri binari

Tramite i numeri binari è possibile compiere calcoli molto facilmente. Somma e addizione tra due bit sono piuttosto intuitive, con la sola caratteristica che la somma tra due 1 fa 0 con 1 di riporto, o in altre parole 10, che è la forma binaria di 2.

L'addizione e la sottrazione tra due numeri binari formati da più bit si basano sullo stesso procedimento dell'algebra decimale, dove si compie l'operazione in colonna; per la somma pertanto vale la regola del riporto, ossia si trasporta l'unità in eccesso alla posizione più alta, mentre per la sottrazione, nel caso in cui la cifra del secondo numero è maggiore, il bit del primo numero riceve una unità dalla posizione più alta. Procedimento analogo alle operazioni decimali si verifica anche considerando la moltiplicazione.

Rappresentazioni dei numeri binari negativi

In segno e modulo

Per indicare la positività e la negatività di un numero basta un bit. Si sceglie in genere di usare il MSB per indicare il segno, in modo da lasciare invariato il numero; si sceglie inoltre di usare il valore 0 per i positivi, in modo da lasciare invariato il loro valore, mentre per i negativi si usa il valore 1. Tramite l bit, è possibile quindi usarne l−1 per rappresentare il valore e 1 per il segno, permettendo la rappresentazione di valori che vanno da −(2^l−1 − 1) a 2^l−1 − 1. Questa rappresentazione è detta per segno e modulo.

I problemi posti da questo tipo di rappresentazione sono però vari: c'è la presenza di 2 valori per lo 0, uno negativo e uno positivo, ed inoltre la somma tra due numeri non è più immediata se uno dei due è negativo, poiché il procedimento usato per i numeri positivi non fornisce i risultati esatti. Questa rappresentazione, quindi, andrebbe a complicare di molto le operazioni per la necessità di effettuare numerosi controlli ai valori di input e di output ed effettuare nel caso opportune modifiche, e quindi complicherebbe anche la struttura logica dei calcolatori.

Per complemento a due

Una rappresentazione più comoda per la computazione è quella detta per complemento a due, che permette di effettuare le operazioni di addizione e sottrazione con un metodo comune, e che necessita di un unico controllo all'input. Rispetto alla rappresentazione per segno e modulo, in quella per complemento a due i valori negativi, quelli che vanno da −2^l − 1 a −1, sono traslati di 2^l−1, passando quindi all’intervallo −2^l−1 a 2^l−1 − 1, mentre lo 0 e i valori positivi restano invariati. In questo modo, in seguito al valore 0 non è presente uno zero negativo, bensì il valore −2^l, rimuovendo la simmetria della rappresentazione ma soprattutto il problema dei due zeri.

In una codifica a l bit, per calcolare quindi il complemento a due (ossia il numero binario di un numero nella rappresentazione per complemento a due) di un numero binario negativo rappresentato per segno e modulo, si sottrae il valore assoluto di tale numero (ossia lo stesso valore ma con il MSB nullo) a 2^l, applicando pertanto la traslazione che è alla base della rappresentazione.

Per complemento diminuito

La rappresentazione per complemento alla base diminuita si basa sullo stesso principio della precedente, ma non somma l’unità; pertanto, vi è una doppia rappresentazione dello 0.

Per eccessi

Un sistema alternativo alla rappresentazione per complemento a due è la rappresentazione per eccessi, che si basa sulla traslazione di tutti i valori della rappresentazione per segno e modulo, positivi e negativi, di 2^l−1. Generalmente, corrisponde alla rappresentazione per complemento alla base ma con il bit del segno invertito. La rappresentazione per eccessi può però essere implementata secondo piccole varianti: per definizione, una "rappresentazione per eccesso N" corrisponde ad una rappresentazione per eccessi dove il valore più negativo è traslato di N.