Appunti ed esercizi Fondamenti di informatica

I'm sorry, I can't transcribe the text as there is no visible content in the image you provided. If you have another image with text, please share it, and I'll be happy to assist you!

I'm sorry, but I can't extract text from the provided image.

Macchina di Von Neumann

• Unità di ingresso (input)
• Programmi e dati
• Memoria
• Bus
• Unità di controllo
• Registri
• ALU
• CPU
• Unità centrale
• Unità di uscita (output)
• Risultati

Memoria centrale

000 cella istruzione LDA 104... 2 3 dati 127 indirizzo.

RAM (Random Access Memory): accesso diretto alla memoria sulla quale è possibile anche scrivere. È usata per contenere dati e programmi in esecuzione quindi è anche detta "memoria utile". È volatile perché se si spegne il computer viene perso tutto.

ROM (Read Only Memory): il suo contenuto può essere letto ma mai modificato/riscritto. Contiene le info fondamentali come le istruzioni di avvio del sistema.

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.

Si trovano registri nella memoria?

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.

Essa 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 istruzione (IR): istruzione da eseguire
• Program Counter (PC): indirizzo in memoria della prossima istruzione da eseguire
• Registri flag: eventuali anomalie emerse durante l'esecuzione
• MAR: indirizzo a cui puntare in memoria durante il trasferimento dati
• MBR: dati letti o da trasferire

Indirizzo del dato da trasferire.

Dato da trasferire da/verso la memoria.

Trasferimenti dati

Trasferisci il dato contenuto nella cella all'indirizzo 123 nel registro 2.

• Bus controlli read
• MAR 123
• Lettura
• MBR 45
• (MBR) → R2
• R2 45

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

• (R5) → MBR
• MBR 32
• Bus controlli write
• MAR 126
• 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.

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

Ciclo macchina

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

• (PL) → MAR
• ((MAR)) → MBR
• (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 frazia = moltiplicazione.

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

Le tecniche di codifica

• Valore assoluto
• Complemento a 2/16/8
• Modulo e segno
• Eccesso 127

Modulo e segno e complemento a 2

Lo zero: 00000...01︹ 00000...01︹ 00000...0.

Valore max: 2^n-1 - 1; 2^n-1 - 1.

Valore min: -2^n-1 + 1; -2^n-1.

Bit di segno: 0 positivi, 1 negativi; 0 positivi, 1 negativi.

Valore assoluto: solo positivi.

Compl a 2: 0 pos, 1 neg.

Compl a 8: 0-3 pos, 4-7 neg.

Compl a 16: 0-7 pos, 8-F neg.

H.S.: 0 pos, 1 neg.

Se x = 2^n-1 positivo → valore assoluto.

Se x = 2ⁿ negativo → b^m = |x| = vm ≝ cifre.

x: valore assoluto (+).

y: numero rappresentato in complemento (-).

Compl A 100: 0-49 pos, 50-99 neg.

Eccesso 127: 0 neg, 1 pos.

qElc - 127 = 1.

Esercizi virgola mobile

A = S . O . M x b^E.

IEEE 754.

Da decimale a binario

• Conversione in binario parte intera e decimale
• Normalizzazione
• Rappresentazione in virgola mobile
• (E se va scritto in eccesso 127 bisogna base 10 → eccesso 127 (sommo)

Da binario a decimale

• Guardo il segno
• 0 → positivo
• 1 → negativo
• Conversione in decimale dell’esponente
• (E se è scritto in eccesso 127 bisogna eccesso 127 → base 10 (sottraggo)
• Normalizzazione della mantissa
• Conversione in decimale della mantissa

Operazioni in virgola mobile

Operazioni (in virgola mobile) 0 02 6502000000000 + 0 04 2347000000000 = → 0 04 0065020000000 + 0 04 0234700000000 = 0 04 2312020000000 = 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.

Esercizi sistemi di codifica

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

C ≤ 2ⁿ.

n = ⌈log₂(C)⌉ = M.

8 ≤ M (9).

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.

000 0000 1000 1001 111 ] H=1 1010 1011 1001 ] H=3 101 0101 110 0111 ] H=2 1111.

H ≥ 2 ha capacità di rivelazione d'errore.

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

0 0 0 P P P 0 1 0 1 1 0 1 1 1 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.

0 0 0 0.

0 1 0 1.

No numeri negativi!

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

8 bit → 256 simboli.

Esercizi algebra di Boole

Ø falso.

1 vero.

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

Restituisce il valore opposto.

XX̄ 0110.

AND (*).

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

XY X*Y 000 010 100 111.

OR (+).

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

XY X+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.

XY X⊕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̄·Ȳ = X̄ + Ȳ.

X̄+Ȳ = X̄ · Ȳ.

E altre proprietà.

Esercizi codifica immagini

Immagine suddivisa in pixel.

• 1 pixel = 8 bit
• 3 pixel = 24 bit (8×3)
• 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 × 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 × 800
• Profondità di colore = 24 bit

Memoria senza palette = 400 × 800 × 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 × 24 bit) + (400 × 800 × 4 bit).

kbit = 2¹⁰ bit.

byte = bit.

v = s/t → s la chiamo M → v = M/t ( t = M/v ).

Esercizi codifica segnali

n ai campioni 3 2 1 0.

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.

Q = errore di quantizzazione.

Q = ^P/₂ = ^R/_2ⁿ⁺¹.

Fc = frequenza di campionamento = 2 x B.

Fc = ^campioni/_sec (kHz = 10³ Hz).

t = ¹/_Fc.

v = ^bit/_sec (kbit = 2ⁿ bit).

M = v . t = ^bit/_sec = (n . Fc) . 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.

Classificazione di sistemi operativi

• Dedicati
• A lotti (batch)
• Multiprogrammazione
• Interattivi (time-sharing)
• Real-time
• Per macchine multiprocessori (sistemi concorrenti)

Esempio:

Running Ready Blocked.

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

Running Ready Blocked.

Abbiamo assegnato la priorità al P₁.

Running Ready Blocked.

Il processo ha terminato le operazioni di I/O.

Running → processo in esecuzione.

Ready → il processo fa operazioni di I/O.

Esercizi strutture informative

8-alberi

Radice livello 1 livello 2 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.

• Esamina la radice
• Visita il 1º sottoalbero (si parte da sx) in ordine anticipato
• Visita il nº sottoalbero in ordine anticipato

Visita in ordine differito

LIGEFHCBDA.

• Visita il 1º sottoalbero (si parte da sx) in ordine differito
• Visita il nº sottoalbero in ordine differito
• Esamina la radice

← Albero binario.

Figlio sx = primo figlio (es C).

Figlio dx = fratello (es D).

Visita in ordine simmetrico

LIGEFHCDBA.

• Visita il sottoalbero sx in ordine simmetrico
• Esamina la radice
• Visita il sottoalbero dx in ordine simmetrico

Anticipato albero ordinato = anticipato albero binario.

Differito albero ordinato = simmetrico albero binario.