Lezioni, Fondamenti di Informatica

U+XXXX XXXX

Unicode è indicato con la notazione dove rappresenta il valore del code point in

U + 0000H U + FFFFH

base esadecimale. Il range di caratteri originali, da a è noto come Basic

Multilingual Plane (BMP) e copre tutti i principali linguaggi attualmente in uso.

Esistono altri due tipi di codifica:

 UTF-8 (UNICODE TRANSFORMATION FORMAT-8 BIT), usa un numero di byte variabile da 1

a 4. In particolare, 1 byte è sufficiente per rappresentare i 128 caratteri ASCII. Questa

codifica usa 1-3 byte per i caratteri nel set BMP (16-bit) e 4 byte per quelli fuori dal set

BMP (21 bit). I caratteri ASCII usano 1 byte: il bit iniziale è 0 per cui il “code point” del

carattere è lo stesso del set ASCII.

La maggior parte dei caratteri Europei e Medio Orientali richiedono 2 byte (per esempio

lettere latine accentate). Cinese, Giapponese e Coreano (CJK) usano 3 byte. In UTF-8 tutti i

byte, eccetto il byte per i caratteri ASCII, hanno un bit iniziale 1; i byte ASCII possono essere

riconosciuti e decodificati facilmente (efficiente per documenti che contengono molti

caratteri ASCII); 13

 La codifica MULTI-BYTE per il formato di un file di testo, che può essere:

- Byte-Order: in una codifica multi-byte, l’ordine di memorizzazione dei byte è

importante. In Big-Endian il byte più significativo è memorizzato nella locazione di

memoria con l’indirizzo più piccolo (“Big-byte first”); in Little-Endian succede il

contrario. Il Big-Endian è l’ordinamento più comune.

- U-FEFF,

Byte-Order-Mark (BOM): è un carattere Unicode speciale, code number

FFH)

utilizzato in alcuni casi per distinguere tra Big-Endian (FEH e Little-Endian

FEH). FF)

(FFH I due code number (FE e sono riservati per non essere

confondibili con altri caratteri.

Lo schema di codifica dei caratteri su Windows è noto come codepage. Il codepage predefinito è il

Windows-437 (quello usato nel DOS originale); è una codifica a 8-bit chiamata anche Extended-

ASCII. Non coincide con Latin-1 (i caratteri con code number superiori a 127 sono diversi).

Nell’ordinamento dei caratteri la stringa è una sequenza di caratteri (maiuscoli o minuscoli) come

apple, BOY, Cat, il cui ordinamento e confronto è basato sull’ordine dei code number (p.e. quelli

ASCII) e produce risultati differenti rispetto all’ordinamento “da dizionario”, perché le maiuscole

hanno code number più piccolo delle minuscole.

Le collating sequences specificano la posizione di lettere, numeri e altri simboli nella sequenza

ordinata. Ne esistono diverse a seconda delle esigenze del programma che si sta sviluppando. Ad

esempio: case-insensitive dictionary order, case-sensitive dicionary order (dove in genere le

maiuscole vengono prima delle minuscole). La sequenza è “language-dependent”: ossia differenti

linguaggi utilizzano differenti simboli con il proprio ordinamento.

Alla base della realizzazione dei circuiti integrati digitali, vi sono le reti logiche. Tali circuiti hanno la

duplice funzione di immagazzinamento di informazioni e di immagazzinamento della logica di

controllo.

Nel 1854 il matematico George Boole pubblica un lavoro circa un’algebra delle relazioni logiche. In

esso, investigava le proprietà dei sistemi binari. L’algebra booleana opera su variabili, dette

logiche o booleane, che possono assumere soltanto valore 0 falso o 1 vero. Quindi una variabile

booleana corrisponde ad un bit di informazione.

Dato un insieme di variabili booleane x ,……,x si dice funzione booleana una funzione di tali

1 n

variabili f(x ,……,x ). Per la natura stessa delle variabili booleane, una funzione booleana può

1 n

essere completamente definita da una tavola di verità che esprime il valore logico di f in relazione

a tutti i possibili valori assunti da x ,……,x .

1 n

n

Con n variabili booleane si hanno 2 possibili permutazioni, il numero complessivo di funzioni

2^n

booleane definibili sull’insieme è quindi 2

Un gate logico (porta logica) è un dispositivo elettronico che implementa una semplice operazione

booleana fra variabili binarie. I gate logici di base trasformano due valori booleani in ingresso A e B

(input) in un valore booleano in uscita Z (output).

14

Nell’algebra booleana esistono tre operatori fondamentali:

 AND (prodotto logico indicato con il simbolo ):

 OR (somma logica indicata con il simbolo + ):

 NOT (negazione o complementazione, indicata con il simbolo - ):

⊕):

 XOR (è un OR esclusivo, indicato con il simbolo

 XNOR (implementa la funzione inversa di XOR, e si indica con il simbolo ʘ):

Ogni operatore è caratterizzato da un simbolo grafico circuitale che mette in relazione le variabili

di ingresso con quelle di uscita. AND, OR e NOT possono essere sostituiti da diversi altri operatori

logici, chiamati universali, in quanto ognuno di essi è in grado di sostituire da solo i tre operatori

principali:

 NOR ( simbolo , implementa la funzione inversa di OR):

15

 NAND ( simbolo | , implementa la funzione inversa di AND):

L’importanza di tali operatori deriva dal fatto che essi trovano semplice realizzazione tramite

circuiti elettronici a transistor, denominati porte logiche.

La scoperta del transistor e la conseguente costruzione di porte logiche miniaturizzate è stato uno

degli eventi più importanti nella storia dei calcolatori moderni. A livello circuitale, i valori logici

sono rappresentati elettricamente da valori di tensione positivi o nulli che variano a seconda del

tipo di componenti utilizzati.

L’algebra Booleana può essere definita come un reticolo rispetto alle operazioni di somma o

prodotto logico. Ogni reticolo possiede tre proprietà fondamentali:

 Proprietà commutativa:

 Proprietà associativa:

 Proprietà di assorbimento:

Inoltre vi sono altre proprietà supplementari:

 Esistenza di elementi neutri:

 Esistenza del complementare:

 Proprietà distributiva:

 Annichilazione per il prodotto:

 Annichilazione per la somma:

 Idempotenza del prodotto:

 Idempotenza della somma:

 Distributività della somma sul prodotto:

L’operazione di complementazione (o negazione) è definita dalle due proprietà:

 (complementazione 1) 16

 (complementazione 2)

Come in algebra ordinaria:

 (doppia negazione)

A differenza dell’algebra ordinaria valgono le leggi di De Morgan:

 (De Morgan 1)

 (De Morgan 2)

Una caratteristica importante dei teoremi e delle proprietà considerate prende il nome di principio

di dualità: data una relazione vera è certamente vera anche la relazione ottenuta sostituendo

l’operatore AND con l’operatore OR, i valori 0 con i valori 1 e viceversa.

L’operazione di sintesi consiste nel trovare una funzione logica, la più semplice esistente, relativa

ad una tavola di verità nota. Nell’operazione di sintesi vengono utilizzati teoremi e proprietà

fondamentali dell’algebra booleana. La metodologia applicata può essere complessa oppure

diretta. Tavola di verità

Procedendo per righe si valutano in particolare le righe per le quali la funzione assume valore uno.

Si ha immediatamente:

e quindi, per la proprietà distributiva:

Per l’esistenza del complementare, l’espressione vale 1; si ha quindi:

espressione che può essere ulteriormente semplificata per l’esistenza dell’elemento neutro:

Quindi ora è possibile applicare la proprietà di assorbimento, scrivendo come .

Raccogliendo a fattor comune e semplificando si ottiene alla fine:

Le porte logiche sono i mattoni elementari che consentono la realizzazione di circuiti complessi,

caratterizzati da più ingressi e più uscite. Tali circuiti, indicati come reti logiche, possono essere

distinti in due classi molto diverse: reti combinatorie e reti sequenziali.

17

Una rete combinatoria è uno strumento potente per immagazzinare conoscenza riguardo ad un

problema. Le uscite di una rete combinatoria possono quindi essere utilizzate per prendere

decisioni e/o per controllare dispositivi in cascata.

Una rete sequenziale è comunemente caratterizzata da uno o più interni che dipendono

dall’evoluzione nel tempo dei valori di ingresso. Gli stati interni di una rete sequenziale possono

quindi essere utilizzati molto opportunamente per memorizzare informazioni e conservare i valori

memorizzati fino a quando non si verifica una precisa configurazione dei valori di ingresso.

La circuiteria di una moderna macchina da calcolo comprende unità funzionali che comprendono

uno o più dispositivi periferici per l’ingresso/uscita dei dati, uno o più supporti di memoria diversi

per tipo e funzione, una o più unità centrali di elaborazione (CPU).

La CPU viene istruita ad eseguire delle operazioni utilizzando un particolare linguaggio, detto

linguaggio macchina (istruzioni binarie). Immaginiamo che ad ogni ciclo di clock interno una CPU

possa eseguire una sola istruzione. L’insieme elementare di istruzioni che una CPU può eseguire è

detto ciclo fetch-execute.

La CPU preleva dalla memoria la prossima istruzione da eseguire, decodifica l’istruzione da

eseguire (il codice macchina corrispondente a questa istruzione è detto opcode, “operation

code”), preleva dalla memoria gli eventuali operandi e esegue infine l’istruzione e memorizza il

risultato.

Un computer manipola simboli binari soggetti all’algebra Booleane. Il linguaggio macchina è un

insieme di istruzioni in forma binaria (sequenze di bit), con una sintassi ben definita ma non di

facile lettura/scrittura per un essere umano. Vi è perciò la necessità di migliorare la definizione

sintattica del linguaggio per renderlo più intellegibile. Questo è il linguaggio Assembly, che ad ogni

istruzione binaria elementare (funzioni primitive) associa un equivalente mnemonico.

Dalla necessità di poter programmare un calcolatore con linguaggi più semplici di Assembly

nascono i primi linguaggi di alto livello, che rappresentano un’interfaccia tra il linguaggio umano e

il linguaggio macchina.

I linguaggi di alto livello devono avere tre elementi caratteristici:

 Una sintassi più concisa dell’Assembly (una sola istruzione deve corrispondere ad un

insieme potenzialmente grande di istruzioni Assembly).

 Indipendenza dall’Assembly: la sua sintassi non deve dipendere dai dettagli

dell’architettura della CPU.

 Deve avere un parser, cioè un programma capace di tradurre la sintassi del linguaggio di

alto livello in codice macchina