Fondamenti di informatica - Riassunto completo

INTRODUZIONE

L’informatica si occupa della e dell’elaborazione dell’informazione. Quindi l’informatica

rappresentazione

le prime macchine in grado di elaborare le informazioni risalgono al ’600 (pascal

esiste da parecchio tempo:

costruì una calcolatrice in grado di svolgere le operazioni di somma e sottrazione, poi ampliata da Leibnitz nel

1670 che la rese in grado di eseguire anche moltiplicazioni e divisioni).

’30 si passò da metodi

Negli ultimi anni meccanici a metodi pneumatici (in funzione della pressione nei tubuli

si rappresentavano ed elaboravano informazioni). Ora ci sono i calcolatori elettronici, che una volta svolgevano

compiti di natura bellica, per esempio venivano utilizzati per calcolare le traiettorie dei missili.

Con una codifica di natura elettronica (tensione e corrente) abbiamo 2 meccanismi: analogico e digitale.

= 3.14 )

Analogico : per rappresentare un valore devo immettere una tensione corrispondente (

è una giustapposizione di cifre ( di 4 cifre simbolo:

= 3.14

Digitale : l’informazione visto come l’insieme

“3”, “.”

cifra simbolo cifra simbolo ecc.)

Nel digitale non c’è corrente o tensione che corrisponde alla rappresentazione, ma cifre giustapposte.

Le rappresentazioni analogiche sono affette da rumore, da effetti del mondo esterno, quindi oggi si utilizza

soprattutto il mondo digitale.

RAPPRESENTAZIONE DELL’INFORMAZIONE

Vogliamo rappresentare un’informazione che poi andrà elaborata, quindi informazioni di tipo:

- Numerico

- Alfanumerico (lettere, numeri, simboli)

- Multimediale (immagini, suoni, video)

Focalizziamo l’attenzione sulle informazioni di natura numerica.

ℕ, ℤ, ℚ, ℝ, ℂ.

Abbiamo 5 spazi di informazioni: gli insiemi numerici

Dato che utilizziamo il meccanismo di codifica digitale, rappresentiamo le informazioni come cifre.

cifre? In un mondo decimale l’alfabeto

Come scriverò queste conterebbe 10 cifre.

possiamo utilizzare i suoi “digit”,

Quando creiamo un alfabeto cioè i simboli che contiene, per rappresentare

l’informazione, creando corrispondenze biunivoche tra l’alfabeto e l’insieme numerico di riferimento.

operazioni all’interno di ℕ).

Il mio obiettivo è quello di svolgere un insieme numerico definito (per esempio

Il principio di conservazione delle proprietà formali di Dedekind ci dice che le proprietà formali in un

insieme D in base k restano valide anche in un insieme con una base diversa.

Lo strumento che utilizziamo è il transistor: un oggetto elettronico che opera in due soli stati stabili, quindi il

(0,1)

= dove 0 = 0 ∧ 1 = 3.3.

suo alfabeto ha due simboli, per convenzione Quindi dovrò considerare un

sistema di riferimento in base 2. Grazie a Dedekind posso dire che le proprietà formali delle operazioni in base

10 si conservano anche per le operazioni in base 2.

Bit: quantità di informazione (qualsiasi informazione) associata ad un alfabeto composto da due simboli.

Osserviamo che se l’alfabeto è D posso codificare (rappresentare in modo univoco) un numero di simboli pari a

aumentare il potere espressivo dell’alfabeto:

#. Devo perciò il metodo più efficiente per ottenere ciò consiste

i simboli dell’alfabeto

nel giustapporre (metodo posizionale pesato).

= 219,

Poniamo qual è il potere espressivo di tale rappresentazione?

10 10 − 1.

Se avessi a disposizione n cifre, da a potrei rappresentare codifiche e arrivare al numero

0 −1

Rappresentazione posizionale e pesata: con poca spesa (n cifre) posso rappresentare un numero di informazioni

che cresce esponenzialmente con n. Per questo il metodo posizionale ha un grande potere espressivo.

… : il valore assunto dai simboli dipende dalla loro posizione.

−1 1 0 −1 −2 1 0

, , … , ,

Associato ad una posizione ho uno specifico peso: il peso dipende dalla base k.

Storicamente si è passati da rappresentazioni con poco potere espressivo a rappresentazioni sempre migliori.

è il metodo odierno di codifica dell’informazione.

La notazione posizionale pesata

̅ ̅ { }

, ∈ = , … ,

Siano dati uno spazio simboli e

0 −1

…

⏟ ⏟

Avendo a disposizione n cifre, data la codifica , potrei disporre di codifiche distinte.

−1 0

−1 0

̅ ̅

= ⇒ = 10; = ⇒ = 2

Byte: una codifica di informazioni che giustappone 8 simboli binari.

Voglio realizzare una macchina fisica che, ricevuti due numeri a e b in base 10, possa eseguire almeno qualche

= ∘

operazione e fornisca un risultato .

10 10 10 → ; →

La macchina fisica (transistor) opera in modo efficiente in base 2, quindi dovrò convertire 10 2 10 2

→

e anticonvertire il risultato 2 10 −1

Poniamo C: fase di codifica delle informazioni; : fase di decodifica delle informazioni.

∈ ℕ

Consideriamo un numero 10

un’elettronica in grado di codificare

Supponiamo di disporre di n cifre in binario.

: … ∧ ∈ ⇒ 0 ≤ ≤ 2 − 1

2 −1 1 0 10 ℕ.

Se dispongo di un numero finito n di cifre rappresenterò un sottoinsieme di Per ciascun numero

rappresentato potrò creare un’associazione biunivoca tra codifica e numero. La rappresentazione dovrà essere

posizionale e pesata.

−1 −1 −2 )

= ∑ 2 = + ⋯ + 2 = + 2( + 2 + ⋯ + 2

10 0 −1 0 1 2 −1

=0

è il resto della divisione tra e 2 e la parte restante ne è il quoziente.

0 10

Ho determinato , devo generare :

0 1

−

10 0 −2 −3

= + ⋯ + 2 = + 2( + ⋯ + 2 )

1 −2 1 2 −1

2 −

10 0

è il resto della divisione tra e 2 e la parte restante ne è il quoziente.

1 2

Questo procedimento si dice algoritmo di lunga divisione.

Si dice algoritmo un procedimento che risolve un problema con un numero finito di passaggi in un tempo

finito. = 13

Es. 10

13 = 6 con = 1 ⇒ = 1

0

2

6 = 3 con = 0 ⇒ = 0

1

2

3 = 1 con = 1 ⇒ = 1

2

2

1 = 0 con = 1 ⇒ = 1

3

2

= 1101

2

Ora bisogna decodificare il risultato:

3 0 1 2 3

= ∑ 2 = 1 ⋅ 2 + 0 ⋅ 2 + 1 ⋅ 2 + 1 ⋅ 2 = 1 + 4 + 8 = 13

10

=0

= 147 0 ≤ ≤ 2 − 1 = 8:

Se deve essere soddisfatta la relazione e quindi serve un byte.

10 10

DELL’INFORMAZIONE

ELABORAZIONE

Per elaborare l’informazione devo essere in grado di compiere operazioni.

{+,

= −,⋅,/}

+ 0 1

0 1

0 1 0

1 {0,1,

= , , 4,5,6,7,8,9}

= 2, = 3 + = 5

Sommare 3 significa spostarsi verso destra 3 volte. Quindi

= 7, = 5

Se l’alfabeto, così com’è, + = 12

non basta, allora si genera un riporto, quindi

137 2 907 2

Es. 1

68 1

453

0

34 1

226

= 137 = 10001001

10 2 0

17 0

113

= 907 = 1110001011

10 2 1

8 1

56

0

4 0

28

+ :

2 2 10001001 + 0

2 0

14

=

1110001011 0

1 0

7

10000010100 1

0 1

3 1

1 1

0

Il vantaggio dell’uso di macchine automatiche è duplice: la velocità è infinitamente più alta e non ci sono

possibilità di errore.

sono chiusi rispetto all’insieme –

⋅ ℕ,

Problema: + e ma e / no!

La divisione può però essere vista come un insieme di sottrazioni, quindi basterà capire come eseguire

l’operazione di sottrazione. Essa può essere vista come la somma algebrica di un numero positivo con un

l’insieme

ℤ

numero negativo, quindi, ampliando a di riferimento avremo risolto il problema.

−

ℕ → ℤ (hanno lo stesso numero di elementi)

aumenta di un bit (dovuto al segno) la grandezza dell’informazione.

ℕ ℤ

Il passaggio da a

Notazione Modulo e Segno

∈ ℤ

10 ) | |

= ( ⋅ ∈ ℕ

⏟ ma

⏟

10 10 10 10

1 bit 1 bit

|

= |

2, 10

= 13 ⇒ = ⏟

0 1101

⏟ = −13 ⇒ = 11101

;

10 2, 10 2,

Se ora dovessi svolgere una sottrazione tra due numeri, come potrei conoscere il segno del risultato? Dovrei

sapere quale numero è il più grande. Sarebbe complesso e costoso utilizzare questo algoritmo, infatti non viene

utilizzato quasi mai al giorno d’oggi.

Complemento a 2

L’utilizzo del complemento a 2 facilita molto il procedimento.

La codifica di 0 deve esistere ed essere univoca e bisogna trasformare le sottrazioni in una somma aritmetica.

Ma per Dedekind potrei usare il complemento a 10.

, , ∈ ℤ

= +, −

= ∘

Fissato l’operatore +, esiste una codifica per a, b e c che mi restituisca un risultato corretto?

è l’opposto di

(−)

− = + − .

dove In uno spazio algebrico non ci sono più le sottrazioni, ma le

somme algebriche. Devo introdurre il concetto di opposto.

̅ ̅ si legge “bi complementare” e

(−)

− = + = + ⏟

+ 1 dove significa che inverto gli 1 con gli 0 e

−

̅

= 01 ⇒ = 10

viceversa: ̅

− = + 1

Operazione di complementazione: −1 −1

: ∈ ℤ −2 ≤ ≤ 2 − 1

può essere rappresentato su n bit. Quindi

10 10

ℤ

In si utilizzano metà delle codifiche per rappresentare i positivi e metà per i negativi, quindi i positivi

2

rappresentabili saranno come i negativi.

2

| |

≥ 0 ⇒ =

Se 10 2 10 ,

ℕ ℤ,

Avendo rappresento un sottoinsieme di se il numero in base 10 è positivo, allora la rappresentazione in

CP2 coincide con il modulo in binario naturale su n bit.

(2 | |) | |

< 0 ⇒ = − = 2 −

Se 10 2 10 , 10 ,

2

Perché c’è ancora la sottrazione è qualcosa che sta all’esterno del nostro

2

in fase di codifica? Il sistema di

−1

2

riferimento poiché il peso massimo che può essere assunto da una cifra della codifica è . Questa

sottrazione introduce dunque l’effetto specchio.

= 23 0 ≤ ≤ 2 − 1

ES. ?

10 2, 10

−1 −1

−2 ≤ ≤ 2 − 1

?

2 10

23 = 10111

10 2 quindi devo continuare l’algoritmo e aggiungo

= 6, 0 ≤ ≤ 2 − 1

Ho bisogno di almeno perché 10

uno 0.

= 010111

2

PREMESSA

Il CP2 permette di rappresentare i numeri interi ed esiste una sola codifica per rappresentare ogni numero

intero, quindi è una rappresentazione non ridondante. Ciò permette una simmetria di rappresentazione: lo spazio

−1 −1

−2 ≤ ≤ 2 − 1.

di rappresentazione è 10

ℤ 2

Dato e avendo n bit posso definire codifiche che staranno in uno spazio C avente base 2. Con queste

ℤ.

codifiche creo delle corrispondenze biunivoche con gli elementi di −1

si dice “c” e l’inversa “ ”.

La trasformazione diretta di codifica di decodifica

Il nostro obiettivo è quello di realizzare una macchina fisica in grado di eseguire almeno le operazioni di

addizione e sottrazione e che, accettando input decimali codifichi un codice binario e restituisca un risultato

decimale.

L’INSIEME ℤ (−)

+ = 0

Il punto chiave della definizione del CP2 è il calcolo del CP2 opposto, tale che

“in bit”

| |

∈ ℤ ∧ ≥ 0 ⇒ = ,

Se dove sta a significare binario naturale su n

10 10 2 10 ,

| | (2 | |)

∈ ℤ ∧ < 0 ⇒ = 2 − = −

Se 10 10 2 10 , 10 ,

2 10

: l’unica differenza strutturale è la sottrazione di

− 2

Considero e . Si dimostra che

10 10 ̅̅̅̅̅̅

| | (2 | |) | |

= 2 − = − = + 1

2 10 , 10 , 10 ,

2 10

= 12

ES. devo calcolare n

10

−1 −1

−2 ≤ ≤ 2 − 1 ⇒ = 5 ho bisogno di 5 bit

10

= 01100

2

− = −12

10

−1 −1

−2 ≤ ≤ 2 − 1 ⇒ = 5

10

5

2 = 100000

2 | |

= 2 − = 100000 − 01100 = 0 10100

⏟

procedimento 1: 2 10 ,

2 codifica

10100 + 01100 = 00000

(2 | |) (32

= − = − 12) = 20 = 10100

procedimento 2: 2 10 , , ,

10

̅̅̅̅̅̅

| |

= + 1 = 10011 + 1 = 10100

procedimento 3: 2 10 ,

Si dimostra che le codifiche che derivano dalla trasformazione di numeri positivi hanno, come bit in posizione

più significativa uno 0, per i negativi è 1. Questo bit sarà il bit di segno.

1011: è un numero. Se fosse un binario naturale varrebbe 11. Se fosse un CP2 sarebbe un numero negativo. Se

voglio sapere quanto vale bisogna decodificarlo generando l’opposto con il complemento bit a bit e sommando

1, otterremmo 0101=5 quindi 1011= -5.

Questo per dire che l’elaborazione di un’informazione dipende dal contesto nel quale la si pone.

OPERAZIONI IN CP2

= −5 ∧ = −2 + ?

Dati come svolgere la somma

−1 −1 |−5|

= −5 ∧ −2 ≤ ≤ 2 − 1 ⇒ = 4 ⇒ = 0101 ⇒ − = 1010 + 1 = 1011

10 ,2

−1 −1 |−2|

= −2 ∧ −2 ≤ ≤ 2 − 1 ⇒ = 2 ⇒ = 10 ⇒ 01 + 1 = 10

10 ,2

Osserviamo che la codifica del numero 2 in binario naturale coincide con la codifica del numero -2 in

complemento a 2. Questo non ha nessuna implicazione: è semplicemente una coincidenza, infatti la codifica in

binario naturale è un sistema di riferimento diverso dalla codifica in complemento a 2 e non ci sono relazioni

immediate o intuitive tra di esse.

Svolgiamo l’operazione +

Non si possono sommare due elementi, che potrebbero essere vettori, di dimensioni diverse.

= 2

Come portare 10 a 4 bit? Basta dire che, se è il numero minimo di bit necessari è sufficiente estendere

con due zeri il binario naturale, che diverrà 0010. Poi utilizzerò questa codifica per i calcoli in CP2.

A riguardo, esiste questa regola: si considera il bit di segno e si ripropone alla sinistra tante volte quante sono

necessarie a completare la codifica in bit.

1011 + 1110 = 11001

Ora però sorge un problema: noi disponiamo di soli 4 bit, mentre il risultato ottenuto ne necessita 5 per essere

rappresentato. Sulla nostra macchina fisica, che dispone di una rappresentazione a 4 bit visualizzeremo il

risultato 1001, che è la codifica di un numero negativo e quindi potrebbe essere il risultato corretto.

Genero l’opposto e sommo 1: 0110 + 1 = 0111. Questo è un numero positivo, ma io so che la

rappresentazione in CP2 di un numero positivo coincide con la rappresentazione in binario naturale del modulo

così l’antitrasformazione, 0111 = 7.

(svolgiamo cioè la decodifica), quindi Quindi il risultato complessivo è -7.

−

Svolgere la sottrazione

(−)

− = + −

Devo generare

̅ ora genero l’opposto per

(−)

− = + 1 = 0001 + 1 = 0010 = 2 ⇒ + = 1011 + 0010 = 1101

0010 + 1 = 0011 = 3. − = −3.

decodificarlo: Quindi

= 7 ∧ = 3; + ?

Es. −1 −1

−2 ≤ ≤ 2 − 1 ⇒ = 4; = 3 ⇒ = 4

10

7 = 0111 =

7=4+2+1⇒ 2

3 = 0011 =

3=2+1⇒ 2

+ = 0111 + 0011 = 1010 che è un numero negativo. Questo risultato è impossibile. Ciò significa

che il risultato non può essere rappresentato su 4 bit. Si dice che è avvenuto un trabocco o overflow. (un

esempio in base dieci potrebbe essere: 999 + 002 in 3 bit decimali).

Può esserci overflow quando la somma algebrica genera un risultato che non può essere rappresentato

attraverso il numero di bit stabilito: questa situazione si manifesta solo quando ho delle operazioni che

compongono segni concordi.

Abbiamo overflow quando i segno concordi degli operandi sono discordi da quello del risultato. Se si verifica

l’overflow il risultato su n bit non è corretto.

=