Appunti ed esercizi Fondamenti di informatica

MACCHINA DI VON NEUMANN

UNITÀ DI INGRESSO (INPUT)

PROGRAMMI E DATI

BUS

UNITÀ DI USCITA (OUTPUT)

RISULTATI

MEMORIA CENTRALE

CELLA

ISTRUZIONE

LDA 104

DATI

INDIRIZZO

• RAM (Random Access Memory)
• ROM (Read Only Memory)
• BUFFER

MBR (Memory Buffer Register)

MAR (Memory Address Register)

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 o 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)

I REGISTRI

Sono gli elementi di memoria della CPU (celle nelle quali si può leggere/scrivere/memorizzare).

• REGISTRI DATI: dati da elaborare
• REGISTRO ISTRUZIONI (IR): istruzione da eseguire
• PROGRAM COUNTER (PC): indirizzo in memoria della prossima istruzione da eseguire
• REGISTRI FLAG: segnalano anomalie ed errori
• MAR: indirizzo memoria durante l'esecuzione
• MBR: dati prelevati da memorie o da trasferire in memoria

INDIRIZZO del dato da trasferire

DATO da trasferire da/verso la memoria

TRASFERISCI IL DATO CONTENUTO NELLA CELLA ALL'INDIRIZZO 123 NEL REGISTRO 2

1. BUS CONTROLLI read
2. MAR 123
3. lettura
4. MBR 45
5. (MBR) → R2
6. R2 45

TRASFERISCI 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à centr.

PROGRAM COUNTER (PC) = contiene l'indirizzo della cella di memoria contenente la prossima istruzione da eseguire

ISTRUCTION REGISTER (IR) = contiene l'istruzione da eseguire

Ciclo Macchina

FASE DI FETCH vengono letti i campi che costituiscono l'istruz:

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

(PC)+1 -> PC

FASE DI DECODE l'istruzione viene decodificata

FASE DI EXECUTE l'istruzione viene eseguita

ESERCIZI CODIFICA INTERI

Base β → Base 10 Calcolo del polinomio Base 10 → Base β Parte intera = divisione Parte fraz. = moltiplicazione

Esempio: 58,07₁₀ → 111010, 000100_{1 2}

MOLTIPLICARE "L'ARCOBALENO AL CONTRARIO"

LE TECNICHE DI CODIFICA:

• VALORE ASSOLUTO
• COMPLEMENTO A 2/16/8
• MODULO E SEGNO
• ECCESSO 127

VALORE ASSOLUTO

se x = 2ⁿ positivo → valore assoluto se x = 2ⁿ negativo → b^m − | x | = v x = valore assoluto (+) m = cifra v = numero rappresentato in complemento (-)

q_Rc−127 → numero

Esercizi Virgola Mobile

A = S O_M x B^E

• Da Decimale a Binario
• 1) Conversione in binario parte intera e decimale
• 2) Normalizzazione
• 3) Rappresentazione in virgola mobile
• (E se va scritto in eccesso 127 bisogna base 10 -> eccesso 127 (sommo))
• Da Binario a Decimale
• 1) Guardo il segno
• 2) Conversione in decimale dell’esponente
• (E se è scritto in eccesso 127 bisogna eccesso 127 -> base 10 (sottraggo))
• 3) Normalizzazione della mantissa
• 4) Conversione in decimale della mantissa

Operazioni (in virgola mobile):

0 02 6502 0000000000 +0 04 2347 0000000000 =

No→0 04 006502 0000000000 +0 04 2347 0000000000 =0 04 231202 0000000000 =

gli esponenti devono essere uguali!per farlo devo allineare le mantisse, quindi sposto verso dx del numero di cifre pari alla 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 (= 4¹)

Attenzione a:- esponenti- bit nascosto

Esercizi Sistemi di Codifica

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

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

000111 ] H = 11011100000101001011111 ] H = 21000100110110001 ] H = 3

H = 2 _{Ha capacità di rivelazione d'errore}

H > 2 _{Ha capacità di rivelazione + correzione d'errore}

P P P0 0 00 0 10 1 01 0 0
• 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
xx 01 10

AND (*)

• Restituisce 1 (vero) solo se entrambi gli operatori sono veri (1·1=1)
xyx*y 000 010 100 111

OR (+)

• Restituisce 1 (vero) se almeno uno dei due operatori è 1 (vero)
xyx+y 000 011 101 111

NAND (/) = negazione dell'AND

NOR (↓) = negazione dell'OR

EXOR o "sommatore di modulo 2" (⊕)

• Restituisce 1 se e solo se il numero degli operatori uguali a 1 è dispari, altrimenti restituisce 0
xyx⊕y 000 011 101 110

Teorema di Dualità

Ogni identità resta valida se si scambiano tra loro gli elementi 0,1 e gli operatori AND, OR

x+1 = 1

x·0 = 0

De Morgan

x·y = 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

^2bit = 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 byt = bit

v = _S/^t → S la chiamo M → v = _M/^t (t = _M/^v)

ESERCIZI

CODIFICA

SEGNALI

• 3 101
• 2 100011
• 1 001
• 0 000

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/²ⁿ)

Q = Errore di quantizzazione

Q = _P/² = _R/²ⁿ⁺¹

F_c = frequenza di campionamento = 2 × B

F_c = _campioni/^sec

(kHz = 10³ Hz)

t = 1/F_c

v = _bit/^sec

(kbit = 2ⁿ bit)

M = v · t = _bit/^sec · sec = (n · F_c) · t =

= _bit/^campione · _campione/^sec · sec = bit

NUMERO DI campioni × _{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 lotti (Batch)
• Multiprogrammazione
• Interattivi (Time-Sharing)
• Real-Time
• Per macchine multiprocessori (Sistemi concorrenti)

Esempio

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

Abbiamo assegnato la priorità al P1

"L'unità di tempo a testa"

Il processo ha terminato le operazioni di I/O

Running → processo in esecuzione

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: ABCILEGFHO

1. Esamina la radice
2. Visita il 1^o sottoalbero (si parte da sx) in ordine anticipato
3. Visita il n^o sottoalbero in ordine anticipato

VISITA IN ORDINE DIFFERITO: LIGEFHCDBA

1. Visita il 1^o sottoalbero (si parte da sx) in ordine differito
2. Visita il n^o sottoalbero in ordine differito
3. Esamina la radice

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