Informatica appunti

Informatica

Descrizione del corso

Venerdì 28 settembre 2018

Scheda del corso:

• 36 ore di lezione (9 volte, 4 ore).
• Si uscirà per le 5.30 più o meno e ci saranno pause.
• Il corso finirà a gennaio.

Esame

- Test a quiz (probabilmente sarà al pc) con 32 domande a risposta chiusa (durata: 45 min). Le domande saranno sulle nozioni che ha dato più qualche esercizio.

- Non c’è bisogno di comprare il libro e più avanti metterà a disposizione un’esercitazione simile all’esame.

- A lezione dice quello che c’è sulle slide ed è quello che chiederà all’esame.

Codifica e decodifica dell'informazione

Introduzione

Come faccio a mettere un’immagine sul computer? L’informazione che può essere compresa da un essere umano o da una macchina ha un formato completamente differente: da qui il bisogno di fare una conversione da un tipo di informazione che possiamo comprendere e maneggiare noi ad un’informazione che possano maneggiare le macchine (un computer in generale).

Le informazioni vengono codificate secondo le sfilze di 0 e 1.

Il Bit

L’unità di informazione minima che possiamo verificare su un computer è il bit (=celletta). Il bit può contenere solo due valori, 0 e 1, ovvero le macchine possono scrivere solo 0 e 1 per limiti di tipo tecnologico.

Questo perché i dispositivi che compongono un computer sono bistabili: assumono sempre due stati, ovvero possono assumere uno stato fra due possibili.

Questi due termini fisici possono essere tradotti con un sistema binario, cioè a 2 simboli: 0 e 1. [Es. la carica elettrica/magnetica può essere + o -].

Sequenze di bit

Con un bit singolo è possibile dunque discriminare due stati. Usando però un solo bit, uso sequenze di bit.

[Es. se io avessi solo due bit a disposizione potrei rappresentare 4 identità: quadrato, cerchietto...].

Quante entità possono essere codificate con una sequenza di N bit?

Es. 3 bit codifico 8 entità. 1 bit: 2 entità dunque 2³. → 2 bit codifico 4, dunque 2². → 1 bit posso codificare 2 = 2¹ entità.

Di quanti bit ho bisogno per discriminare M entità?

Selezionando un numero di bit N tale che il numero delle configurazioni possibili sia superiore o uguale a M, esiste almeno una configurazione da far corrispondere a ogni simbolo dell’alfabeto.

Matematicamente, la formula è log₂(M) = ln(M)/ln(2)

Esempio: M = 350 log₂(350) = ln(350) / ln(2) = 8.4512... quindi 9 bit.

Il Byte

È stata scelta una sequenza di bit, uguale per tutti, su cui basare tutti i conti. Si è deciso di contare come sequenza standard quella lunga 8 bit che è chiamata 1 byte.

Kilobyte = 2¹⁰ byte = 1 migliaio

Megabyte = 2²⁰ byte = 1 milione

Gigabyte = 2³⁰ byte = 1 miliardo

Terabyte = 2⁴⁰ = mille miliardi di byte

I caratteri della comunicazione scritta

Il problema che mi si pone è decidere di quanti bit ho bisogno per codificare tutti i caratteri del testo scritto.

Abbiamo:

• 52 lettere dell’alfabeto anglosassone (minuscole e maiuscole)
• Punteggiatura
• Segni matematici
• Caratteri nazionali (lettere accentate che nell’alfabeto anglosassone non ci sono)

In totale sono circa 220 caratteri quindi ho bisogno di 8 bit = 1 byte (sequenza minima per codificare i caratteri occidentali).

[Es. Io posso decidere che la lettera “a” equivale alla sequenza di 8 zeri, di 8 uni non c’è un modo univoco per codificare una sequenza di bit in caratteri].

Ciò che devo fare però è decidere che quella sequenza di bit la associo sempre a quel particolare carattere.

Codifica e decodifica ASCII

Per questo sono state scelte delle sequenze standard:

• ASCII STANDARD = 7 bit per carattere, rappresenta 128 caratteri (senza i caratteri nazionali perché l’americano non ha gli accenti)
• ASCII ESTESO = 8 bit per carattere, rappresenta 256 caratteri (tutti quelli di cui abbiamo parlato prima)
• UNICODE = 16 bit per carattere perché contiene sia l’ASCII ESTESO che i caratteri etnici. Rappresenta circa 65.000 caratteri.

Come faccio a codificare una parola?

Banalmente concateno una sequenza di bit che compone i singoli caratteri.

[Es. voglio codificare il testo “il Po!”. i = 01101001 (codificata in ascii esteso perché vale 8 bit), l = 01101100, lo spazio perché è un carattere = 00000000]

In questo modo trasformo il testo da un carattere comprensibile all’umano in una sequenza di bit che può essere inserita in un computer!

Come faccio a decodificare una parola? Devo dividere la sequenza in 4 pezzetti ognuno dei quali viene trasformato nel suo omonimo in caratteri.

[Es. 01010000 = P]

Numeri e codifica ASCII

Lo standard di codifica ASCII (così come le altre codifiche standard) permette di codificare cifre decimali da 0 a 9 come caratteri: è quindi possibile, utilizzando tale codifica, rappresentare numeri come sequenze di caratteri. Il problema è che le operazioni matematiche sui numeri risultano molto complesse.

Se voglio fare dei conti sopra, la codifica dei caratteri non funziona. Ci dobbiamo rifare dunque alla legge di conversione di numeri in basi differenti.

Il sistema di numerazione posizionale

Notazione posizionale:

• Ogni cifra di numero assume un valore in base alla sua posizione

[≠ gli antichi romani usavano un sistema additivo: fare addizioni per capire a che n° faceva riferimento.]

[Es. 365: 3 centinaia, 6 decine, 5 unità. = 3 x 100 + 6 x 10 + 5 x 1 = 3 x 10² (moltiplicato per 2 perché in seconda posizione) + 6 x 10¹ + 5 x 10⁰]

La notazione posizionale può essere usata con qualunque base, non solo quella decimale, creando così differenti sistemi di numerazione.

Le basi del computer

Nella rappresentazione informatica di utilizzano prevalentemente 3 sistemi di numerazione:

• Binaria (base 2)
• Ottale (base 8)
• Esadecimale (base 16)

Per ogni base di numerazione si utilizzerà un numero di cifre uguale alla base:

• Decimale: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
• Binaria: 0, 1
• Ottale: 0, 1, 2, 3, 4, 5, 6, 7
• Esadecimale: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A (=10), B (11), C (12), D (13), E (14), F (15)

Quando non è evidente dal contesto in quale base un numero è scritto, è necessario indicarla in modo esplicito, ponendo la base come pedice al numero (1001₁₀ ≠ 1001₂).

Conversione da base b a base 10

Per convertire un numero da una qualunque base alla base 10 è sufficiente rappresentare esplicitamente i calcoli.

Esempi:

Da base 2 a base 10:

• 101001₂ = 1 x 2⁵ + 0 x 2⁴ + 1 x 2³ + 0 x 2² + 0 x 2¹ + 1 x 2⁰ = 32₁₀ + 0 + 8₁₀ + 0 + 0 + 1₁₀ = 41₁₀

Lo scompongo nei suoi fattori ma anziché moltiplicare per 10, la moltiplico per 2 elevato alla posizione.

Da base 8 a base 10:

• 2007₈ = 2 x 8³ + 0 x 8² + 0 x 8¹ + 7 x 8⁰ = 1024₁₀ + 0 + 0 + 7₁₀ = 1031₁₀

Da base 16 a base 10:

• B7FC₁₆ = 11 x 16³ + 7 x 16² + 15 x 16¹ + 12 x 16⁰ = 45056₁₀ + 1792₁₀ + 240₁₀ + 12₁₀ = 47100₁₀

Conversione da base 10 a base b

Per convertire un numero dalla base 10 ad una qualunque base b occorre trovare tutti i resti delle successive divisioni del numero per la base b.

Esempi:

Convertire 210₁₀ in base 2:

• Divido 210 per 2 → 210: 2 = 105 x 2 + 0 e memorizzo 0
• Divido 105 per 2 → 105: 2 = 52 x 2 + 1 e memorizzo 1
• Divido 52 per 2 → 52: 2 = 26 x 2 + 0 e memorizzo 0
• Divido 26 per 2 → 26: 2 = 13 x 2 + 0 e memorizzo 0
• Divido 13 per 2 → 13: 2 = 6 x 2 + 1 e memorizzo 1
• Divido 6 per 2 → 6: 2 = 3 x 2 + 0 e memorizzo 0
• Divido 3 per 2 → 3: 2 = 1 x 2 + 1 e memorizzo 1
• Divido 1 per 2 → 1: 2 = 0 x 2 + 1 e memorizzo 1

Riscrivendo i resti in ordine inverso ottengo 11010010₂ (= 210₁₀).

Convertire 210₁₀ in base 16:

• Divido 210 per 16 → 210: 16 = 13 x 16 + 2 e memorizzo 2
• Divido 13 per 16 → 13: 16 = 0 x 16 + 13 e memorizzo D (= 13₁₀)

Riscrivendo i resti in ordine inverso ottengo D2₁₆ (= 210₁₀).

Conversione tra basi 2, 8 e 16

Le basi ottale ed esadecimale non sono realmente usate dai computer, ma servono a noi umani, per rappresentare in maniera più semplice i numeri del sistema binario (è più semplice passare da un numero a base binaria ad un numero a base 8 o 16).

• Separare i bit del numero binario in gruppi, da sinistra a destra, contenenti 3 bit per la base ottale o 4 bit per la base esadecimale;
• Per ogni sequenza di bit, trovare l’equivalente nella base 8 o 16;
• Scrivere il numero ottenuto concatenando le cifre.

La conversione da queste due basi alla base binaria funziona all’inverso.

[Esempio: conversione di 111110011001₂

• Ottale: 111 110 011 001 → 7 6 3 1 → 7631₈
• Esadecimale: 1111 1001 1001 → F 9 9 → F99₁₆

Conversione di un numero in base N ad un numero in N

Utilizzata per i numeri che non siano 2, 8, 10 e 16:

• Utilizzo il metodo "2/10"
• Utilizzo il metodo "10/N", con il numero ottenuto nel primo passaggio
• Scrivo il numero ottenuto, leggendo la riga dei resti da dx a sx

Esempio: 53 in base 7 = 38 in base 10 = 123 in base 5.

Rappresentazione dei numeri

In generale, un numero può essere in una di queste 3 categorie:

• Interi senza segno (positivi)
• Interi con segno (positivi e negativi)
• Reali (numeri positivi e negativi con virgola)

Quella che abbiamo visto precedentemente è la codifica degli interi senza segno, la più semplice. Gli altri tipi di numeri sono codificati in maniera più complessa, ma non ci interessano.

Indipendentemente dalla rappresentazione scelta, essa sarà di tipo finito e consentirà di rappresentare solo un sottoinsieme finito di numeri.

Con 4 cifre a disposizione, qual è il più grande numero rappresentabile?

• In base 10: 9999 = 10⁴ - 1
• In base 2: 1111 (15₁₀) = 2⁴ - 1
• In base 16: FFFF (65535₁₀) = 16⁴ - 1
• In base 8: 7777 (4095₁₀) = 8⁴ - 1

In generale, con n cifre a disposizione e base b, il numero massimo (intero positivo) rappresentabile sarà bⁿ – 1.

Ma cosa succede se come risultato di un’operazione ottengo un numero superiore al massimo numero intero rappresentabile?

Esempio: Supponiamo che il computer supporti una rappresentazione dei numeri a 8 bit, e si vogliano sommare i numeri 11111111₂ e 00000001₂: il risultato è 100000000₂, numero non rappresentabile con 8 bit!

Il computer segnalerà un errore di overflow.

Codifica delle immagini

Introduzione

I caratteri alfanumerici ed i numeri non costituiscono le uniche informazioni che gli elaboratori utilizzano. Le applicazioni multimediali (come il Web) utilizzano ed elaborano informazioni che contengono anche immagini, suoni e filmati.

Come si codificano?

Cominciamo col considerare una semplice immagine in bianco e nero, senza alcuna ombreggiatura o livello di chiaroscuri.

Utilizzando una tecnica classica dei disegnatori per riprodurre figure rispettandone le proporzioni, suddividiamo l’immagine mediante una griglia formata da linee orizzontali e verticali equidistanti tra loro.

Codifica pixel

Ogni quadratino derivante da tale suddivisione prende il nome di pixel (“picture element”) e può essere codificato in binario secondo la seguente convenzione:

• Il simbolo “0” viene utilizzato per la codifica di un pixel corrispondente ad un quadratino in cui il bianco è predominante
• Il simbolo “1” viene utilizzato per la codifica di un pixel corrispondente ad un quadratino in cui il nero è predominante

Poiché una sequenza di bit deve essere lineare, è necessario definire convenzioni per ordinare la griglia dei pixel in una sequenza; assumiamo che i pixel siano ordinati dal basso verso l’alto e da sinistra verso destra, la codifica risulta: 1 0 0011100000 0001000000

Quella che si ottiene nella codifica è un’approssimazione dell’immagine originaria, che può essere più o meno precisa in base alla grandezza dei pixel: con la digitalizzazione si parla dunque di perdita di qualità.

Immagini a toni di grigio e a colori, RGB

Assegnando un bit ad ogni pixel è possibile codificare solo immagini in bianco e nero. Per codificare le immagini con diversi livelli di grigio oppure a colori si usa la stessa tecnica, ma per ogni pixel viene assegnata una sequenza di bit: per esempio, se utilizziamo quattro bit a pixel possiamo rappresentare 2⁴ = 16 livelli di grigio o 16 colori diversi.

Modello RGB

Uno dei modelli di rappresentazione di colori più utilizzato è chiamato RGB (Red, Green, Blue), grazie al quale un qualsiasi colore può essere rappresentato componendo rosso, verde e blu (colori primari).

Ogni pixel codificato in RGB:

• Contiene la sfumatura di rosso, di verde e di blu che lo compone
• Ogni colore primario (rosso, verde e blu) è rappresentato con 1 byte, pertanto si possono esprimere 256 sfumature per il rosso, 256 per il blu e 256 per il verde che, combinate insieme, danno origine a 16.777.216 colori diversi

Quindi ogni pixel per essere memorizzato richiede in tutto 3 byte: 1 byte per ognuno dei tre colori primari.

Grafica bitmap

Le immagini codificate pixel per pixel, con la tecnica che abbiamo visto, sono dette immagini in grafica bitmap ed occupano molto spazio. Per questo motivo esistono degli standard di codifica delle immagini che utilizzano tecniche di compressione, in modo da ridurre le dimensioni delle immagini rispetto al formato bitmap.

Queste tecniche sfruttano strumenti di teoria dell’informazione, o alcune regolarità presenti nelle immagini.

[Ad esempio, se in un’immagine più punti vicini tra di loro assumono lo stesso colore, si può memorizzare la codifica del colore una sola volta e poi ricordare per quante volte deve essere ripetuta] Alcuni esempi di formati compressi molto utilizzati sono GIF e JPEG.

Anche qua, oltre alle dimensioni, anche la qualità delle immagini si riduce rispetto allo standard bitmap: per l’utente medio la differenza è però quasi invisibile, ma per chi si occupa di grafica l’immagine risulterà più difficile da manipolare.

Esercizio

Un'immagine a 16.777.216 colori è formata da 400x400 pixel. Quanto spazio occupa?

• 400 x 400 = 16 x 10⁴ pixel
• 1 pixel = 3 B
• Spazio occupato 48 x 10⁴ B (circa 480 KB)

Grafica vettoriale

Un altro tipo di codifica delle immagini è quella vettoriale: in una codifica di tipo vettoriale non si specificano le informazioni di colore dei singoli pixel dell’immagine.

Viene invece specificato individualmente ogni elemento geometrico primitivo (per esempio linee, curve), attraverso un numero od una formula matematica.

Le immagini vengono costruite a partire dalla descrizione degli elementi che le compongono mediante un linguaggio testuale, che specifica le forme geometriche base che compongono l’immagine da codificare, la loro posizione e dimensione.

A esempio Google nel 2015 ha cambiato logo per renderlo vettoriale: è formato da 10 cerchi, 5 rettangoli ed una curva (per la g).

Grafica vettoriale vs bitmap

La grafica vettoriale viene utilizzata perché per immagini semplici spesso si occupa meno spazio rispetto all’uso del bitmap o di altri standard compressi, e le immagini non perdono in definizione se ingrandite.

La grafica bitmap, invece, riesce a rendere con qualità maggiore immagini con un numero elevato di colori e di sfumature, mentre le immagini vettoriali sono più adatte ad immagini con colori piatti e forme geometriche semplici.

Codifica dei suoni

Fisicamente un suono è rappresentato come un onda che descrive la variazione della pressione dell’aria nel tempo (onda sonora).

[Sull’asse delle ascisse viene rappresentato il tempo e sull’asse delle ordinate viene rappresentata la variazione di pressione corrispondente al suono stesso.]

Processo di codifica

Per la codifica dei suoni:

1. Si effettuano dei campionamenti sull’onda: cioè si misura il valore dell’onda a intervalli di tempo costanti.
2. Si codificano in forma digitale le informazioni estratte da tali campionamenti: il valore numerico sull’asse delle ordinate.

Il numero di campioni raccolti per secondo definisce la frequenza di campionamento si misura in Hertz (Hz).

Quanto più frequentemente il valore di intensità dell’onda viene campionato, tanto più precisa sarà la sua rappresentazione.

La sequenza dei valori numerici ottenuti dai campioni può essere facilmente codificata con sequenze di bit, concatenandoli tra loro.

La rappresentazione è tanto più precisa quanto maggiore è:

• La frequenza dei campionamenti
• Il numero di bit utilizzati per codificare l’informazione estratta in fase di campionamento (il valore dell’onda nell’istante di tempo)

[Es: con 2 bit potrò rappresentare solo 4 valori, con 8 saranno 256, con 16 invece 65.536, e così via.]

Questo è il modo generico per codificare i suoni. Standard di codifica diversi useranno la stessa tecnica di base, ma variando il numero di campionamenti al secondo e la loro precisione (ossia con quanti bit rappresentare un singolo campionamento).

Esempio di codifica audio

Ad esempio, per codificare la musica di qualità CD bisogna:

• Utilizzare due registrazioni corrispondenti a due microfoni distinti (per il canale destro e sinistro).
• Campionare il segnale musicale producendo 44.100 campioni al secondo.
• Per ogni campione (che è un numero) si usano 16 bit.

Per cui, il numero di bit che sarebbero necessari per codificare ogni secondo è pari a 2 x 44.100 campioni.