Riassunto esame Informatica, prof. Console, libro consigliato Manuale di Informatica

Introduzione all'informatica

La rappresentazione delle informazioni

Negli elaboratori viene usata una rappresentazione binaria che usa due soli simboli: "0" e "1". Le ragioni sono principalmente di tipo tecnologico.

Bit: entità minima di informazione, può assumere solo due valori (0 o 1). Con un bit si possono rappresentare due informazioni. Per poter rappresentare un numero maggiore di informazioni si usano aggregazioni (sequenze) di bit. Con un'aggregazione di N bit si possono decodificare 2^N informazioni diverse.

Byte: aggregazione di 8 bit. Si possono codificare 2⁸ = 256 informazioni.

Codifica caratteri

Il metodo più diffuso di codifica dei caratteri si chiama Codice ASCII (American Standard Code for Information Interchange), ma esiste anche il Codice EBCDIC. Codice ASCII Standard usa 7 bit per codificare simboli dell'alfabeto. Le prime 32 sono usate per simboli speciali (spazio, fine riga…), ma sono contenuti tutti i caratteri (cifre, punteggiatura, caratteri maiuscoli e minuscoli). Di solito però usa 8 bit (comodità), il primo è sempre 0. 2⁸ = 256 configurazioni diverse.

Codice ASCII esteso: primo bit 1, usati per codificare i simboli speciali (esempio le lettere greche).

Unicode: usa 16 bit, quindi 65536 configurazioni. Codifica tutti gli alfabeti.

Codifica numeri

I numeri vengono rappresentati usando le due cifre "0" e "1". Le operazioni aritmetiche NON si fanno mediante la codifica ASCII.

Overflow: errore che avviene quando si esce dal numero di cifre possibili. Date N cifre binarie, si rappresentano i numeri da 0 a 2^N-1. Ad esempio: 8 bit = da 0 a 255, non è possibile rappresentare il numero 256.

Solitamente si usano 32 bit (4 byte) per rappresentare i numeri nei pc.

Conversione da base 10 a base 2

Divisione per due fino ad arrivare a 0: il risultato è tutti i resti da destra verso sinistra.

Esempio: 345₁₀

• 345 / 2 = 172 RESTO 1
• 172 / 2 = 86 RESTO 0
• 86 / 2 = 43 RESTO 0
• 43 / 2 = 21 RESTO 1
• 21 / 2 = 10 RESTO 1
• 10 / 2 = 5 RESTO 0
• 5 / 2 = 2 RESTO 1
• 2 / 2 = 1 RESTO 0
• 1 / 2 = 0 RESTO 1

Prendo tutti i resti a partire dal fondo e ottengo: 101011001₂

Conversione da base 2 a base 10

Da destra verso sinistra si moltiplica ogni cifra per le potenze progressive del 2.

Esempio: 101011001₂

• 1 x 2⁰ = 1
• 0 x 2¹ = 0
• 0 x 2² = 0
• 1 x 2³ = 8
• 1 x 2⁴ = 16
• 0 x 2⁵ = 0
• 1 x 2⁶ = 64
• 0 x 2⁷ = 0
• 1 x 2⁸ = 256

Sommo tutto: 1 + 0 + 0 + 8 + 16 + 0 + 64 + 0 + 256 = 345₁₀

Numeri binari: se finiscono con 0 sono PARI. Se finiscono con 1 sono DISPARI.

Operazioni sui numeri binari

Le regole per il calcolo delle somme sono le seguenti:

• 0 + 0 = 0 con riporto 0
• 0 + 1 = 1 con riporto 0
• 1 + 0 = 1 con riporto 0
• 1 + 1 = 0 con riporto 1

Complemento a due

Per rappresentare i numeri CON SEGNO e per compiere corrette operazioni aritmetiche. Numero di bit = N, 2^N diviso 2 è il numero di numeri positivi e negativi rappresentabili. Ad esempio, con 4 bit si hanno 8 positivi e 8 negativi.

Primo bit: 0 → numero positivo. 1 → numero negativo.

Per rappresentare numeri negativi:

1. Si prende il valore assoluto del corrispettivo numero positivo.
2. Si invertono i bit.
3. Si somma 1 al risultato.

Da numero in complemento a due a numero decimale

• Se è positivo (primo bit 0), si fa conversione da binario a decimale.
• Se è negativo (primo bit 1): ignoro il primo bit, inverto gli altri bit, converto da binario a decimale e sommo 1 al numero ottenuto.

Rappresentazione esadecimale

16 cifre (1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F). Da base 10 a base 16 si fa come per la base 2.

Codifica immagini

Pixel (picture element) sono i quadratini della griglia, unità di informazione minima di un'immagine. I livelli di grigi variano: con 4 bit si hanno 16 livelli, con 8 bit 256. I video semplici offrono 65536 colori a risoluzioni come 800x600 Pixel, o 16 milioni di colori a 1024x768 e 1280x1024.

Standard di codifica: RGB (red green blue), CMY (cyan, magenta, yellow). Solitamente in RGB si usano 256 livelli per ogni colore base.

Rappresentazione di un'immagine mediante la codifica di tutti i suoi pixel: codifica bitmap

• 1 pixel a 2 colori occupa 1 bit
• 1 pixel a 256 colori occupa 1 byte
• 1 pixel a 65536 colori occupa 2 byte
• 1 pixel a 16 milioni di colori occupa 3 byte

Risoluzione: numero di pixel utilizzati. Bit e Byte definiscono lo spazio necessario a memorizzare un'immagine.

Compressione immagini

1. Lossless Compression (senza perdita di dati): aree con lo stesso colore vengono codificate ugualmente (poca compressione, salvaguarda dalla perdita di informazioni nella fase di decompressione).
2. Lossy Compression (perdita di dati): si comprime fino a 10 volte.

Formato BMP (bitmap): formato non compresso, i dati dell'immagine vengono divisi in blocchi da 4 byte (DWORD). Vi è un header che contiene le informazioni per la decodifica, è semplice ed è supportato da tutti i sistemi operativi Windows. L'unico svantaggio è che occupa troppo spazio su disco.

Tecnica RLE (Run Length Encoding): sequenze di pixel dello stesso colore vengono codificate memorizzando il numero di ripetizioni di pixel uguali. Ha un algoritmo di compressione/decompressione veloce ed efficiente. Lossless, nonostante non conceda un eccessivo guadagno in termini di spazio.

Formato PCX: usa la tecnica RLE. Usa un header lungo 128 byte che contiene informazioni sulla risoluzione, il numero di colori e sul formato di compressione. Dopo la codifica dell'immagine si hanno ancora 768 byte che contengono la PALETTE DEI COLORI (espressi in RGB). Lossless, riduzione dello spazio del 30-40%.

Formato GIF (Graphics Interchange Format): molto usato in ambiente web, alta definizione di immagine, compatibili con hardware diversi. Nell'header sono contenute varie informazioni: la versione, la definizione dello schermo utilizzato, le informazioni sulla mappa dei colori. La compressione avviene mediante l'algoritmo LZW. Per l'uso in Internet vi è la possibilità di creare immagini interlacciate divise in 4 sequenze di caricamento successive che ottimizzano sempre più l'immagine. Questo formato è limitato ai 256 colori.

Algoritmo JPEG (Joint Photographic Experts Group): 1992 standard mondiale per la compressione delle immagini ad alta definizione. La compressione prevede diverse fasi in cui l'immagine viene decomposta in blocchi di pixel cui vengono applicate funzioni matematiche per trasformare le sequenze numeriche corrispondenti ai diversi blocchi. I tempi di elaborazione sono più lunghi rispetto ai formati precedenti. È possibile definire il bilanciamento fra livello di compressione, perdita di dati e velocità di codifica/decodifica.

Formato TIFF (lossless): è strutturato a blocchi chiamati tag, ognuno dei quali indica un particolare tipo di informazione: tipo di compressione, altezza, larghezza, orientamento. Adatto a gestire immagini ad alta risoluzione utilizzando l'algoritmo LZW.

Immagini in movimento

Possono essere utilizzate le stesse tecniche di codifica e compressione usate per le immagini fisse. Partendo dal presupposto che spesso non vi sono grandi differenze tra due fotogrammi consecutivi, si può pensare che basti memorizzare le differenze rispetto al fotogramma memorizzato in modo completo. Dopo un certo insieme di fotogrammi memorizzati per differenza sarà indispensabile memorizzare un nuovo fotogramma in modo completo.

Formato AVI (Audio Video Interleaved): creato da Microsoft. Header descrittivo di 8 byte.

Formato FLI, e FLC: sfrutta la somiglianza tra due fotogrammi successivi: se due frame successivi hanno delle parti in comune il secondo fotogramma viene visualizzato in modo più efficiente, disegnando solamente le differenze rispetto al primo.

Formato MOV (QuickTime): sviluppato dalla Apple, permette di memorizzare tipi diversi di informazioni multimediali, dalle immagini ai suoni. Lossy.

Formato MPEG (Moving Picture Experts Group): sono state prodotte 5 estensioni. Standard predittivo: ipotizza il fotogramma successivo partendo dal precedente; utilizza 2 tecniche: compensazione di moto e dei singoli fotogrammi, in maniera simile a quanto fatto dal JPEG per le immagini.

Codec (Compressor o Decompressor): software che codifica un flusso di dati – un video - Gestisce sia la codifica, sia la decodifica di dati. Il codec principale è MPEG, arriva a livelli di compressione di 200:1, garantendo una buona qualità di riproduzione ma con perdita di informazione.

DIVX: alti fattori di compressione delle immagini e permette di rendere disponibili e scaricabili anche in rete filmati di varie dimensioni.

MOTION JPEG: gestisce i filmati comprimendoli fino a 100:1 senza grandi perdite; l'immagine e la fluidità del video sono di altissima qualità.

INDEO, Intel: buona compatibilità con Internet legata al sistema di scaricamento progressivo continuo.

Codifica suoni

Fisicamente il suono è un'alterazione della pressione dell'aria che, se rilevata, viene trasformata in un particolare stimolo elettrico. La durata, l'intensità e la variazione nel tempo della pressione sono le quantità fisiche che rendono un suono diverso da ogni altro. Un suono è rappresentato come un'onda che descrive la variazione della pressione dell'aria nel tempo o la variazione dello stimolo elettrico corrispondente. Per la rappresentazione digitale, si tratta di effettuare dei campionamenti sull'onda e di codificare in forma digitale l'informazione estratta da tali campionamenti.

Nel suono bisogna rilevare il valore dell'onda ad intervalli costanti nel tempo. Quanto più frequentemente il valore di intensità dell'onda viene campionato, tanto più precisa sarà la sua rappresentazione. Le schede per la gestione dell'audio utilizzano una frequenza di campionamento che prevede tra i 10000 e i 40000 campionamenti al secondo (10000-40000 Hz) e usano 16 bit per la memorizzazione dei valori estratti (occorrono molti byte per memorizzare piccoli frammenti di suono). Es. 1Hz=1 volta al secondo, 1KHz=1.000 volte al secondo, 1MHz=evento che si ripete 1 milione di volte al secondo.

Formato WAVE: usato in Windows, è legato al formato AVI. Permette di campionare segnali mono e stereo, con campioni da 8 e 32 bit. Usato per file sonori di breve durata visto il grosso spazio richiesto. Il formato AIFF è l'analogo in ambiente Mac.

MP3 (Mpeg Audio Layer 3): fattore di compressione 12:1. Ad esempio, un file Wave campionato a 44,1 Khz con 16 bit per campione, che occuperebbe circa 50 milioni di byte, compresso in (chunks) detti frames, ognuno dei quali è provvisto di un marcatore del tasso di compressione: diventa quindi possibile modificare il file audio dinamicamente mentre viene riprodotto. MP3 ne occupa meno di 5 milioni, senza perdita di qualità sonora.

Come unità di misura della velocità di trasmissione si usa il bit rate, ossia la quantità di informazione trasferita nell'unità di tempo (un secondo). Maggiore è il bit rate, più informazioni si possono includere nel file.

Possiamo dividere i formati audio in lossy e non lossy. L'idea dei formati lossy nasce dalla constatazione che non tutti i suoni presenti nei 44.100 campioni al secondo contenuti in un file Wav standard vengono correttamente percepiti dall'orecchio umano. In questo modo si vanno a tagliare le alte frequenze, che più vengono tagliate, e più diminuisce lo spazio occupato. Altri formati lossy sono WMA, AC3, Nero Mp4 AAC. Se riconvertito in WAV il suono sarà identico a quello originale.

Esistono tecniche per la rappresentazione e generazione di suoni sintetizzati:

Formato MIDI: linguaggio testuale per rappresentare suoni e musica. Un particolare interprete è in grado di produrre i suoni sintetizzati; permette di rappresentare della musica sintetizzata molto compatta ma consente solo la rappresentazione di suoni sintetizzati e non di quelli reali.

Strutturazione logica dei dati: I FILE

Un file è una struttura lineare costituita da una sequenza di record, ciascuno formato da una sequenza di campi, ovvero da una sequenza di byte. Un file è un meccanismo di strutturazione delle informazioni che permette di aggregare informazioni elementari in strutture più complesse. È l'entità fondamentale per l'organizzazione logica delle informazioni in un sistema di elaborazione. Essi possono essere:

• Strutturati: sono effettivamente sequenze di record.
• Non strutturati: l'informazione è una sequenza di caratteri (byte) che costituiscono un testo; si può pensare che il record coincida con il singolo carattere e non sia possibile suddividerlo ulteriormente in campi.

Un file è costituito da una sequenza di record. Un campo è costituito da un insieme di byte e serve per codificare una singola informazione, che può essere numerica, alfabetica o un'immagine o un suono. Un record è costituito da un insieme di campi logicamente correlati tra loro e che costituiscono un'informazione complessa. I record di un file possono essere:

• A lunghezza costante: tutti i record sono formati dallo stesso numero di byte, hanno lo stesso insieme di campi e ogni campo ha la stessa dimensione, indipendentemente dall'informazione che dovrà contenere. Deve essere precisato il numero di byte destinato a ciascun campo. Comporta uno spreco di spazio, in quanto ogni campo deve essere stimato a priori sufficientemente grande da poter occupare la più lunga informazione. L'informazione in molti casi occupa meno spazio di quello a disposizione.
• A lunghezza variabile: la lunghezza varia in funzione dell'informazione contenuta. In tal caso è richiesto un carattere speciale nella sequenza di byte che possa separare le varie informazioni. Occorre un carattere speciale per separare i record tra loro e un carattere speciale per separare i campi all'interno di ciascun record. Esempio: OS di una banca.

Esistono tre metodi di reperimento e accesso alle informazioni:

• Sequenziale: la ricerca dei record avviene a partire dall'inizio del file, leggendo tutti i record l'uno dopo l'altro, fino a quando non si arriva a quello desiderato. L'unico vantaggio è che è applicabile sia ai record a lunghezza costante che a lunghezza variabile. In un file con record a dimensione costante, ad ogni passo nella ricerca, invece di cercare i simboli di separazione tra record e campi, si avanza di un numero di byte prestabilito.
• Diretto: il primo campo all'interno di un file prende il nome di indirizzo del record. Poiché un file è un insieme di byte, possiamo definire come indirizzo di un byte il numero che corrisponde alla posizione del byte nella sequenza (il primo byte ha indirizzo 0, il secondo 1,…). L'indirizzo di un campo è l'indirizzo del primo byte nel campo e l'indirizzo di un record è l'indirizzo del primo campo del record. Se l'indirizzo di un record è noto, è possibile posizionarsi direttamente in quel punto ed accedere alle informazioni in modo diretto, senza considerare quelle precedenti. L'accesso diretto ai record non è possibile con quelli a lunghezza variabile, poiché non è possibile calcolare l'indirizzo di un record non sapendo l'esatta posizione nella sequenza. Se l'indirizzo non è disponibile l'accesso diretto non è possibile.
• Accesso con chiave: permette di mantenere le informazioni sugli indirizzi al di fuori del file. Occorre individuare il campo chiave che è presente in tutti i record e fornisce un riferimento univoco ai record stessi, come se fosse il nome del record. Il campo chiave sarà inserito in un nuovo file, il file delle chiavi, che è costituito da record a dimensione costante formati da due campi: un campo per il valore della chiave, e l'altro per l'indirizzo del record nel file. Il file delle chiavi ha tanti record quanti sono quelli del file originario. Pertanto il metodo d'accesso prevede prima che si acceda al file delle chiavi per cercare la chiave, e poi si accederà in modo diretto al record nel file delle informazioni. Esso è la combinazione di due accessi diretti. L'unico svantaggio è la memorizzazione ulteriore di una tabella delle chiavi. Nei casi in cui un singolo campo non svolga il ruolo di chiave univoca, possono essere presi due se non tre campi che potranno identificare in modo univoco un record.

Le strategie di ricerca sono le seguenti:

• Sequenziale
• Ricerca binaria, che richiede che le chiavi siano mantenute ordinate. Viene preso il record che si trova a metà della tabella (posizione N/2) e si legge il valore della chiave. Se k = k*, ossia l'elemento cercato è quello a metà, abbiamo terminato la ricerca. Se k < k*, allora l'elemento cercato è nella prima metà della tabella, e si prosegue la ricerca ripartendo ma considerando solo la tabella che contiene N/2 -1 elementi. Se k > k*, allora l'elemento cercato è nella seconda metà della tabella, e si prosegue ripartendo dall'inizio ma considerando la tabella che contiene solo gli elementi da N/2 +1 fino alla fine. Con questa tecnica la ricerca di un elemento richiede un numero di passi logaritmici in N, dove N è il numero delle chiavi.
• Funzione di Hash: l'inserimento degli elementi nelle righe avviene utilizzando la funzione di hash che deve essere definita per tutti i possibili valori del campo chiave e deve avere la proprietà che, quando applicata ad una chiave k, restituisce sempre un valore compreso tra 0 ≤ α ≤ N-1: hash(k)= α con 0. Per inserire nella tabella delle chiavi il record della chiave k bisogna valutare hash(k). Supponendo che il valore sia α, si inserisce il record corrispondente.