Informatica generale

Lezione 1-3/04/25
Definizione di informatica
- Dal francese informatique—> information e automatic
- In inglese computer science, in analogia con management science

The discipline of computing is the systematic study of algorithmic processes that describe vedo slide

Cosa NON è l’informatica

- Non è l’uso delle applicazioni
- Non è la “scienza” dei computer
- Attribuita a Edsger Dijkstra

Fluency: capitolo 1
Computer: etimologia
Ciò che computa, è un processo strettamente legato allo svolgimento di calcoli numerici.
Parola in uso dal XVII secolo—> qualcuno che computa
Fino ad anni 1940: “computer umano”
- Calcoli lunghi e noiosi svolti da persone
- Dal 1800 anche donne
Da fine 1800—> macchina calcolatrice
Da 1930–> macchina digitale programmabile

Recap dello sviluppo tecnologico

Abbiamo sempre avuto bisogno di contare.

Sistemi di calcolo primitivi

- Osso di Lebombo
- Osso di Ishango
Misure del tempo, calendari, fasi lunari…
Sistemi di calcolo
- “Calculi”, sassolini
Forme/decorazioni diverse per indicare valori diversi (pagamenti, contabilità)
- Calcoli di argilla (riproduzione), Mesopotamia, circa 3500 a.C.
- Abaco (tavola, asse)
- Tavola di Salamina—> circa 300 a.C.
Contabilità finanziaria
- Astrolabi
Dispositivi di calcolo
- Calcolatrici meccaniche:
-Schickard, l’orologio calcolatore
-Pascal, la Pascaline
Le macchine di Babbage
- Charles Babbage (1791-1871):
primo computer meccanico, concettualmente simile a computer moderni
- Macchina analitica
Programmabile via schede perforate
Con un linguaggio di programmazione
 Mai realizzata

Lezione 16/04/2025
Algoritmi-parte 2
Un problema, molti algoritmi
Dato un problema computazionale, ci sono molti algoritmi che lo risolvono.
Cos’è un problema di ricerca? È un tipo di algoritmo—> ti do una lista e tu devi trovare gli elementi.
Problema molto frequente e deve essere risolto velocemente.

Ci sono due algoritmi della ricerca:

- Binaria
- Dicotomica

Cosa sono input e output? Input cosa entra (nel caso del problema della ricerca la lista ordinata degli
elementi). L’output è ciò che esce, in questo caso la posizione dell’elemento. Ci interessa sapere se
l’elemento è presente nella lista, non le sue caratteristiche.

Nella specifica degli input la lista è ordinata, se la lista non è ordinata il processo è più complicato. L’unica
possibilità sensata è quella di ordinare la lista, specialmente se abbiamo bisogno di utilizzarla spesso, anche
se questo processo richiede un certo sforzo.

Ricerca lineare
Idea—> esamino tutta la lista finche non trovo l’elemento cercato
Input: lista di elementi, elemento da cercare
Output: vero/falso
 L’algoritmo funziona sia che la lista sia ordinata che no.

Pseudo codice
Composto da istruzioni base e composte—> quelle che fanno il loop (while con se e altrimenti)

-elemento corrente (assegnato al primo elemento della lista)

-Finché non trovo l’elemento e la lista non è finita
Loop:
Se l’elemento corrente è uguale a quello cercato allora output vero
Altrimenti passa all’elemento successivo
-Se la lista è finita allora—> elemento non trovato
Altrimenti—> elemento trovato

Ex cerco autore in uno scaffale di 16 libri

- Caso fortunato (ottimo) cerco Asimov, trovato con un confronto, siamo usciti dal loop
immediatamente
- Caso sfortunato (pessimo) cerco Wells, trovato con 16 confronti
- Altro caso pessimo (elemento non presente)
- Elemento non presente e lista non ordinata
- Caso probabile (medio), cerco Kafka con 8 confronti, è il più difficile da stabilire richiede
assunzioni probabilistiche
Con l’ottimizzazione esamino gli elementi finché non trovo quello cercato o fino a che non ho superato la
posizione.
Ricerca binaria
Versione più veloce da eseguire.
Come cercare sonnambulo su un vocabolario di italiano?
- Ricerca binaria, apro una pagina a ¾ del libro, poi vado avanti e indietro… è la strategia migliore
assumendo che l’elenco sia ordinato

Ma cosa vuol dire ordinare una lista? Dipende dai dati:

- Numeri: ordine dei numeri naturali/reali
- Parole: ordine alfabetico
- Libri: ordine per autore, titolo, ISBN, editore

Idea
-esaminiamo l’elemento a metà della lista
-se siamo fortunati è quello cercato, altrimenti…
-se è più grande ad es è una parola che sta dopo a quella cercata secondo l’ordine alfabetico
-se è più piccolo, vale il ragionamento opposto

Caso ottimo kafka con 1 confronto

Caso pessimo wells con 5 confronti
Elemento non trovato, eco con 4 confronti
Caso medio, moore trovato con 3 confronti

Algoritmo vedo slide 25

Loop simile al precedente

Riassunto: algoritmi e linguaggi vedo slide 27

Programmi e sotto programmi

Un programma usa un sottoprogramma definito precedentemente

Algoritmi parte 3
Prestazioni di un algoritmo
Quanto tempo impiega l’algoritmo di ricerca dicotomica per cercare un valore?
Domanda mal posta, la risposta dipende da:
- Quanto è lunga la lista
- Dove si trova l’elemento da cercare nella lista
- Su quale computer viene eseguito (diversi processori, sistemi operativi)
- Il linguaggio di programmazione in cui è stato implementato l’algoritmo (meno significativo)

Devo costruire una funzione per definire il tempo di esecuzione T di un algoritmo. Facciamo prima alcune
ipotesi:
- Le operazioni base hanno tutte lo stesso tempo di esecuzione circa su ogni computer
- Definiamo il tempo di esecuzione T di un algoritmo come il numero di operazioni base eseguite
o Quindi non è un tempo in secondi, è un numero
o Definizione indipendente dal computer su cui si esegue l’algoritmo
 Modello di costo: il tempo di esecuzione di un algoritmo dipende in generale da:
- Numero di operazioni base eseguite, che però a loro volta dipendono da:
- Dimensione dei dati da elaborare (es. dimensione della lista in cui cercare e in subordine…)
- Caratteristiche dei dati da elaborare (es. elemento cercato coincide con il primo della lista)
Noi vogliamo stimare una funzione T(n) che descrive il tempo di esecuzione unicamente in funzione della
dimensione n dei dati.

Come gestire le caratteristiche dei dati?

Di solito si stima T(n) per eccesso, ovvero nel caso pessimo del valore dei dati—> a seconda del problema
la def di caso pessimo assume significati diversi

Si possono anche fare stime di caso medio (con ipotesi statistiche, es. lista di numeri e numero da cercare
generati in maniera casuale).

Prestazioni di algoritmi di ricerca

Prestazioni ricerca lineare
Dimensione problema: n elementi nella lista
Contiamo come operazione base il confronto tra elementi
Caso pessimo (elemento non presente)—> allora si eseguono esattamente n confronti, possiamo dire che
“T(n) è all’incirca proporzionale a n”
Astraiamo da costi legati ad altre operazioni come “passa all’elemento successivo”

Prestazioni ricerca binaria

Contiamo confronti nel caso pessimo di elemento non presente in lista n elementi (come x ricerca lineare)
Dopo ogni confronto rimane da esaminare la metà degli elementi precedenti
- Confronto 1:lista n di elementi
- Confronto 2: sotto lista n/2 di elementi
- Confronto 3. Sotto lista n/4 elementi…
- Dopo k confronti: sotto lista di un elemento—> ho finito
- Quindi
T(n)=k
Quanto vale k? Es. T(16)= 4. In generale?

Logaritmo
Inverso dell’esponenziale
L=log(b) a
base
argomento
esponente da dare alla base b per ottenere l’argomento a=b^L
Es. L= log (2) 16 (2 base 16 argomento)
2^4=16 , quindi L=log (2) 16=4

Logaritmo e divisibilità
Logaritmo in base 2 è numero di volte in cui un numero è divisibile per due.
Ad es. numero 256=2^8 —> 8=log(2) 256
 Divisibile per due 8 volte
In generale un numero n=2^k è divisibile per due esattamente k=log(2) n volte
Altri numeri che non sono potenze esatte di 2: si usa la divisione senza resto. Ad es:
21/2=10 10/2=5 5/2=2 2/2=1

Confronto tra algoritmi di ricerca

In generale: log(2)n < n
Il numero di confronti effettuati dalla ricerca binaria è sempre minori di quella della ricerca lineare.

Funzioni e andamenti
Al crescere di n le varie funzioni divergono significativamente.

Ci interessa cosa succede quando n è molto grande, perché per n piccolo tutti gli algoritmi sono veloci!
Es in figura:
- Per valori piccolo di n i grafici si intersecano
- Per n>1 (e per sempre) n^2>2
- Per n>4 (e per sempre) 2^n>n^2
In generale, per n grande—> log(2)n<n<n^2<n^k<2^n

Confronto tra algoritmi di ricerca

In un linguaggio di programmazione standard (es. Java) un computer esegue un confronto in 10 nanosecondi
(10^-8 sec)
Riassunto
Modello di costo per le prestazioni di un algoritmo.
Definizione di dimensione n di un problema.
- Operazioni base
- Caso pessimo
Definizione di tempo di esecuzione T(n)
- Tempo come funzione della dimensione del problema (es. funzione lineare o logaritmica)
Prestazione di algoritmi di ricerca
- Dicotomica molto più veloce di lineare alla crescita di n: log(n) < n

Un problema “intrattabile”
Il gioco delle torri di Hanoi
Un esempio di problema intrattabile.
Scopo del gioco: spostare la torre di dischi da un piolo “origine” ad un piolo “destinazione”.
Regole del gioco: si può spostare un solo disco per volta, in ogni istante un disco non può poggiare su un
disco più piccolo.

Torre di Hanoi: soluzione ricorsiva

Problema a n=1 disco e n=2 dischi—> soluzione banale, rispettivamente 1 e 3 mosse
Problema a n=3 dischi
1. Risolvo il problema a 2 dischi, ovvero sposto i 2 dischi più piccoli con le mosse del problema a 2
dischi (il terzo è come se non ci fosse)
2. Sposto il disco più grande
3. Risolvo nuovamente il problema a 2 dischi
Problema n=4 dischi
1. Risolvo il problema a 3 dischi
2. Sposto il disco più grande
3. Risolvo nuovamente il problema a dischi

Soluzione
In generale, soluzione del problema a n dischi
1. Risolvo il problema a n-1 dischi
2. Sposto il disco più grande
3. Risolvo nuovamente il problema a n-1 dischi

Regola mnemonica di soluzione:

Spostare il disco più piccolo una volta ogni 2 mosse, sempre nella stessa direzione—> ovvero dal piolo 1 al
piolo 2, dal piolo 2 al piolo 3, dal piolo 3 al piolo 2, e di nuovo a capo
La mossa intermedia tra due spostamenti del disco più piccolo è l’unica altra mossa possibile.

Quante mosse?
Numero di mosse con n dischi
- Il doppio +1 delle mosse con n-1 dischi
Con n dischi il numero di mosse è 2^n-1
Il numero di mosse è funzione esponenziale del numero n di dischi
Non esistono algoritmi più veloci (lower bound)

Tempo di soluzione
La nel lontano oriente misterioso, ogni giorno i sacerdoti di un segreto tempio hindu muovono uno dei 64
dischi della torre sacra. L’antica profezia a cui obbediscono afferma che quando l’ultima mossa del gioco
sarà completata l’universo cesserà di esistere…

Supponendo che i monaci non sbaglino mai nemmeno una mossa, il tempo impiegato per arrivare alla fine
del gioco è:
(2^64-1) giorni= circa 44 milioni di miliardi di anni

Scala Richter
Utilizzata per misurare l’intensità dei terremoti. La magnitudo data dal log(10) de max spostamento della
traccia in un sismografo.
Ogni aumento di un grado corrisponde a un’ampiezza del movimento del terreno 10 volte maggiore e a
un’energia libertà circa 31,6 volte maggiore. Quindi se passo da magnitudo 5 a 6 sulla scala Richter,
l’energia liberata aumenta di oltre 30 volte.

Indice di trasmissione
Indice R_0 di trasmissione di Sars-COVID19
Se R_0= 2, crescita dei contagi è esponenziale
In realtà le cose sono più complicate e dipendono significativamente dal periodo di incubazione…

Complessità di un problema
Come assegnare una complessità computazionale ad un problema, visto che può essere risolto da diversi
algoritmi?
 La complessità di un problema è data dalle prestazioni del più veloce algoritmo (noto) in grado di
risolverlo
Es. la complessità del problema della ricerca log(2) n—> queste sono e prestazioni dell’algoritmo di ricerca
binaria—> è questo l’algoritmo più veloce

Classi di complessità
Un algoritmo è:
- Efficiente se le sue prestazioni (caso pessimo) sono al più polinomiali, ovvero log(2) n, n^2,n^k…
- Inefficiente se le sue prestazioni (caso pessimo) sono almeno esponenziali, ovvero 2^n, n^n…

Un problema è:
- Trattabile se la complessità dell’algoritmo risolutivo è al più polinomiale
- Intrattabile se la complessità è almeno esponenziale

Molti problemi realistici si pensa siano intrattabili

Anche se un problema è intrattabile posiamo cercare soluzioni non ottimali

Esercizi su algoritmi—> vedo slide

PowerPoint su breaking news Meta e TikTok

Informatica, una definizione in breve (Grin)

L’informatica è la scienza che si occupa dei sistemi e processi computazionali e del trattamento automatico
dell’informazione e ne studia gli aspetti fondazionali, metodologici, tecnologici, sociali e didattici

Rappresentazione dell’informazione
Simboli e informazione
Per rappresentare l’informazione si può usare un insieme di simboli qualsiasi. Quando sappiamo cosa è
rappresentato da un certo dato, allora abbiamo informazione.
 L’informazione è costituita da un insieme di dati espressi mediante una rappresentazione
simbolica
Della stessa informazione sono possibili diverse rappresentazioni, che usano supporti fisici e regole
diverse.

Codici
Un codice disciplina la relazione tra dati (rappresentato) e simboli (rappresentante).
Per rappresentare l’informazione dobbiamo:
1. Determinare le informazioni da rappresentare (numeri, testi, immagini)…
2. Definire un insieme di simboli per rappresentarle tratti da un alfabeto finito, per numeri interi,
secondo regole di formazione.
3. Associare non ambiguamente ogni simbolo ad un dato: “corrispondenza bi-univoca” (idealmente)

Altri esempi di codici:

 Codice Morse
 CAP (codice di avviamento postale)
 Stele di Rosetta
 Codice ASCII
 Codice a barre

Rappresentazione digitale
In informatica per rappresentare qualsiasi informazione si usano solo due simboli.
Definizione: BIT—> Binary digIT, unità minima di informazione che può assumere solo due valori (0 e 1)
Suddividiamo l’informazione in due soli casi:
- PandA (Presence and Absence), “assenza” non è mancanza di informazione!

Tante possibili interpretazioni, a seconda del contesto…

Bistabilità
In informatica per rappresentare qualsiasi informazione si usano solo due simboli.
- Perché due simboli corrispondono facilmente a stati fisici di un dispositivo elettronico (es. transistor
acceso o spento)—> dispositivo bistabile
- Computer adottano la rappresentazione binaria perché è più facile costruire circuiti logici che
distinguono tra due livelli invece che dieci
- …per non parlare di livelli infiniti/continui come la luminosità, il volume…
Esempio DVD

Quanti valori? Sequenze di bit

Con un bit posso rappresentare solo 2 valori (risorsa apparentemente limitata)
Con una sequenza di n bit posso rappresentare molti più valori. Quanti?
Lezione- 30/04/2025
Multimedia
Termine coniato da Bob Goldstein (artista americano, nato nel 1936)
Definizione: tipo di comunicazione basata su integrazione di testo, audio, immagini, animazioni, video,
contenuto interattivo
 1. Multimedia “lineare”= presentazione del contenuto in maniera lineare, senza controllo di
navigazione da parte dell’utente (es. cinema)
2. Multimedia “non lineare”= presentazione del contenuto controllata in maniera interattiva (es. video-
giochi)

Informazione multimediale
Vogliamo capire come un computer rappresenta ed elabora: un colore, un’immagine, una video, una canzone,
una voce.
Tutto è bit

Rappresentazione digitale di immagini

Immagini digitali
Due formati di rappresentazione:
- Bitmap (o raster), dove l’immagine è divisa in punti di colore
Bitmap= mappa di bit
Raster= dal latino rastrum, rastrello dal tipo catodico
Formato per immagini complesse e irregolari, es. scanners, foto digitali

- Vettoriale: immagine codificata come un insieme di linee e figure geometriche

Adatto per immagini regolari, es. grafici

Immagini raster
Pixel: (Picture Element) unità elementare che compone un’immagine
Nella rappresentazione raster l’immagine viene vista come un insieme di punti di colore.
Un computer visualizza un’immagine riproducendo i pixel che la compongono, più pixel=più qualità.

Slide sul pixel

La risoluzione di un’immagine è il numero totale di pixel in cui è divisa.
Un’immagine con risoluzione 800x600 richiede 480.000 pixel

Risoluzione e medium di output

La qualità dipende non solo da risoluzione ma anche da dimensione (lunghezza diagonale)
Unità di misura più utile è la densità di pixel, PPI (pixels per inch), pixel per unità di superficie
Es. monitor di 15 pollici con risoluzione 1024x768
- Diagonale 15–> Pitagora lati 12x9 pollici
- 1024/12=768/9=85 quindi PPI è 85

Pixel e bit
Per tradurre un’immagine in BIT occorre pensare a ogni pixel come a un punto di colore.
- Convenzione: rappresentiamo pixel dal basso in alto e da sinistra a destra
- Se associamo a ogni colore una codifica binaria, ogni pixel corrisponde a una sequenza di BIT
- Caso più semplice: immagine in bianco e nero (ogni pixel può avere solo due colori). Basta un BIT
per ogni pixel, 0 indica il bianco 1 indica il nero
- Guardo i due esempi

Rappresentazione dei colori

Colori
Definizione dei colori primari= insieme di colori che si possono combinare in varie proporzioni per produrre
una gamma di colori.
Combinazione additiva dei colori= sorgenti luminose di colori diversi che stimolano la stessa area della
retina sommano i propri effetti
Tre colori primari additivi: rosso, verde, blu (RGB)
Il sistema è additivo perché si aggiungono lunghezze d’onda di luce per creare nuovi colori, si parte dal nero
(assenza di luce) aggiungendo i colori primari fino al bianco.

Colori RGB
Palette di 125 colori e codici esadecimali

Un colore è specificato da tre componenti: rosso, verde, blu

L’intensità di ogni colore è rappresentata da una quantità (da 0 a 255, quindi 8 BIT)
Nero=assenza di colore
Bianco= massima intensità di tutti i componenti
Se i tre su pixel sono tutti uguali, allora è un grigio (più o meno intenso a seconda se vicino a 0 o 255)

Codifica dei colori RGB

Per ognuno dei 3 colori (subpixel) si possono avere 256 livelli di luminosità. La luminosità di un subpixel è
codificata in un byte.

Modifica di un colore
Ne modifichiamo la quantità di pixel, si può aggiungere qualsiasi quantità al byte di un colore, ma il risultato
deve esser sempre minore di 255, altrimenti errore di overflow

Fotoritocco
Cambiare il colore è una semplice somma tra numeri binari
- Luminosità: quantità complessiva di luce presente in un’immagine. Nel modello RGB, strettamente
legato all’intensità dei singoli pixel
 Vicinanza al bianco (255, 255, 255)
Sommare un valore positivo aumenta la luminosità, sottraendo diminuisce

- Contrasto: differenza di luminosità tra le parti più chiare e più scure

Maggiore la differenza, maggiore il contrasto
Aumentare il contrasto= amplificare la differenza tra i valori di pixel chiari e scuri. I pixel scuri
devono rimanere invariati, quelli chiari si devono schiarire progressivamente di più.
 Per ogni pixel moltiplica ogni colore per un fattore costante K

Aggiunta di colori
Modifichiamo in maniera differenziata pixel di luminosità diverse.

Colore digitale: riepilogo

Il colore è rappresentato da 3 quantità.
- Intensità di rosso verde blu

Insieme i tre valori formano un pixel

- Le parti costituenti sono sub-pixel
Assegniamo un byte a ciascuna intensità, tra 0 e 255
Le intensità sono numeri binari che possiamo elaborare
Compressione
Comprimere/decomprimere
Es. gas naturale
Non esempio acqua

Compressione dati
È utili comprimere dati e ridurne le dimensioni per memorizzarli e trasmetterli.
Compressione dati pre- computer:
- Tagli delle frequenze alte in telefonie
- Codici più brevi a lettere più comuni in codice Morse

Compressione digitale, usi:

- Quando si scarica del software
- Quando si trasmettono file di una certa dimensione
- Skype, zoom… VOIP (Voice Over Internet Protocol)

Algoritmi di compressione
È un campo di ricerca a sé stante
Tecniche di comprensione dei dati:
- Lossless (senza perdita). La rappresentazione originale ricostruibile perfettamente dalla
rappresentazione compressa
- Lossy (con perdita). Si rinuncia a ricostruire in modo esatto la rappresentazione digitale da quella
compressa, ma si sfruttano principi cognitivi così che questa perdita sia minimizzata e
irrilevante/non percepita

Lezione del 7/05/2025

Compressione lossless
Ricostruzione via inversione
- Decompressione è inverso della compressione
Fondamentale per situazioni dove non si può perdere informazione, pena inutilizzabilità:
- Testi
- Programmi eseguibili
- Dati scientifici
- Sistemi di backup e archiviazione
Processo di compressione
- L’algoritmo identifica schemi, ridondanze o proprietà statistiche nei dati originali
- Applica una serie di trasformazioni per rappresentare i dati in modo più efficiente, riducendo le
dimensioni
- I dati compressi sono una rappresentazione compatta d quelli originali
Processo di decompressione:
- L'algoritmo prende dati compressi come input
- Esegue le operazioni inverse di quelle applicate durante la compressione
Applicando le operazioni inverse, i dati originali vengono ricostruiti perfettamente dai dati compressi

Livello di compressione
 Rapporto tra dimensione del file non compresso e quello compresso
(3:1 per i testi, 2:1 per i binari in media)
Due tecniche:
1. Di sostituzione (basate su regolarità)
2. Statistiche (basate su frequenze)

Algoritmi lossless
RLE= Run-length encoding: run di un dato codificato dalla sua lunghezza
L’idea è trovare parti ripetitive adiacenti e riassumerle
Intuizione: pensate a dettare la stringa da comprimere

Es. 56 char: AAAAAAAAAAAAAAAAAAAABCBCBCBCBCBCBCBCBCBCAAAAAADEFDEFDEF

Compresso a (21,A)(10,BC)(6,A)(3,DEF)—> 17 char, parentesi per leggibilità, rapporto 3:1

Applicabile solo a file dove ripetizioni sono adiacenti (es fax o scansioni dove gran parte è bianca

Quindi RLE codifica:

- Valore dell’elemento ripetuto
- La lunghezza della run (quante volte l’elemento si ripete consecutivamente)

Pro Contro
Semplicità Inefficace con dati NON ripetitivi
(RLE può addirittura aumentare
la dimensione del file)
Efficacia con dati ripetitivi
Compressione lossless
Decompressione veloce

Oltre RLE
L’idea è simile: trovare ripetizioni, ma NON adiacenti
Algoritmo “come prima”:
- Quanto prima
- Quali ripetizioni

Es (63 char) VJGDNQMYLH KW VJGDNQMYLH ADXSGF O VJGDNQMYLH ADXSGF

VJGDNQMYLH EH ADXSGF
Prima parte, inalterata VJGDNQMYLH KW, poi vai indietro di 12 e copia 10. Quindi: b12c10 ADXSGF è
nuova, quindi resta, e così via.

● Risultato (44 char): VJGDNQMYLH KW b12c10 ADXSGF O b17c16 b16c10 EH b18c6

Con la ripetizione non adiacente comprimo e torno indietro

Compressione lossless statistica

Assegnare ai simboli un rappresentazioni a bit variabile, utilizzando meno bit per i simboli più frequenti
(Huffman coding)
Es, un milione di dati, abbiamo due milioni di bit
Dati tratti da A,C,G,T—> cod binaria 00-A, 01-C, 10-G, 11-T
Ad A assegno un bit perché è più frequente

Sembra banale, ma l’idea descritta è la base dell’algoritmo in zip

Funziona soprattutto con i testi, ma non sempre

Immagine non comprimibile

Compressione delle immagini

Spazio occupato da un’immagine
Immagini in bianco e nero: 1 BIT per pixel
Quindi lo spazio di un’immagine è il n di bit o byte per pixel, moltiplicato per il n di pixel

Es. immagine in bianco e nero risoluzione 800x600

- 1 BIT/PIXEL x (800x600) PIXEL= 1 BIT/PIXEL x 480.000 PIXEL= 480.000 BIT= 60.000 Byte=
60 KByte

Formato GIF
● Palette di colori limitata:
– GIF utilizza una tavolozza di colori indicizzata con un massimo di 256 colori. Questo limita la qualità delle
immagini ma riduce le dimensioni dei file, ideale per la grafica nei primi anni di Internet.

● Il formato GIF utilizza la compressione lossless

● Supporto per le animazioni:

– Un file GIF animato può contenere una serie di immagini (frame) che vengono riprodotte in sequenza,
creando un effetto di animazione
.
● Trasparenza:
– GIF supporta la trasparenza a livello di singolo colore, utile per sovrapporre immagini su sfondi di vari
colori.
Formato GiF esempio—> bandiera Ungheria e Italia

GIF animate
● Un singolo file .gif può contenere molte immagini
– Codificate una dopo l’altra all’interno del file
● Varie immagini (frame) sovrapposte a tempi diversi: semplice video clip
– Molto popolare nei primi browser
● Animazioni elementari senza usare veri video

GIF still kicking

● Compatibilità universale: GIF è supportato praticamente ovunque, su tutti i browser e le
piattaforme social.

● Semplicità d'uso: Creare e condividere GIF è semplice e non richiede software complessi.

● Cultura di Internet: GIF è diventato una parte integrante della cultura di Internet, soprattutto per quanto
riguarda i meme e le reazioni animate.
– La gif di Nyan Cat è andata all'asta per mezzo milione di dollari, o meglio: 300 ether.

Compressione lossy
● Principio: si può accettare di perdere delle informazioni durante la compressione se il risultato della
decompressione è ancora “appropriato”
● Immagini fisse: capacità dell’occhio di reintegrare informazioni eliminate
● Video: basato su ridondanza:
– Tieni solo le differenze
● Audio: elimina le parti non nelle frequenze udibili da orecchio umano.
● Maggiore compressione, maggiore perdita di informazioni, peggiore il risultato

Compressione lossy di un’immagine

Immagine bianca e nera
● Idea: Cancella ogni seconda riga e ogni seconda colonna
– Se immagine era 320 x 240, ora 160 x 120, ¼ dell’originale
● E posso andare avanti… ma poi “compression artifacts”
Decompressione?
● Bisogna “inventarsi” i pixel cancellati
– Diamo il colore di uno dei suoi vicini (es diagonale sinistra) – perdita è comunque irreversibile
● Algoritmi veri cancellano “meglio”, vedi JPEG

Formato JPEG
Inventato dal Joint Photographic Experts Group di ISO (International Standard Organizazion)
– Formato lossy
– Nato con lo scopo di standardizzare diversi formati per immagini con compressione di qualità
– Codifica colore a 24 bit
– Il grado di compressione può essere regolato dall’utente
– Si possono raggiungere dei livelli di compressione alti (10:1 o più, contro il 4:1 del GIF)

Codifica percettiva

– Sfrutta limiti della percezione visiva umana

● Due idee principali: l’occhio umano

– su un’area ampia è molto sensibile a piccole variazioni di luminanza (luminosità) e poco a
piccole variazioni di crominanza (colore)
– su un'area piccola è poco sensibile a rapide variazioni di luminosità

● Allora l'immagine viene “corrotta” nelle zone in cui l'occhio umano non lo nota

Es p. 20

Lezione 8/05/2025 integro con slide

Rappresentazione digitale del suono
Da analogico a digitale
Il mondo reale è analogico, parliamo di una continuità di dati come i suoni. I computer però elaborano solo
quantità discrete.

Cos’è il suono?
È un fenomeno di natura ondulatoria, è un’onda che si propaga in un mezzo meccanico, ha bisogno di un
supporto fisico (tendenzialmente è l’aria, ma può essere anche un elemento solido/liquido).
Per essere suono deve generare una percezione uditiva, altrimenti non si parlerà di questo.

Le tre componenti di un suono sono:

- Sorgente
- Mezzo di trasmissione
- Ricevitore
Un oggetto vibrante come una corda, fa vibrare l’aria intorno a sé.
 Vibrazioni si trasmettono all’orecchio e fanno vibrare il timpano. Hanno due principali
caratteristiche:
- Intensità: ampiezza dell’ombra sonora (volume)
- Frequenza: numero di vibrazioni al secondo

Es. onda sinusoidale, molto importante per quanto riguarda i fenomeni ondulatori, a livello uditivo
assomiglia a un fischio molto pulito.

Campionamento
 Misurazione discreta a intervalli regolari dell’ampiezza dell’onda sonora continua. Riduce il
continuo in intervalli discreti
Definizione: campione [equivalente audio di pixel]
– Valore dell'ampiezza dell'onda misurato in un istante di campionamento

Definizione: frequenza di campionamento

– Numero di campioni in un secondo (misurati in Hertz)
Hertz—> ogni quanto si ripete—> 1 volta al secondo= 1 Hertz

Es. slide
Per trovare la frequenza di campionamento devo calcolare il reciproco (1/….)

● Tra i tempi 0 e 330 millisec, abbiamo campionato ogni 30 millisec

– 12 campioni
● … che rappresentiamo come punti
(0, 7)
(30, 95.98676803710936)
(60, -71.43289186523432)
(90, -106.55949554687498) etc
● E poi immagazziniamo con arrotondamento

Hertz —>Unità di misura del Sistema internazionale della frequenza

Numero di ripetizioni di un evento periodico per secondo
– esempio: scatto lancetta dei secondi ha frequenza 1 Hz
Se un evento si ripete 10 volte al secondo diciamo che ha frequenza 10 Hz megaHz = 1 milione, GigaHz un
miliardo
– la velocità di clock degli ultimi microprocessori singoli (anni 2000-oggi): da 2 a 5 GHz:

Due domande
1. Quale frequenza di campionamento?
Più è alta, meglio è dal punto di vista della qualità (come per la risoluzione delle immagini)

Teorema del campionamento di Nyquist

Teorema del campionamento di Nyquist (1928) definisce la minima frequenza necessaria per campionare un
segnale analogico senza perdere informazioni, e per poter quindi ricostruire il segnale analogico originario.
– La frequenza di campionamento deve essere almeno doppia della massima frequenza del segnale che si
vuole registrare

Esempio: frequenze presenti nel parlato (segnali vocali) arrivano al massimo a 4 KHz (ovvero 4000 Hz)
– Allora nelle trasmissioni telefoniche si usa una frequenza di campionamento di 8 KHz (8000 campioni al
secondo)

Campionamento e percezione
In generale l'uomo è in grado di percepire frequenze fino a 20 KHz
– Oltre si parla di ultrasuoni
– Curve “equal-loudness”

Siamo più sensibili alle frequenze medie, sentiamo poco le basse e le alte
Allora in generale serve freq. di campionamento di almeno 40 KHz
– Le frequenze standard usate sono leggermente più alte: 44.1 KHz (standard CD)

Digressione: Presbiocusia
Percezione delle frequenze varia con l'età
● Presbioacusia: invecchiando si diventa progressivamente sordi alle alte frequenze
– Sopra i 30 anni non si sentono più una frequenza a 17 KHz
● Applicazione: suoneria del telefono udibili solo per i giovanissimi
– Verificate qui se lo sentite, o siete ormai dei vecchi

Valore di un campione
Ogni campione ha una ampiezza
– Rappresenta il valore dell'ampiezza dell'onda (pressione acustica dell’aria, segnale elettrico
prodotto da un microfono...) nell’istante di campionamento

Rappresentazione digitale
– Campione → sequenza di bit che ne codifica l’ampiezza

Analogia con immagini

– Ogni pixel ha un colore (in bit)
– Ogni campione ha un’ampiezza (in bit)
Digitalizzare un campione
Quanti bit per un campione?
– Accuratezza perfetta → infiniti per campione
– Tipici valori: 16 (CD), 24 (DVD), 32 (elaborazione)
– Più bit, maggiore precisione

Esempio semplificato: 3 bit

- Un bit per il segno
- 3 valori positivi e 3 negativi
- Tutti i valori nella striscia blu (larga) vengono quantizzati a (+10)2

– 4 bit (raddoppio accuratezza)

● Tutti i valori nella striscia blu (più stretta) vengono quantizzati a (+101)2

Catena audio: ADC-CoDec-DAC

Digitalizzazione
– Suono rilevato da microfono (che trasduce onda acustica in onda elettrica)

– ADC (Analog-to-Digital Converter)

Convertitore analogico-digitale
Segnale elettrico (analogico) viene campionato e trasformato in segnale digitale
Come lo scanner per le immagini

– Co (Compressor or Encoder)
Eventualmente il suono viene compresso (mp3, ecc.)

Riproduzione
– Cammino inverso

– Dec (Decompressor or Decoder)

Eventualmente suono viene decompresso

– DAC (Digital-to-Analog Converter)

Convertitore digitale-analogico
Segnale campionato ri-trasformato in segnale elettrico

– Alla fine segnale elettrico riprodotto da un altoparlante (diffusore, cuffie)

Trasduzione da onda elettrica a onda sonora

Suono: formati e compressione

Spazio occupato da un suono
Bisogna sapere
– Quanti byte per campione Es: 2,3,4 byte sono valori tipici
– Quale frequenza di campionamento Es.: 8 kHz, oppure 44.1 kHz, oppure 48 kHz
– Quanti canali Es.: 2 canali per una tipica canzone registrata in stereo

● Quindi un file audio occupa

(n. byte per campione) x (n. canali) x (n. campioni)
● E il numero di campioni è dato da
(freq. di campionamento) x (durata in secondi)

● “Qualità CD”: 2 byte per campione, 2 canali

stereo, freq. di campionamento 44.1 kHz
– Quindi un file audio qualità CD occupa 2 x 2 byte x 44100 x durata in secondi

● Definizione: bitrate.
– Bit al secondo, ovvero numero di bit necessari per codificare/trasmettere un secondo di audio

● Qualità CD: bitrate

– 16 bit x 2 canali x 44100 campioni = 1.41 Mbit/s

● Un'ora di musica in qualità CD

– 1.41 Mbit x 60 x 60 = 5076 Mbit = 635 MB
– È proprio la capacità di memoria dei vecchi CD!

Formati e compressione
● Audio di qualità CD occupa molto spazio!
– Formato wave (.wav), non compresso

● Compressione lossless
– FLAC (Free Lossless Audio Codec)
– ALAC (Apple Lossless Audio Codec, usato su iTunes)
– Monkey's Audio (ape).

● Compressione lossy
– Ad es. formato “MPEG-1” layer 3 (.mp3)
– oppure Ogg Vorbis (.ogg) usato da Spotify

Formato mp3
● Inventato dal MPEG (Moving Pictures Experts Group) per video e audio, standardizzato nel 1991
– Formato lossy
● Il grado di compressione può essere regolato dall’utente, che può scegliere
– Frequenza di campionamento, ad es. 44.1 kHz
– Bitrate (in kbit al secondo), ad es. 192 kbit/s
● Alti livelli di compressione
– 10:1 o più contro meno di 2:1 per FLAC

● Codifica percettiva
– Sfrutta i limiti della percezione umana del suono

● Idea principale: mascheramento

– Un suono può essere reso inudibile da un altro suono simultaneo (o quasi) a frequenza vicina

● Allora bit assegnati a diverse zone di frequenza

-Una frequenza mascherata da altre viene rappresentata con pochi bit
-“Rumore di quantizzazione”, che però non si sente (o si sente poco) grazie al mascheramento (errore).

Ha più senso quindi dare informazione alle frequenze che sentiamo meglio

“The mother of mp3”

● Come si valutò la qualità della codifica mp3?
– Test di ascolto con molti soggetti e molti brani
– Confronto tra brani non compressi e compressi con diverse tecniche / livelli di compressione
● “Tom's diner”, di Suzanne Vega
– Brano molto utilizzato nei test del gruppo MPEG
– Voce “a cappella”, quasi monofonica: i difetti introdotti dalla compressione sono più evidenti all'ascolto

AI e Codec naturali
● Le nuove tecniche di AI basate su Reti Neurali hanno permesso lo sviluppo di Codec ancora più efficienti
● Es. “Encodec” di Facebook Research (2022)
– Comprime audio stereo a 48 kHz con bitrate tra i 24 e i 3 kbps
– Quindi rapporto di compressione tra i 96:1 e i 768:1

Problema dei multimedia

● Latenza: tempo impiegato per creazione e trasmissione delle informazioni
– Pagine che non si caricano
– (video)chiamate disturbate
← server sovraccarichi e rete congestionata

● Ampiezza di banda: quantità di informazioni trasmesse x unità di tempo

– Es: 10 MB trasmessi su banda da 5 MB/s ha latenza minima 2
– Maggiore banda, minore latenza

Conclusioni
I bit sono tutto
Cosa significa questa sequenza di bit?
0000 0000 1111 0001 0000 1000 0010 0001
– Domanda mal posta: a seconda del contesto e della codifica può significare molte cose diverse
Ad esempio
– Il numero intero positivo (15796257)10
– Il colore RGB (241, 8, 33) – ultimi 3 byte
– Quattro caratteri di ASCII esteso: NU ñ BS !
– Due campioni audio
– Altro: un'istruzione del processore, un indirizzo IP, ...

● Principio del mezzo universale e indifferente.

– I bit possono rappresentare qualsiasi info discreta
– I bit non hanno alcun significato intrinseco
● “Informazione discreta”
– Composta da insiemi di valori “enumerabili”, che si possono contare (a cui si può attribuire un codice)
Se è “continua” (es. disegno su un foglio, suono da un microfono) va prima discretizzata (pixel,
campioni)
● “I bit sono bit”
– Il loro significato dipende dall'interpretazione
Ad es. in rete si trasmettono bit. Chi li trasmette/riceve li interpreta come un testo, una foto, un mp3, ecc.
Suffisso del file (.txt, .mp3, .jpeg, .exe) aiuta
Lezione 14/05/25
Architettura di un computer
 Architettura riguarda gli elementi hardware, le loro funzioni e connessioni.
Quasi tutti i computer odierni hanno un’architettura simile.

Macchine di John von Neumann

È l’autore del primo documento che descrive una macchina elettronica nella cui memoria vengono registrati
dati e programmi (1945).
L’architettura dei moderni computer è molto simile a questo modello—> sono quindi dette macchine (o
architetture) di von Neumann.
In realtà già prima di allora esistevano molte macchie che adottavano questa architettura, anche altri
documenti—> Turing 1936

Il modello di von Neumann

 1. Unita di calcolo (processore) CPU
- Unita di controllo (dice cosa fare e quando)
- ALU

2. Memoria centrale che immagazzina sia i dati (temporanei) che il programma

3. Memoria di massa (esterna)
4. Meccanismi di input e output

Tutti collegai da un bus dove si scambiano istruzioni e dati

Caratteristiche della memoria

Dobbiamo pensarla come una lista che ha degli indirizzi
  Contiene sia il programma che i dati
 Organizzata in una lunga sequenza di locazioni discrete
 Ogni locazione ha un indirizzo (interi positivi)
-accesso ai dati via indirizzo (come la casella della posta)
 Le locazioni contengono un valore
 Le locazioni hanno una capacità finita

“Stored-program” vs fixed
Le prime macchine avevano programmi fissi, ad es. il calcolatore tascabile faceva solo quei conti.
Riprogrammare significava ridisegnare la macchina.
ENIAC: tre settimane per eseguire un programma diverso

Unità centrale di elaborazione

CPU—> Central Processing Unit
È il cuore del computer, spesso definita “processore”.
- Individua ed esegue le istruzioni del programma
- Effettua elaborazioni aritmetiche e logiche con la sua unità aritmetico logica
- Reperisce dati dalla memoria e altri dispositivi periferici e ve li rispedisce dopo averli elaborati
- È costituita da uno o più chip (miliardi di transistor inteconnessi)

Dal punto di vista logico, tre parti principali:

- Unità aritmetico-logica (ALU): operazioni aritmetiche e logiche
- Unità di controllo: governa il funzionamento
- Registri: spazi di memoria ad accesso molto veloce per dati e istruzioni da eseguire

Unità di controllo e clock

Unità di controllo:
 - Esegue le istruzioni dei programmi
- Coordina le attività del processore
- Controlla la comunicazione tra CPU e memoria

Svolge la sua attività in modo ciclico

Scandito dall’orologio di sistema (clock, un oscillatore elettronico)
- La frequenza del clock determina la velocità operativa della CPU
(CPU di un telefono Samsung midrange: 2.2GHz, 2.2 miliardi di cicli al secondo)

Il contatore di programma
Program Counter (PC):
- Un registro speciale che dice quale prossima istruzione eseguire a seconda del flusso di controllo
dell’algoritmo originario
Ogni istruzione ha un indirizzo:
- Indirizzo della locazione di memoria in cui si è scritta
- Nella fase di “fetch” viene letta in memoria l’istruzione il cui indirizzo è contenuto nel PC
- Poi il PC si incrementa (l’incremento dipende dalla lunghezza delle istruzioni)

CPU: ciclo di funzionamento

La CPU esegue le istruzioni di tutti i programmi in esecuzione sul computer
- Una istruzione alla volta, secondo una scansione governata dall’unita di controllo e dal clock
Ciclo fetch-decide-execute (carica-decodifica-esegui)

 Accesso (fetch): istruzione presa dalla memoria e memorizzata in un registro

 Decodifica (decode): istruzione letta e compresa
 Esecuzione (execute): istruzione eseguita, eventualmente utilizzando dati e restituendo risultato (es.
somma di due addendi)

Istruzioni macchina
I programmi eseguiti dalla CPU sono composti da istruzioni macchina
- Istruzioni elementari, che in sequenza fanno svolgere al computer compiti diversi e compressi
Es. somma de numeri
Formato:
- Es. istruzione a 32 bit, diverse porzioni di bit hanno diversi significati
 o Non è la somma di 4000 2000 e 2080
o Somma i numeri nelle locazioni 2080 e 2000
o Scrive il risultato nella locazione di memoria 4000
o Posso usare le stesse locazioni per sommare numeri arbitrari

Bisogna vedere che numeri ci sono all’interno degli indirizzi (slide 24)

Ogni tipo di processore è in grado di eseguire un numero limitato di istruzioni, che costituiscono un certo
linguaggio macchina.
Famiglie di processori: Intel, AMD, Nvidia…
Circa 100 istruzioni primitive
- Di cui 20 distinte (stesse operazioni su tipi diversi, es. somma su bit, su byte, su numeri con
virgola…)
Linguaggio assembly—> linguaggio intermedio, ultimo passo prima del linguaggio binario
In queste slide NON usiamo il vero linguaggio macchina, ma quello assembly
La macchina capisce solo i bit, laddove assembly permette di usare nomi al posto del loro binario.
Assembly come rappresentazione intermedia del binario compreso da CPU
Vedo slide

Memoria primaria e secondaria

Caratteristiche della memoria (già affrontate)

Due tipi di memoria: primaria e secondaria

Entrambe immagazzinano dati e istruzioni, ma con ruoli diversi. La memoria è suddivisa in celle, ognuna
delle quali ha un indirizzo.
Ogni cella contiene un numero predefinito di bit (una volt erano 8, 1 byte)

Istruzioni e dati occupano spesso piu di 1 byte

- Si usano gruppi di celle contigue (parole, word) per rappresentare un dato o un’istruzione
- L’indirizzo di una parola è l’indirizzo del suo primo byte (es. parole da 4 byte: gli indirizzi delle
parole si incrementano di 4 alla volta
- Ora: processori a 64 bit e quindi parole da 8 byte
Le operazioni che si eseguono sulla memoria (sia rimarrà che secondaria) sono operazioni di lettura e
scrittura

Memoria primaria o centrale

È veloce (tempi di lettura/scrittura di circa 10-40 nanosecondi), ma è piu costosa—x 70-120 euro per 16GB
Due tipi principali di memoria primaria
- ROM (memoria di sola lettura)
- RAM (memoria ad accesso casuale), accesso diretto non in sequenza

Sono costituite da chip, come la CPU

- In questo caso i transistor servono da bit di memoria

Memoria RAM
Consente sia lettura che scrittura dei dati e programmi in essa contenuti
Contiene dati in fase di modifica e programmi che devono essere disponibili alla CPU
È una memoria volatile, perde i dati quando si spegne il computer
Accesso casuale significa che il tempo per accedere a una cella non dipende dalla sua posizione (indirizzo)
 Vero anche per la ROM, ma solo in lettura

Memoria ROM
● È una memoria non volatile: i dati contenuti non vengono persi quando viene rimossa l'alimentazione.
● È una memoria di sola lettura: i dati non possono essere modificati durante il funzionamento del sistema.
● È utilizzata per memorizzare informazioni permanenti, come il codice del BIOS (Basic Input/Output
System) o altre istruzioni di avvio del sistema operativo.
● Il contenuto della ROM viene programmato dal produttore durante la fase di produzione.

Memoria secondaria (o di massa)

● Meno costosa ($110–170 per 1TB) della memoria primaria ma molto più lenta (tempi di accesso in
lettura/scrittura):
● È una memoria non volatile
– Programmi e dati risiedono in memoria secondaria, vengono caricati in RAM quando necessario alla CPU,
per poi tornarvi aggiornati se e quando necessario
● Tipiche memorie secondarie:
– Disco rigido (hard-drive), o disco fisso
– Memoria a stato solido (flash)
– Memorie ottiche (DVD, Bluray, ecc.)

Memoria secondaria: disco fisso

● Primi hard-disk: “IBM 350 RAMAC”, 1956
– Capacità: 3.75Mbyte
– Dimensioni: 1.9m3
– Peso: 910Kg
● Attualmente
– Capacità: ~10Tbyte
– Dimensioni: ~50cm3
– Peso: ~100g

Memoria secondaria: flash

● Memoria “a stato solido” (solid state memory, SSD)
– In rapidissima diffusione
– Non volatile e riscrivibile
– Senza parti mobili, resiste a sollecitazioni e urti
– Leggera e piccola, indicata per la trasportabilità (fotocamere digitali, cellulari, ecc.)
– Sostituisce hard disk di laptop
– Costi in costante diminuzione ($100 x 1TB)
– Minore durabilità

Altre memorie secondarie

● A tecnologia ottica
– CD-ROM, come un CD audio; capacità ~700 Mbyte; sola lettura
– CD-R (Recordable), può essere scritto dall’utente (una volta; più volte se CD-RW)
– DVD, (Digital Versatile Disk, capacità 4.7 Gbyte)
– Blue-Ray (capacità 50 Gbyte)
● Tape (nastri per dati)
– Elevata capacità, economici ma lenti
– Accesso sequenziale ai dati (bisogna avvolgere o svolgere il nastro per raggiungere un dato)
Recupero lezione 15/05/25

Lezione 21/05/25-prof Mattia Monga

Mimetismo e analisi dei dati nell’infosfera (universo informatico)

L’universo informatico
Si ragiona su come l’informazione può essere rappresentata/modellata tramite dati “concreti”.
Si riflette su come i dati possono elaborati/informati.
Si predispone di un dispositivo automatico capace di elaborare automaticamente la trasformazione,
producendo nuovi dati.
Quando l’informazione non è esplicitamente rappresentata, può essere impossibile compiere una determinata
elaborazione.
Se l’informazione non esiste, non possiamo crearla, si elabora quella che si ha.

Elezioni regionali 2022 in Lombardia—> esprimere due preferenze di genere diverso, ma il sesso non è
indicato nei manifesti elettorali.
Nel caso delle elezioni desidereremmo un’elaborazione deterministica, ma non è sempre così.

 Un bit è l’informazione necessaria per decidere tra due alternative possibili.

In molti casi vengono raccolti dati superflui, magari anche conservati a lungo.
Raccogliere solo dati strettamente necessari.

GDPR non tutela totalmente.

E i dati raccolti
È possibile renderli anonimi? Che cosa vuol dire?
La tecnica classica è basata sul concetto di k-anonimity, introdotta negli anni 90.
Soppressioni e generalizzazioni in modo che per un certo insieme di proprietà ci siano k record uguali. Per
ogni combinazione di (età, sesso, residenza) ci sono 2 record uguali (quasi-identificatore).
Cancellare le informazioni non significa garantire anonimato.
Spesso è possibile una re-identificazione dei soggetti coinvolti!

Attualmente le tecniche più promettenti sono quelle di privacy differenziale, che pero vanno progettate
adeguatamente per ogni caso.

RECUPERO LEZIONE DEL 22 MAGGIO

Lezione 28/05/2025
Internet, una breve storia
Storia

p. 14
p. 12