Appunti ed esercizi Fondamenti di informatica

Macchina di Von Neumann

Unità di ingresso (input).

Memoria.

Bus.

Unità di uscita (output).

Programmi e dati.

Risultati.

Unità di controllo.

Registri.

ALU.

CPU.

Unità centrale.

Memoria centrale.

Cella.

Istruzione.

Dati.

Indirizzo.

RAM e ROM

RAM (Random Access Memory): accesso diretto alla memoria, sulla quale è possibile anche scrivere.

È usata per contenere dati e programmi in esecuzione quindi si anche detta "memoria attiva".

È volatile perché se si spegne il computer viene perso tutto.

ROM (Read Only Memory): il suo contenuto può essere letto ma mai modificato/cancellato.

Contiene le info fondamentali come le istruzioni di avvio del sistema.

Buffer, MBR e MAR

Buffer.

MBR (Memory Buffer Register).

MAR (Memory Address Register).

È una zona di transito della memoria utilizzata per compensare differenze di velocità nel trasferimento di dati o nell'esecuzione delle operazioni.

(La RAM è più veloce della CPU).

MBR = dato da trasferire da/verso la memoria.

MAR = indirizzo del dato da trasferire.

Qualunque dato o programma da eseguire deve essere trasferito in memoria centrale (RAM) per poter essere utilizzato dalla CPU.

CPU

Il compito della CPU è quello di eseguire le istruzioni di un programma.

Elabora le informazioni il programma può trovarsi nella RAM, nella ROM, o in altri dispositivi.

La CPU lo preleva e lo esegue.

Durante l'esecuzione del programma la CPU legge e scrive dati nella RAM.

Il risultato dell'esecuzione dipende:

• Dall'istruzione.
• Dal dato.
• Dallo stato interno della CPU.

La ALU esegue le operazioni di calcolo aritmetiche e logiche.

L'unità di controllo stabilisce quali operazioni debbano essere eseguite.

Fornisce alla CPU dei segnali elettrici che attivano o disattivano le sue componenti.

Questi segnali vengono forniti in sincrono con un orologio interno alla macchina chiamato clock.

Ad ogni scatto del clock viene inviato un segnale e la CPU cambia il suo stato interno.

In questo modo ad ogni circuito che compone la CPU viene indotto se attivarsi o meno.

La frequenza del clock deve garantire che il ciclo di clock sia sufficientemente lungo da consentire a tutti i circuiti (anche il più lento) di completare le proprie operazioni.

Questa determina a che velocità la CPU esegue le istruzioni.

Set di istruzioni di base

• Istruzioni aritmetico/logiche (ALU).
• Istruzioni di accesso alla memoria (trasferim. dati).
• Memoria -> memoria.
• Memoria -> registri.
• Registri -> memoria.
• Istruzioni di controllo (esempio: salti).

Registri della CPU

I registri sono gli elementi di memoria della CPU (celle nelle quali si può leggere/scrivere/muovere).

Registri dati: dati da elaborare.

Registro istruzione (IR): istruzione da eseguire.

Program Counter (PC): indirizzo in memoria della prossima istruzione da eseguire.

Registri flag: eventuali anomalie durante l'esecuzione.

MBR: dato da trasferire da/verso la memoria.

MAR: indirizzo del dato da trasferire.

Bus e trasferimenti

CPU.

Address bus.

ROM.

MAR.

MBR.

RAM.

Data bus.

Control bus.

Indirizzo del dato da trasferire.

Dato da trasferire nella memoria da/verso.

Trasferisci il dato contenuto nella cella su indirizzo 123 nel registro 2:

1. Bus controlli read.
2. MAR 123.
3. Lettura.
4. MBR 45.
5. (MBR) -> R2.
6. R2 45.

Trasferisca il dato che si trova nel registro 5 nella cella di indirizzo 126:

1. (R5) -> MBR.
2. MBR 32.
3. Bus controlli write.
4. MAR 126.
5. Scrittura.

ACC = accumulatore dei risultati della ALU (sono registri).

Registro di stato (flag) = contiene informazioni che determinano lo stato dell'unità centrale.

Program Counter (PC) = contiene l'indirizzo della cella di memoria contenente le prossima istruzione da eseguire.

Instruction Register (IR) = contiene l'istruzione da eseguire.

Ciclo macchina

CPU.

Memoria.

Program Counter.

Instruction Register.

Bus.

Address Cells.

A0.

A1.

A2.

A3.

156C.

166D.

Questa CPU quando si esegue una istruzione.

Ciclo macchina.

Fase di fetch: vengono letti i campi che costituiscono l'istruzione.

1. (PC) -> MAR.
2. ((MAR)) -> MBR.
3. (PC) + 1 -> PC.
4. (MBR) -> IR.

Fase di decode: l'istruzione viene decodificata.

Fase di execute: l'istruzione viene eseguita.

Esercizi codifica interi

Base B → base 10.

Calcolo del polinomio.

Base 10 → base B.

Parte intera = divisione.

Parte frazionaria = moltiplicazione.

Ricordar "l'arcobaleno al contrario".

Divido 1 moltiplico.

Esempio: 58,07₁₀ → 111010,000100011₂.

Tecniche di codifica

• Valore assoluto.
• Complemento a 2/16/8.
• Modulo e segno.
• Eccesso 127.
• Lo zero.
• Modulo e segno.
• Complemento a 2.
• Valore max.
• Valore min.
• Bit di segno.
• Solo positivi.
• Comp a 2.
• Comp a 8.
• Comp a 16.
• M.S.
• Eccesso 127.
• Comp a 10.

Se x è positivo → valore assoluto.

Se x è negativo → b^m - |x| = v.

m = cifre.

x = valore assoluto (+).

v = numero rapportato in complemento (-).

g/c - 127 = numero.

0 POS.

4-9 NEG.

0 positivi.

1 negativi.

0 positivi.

1 negativi.

0 POS.

1 NEG.

Esercizi virgola mobile

A = S M x B^E.

S E M.

Sempre 1 bit.

Complemento alla base.

IEEE 754.

S E M.

Sempre 1 bit.

Eccesso 127.

1 b1 b2 b3 ...

Da decimale -> a binario.

1. Conversione in binario parte intera e decimale.
2. Normalizzazione.
3. Rappresentazione in virgola mobile.

E se va sotto in eccesso 127 bisogna x + 127 = 0.

Base 10 -> eccesso 127 (sommo).

Da binario -> a decimale.

0 positivo.

1 negativo.

1. Guardo il segno.
2. Conversione in decimale dell'esponente.

E se è scritto in eccesso 127 bisogna x - 127 = 0.

Eccesso 127 -> base 10 (sottraggo).

1. Normalizzazione della mantissa.
2. Conversione in decimale della mantissa.

Operazioni in virgola mobile

Operazioni (in virgola mobile):

0 02 650200000000 + 0 04 234700000000 = NO.

0 04 006502000000 + 0 04 234700000000 = 0 04 231202000000.

Attenzione a:

• Esponenti.
• Bit nascosto.

Gli esponenti devono essere uguali!

Per farlo devo allineare le mantisse, quindi sposto verso dx del numero di cifre per la differenza tra gli esponenti e più piccolo viene reso uguale all'e più grande.

• Vengono sommate/sottratte solo le mantisse.
• Se sono in IEEE 754, durante lo shift verso destra devo "far ricomparire" il bit nascosto (=1)!!

Esercizi sistemi di codifica (3)

C è la cardinalità (= numero di elementi).

C ≤ 2ⁿ.

n ≥ [log₂(C)] = M.

Numero di bit usato effettivamente nel codice.

Minimo numero di bit necessario.

n = M → H = 1.

Il codice è non ridondante.

n > M → H ≥ 1.

Il codice è ridondante.

Distanza di Hamming: H è la distanza di Hamming (= numero di bit diversi che compaiono in posizioni corrispondenti di due parole della stessa lunghezza).

H di un codice è il minimo numero di bit di cui differiscono due parole qualsiasi del codice.

000111011101110.

H = 1.

00001010010111001111.

H = 2.

H = 2 ha capacità di rilevazione d'errore.

1000100110110001.

H = 3.

H > 2 ha capacità di rilevazione + correzione d'errore.

Codice di parità: quando aggiungo 1 bit al codice non ridondante.

Pari → numero di 1 pari.

Dispari → numero di 1 dispari.

Codice a parità dispari.

Se aggiungo questo bit, codice a parità pari.

Codice BCD: ogni cifra decimale viene codificata con 4 bit e con il suo corrispondente valore in binario.

(245 → 0010 0100 0101) NO numeri negativi!

Codice ASCII: 7 bit → 128 simboli + 1 bit di parità (H=2).

8 bit → 256 simboli.

Esercizi algebra di Boole

0 falso.

1 vero.

NOT (- solitamente sopra ma può stare anche sotto -).

Restituisce il valore opposto.

AND (*).

Restituisce 1 (vero) solo se entrambi gli operatori sono veri (1.1 = 1).

OR (+).

Restituisce 1 (vero) se almeno uno dei due operatori è 1 (vero).

NAND (/) = negazione dell'AND.

NOR (v) = negazione dell'OR.

XOR o "sommatore di modulo 2" (⊕).

Restituisce 1 se e solo se il numero degli operatori uguali a 1 è dispari, altrimenti restituisce 0.

Teorema di dualità: ogni identità resta valida se si scambiano tra loro gli elementi 0,1 e gli operatori AND, OR.

De Morgan:

xy = x + y.

x+y = x y.

E altre proprietà.

Esercizi codifica immagini

Immagine suddivisa in pixel codificati in bit.

1 pixel = 8 bit.

3 pixel = 24 bit (8x3).

Numero di pixel per unità di lunghezza = risoluzione.

Numero di bit usati per codificare ogni pixel = profondità di colore.

2^BIT = numero di colori.

Memoria = numero totale di bit necessari per codificare l'immagine.

Risoluzione x profondità di colore.

Palette = è una lista di colori scelti tra tutti quelli disponibili.

Ogni colore della tavolozza è associato ad un indice che identifica il colore nella tavolozza stessa.

Esempio: risoluzione = 400 x 800.

Profondità di colore = 24 bit.

Memoria senza palette = 400 x 800 x 24 bit.

Palette a 16 colori.

16 colori = 2⁴ colori -> 4 bit usati per codificare ciascun pixel.

Profondità di colore = 24 bit non sono più i bit necessari a codificare ciascun pixel, ma i bit necessari ai colori nella palette!

Quindi:

Memoria con palette = (palette) + (immagine) == (16 x 24 bit) + (400 x 800 x 4 bit).

kbit = 2¹⁰ bit.

byte = bit / 8.

v = s / t -> s la chiamo M -> v = M / t (t = M / v).

Esercizi codifica segnali

n di campioni.

5 101.

4 100.

3 011.

2 101.

1 010.

0 000.

Banda.

tempo.

R.

R = range dei valori.

P = precisione con cui rappresentare ciascun valore (= ampiezza di ogni livello).

M = numero di livelli.

M = R / P.

n = bit/campione.

n = log₂(R/P).

P = R / 2ⁿ.

Q = errore di quantizzazione.

Q = P / 2 = R / 2ⁿ⁺¹.

F_c = frequenza di campionamento = 2 x B.

F_c = campioni/sec.

t = 1 / F_c.

u = bit/sec.

M = u . t = bit/sec . sec = (n . F_c) . t = bit/campione . campione/sec . sec = bit.

Numero di campioni x numero di bit/campione = bit.

Esercizi sistemi operativi

"Interfaccia macchina - utente" è l'insieme di programmi che rendono facilmente disponibile all'utente le potenzialità offerte dalla macchina (hardware).

Nucleo (kernel).

Software di base.

Sistema operativo.

Classificazione di sistemi operativi.

• Dedicati a luti (batch).
• Multiprogrammazione.
• Interattivi (time-sharing).
• Real-time.
• Per macchine multiprocessori (sistemi concorrenti).

Esempio:

Dedicati.

Multiprogrammato.

Time-sharing.

"L'esecuzione occupa la CPU finché non finisce poi tocca all'altro".

"1 unità di tempo a testa".

Running → processo in esecuzione.

Ready.

Blocked → il processo fa operazioni di I/O.

Esercizi strutture informative

8-alberi.

Radice.

Livello 1.

Livello 2.

Sottoalbero.

Livello 3.

Livello 4.

Livello 5.

Grado di un nodo = numero di sottoalberi del nodo stesso.

(Grado di A 2).

(Grado di D 0).

Visita in ordine anticipato

Visita in ordine anticipato: ABCILEFGHD.

1. Esamina la radice.
2. Visita il 1° sottoalbero (si parte da SX) in ordine anticipato.
3. Visita il 1° sottoalbero in ordine anticipato.

Visita in ordine differito

Visita in ordine differito: LIGEFHCBDA.

1. Visita il 1° sottoalbero (si parte da SX) in ordine differito.
2. Visita il 1° sottoalbero in ordine differito.
3. Esamina la radice.

Albero binario

Albero binario.

Figlio SX = primo figlio (es C).

Figlio DX = fratello (es D).

Visita in ordine simmetrico: LIGEFHCBDA.

1. Visita il sottoalbero SX in ordine simmetrico.
2. Esamina la radice.
3. Visita il sottoalbero DX in ordine simmetrico.

Anticipato albero ordinato = anticipato albero binario.

Differito albero ordinato = simmetrico albero binario.