Materiale Ingegneria Informatica

Il Concetto di Algoritmo

1. Definizione

Un Algoritmo è una sequenza precisa (non ambigua) e finita di operazioni che porta alla realizzazione di un compito o alla risoluzione di un problema.

L'esecuzione delle azioni nell'ordine specificato consente di trasformare i dati di partenza (input) nei risultati desiderati (output).

2. Proprietà Fondamentali

Affinché una procedura possa essere considerata un algoritmo, deve soddisfare i seguenti requisiti:

• Atomicità: Ogni istruzione deve essere elementare, ovvero non ulteriormente scomponibile.
• Non ambiguità (Univocità): I passi devono essere interpretabili in un unico modo, senza incertezze per l'esecutore.
• Finitezza: L'algoritmo deve essere composto da un numero discreto di passi e deve terminare dopo un tempo finito.
• Determinismo: Partendo dagli stessi dati di input, l'algoritmo deve produrre ogni volta i medesimi risultati.
• Generalità: L'algoritmo deve risolvere una classe di problemi e non un singolo caso specifico (es: deve saper sommare due numeri qualsiasi, non solo 5 e 3).

Le 3 Categorie di Operazioni

Le operazioni elementari utilizzate negli algoritmi appartengono a una di queste categorie:

• 1. Operazioni Sequenziali:
  Realizzano una singola azione. Quando l'azione è terminata, si passa automaticamente all'istruzione successiva nella lista.
• 2. Operazioni Condizionali:
  Controllano una condizione (Vero/Falso). In base al valore della condizione, selezionano quale operazione eseguire successivamente (bivi logici).
• 3. Operazioni Iterative (Cicli):
  Ripetono l'esecuzione di un blocco di operazioni finché non viene verificata una determinata condizione.

Flusso di Risoluzione del Problema

Risolvere un problema significa produrre risultati a partire da dati in ingresso. L'algoritmo è lo strumento che guida l'esecutore in questo processo.

Programmazione e Linguaggi

Il Programma

La formulazione testuale di un algoritmo in un linguaggio comprensibile ad un calcolatore è detta PROGRAMMA.

Fasi di Risoluzione:

1. Individuazione di un procedimento risolutivo.
2. Scomposizione del procedimento in un insieme ordinato di azioni → ALGORITMO.
3. Rappresentazione dei dati e dell’algoritmo attraverso un formalismo comprensibile al calcolatore → LINGUAGGIO DI PROGRAMMAZIONE.

Linguaggi di Programmazione

Un Linguaggio di Programmazione è una notazione formale usata per descrivere algoritmi. Definisce quali sono gli elementi linguistici primitivi, le frasi lecite e se una frase appartiene al linguaggio.

Perché non usare il Linguaggio Naturale?

• Non evita le ambiguità (una frase può avere più significati).
• Non si presta a descrivere processi computazionali automatizzabili.

Sintassi e Semantica

Ogni linguaggio è caratterizzato da:

Grammatiche

Una Grammatica è definita dalla quadrupla:

G = <V, V_N, P, S>

• V: insieme finito di simboli terminali (entità atomiche e predefinite).
• V_N: insieme finito di simboli non terminali (detti anche "categorie sintattiche").
• P: insieme finito di regole di produzione.
• S: simbolo non terminale detto simbolo iniziale.

Data una grammatica G, si dice Linguaggio L_G generato da G l’insieme delle frasi di V:

• Derivabili dal simbolo iniziale S.
• Applicando le regole di produzione P.

Le frasi di un linguaggio di programmazione vengono dette programmi.

Grammatica BNF (Backus-Naur Form)

È una grammatica le cui regole di produzione sono della forma:

Dove X è un simbolo non terminale ed A₁...A_n è una sequenza di simboli (terminali o non terminali).

Una grammatica BNF definisce un linguaggio sull’alfabeto terminale V mediante un meccanismo di derivazione (riscrittura).

Si dice che A deriva da X se esiste una sequenza di derivazioni da X ad A.

Costrutto "one of":

Indica che X può assumere una unica alternativa tra A₁, ..., A_n.

Esempio di Grammatica BNF

Definizione G = <V, V_N, P, S>:

• V = {lupo, canarino, bosco, cielo, mangia, vola, canta, ., il, lo} (Simboli terminali)
• V_N = {frase, soggetto, verbo, articolo, nome} (Categorie sintattiche)
• S = frase

Regole di Produzione P:

frase    → soggetto verbo .
soggetto → articolo nome
articolo → one of { il, lo }
nome     → one of { lupo, canarino, bosco, cielo }
verbo    → one of { mangia, vola, canta }

Esempio di Derivazione della frase "il lupo mangia .":

frase → soggetto verbo .
      → articolo nome verbo .
      → il nome verbo .
      → il lupo verbo .
      → il lupo mangia .

Altri Costrutti del Metalinguaggio

Oltre alle regole di base, il metalinguaggio BNF offre costrutti comodi per semplificare la scrittura delle grammatiche e renderle più compatte.

1. Presenza Opzionale (opt)

Indica che un simbolo (terminale o non terminale) è opzionale: può apparire nella frase oppure essere omesso.

Analogamente, la regola X → A₁ A₂opt genera le frasi A1 A2 oppure A1.

2. Sequenza (seq)

Permette di definire una sequenza di simboli identici (ripetizione) senza dover scrivere regole ricorsive esplicite.

Sia A un simbolo. Indicheremo con A-seq una sequenza di tali simboli di lunghezza maggiore o uguale a uno.

Esempio:

Se la categoria nome include simboli come {lupo, canarino, bosco}, allora la regola nome-seq può generare frasi composte da una sequenza arbitraria di nomi:

lupo canarino lupo lupo

Questa frase è coerente con la regola di produzione nome-seq.

Approccio Compilato

Nello sviluppo di software, l'approccio compilato prevede la traduzione completa del codice sorgente in linguaggio macchina prima dell'esecuzione.

Fasi dello Sviluppo

1. Editing: Scrittura del testo del programma (codice sorgente) tramite un editor e memorizzazione su supporti permanenti (es. Hard Disk).
2. Compilazione e Linking:
   • Il Compilatore traduce il codice sorgente in codice oggetto (non ancora eseguibile).
   • Il Linker unisce il codice oggetto con le librerie necessarie per creare il programma eseguibile finale.
3. Esecuzione: Il sistema operativo carica l'eseguibile in memoria centrale (RAM) e la CPU lo esegue.

Il Compilatore

È il software responsabile della traduzione. Il suo lavoro si divide in due macro-fasi:

Esempi di linguaggi compilati: C, C++, Fortran, Rust, Go.

L'Approccio Compilato in C++

Il C++ utilizza un modello di compilazione "ahead-of-time" (AOT). A differenza di altri linguaggi, il processo trasforma il testo in un binario specifico per l'architettura hardware di destinazione.

Dettaglio delle Fasi di Build

1. Pre-elaborazione (Preprocessing): Prima della compilazione vera e propria, il Preprocessore analizza le direttive che iniziano con #.
   • Risolve le inclusioni (#include) copiando il contenuto degli header nel file.
   • Sostituisce le macro (#define).
   • Gestisce la compilazione condizionale (#ifdef).
   Output: Un file sorgente "espanso" (pure C++ code).
2. Compilazione (Analisi e Traduzione): Il compilatore trasforma il codice espanso in linguaggio assembly e poi in codice oggetto (file .obj o .o).
   • Analisi Semantica: Il C++ è un linguaggio a tipizzazione forte; qui il compilatore verifica che le operazioni siano coerenti con i tipi di dati (es. non si può sommare una stringa a un intero).
   • Ottimizzazione: Il compilatore riorganizza le istruzioni per massimizzare la velocità o ridurre l'occupazione di memoria.
3. Linking (Collegamento): Il Linker è l'architetto finale. Spesso un progetto C++ è diviso in molti file;
   il linker:
   • Risolve i riferimenti esterni (se il file A usa una funzione definita nel file B).
   • Collega le Librerie Standard (es. iostream).
   • Genera il file Eseguibile (.exe su Windows, out su Unix).

Dove avviene l'errore?

Capire in quale fase si interrompe il processo è fondamentale per il debugging:

Approccio Interpretato

A differenza dell'approccio compilato, l'approccio interpretato non produce un file eseguibile separato prima dell'uso. Il codice sorgente viene analizzato ed eseguito direttamente, istruzione per istruzione, da un programma chiamato Interprete.

Fasi dello Sviluppo

1. Editing: Scrittura del testo del programma e memorizzazione su supporti permanenti.
2. Interpretazione: L'interprete legge il sorgente e lo esegue "al volo".

L'Interprete

L'interprete cicla continuamente attraverso queste due fasi per ogni porzione di codice:

Esempi di linguaggi interpretati: Python, Matlab, Javascript.

Rappresentazione dell'Informazione

L’informazione è qualcosa di astratto. Per poterla manipolare è necessario rappresentarla.

All'interno di un calcolatore, i vari tipi di informazione (testi, figure, numeri, musica, ecc.) vengono rappresentati per mezzo di sequenze di bit.

Rappresentazione dei Caratteri

Codifica ASCII

La codifica standard è l'ASCII (American Standard Code for Information Interchange). Utilizza 7 bit per rappresentare 128 caratteri (lettere inglesi, numeri, simboli e caratteri di controllo).

ASCII Esteso:

• Contiene ulteriori 128 caratteri (da 128 a 255), per un totale di 256 caratteri.
• Richiede 8 bit (ossia 1 Byte).
• Per i caratteri standard (0-127), il bit più significativo (MSB) vale 0.

Tabella ASCII Standard (Completa 0-127)

Conversioni in basi diverse

I numeri naturali maggiori o uguali alla base β possono essere rappresentati in maniera unica da una sequenza di cifre secondo la rappresentazione posizionale.

Se un numero naturale N ≥ β è rappresentato in base β dalla sequenza di cifre:

a_p-1 a_p-2 ... a₁ a₀

allora N può essere espresso tramite la "formula della sommatoria":

• a₀ è detta "cifra meno significativa" (LSB - Least Significant Bit/Digit).
• a_p-1 è detta "cifra più significativa" (MSB - Most Significant Bit/Digit).

Conversione Binario → Decimale (Somma Pesata)

Per convertire da base 2 a base 10, si moltiplica ogni cifra binaria per la potenza di 2 corrispondente alla sua posizione (partendo da 0 a destra).

Conversione Decimale → Binario (Divisioni Successive)

Per convertire un numero decimale in binario, si divide ripetutamente il numero per 2 e si prendono i resti in ordine inverso (dall'ultimo al primo).

Esempio 1: Convertire 1310

13 / 2 = 6  con resto 1  ^
 6 / 2 = 3  con resto 0  |
 3 / 2 = 1  con resto 1  | Leggi i resti
 1 / 2 = 0  con resto 1  | dal basso verso l'alto

Risultato: 11012

Esempio 2: Convertire 4210

42 / 2 = 21 con resto 0  ^
21 / 2 = 10 con resto 1  |
10 / 2 = 5  con resto 0  |
 5 / 2 = 2  con resto 1  |
 2 / 2 = 1  con resto 0  |
 1 / 2 = 0  con resto 1  |

Risultato: 1010102

L'Overflow (Traboccamento)

Il calcolatore lavora con un numero finito di bit (fissato dall'hardware o dal tipo di dato, es. 16 bit, 32 bit). Quando il risultato di un'operazione supera il valore massimo rappresentabile con quei bit, si verifica un Overflow.

Esempio pratico (con 16 bit)

Supponiamo di avere p = 16 bit. Il valore massimo rappresentabile (senza segno) è 65.535 ( 2¹⁶-1 ).

  A = 30421 (0111011011010101)
+ B = 43127 (1010100001110111)
------------------------------
TOT = 73548

Il risultato reale (73548) è maggiore del massimo consentito (65535).
In binario, 73548 richiede 17 bit:

Il 17° bit viene "perso". Il computer memorizza solo i 16 bit rimanenti, quindi il risultato sembrerà essere 8012 invece di 73548. Un errore gravissimo!

Aritmetica Binaria

Le operazioni nel sistema binario funzionano in modo analogo a quello decimale, ma sono più semplici poiché ci sono solo due cifre (0 e 1).

Somma Binaria

Si mettono i numeri in colonna allineandoli a destra. Si sommano le cifre colonna per colonna, partendo da destra, tenendo conto dei riporti.

Esempio: 101100 + 111010

  1 1 1       ← Riporti
  1 0 1 1 0 0 +
  1 1 1 0 1 0 =
-------------
1 1 0 0 1 1 0

Sottrazione Binaria

Anche qui si allinea a destra. Se la cifra superiore è minore di quella inferiore (0 - 1), si prende in prestito una unità dalla colonna a sinistra.

Esempio: 11001 - 01011

   0 1 1 0      ← Prestiti (il 1 diventa 0, lo 0 diventa 10 cioè 2)
  1 1 0 0 1 -
  0 1 0 1 1 =
-----------
  0 1 1 1 0

Moltiplicazione Binaria

È molto più semplice di quella decimale perché le cifre sono solo 0 o 1. Non servono tabelline: o si copia il numero (se x1) o si scrive zero (se x0).

Procedimento: Si moltiplica il primo fattore per ogni cifra del secondo, scalando (shift) verso sinistra ogni volta, e infine si sommano i risultati parziali.

Esempio: 1011 × 101

      1 0 1 1 ×
        1 0 1 =
-------------
      1 0 1 1   (1011 × 1)
    0 0 0 0 -   (1011 × 0) - Shift a sx
  1 0 1 1 - -   (1011 × 1) - Shift a sx
-------------
  1 1 0 1 1 1   (Somma finale)

Divisione Binaria

Simile alla divisione in colonna decimale (Euclidea). Si abbassano le cifre del dividendo e si controlla se il divisore "ci sta".

In binario è facile: il divisore "ci sta" solo 1 volta o 0 volte.

Esempio: 11011 : 11 (27 : 3 = 9)

1 1 0 1 1 | 1 1    ← Divisore
1 1       |-------
---       | 1 0 0 1  ← Quoziente (Risultato)
0 0 0     |
    0     | (11 in 0 non ci sta -> scrivo 0)
  ---     |
    0 1   | (abbasso 1)
      0   | (11 in 1 non ci sta -> scrivo 0)
    ---   |
      1 1 | (abbasso 1)
      1 1 | (11 in 11 ci sta 1 volta -> scrivo 1)
      ---
        0   ← Resto

Rappresentazione in Modulo e Segno

È il metodo più intuitivo per rappresentare numeri interi con segno. Il bit più a sinistra (MSB) viene usato per il segno, mentre gli altri rappresentano il valore assoluto.

Esempi (con p = 4 bit)

a = +3
Segno (0) | Modulo (3 -> 011)
Risultato: 0011

a = -3
Segno (1) | Modulo (3 -> 011)
Risultato: 1011

Decodifica (da Binario a Decimale)

Per convertire una sequenza A = (a_(p-1), a_(p-2)...a₍₀₎) in intero:

a = (a_p-1 == 0) ? +a : -a

Tabella dei Valori (p = 4 bit)

Range rappresentabile: da -(2^p-1 - 1) a +(2^p-1 - 1) (es. da -7 a +7).

Rappresentazione in Complemento a 2

Perché i calcolatori utilizzano il CA2?

Il Complemento a due è diventato lo standard universale per tre ragioni fondamentali che ottimizzano l'architettura della CPU:

• Unicità dello Zero: A differenza della rappresentazione in Modulo e Segno (che genera sia +0 che -0), nel CA2 esiste una sola sequenza di bit per lo zero. Questo elimina ambiguità logiche e semplifica drasticamente i circuiti di confronto.
• Semplificazione dell'Hardware (L'Addizionatore): Il vantaggio principale è economico e progettuale: non serve un circuito dedicato alla sottrazione. La CPU calcola A - B come A + (-B). Poiché l'operazione per rendere negativo un numero è quasi istantanea a livello di transistor, il computer usa lo stesso identico componente (ALU Addizionatore) per entrambe le operazioni.
• Gestione coerente dei pesi: Il bit più a sinistra (MSB) continua a indicare il segno (0 per positivo, 1 per negativo), ma assume un valore matematico pari a -2^n-1. Questo permette di trattare tutti i bit con una logica aritmetica uniforme.

1. Codifica (da intero a a bit A)

Dato un numero intero a e un numero di bit p:

Esempi (con p = 4 bit, 2⁴ = 16):

a = +7
Poiché è positivo -> Binario di 7 su 4 bit
A = 0111

a = -1
Poiché è negativo -> Calcolo 16 - |-1| = 15
Binario di 15 su 4 bit
A = 1111

a = -8
Poiché è negativo -> Calcolo 16 - |-8| = 8
Binario di 8 su 4 bit
A = 1000

2. Decodifica (da bit A a intero a)

Per capire che numero rappresenta una sequenza di bit:

• Se il bit più significativo (a_p-1) è 0: Il numero è positivo e vale semplicemente il valore binario.
• Se il bit più significativo (a_p-1) è 1: Il numero è negativo. Il suo valore è -(2^p - A), oppure si applica il peso negativo al bit più alto (-2^p-1).

A = 0111 (MSB è 0)
Valore = +7

A = 1111 (MSB è 1, quindi negativo)
Valore A come unsigned = 15
a = -(16 - 15) = -1

Tabella dei Valori (p = 4 bit)

Notare che esiste un solo zero e il range è asimmetrico: [-8, +7].

Rappresentazione con Bias (o Eccesso K)

In questa rappresentazione, il range dei numeri interi viene "traslato" (spostato) aggiungendo una costante positiva detta Bias (o Eccesso), in modo da ottenere sempre un numero non negativo.

È molto utilizzata per rappresentare gli esponenti nei numeri reali (standard IEEE 754).

Esempi (con p = 4 bit):
Il Bias vale 2^4-1 - 1 = 2³ - 1 = 7.

a = 0   => A = 0 + 7 = 7   (0111)
a = 1   => A = 1 + 7 = 8   (1000)
a = -1  => A = -1 + 7 = 6  (0110)
a = -7  => A = -7 + 7 = 0  (0000)
a = 8   => A = 8 + 7 = 15  (1111)

Tabella dei Valori (p = 4 bit, Bias = 7)

L'intervallo rappresentabile è [-Bias, Bias + 1], ovvero [-7, +8].

Rappresentazione Numeri Reali

Virgola Fissa

In questa rappresentazione, si utilizza un numero fisso di bit per la parte intera e un numero fisso di bit per la parte frazionaria.

Algoritmo di Conversione

Il numero reale viene diviso in due parti: I (intera) e F (frazionaria).

1. Parte Intera: Si converte con il metodo standard (divisioni successive per 2).
2. Parte Frazionaria: Si usa il metodo delle moltiplicazioni successive:
   • Si prende la parte frazionaria e la si moltiplica per 2.
   • La parte intera del risultato diventa il bit (0 o 1).
   • Si ripete l'operazione sulla nuova parte frazionaria ottenuta.
   • Ci si ferma quando la parte frazionaria è 0 o si sono finiti i bit f disponibili.

Esempio 1: Conversione Esatta

Convertire 331.6875 (con p=16 e f=5).

1. PARTE INTERA (331):
   331 in binario = 101001011 (9 bit)

2. PARTE FRAZIONARIA (0.6875):
   0.6875 * 2 = 1.375  -> Bit: 1
   0.375  * 2 = 0.75   -> Bit: 0
   0.75   * 2 = 1.5    -> Bit: 1
   0.5    * 2 = 1.0    -> Bit: 1
   (Resto 0, fine)
   Binario Frazionario = 1011

3. UNIONE (su 16 bit totali, f=5):
   Intero: 00101001011 (padding a 11 bit)
   Frazion.: 10110       (padding a 5 bit)
   
   Risultato: 00101001011.10110

Esempio 2: Errore di Troncamento (Periodicità)

Convertire 2.3 (con f=6).

Alcuni numeri decimali finiti possono diventare periodici in binario, richiedendo infiniti bit.

1. PARTE INTERA (2):
   2 in binario = 10

2. PARTE FRAZIONARIA (0.3):
   0.3 * 2 = 0.6  -> Bit: 0
   0.6 * 2 = 1.2  -> Bit: 1
   0.2 * 2 = 0.4  -> Bit: 0
   0.4 * 2 = 0.8  -> Bit: 0
   0.8 * 2 = 1.6  -> Bit: 1
   0.6 * 2 = 1.2  -> Bit: 1
   ... (si ripete la sequenza 1001) ...

   Binario (infinito): 0.010011001...

Numeri Reali: Virgola Mobile (IEEE 754)

Lo standard IEEE 754 definisce come rappresentare i numeri reali nel calcolatore usando la notazione scientifica normalizzata in base 2.

Un numero reale è rappresentato dalla tripla: (Segno, Esponente, Mantissa).

Formati Standard

Esempi (Half Precision)

Consideriamo 16 bit: 1 segno, 5 esponente (Bias=15), 10 mantissa.

1. Decodifica (da Binario a Reale)

R = 0 01111 0000000001

Segno (s): 0 -> Positivo (+)
Esponente (E): 01111 (15) -> e = 15 - 15 = 0
Mantissa (F): ...001 -> f = 2^-10 (circa 0.00097)

Calcolo:
r = +1.00097 * 2^0 = +1.00097

2. Codifica (da Reale a Binario)

Convertire r = 2.3 in Half Precision.

1. Virgola Fissa: 
   2.3 = 10.010011001... (periodico)

2. Normalizzazione (sposto virgola dopo il primo 1):
   1.0010011001... * 2^1

3. Calcolo Esponente E:
   e = 1
   E = e + Bias = 1 + 15 = 16 -> 10000

4. Mantissa F (prendo 10 bit dopo la virgola):
   0010011001

Risultato R:
0 10000 0010011001