Appunti di Fondamenti di Informatica

Università degli Studi di Napoli "Federico II" - Ingegneria Informatica

Fondamenti d'informatica

L'informatica è la scienza della rappresentazione e dell'elaborazione dell'informazione. L'algoritmo è un procedimento che risolve un determinato problema attraverso un numero finito di passi. L'informazione è un dato associato a una determinata semantica (significato). Il dato è un valore che appartiene a un determinato tipo. Il tipo è un insieme di valori a cui è associato una determinata funzione.

Teorema di De Morgan

NOT (A OR B) = NOT A AND NOT B
NOT (A AND B) = NOT A OR NOT B

Proprietà dell'algebra booleana

• Commutativa: A OR B = B OR A --- A AND B = B AND A
• Associativa: (A OR B) OR C = A OR (B OR C) --- (A AND B) AND C = A AND (B AND C)
• Idempotenza: A OR A = A --- A AND A = A
• Assorbimento: A OR (A AND B) = A --- A AND (A OR B) = A
• Distributiva: A OR (B AND C) = (A OR B) AND (A OR C) --- A AND (B OR C) = (A AND B) OR (A AND C)
• Esistenza di minimo e massimo: A OR V = V --- A AND F = F
• Esistenza del complemento: A OR NOT A = V --- A AND NOT A = F

Codifica e rappresentazione

La codifica è una funzione che associa elementi dell'insieme D ad elementi dell'insieme R. L'insieme D è l'insieme che contiene gli elementi che devono essere codificati. L'insieme R è l'insieme che contiene le possibili parole codice generate dal prodotto cartesiano in cui R è un insieme che ha valori {0, 1}, mentre m è un esponente tale che .2^m.

La rappresentazione è una specifica codifica utilizzata per un determinato tipo di dato. Un codice che non utilizza tutte le parole codice è detto incompleto. Un codice che utilizza più parole codice per uno stesso dato è detto ridondante.

Intervallo di numeri rappresentabili

• Intervallo di numeri naturali rappresentabili con n bit: [0, 2ⁿ-1]
• Rappresentazione in segno e modulo:
  8 bit [ ][ ][ ][ ][ ][ ][ ]
  +/- 2⁶ 2⁵ 2⁴ 2³ 2² 2¹ 2⁰
  Il primo bit viene utilizzato per stabilire il segno del valore, gli altri sette per definire il modulo del valore in binario.
• Intervallo di numeri relativi rappresentabili con n bit (Segno e modulo): [-2^n-1 - 1, 2^n-1-1]
• Rappresentazione in complementi alla base:
  8 bit [ ][ ][ ][ ][ ][ ][ ][ ]
  -2⁷ 2⁶ 2⁵ 2⁴ 2³ 2² 2¹ 2⁰
  Il valore viene convertito in binario, ma il primo bit viene utilizzato per rappresentare i valori negativi, infatti, alla rappresentazione in binario sugli altri sette bit, somma un valore di -2^n-1.
• Intervallo di numeri relativi rappresentabili con n bit (Complementi alla base): [-2^n-1, 2^n-1-1]

Nei calcolatori si utilizza maggiormente la rappresentazione in complementi alla base in quanto l'operazione della somma algebrica si esegue semplicemente con un algoritmo che prevede la somma algebrica dei valori in binario, mentre invece la rappresentazione in segno e modulo richiede un algoritmo più complesso e con un maggior numero di passi.

Gestione dell'overflow

L'overflow è un problema che si verifica quando il numero che si vuole rappresentare è esterno all'intervallo dei numeri rappresentabili da n bit. Se in un algoritmo di somma algebrica il riporto entrante e il riporto uscente dell'ultima addizione sono uguali, allora non si verifica un overflow.

Codifica ASCII

• 0 – 31: Codici di controllo
• 32 – 47: Caratteri speciali e segni d'interpunzione
• 48 – 57: Cifre da ‘0’ a ‘9’
• 58 – 64: Caratteri speciali e segni d'interpunzione
• 65 – 90: Lettere da ‘A’ a ‘Z’
• 91 – 96: Caratteri speciali e segni d'interpunzione
• 97 – 122: Lettere da ‘a’ a ‘z’
• 123 – 126: Caratteri speciali
• 127: Codice di controllo

Modello dell'automa a stati finiti (ASF)

Il modello dell'automa a stati finiti (ASF) è un modello che permette di descrivere con precisione e in maniera formale il comportamento di molti sistemi. L'ASF è una quintupla. Ovvero si può descrivere attraverso la specifica di cinque insiemi:

• I = Insieme degli ingressi
• U = Insieme delle uscite
• Q = Insieme degli stati
• τ: Q × I → Q = Funzione di transizione, definita come e che riceve un ingresso in un determinato stato e determina lo stato successivo
• ω: Q × I → U = Funzione delle uscite, definita come e che riceve un ingresso in un determinato stato e determina un'uscita

Si può descrivere in maniera univoca un automa a stati finiti con una tabella delle transizioni o con un grafo orientato delle transizioni.

La macchina di Turing (MdT)

La macchina di Turing (MdT) è un modello astratto che definisce una macchina in grado di eseguire...