Appunti di Elementi di informatica

IL BISOGNO DELL’INFORMATICA

Nell’ambito dell’ingegneria, l’informatica è fondamentale per:

• analizzare grosse quantità di dati

• automatizzare calcoli complessi e sviluppare software per la

progettazione e l’analisi

• simulare processi e sistemi complessi

• Interfacciarsi con le nuove tecnologie emergenti (e.g. Machine

Learning, AI Generativa, Digital Twins).

Scienza della rappresentazione, della gestione e della elaborazione

(automatica) delle informazioni. Scienza interdisciplinare che riguarda

tutti gli aspetti del trattamento dell’informazione mediante procedure

automatizzabili. L’informatica si occupa di due aspetti essenziali:

• Tecnologico: progettazione di apparecchiature, strumenti, elaboratori

per la manipolazione dell’informazione

• Metodologico: definizione delle metodologie per la gestione delle

informazioni

Informazione: Deriva da informare, ossia dare forma

• Fa riferimento ad un concetto astratto che può coincidere con

qualunque notizia o racconto

• L'informazione è qualcosa che viene comunicato in una qualsiasi forma

scritta o orale. Nella teoria dell’informazione, l'informazione viene spesso

associata al concetto di messaggio • Anche se il messaggio serve solo a

rappresentarla e trasportarla

• Corretta interpretazione di un messaggio • Solo se mittente e

destinatario concordano le regole di interpretazione • Condivisione di un

insieme di regole e convenzioni da seguire per scrivere, e in seguito

leggere, il messaggio da scambiare. L’informazione è legata al concetto

di scelta • Le informazioni permettono di prendere decisioni • Una

informazione è tale se identifica - fra più elementi di un insieme tra cui

effettuare la scelta - un valore, cui è assegnato il significato stabilito.

• Le informazioni sono caratterizzate dalla tripla {tipo, valore, attributo}

• Tipo: definisce l’insieme degli elementi fra i quali si compie la scelta •

Valore: è il particolare elemento scelto • Attributo: è ciò che associa un

significato al valore, dando senso all’informazione. Il semaforo (da sema

“segnale” e foro “portatore”) è un dispositivo che veicola una

informazione in base alle lampade accese e alla loro tempificazione

• L’informazione avrà: • Tipo: {“Rosso fisso”, “Giallo fisso”, “Verde fisso”,

“Giallo lampeggiante”, “Spento”}. • Valore: “Rosso fisso”. • Attributo:

“Semaforo di ingresso in galleria”.

• Informazione: “Il semaforo di ingresso in galleria è rosso”

• Un conducente elabora questa informazione e fa una scelta: •

“Arrestare il mezzo di locomozione e non procedere al transito in

galleria”Scrivere, leggere ed elaborare informazioni richiede un codice

concordato, cioè regole e convenzioni da seguire

• Esistono due modalità diverse di rappresentazione

• Analogica (continua) • Digitale (discreta)

Proprietà del fenomeno rappresentato, omomorfe alla forma della

rappresentazione • Varia in analogia con la grandezza reale • Serve

insieme infinito di rappresentazioni distinte messe in relazione in modo

continuo con la grandezza reale

La rappresentazione digitale (discreta) utilizza un insieme finito di

rappresentazioni distinte che vengono messe in relazione con la

grandezza reale da rappresentare: • E’ un’approssimazione di quella

analogica • Ad ogni variazione della grandezza reale, non si ottiene

necessariamente un’analoga variazione della rappresentazione

• Viene rappresentata con numeri e opera manipolando numer. Le

rappresentazioni digitali di informazioni di tipo non finito possono indurre

ad errori che devono essere opportunamente gestiti nelle operazioni di

calcolo.La codifica è la tecnica adoperata per trasformare

un’informazione in una sua rappresentazione (dato), la decodifica è

l’operazione inversa. • La codifica è l’insieme di convenzioni e regole da

adottare per trasformare un’informazione nella sua rappresentazione.

• Un’informazione può essere codificata in modi diversi

(rappresentazioni diverse): • E.g., 1 e I sono, rispettivamente, le

rappresentazioni mediante codifica araba e romana della stessa

informazione numerica.

Un codice è un sistema di simboli che permette la rappresentazione

dell’informazione in una data codifica.

• Un codice è definito dai seguenti elementi: • I simboli che sono gli

elementi atomici della rappresentazione • L’ alfabeto che rappresenta

l’insieme dei simboli possibili del codice • Con cardinalità (n) del codice

si indica il numero di elementi dell’alfabeto

• Le parole-codice o stringhe ossia le sequenze possibili (ammissibili) di

simboli • Per lunghezza (L) delle stringhe si intende il numero di simboli

dell’alfabeto da cui ciascuna parola codice risulta composta

• Il linguaggio che definisce le regole per costruire parole-codice che

abbiano significato per l’utilizzatore del codice stesso. Dato un alfabeto

A={s1,s2,...,sn}, composto da n simboli distinti • Si considerino diverse

lunghezze L delle parole codice: • con L=1: si hanno tante parole-codice

diverse (n1) quanti sono i simboli dell’alfabeto

• con L=2: si hanno tante parole-codice diverse quante sono le

combinazioni con ripetizione degli n simboli nelle due posizioni (ossia

n2)

• con L=3: si hanno n3 parole-codice diverse • . . .

• In generale il numero di parole codice differenti è uguale anL. Dato

l’insieme dei possibili valori di un’informazione V={v1,v2,...,vm}, di

cardinalità m

• La codifica deve mettere in corrispondenza biunivoca i valori

dell’informazione con le parole-codice: • ad ogni valore dell’informazione

vi deve corrispondere una ed una sola sequenza di simboli

• La lunghezza L deve essere scelta in modo che nL≥m. Se nL>m allora

la codifica è ridondante perché non tutte le configurazioni possibili

vengono utilizzate per la rappresentazione

• La codifica può essere vista come una funzione biunivoca: • →

,

∶

||L≥||. La lunghezza della codifica può essere fissa o variabile

• Codifica a lunghezza fissa: • Tutte le parole codice hanno sempre la

stessa lunghezza, che viene fissata da particolari esigenze applicative

• Codifica a lunghezza variabile • Non tutte le parole codice hanno la

stessa lunghezza • Ad esempio, la scrittura è una codifica a lunghezza

variabile

• I calcolatori adottano spesso codifiche a lunghezza fissa.

RAPPRESENTAZIONE DIGITALE BINARIA

• Assume particolare interesse nell’informatica • Basata su un alfabeto

costituito da due soli simboli distinti, che assumono convenzionalmente

la forma di 0 e 1: • Sono le unità minime di rappresentazione e

memorizzazione digitale e vengono denominate bit (binary digit)

• Nota: solitamente si indica con digitale la rappresentazione basata sui

bit, anche se essa teoricamente sottintende una rappresentazione con

qualsiasi tipo di cifre

1) Memorizzazione semplificata • Alfabeto binario adatto ai registri di

memoria realizzati con componenti elementari semplici detti flip-flop

operanti in due soli stati possibili

• Tanti fenomeni diversi sono facilmente rappresentabili con un bit •

Presenza/assenza di tensione elettrica in un circuito elettrico • Polarità

positiva/negativa di un magnete o di un supporto con caratteristiche

magnetiche tipo nastri e dischi • Condizione di acceso/spento di un

interruttore

2) Memorizzazione affidabile • Maggiore tolleranza a disturbi provenienti

dall’ambiente o ad interferenze di altri componenti (separazione elettrica

massima tra i due stati)

• Il codice binario utilizza un alfabeto A={0,1}con n=2 • Le informazioni

numeriche vengono quindi rappresentate mediante stringhe di bit di

lunghezza L che producono 2L configurazioni (parole-codice) diverse

• Viceversa, se si devono rappresentare K informazioni diverse,

⌈ ⌉

occorrono log2K bit per poter associare opportunamente una

⌈ ⌉

configurazione distinta ad ogni informazione • il simbolo . indica la

funzione ceiling che restituisce il primo intero maggiore o uguale

all’argomento.

• Nei calcolatori la precisione è finita e predeterminata • I numeri sono

memorizzati con parole codice di lunghezza fissata I bit si raggruppano

in potenze di due (2, 4, 8, 16 bit, etc.) poiché in questo modo tutte le

operazioni si semplificano

• Byte : stringhe di bit di lunghezza L=8 → 2L=256 • Usate per ragioni

legate alla costruzione dei moderni calcolatori • Era la più piccola

potenza di due in grado di contenere un set di caratteri ASCII • Anche i

dati contenuti nelle memorie, che sono a 8, 16, 32 o 64 bit, sono

facilmente divisibili in byte

• Word: sequenze di bit più lunghe di un byte • lunghezza dipendente

dalle caratteristiche del sistema • multiplo del byte (16, 32, 64 o 128 bit)Il

sistema di numerazione binario è un sistema posizionale • Ogni cifra

assume valore differente in base alla sua posizione • Non posizionale,

invece, significa che il valore non dipende dalla posizione (ad es. il

semaforo)

• Ogni numero si esprime come la somma dei prodotti di ciascuna cifra

per la base b elevata all’esponente che rappresenta la posizione della

cifra.

• Dato un numero intero dette le cifre di e la base di riferimento

,

(ad es. per il sistema binario):

=2

−1

=

=0

= + + … + LSB = Least Significant Bit

0 0 1 1 −1 −1•

∗ ∗ ∗ ∗

• Bit più a destra (peso 0) è il meno significativo

• MSB = Most Significant Bit • Bit più a sinistra (peso 7) è il più

significativo

Nei moderni calcolatori, codifica a lunghezza fissa con parole codice di

lunghezza che ha valori multipli di 8 (di un byte)

• Per rappresentare K valori dell’informazione in multipli B di byte: (∗)

≥ K

L’adozione di stringhe a lunghezza finita e definita, implica che i numeri

gestiti siano a precisione finita: • Ossia, i numeri possono essere

rappresentati con un numero finito di cifre, o più semplicemente sono

definiti all’interno di un prefissato intervallo di estremi [min, max]

determinati

• Concetto di periodicità • Valori non compresi nell’intervallo di

definizione vengono fatti ricadere in esso per periodicità

Nei sistemi di calcolo con numeri a precisione finita, le operazioni

possono causare errori quando il risultato non appartiene all’insieme dei

valori rappresentabili: • Overflow: • Quando il risultato di un’operazione è

maggiore del più grande valore rappresentabile (max)

• Quando il risultato di un’operazione è minore del più piccolo valore

rappresentabile (min)

• Underflow: il risultato di un’operazione non è compreso nell’insieme dei

valori rappresentabili, pur non essendo né troppo grande né troppo

piccolo• Diversa da quella convenzionale, e alcune proprietà non

sempre sono rispettate ma dipendono dall’ordine di esecuzione delle

operazioni: • Proprietà associativa: + − = + −

Proprietà distributiva: − = − +

∗ ∗ ∗ ∗

SISTEMI DI NUMERAZIONE

• Un sistema di numerazione è un insieme di simboli (cifre) e regole che

assegnano ad ogni sequenza di cifre uno ed un solo valore numerico

• Posizionali • Ogni cifra ha un’importanza variabile a seconda della

relativa posizione • Nel sistema decimale la prima cifra a destra indica

l'unità, la seconda le decine, la terza le centinaia e così via

• Non posizionali • Ogni cifra esprime una quantità non dipendente dalla

posizione • E.g.:, nel sistema romano il simbolo L esprime la quantità 50

indipendentemente dalla posizione. Stringa (i-cifre): una qualsiasi

sequenza ci-1 ci-2 … c1 c0 di cifre/simboli/bit in un sistema di

numerazione posizionale: • Ai simboli c è associato un diverso peso in

base alla posizione j occupata nella stringa che compone il numero

• Il peso dipende dalla base b di numerazione

• Numero intero x rappresentato da i cifre in base b : …10 →

−1 −2

= +

−1 −1 −2

⋅

+⋯+ + In un sistema di numerazione posizionale è

−2 1⋅ 1 0 0.

⋅ ⋅

possibile rappresentare numeri con parte frazionaria usando i + k cifre

• Ad ogni sequenza (stringa) di cifre ci-1 ci-2 … c1 c0 , c-1 c-2 … c-k+1

c-k viene associato uno ed un solo numero x in funzione sia del valore

delle singole cifre che del peso che esse assumono all’interno della

stringa di cifre

• Alla j-esima cifra cj è associato un peso diverso in base alla posizione j

di cj nella stringa di cifre tenendo conto della posizione della virgola

• Il peso di una cifra dipende dalla base (o radice) b di rappresentazione

• Numero reale x rappresentato da i+k cifre in base b ci-1 ci-2 … c1 c0 ,

c-1 c-2 … c-k+1 c-k → x

⸱ ⸱ ⸱ ⸱ ⸱

x = ci-1 bi-1 + ci-2 bi-2 + … +c0 b0 + c-1 b-1 + … + c-k+1 b-k+1 +

⸱

c-k b-k. Definiti dalla base (o radice) utilizzata per la rappresentazione

• In un sistema posizionale in base b, servono b simboli per

rappresentare i diversi valori delle cifre compresi tra 0 e (b-1)

Solo nel sistema decimale è possibile leggere i numeri • Ad es.,

“quarantasette”

• Negli altri sistemi di numerazione, cifre lette da quella di peso maggiore

fino a quella di minor peso, con indicazione della base • Ad es., “uno

quattro due” in base cinque

SISTEMA DI NUMERAZIONE POSIZIONALE: BINARIO

• Minor numero di simboli rispetto al sistema decimale (2 << 10) • Parola

codice più lunga che non in notazione decimale per rappresentare un

⌈ ⌉

numero • Per rappresentare le dieci cifre occorrono log210 = 4 bit •

Stringa di cifre in bit circa tre volte più lunga di quella decimale

OTTALE ED ESADECIMALE

Trasformazione di rappresentazioni di valori nella base 2 (e viceversa)

immediata • Binario → Ottale: Cifre binarie raggruppate in gruppi di tre a

partire dalla posizione di peso minore

• Ottale → Binario: Ogni cifra ottale esplosa nelle tre cifre binarie che la

rappresentano. Binario → Esadecimale: Cifre binarie raggruppate in

gruppi di quattro a partire dalla posizione di peso minore

• Esadecimale → Binario: Ogni cifra esadecimale esplosa nelle quattro

cifre binarie che la rappresentano.

RAPPRESENTAZIONE NUMERI RELATIVI IN BINARIO

RAPPRESENTAZIONE DEI NUMERI NATURALI: BINARIO PURO

• La rappresentazione finora presentata è detta in “binario puro” •

Avendo l bit a disposizione per le parole codice, tale rappresentazione

rende possibile codificare tutti i numeri relativi positivi appartenenti

all’intervallo [0, 2l – 1]

• Numeri relativi • Numeri interi, positivi e negativi incluso lo zero

• Diverse rappresentazioni • Segno e modulo • Complemento a due •

Complemento a uno • Per eccesso

• Perché esistono diverse tipologie di codifica? • Realizzare circuiti

elettronici capaci di effettuare operazioni aritmetiche in un calcolatore in

modo ottimizzato e semplice

RAPPRESENTAZIONE SEGNO E MODULO

• Data una sequenza di l bit, si usano l – 1 bit per rappresentare il

modulo del numero intero in binario puro

• Bit più a sinistra (MSB) per il segno • “0” per indicare un valore positivo

• “1” per indicarne uno negativo

• Numeri relativi rappresentati nell’intervallo [-(2l-1 - 1), (2l-1 – 1)] =

= [-2l-1 + 1, 2l-1 - 1] • 2(l-1)-1 valori positivi, altrettanti negativi, e lo zero

• 2l-1 valori diversi SVANTAGGI PRINCIPALI:

• Due configurazioni dello zero • “0” positivo (00000000) e “0” negativo

(10000000)

• Algoritmi diversi e complessi per somma (e sottrazione): • Confronto

dei segni dei due operandi: • Se i segni sono uguali: 1. Si sommano tutti

i bit meno quello del segno 2. Si aggiunge il bit di segno ai bit ottenuti

dalla somma

La somma algebrica non è applicabile

• Segni diversi 1. Si considerano tutti i bit meno quello del segno 2. Si

sottrae il numero più piccolo in modulo dal numero più grande 3. Si

aggiunge ai bit ottenuti dalla sottrazione il bit di segno del numero in

modulo più grande. Se i segni sono concordi: 1. Si sommano tutti i bit

meno quello del segno 2. Si aggiunge il bit di segno ai bit ottenuti dalla

somma. Se i segni sono discordi: 1. Si considerano tutti i bit meno quello

del segno 2. Si sottrae il numero più piccolo in modulo dal numero più

grande 3. Si aggiunge ai bit ottenuti dalla sottrazione il bit di segno del

numero in modulo più grande

OPERAZIONE DI COMPLEMENTAZIONE ALLA BASE

• Data una sequenza di k cifre che rappresenta il numero N in base b, si

definisce: • Complemento alla base di N il valore Cb = bk – N

• Complemento dimi