Appunti di teoria per Informatica (domande prima metà)

Introduzione agli algoritmi e linguaggi di programmazione

Algoritmo

Un algoritmo è una descrizione precisa di una finita sequenza di azioni che devono essere eseguite per giungere alla soluzione di un problema.

Traduzione di un programma

• File sorgente ➞ compilatore
• File oggetto ➞ linker ← librerie
• File eseguibile (exe)
• Ev. debugger: ambiente di verifica

Tipi di linguaggi

• Ad alto livello: molto astratti, indipendenti dall'hardware: C, Java, Pascal...
• A basso livello: anche detti assembler, poco astratti e dipendenti dall'hardware da programmare.

Elementi del linguaggio

Keyword: identificano le istruzioni e sono riservate al traduttore.

Dati: insieme di bit memorizzati in memoria centrale individuati da:

• Nome (identificatore)
• Interpretazione (tipo) ➞ legata allo spazio occupato
• Modalità di accesso (costante o variabile):
  • Solo lettura
  • Sovrascrivibile

Elaboratore

Costituito da 4 unità fondamentali:

1. Unità di input
2. Unità di memoria (centrale: RAM, di massa: dischi)
3. Unità di elaborazione
4. Unità di output

RAM

Ram: volatile, ad accesso casuale a velocità costante. Non è un periferico.

Microprocessore

Il microprocessore è il chip che realizza le funzioni della CPU. Ha a disposizione una "memoria cache" di bassa capacità ma alte prestazioni.

CPU

La CPU è l'unità centrale di elaborazione suddivisa in:

1. ALU: Unità logico-aritmetica, esegue le operazioni di calcolo.
2. Unità di controllo: dirige le operazioni.
3. Registro, elemento di memoria.
4. Unità di decodifica istruzioni: fornisce comandi comprensibili.
5. Unità di gestione indirizzi: gestisce il movimento di dati non-ALU.
6. Unità di gestione BUS: gestisce i BUS.

Bus

Il Bus è il "sistema circolatorio del PC". È caratterizzato da:

• Capacità di trasporto di un solo dato per volta;
• Frequenza: numero di dati trasportati al secondo;
• Ampiezza: numero di bit di cui è costituito un singolo dato;
• Se mal dimensionato diventa un collo di bottiglia;
• È diviso in 3 sotto bus dedicati a:
  • Bus dati - DBus → Indica la dimensione di una cella;
  • Bus indirizzi - ABus → Determina il max n. di celle indirizzabili;
  • Bus controllo - CBus

La massima memoria interna fisicamente presente è determinabile:
^{max mem = 2ABus x 1DBus bit
es: ABus = 20bit - DBus = 16bit
max mem = (220 x 16) bit = 2MB}
(Tutti i termini in bit, il "convenio tecnologico in byte")

Periferiche

Le periferiche vengono comunicate attraverso controller che codificano i dati e controllano le operazioni.

Registri

I registri sono elementi di memoria locale utilizzati per conservare temporaneamente dei dati.

Unità operativa

L'unità operativa svolge le elaborazioni richieste, utilizzando ALU, flag e registri.

Clock

Il clock è l'elemento dell'elaboratore che scandisce le azioni nel tempo, mantenendo la frequenza temporale comune per tutti gli elementi che costituiscono l'elaboratore. In sostanza genera un'onda quadra di periodo T [sec.] e di frequenza f=1/T, Hertz.

Architettura dei microprocessori

Esempio: tecnologia a 20 nm => lo spessore del CMOS è di 20nm. Il CMOS è il canale dove si muovono gli elettroni.

Sistemi di numerazione

Sistema di numerazione

In un sistema di numerazione siamo vincolati da una BASE, che determina il numero di cifre utilizzabili: es. base 2 = 2 cifre = {0,1}.

Conversioni numeriche

Da binario a decimale

(101)₂ → (?)₁₀
1∙2² + 0∙2¹ + 1∙2⁰ = 5₁₀

Da decimale a binario

(13)₁₀ → (?)₂
Quozienti: 13:2, 6:2, 3:2, 1:2 = 0
Resti: R=1, R=0, R=1, R=1
(1101)₂

Cifre significative

10010
Cifra più significativa = MSB   LSB → cifra meno significativa

Limiti

Un bit è una cifra di un numero. Con un numero di 3 bit, sono rappresentabili:
000, 001, 010, 100, 101, 110, 111, 011
cioè 8 = 2³ informazioni. Dunque con N bit posso rappresentare 2^N informazioni.

Equivalente: con N bit posso ottenere 2^N numeri decimali.

Somma in binario

REGOLE BASE:

• 0 + 0 = 0
• 0 + 1 = 1
• 1 + 0 = 1
• 1 + 1 = 0 con carry: 1 (Ripeto di 1)

ESEMPIO:
  1  _RIPORTI
 0110 +
 0111 =
 1101

Sottrazione in binario

REGOLE BASE:

• 0 - 0 = 0
• 0 - 1 = 1 con borrow = 1 (Prestito di 1)
• 1 - 0 = 1
• 1 - 1 = 0

ESEMPIO:
 1 0 0 1 +
 0 1 1 0
---------
 0 0 1 1

NOTA: Quando avviene un prestito, é come se venissero prestati due "1" un "1" ottiene "1" come risultato.

Overflow

Può avvenire, durante un calcolo, che il risultato del calcolo abbia bisogno di una cifra (bit) in più per essere rappresentato. Questo fenomeno è detto overflow.

esempio:
 0 1 0 1
 + 1 1 0 0
---------
 1 0 0 1 1
---------
 OVERFLOW

Il sistema ottale

Divido così: 2³ = 8, ogni cifra vale 3 bit
esempio: (763)₈ → (?)₂
 7 6 3
 011 110 011
gli spazi LSB (poco signif.) vanno saturati con gli "0"
 111 110 0,11
↓ ↓ ↓
(1111100,11) = (763)₈

Il sistema esadecimale

esempio: (0110 1100 1101)₂ → (?)₁₆
 2⁴ = 16 bit/cifra
 0110 1100 1101
 6 12 13
 6 C D → = (6CD)₁₆

CIFRE:
1 ... 9 - 10 - 11 - 12 - 13 - 14 - 15
1 ... 9 - A - B - C - D - E - F

Numeri con segno

I numeri rappresentati finora erano puri cioè privi di segno. Per rappresentare numeri con segno si utilizzano principalmente 2 notazioni, anzi codifiche: modulo e segno e complemento a due.

Codifica MODULO E SEGNO - M&S:

1 bit più a sinistra indica se il numero è positivo o negativo.
es.: 011 -> positivo
  111 -> negativo

Ovviamente il numero di numeri rappresentabili è pari a 2^N-1
1-bit | N-1 bit
SEGNO | MODULO => da -2^N-1-1 a 2^N-1-1.

Codifica COMPLEMENTO A 2 - CA2:

Da binario a decimale

numero binario

• INIZIA CON 1: ➔ È NEGATIVO
• INIZIA CON 0: ➔ È POSITIVO

Il suo corrispondente positivo, o modulo, è pari al suo complementare (scambiare -> _{gli 0 con i 1 e viceversa}) addizionato di 1 ➔ Si calcola normalmente come un binario puro.

Analogamente lo complementare a partire del primo 1 (escluso), iniziando da dx a sx. Da quest’ultimo si calcola come un binario puro, contando il primo termine come negativo.

^*esempio:Trovare il modulo del binario in CA2, negativo e riportarlo in base decimale:
1010010100
Trovo il complementare (inverto 0 e 1 e viceversa)
01011
Sommo 1 al complementare del numero iniziale
01011+1:01100 ← È il modulo del numero iniziale.
0·2⁴ + 1·2³ + 1·2² + 0·2¹ + 0·2⁰ = 8 + 4 = 12 ← Vale (12)₁₀

Verifica

10100 ← Suppongo sia -12:*
-1·2⁴ + 0·2³ + 1·2² + 0·2¹ + 0·2⁰ = -16 + 4 = -12 ← Vale (-12)₁₀ → OK!

Da decimale a binario cn2

Numero decimale:

• Negativo: Si calcola il binario puro del numero senza il segno negativo. Si antepone al numero un bit di valore 0. Si complementa il risultato, a partire dal primo "1" (escluso), da destra verso sinistra.
• Positivo: Si calcola il binario puro del numero con il metodo tradizionale senza segno. Si antepone al numero un bit di valore 0.

FINE* oppure quanti ne servono se volessi rappresentarli in un certo n° di bit.

esempi:
- (₇)₁₀ → (?)₂ ca2:
 modulo: 111
↓(0111)₂ ca2
- (-₁₂)₁₀ → (?)₂ ca2:
 modulo: 12 6 3 1 0
 0 1 1 → 1100 ora aggiungo 1 a sx
↓01100 → complemento del primo + escluso
(10100)₂ ca2

Trasformare un binario in CA2 nel suo opposto

In qualsiasi caso bisogna sommare 1 al complemento del numero in questione; esempi:
+₇₁₀: 0111 ca2 →
↓1000+1=1001 = -8 + 1 = -7
-₇₁₀: 1001 ca2 →
↓0110+1=0111 = + 4 + 2 + 1 = + 7

Somma e sottrazione in CA2

Si effettua sempre la somma: (+a) + (+b) o (+a) + (-b). Si potrebbe ottenere overflow se i riporti in colonna N e N + 1 sono diversi, con N = cifre del numero.

Esempi

Esempio senza overflow

17 + (-13):
RI-PORTI: 1
17: 010001
-13: 110011
=SOMMA: 000100 = 4₁₀
Si nota che avanza un riporto, ma essendo uguale al riporto precedente, non vi è overflow ed il risultato è corretto.

Esempio con overflow

(-7) + (-31):
RI-PORTI: 1 1 1
-7: 111001
-31: 100001
=SOMMA: 011010 = 26₁₀
Si nota che avanza un riporto che, essendo diverso dal riporto precedente, ci mostra che nell'operazione data avviene overflow, pertanto il risultato è errato.

Regola semplice dell'overflow

Somma di 2 binari
Con segno discorde: MAI overflow
Con segno concorde: C'è overflow se il risultato ha segno discorde.

NOTA: ALL'ESAME, FARE SEMPRE LE VERIFICHE

Equazioni booleane e tavole della verità

AND = · = Vale 1 se entrambi valgono 1.
OR = + = Vale 1 se almeno uno vale 1.
A = A invertito.
f(A, B, C) = AB + BC + AC _{3 var. → 2³ = 8 combinazioni}

^✱ Dove ho un 1 nella colonna f? E di queste, quanto valgono le variabili?
- Dovrei ottenere la stessa funzione di partenza, altrimenti devo ridurre:
f(A, B, C) = AB(C + C) + AB(C + C) + ABC - AB + AB + ABC = A(B + B) + ABC = sempre 1 sempre 1= A + ABC A=1A=0 BC A + ABC= 1 A + BC