Appunti completi di Fondamenti di informatica

Informatica

• Elaborazione automatica: insieme di processi eseguiti da un'unità elettronica/digitale automatica (elaboratore o calcolatore elettronico) su dei dati in ingresso (input) per ottenere dei risultati in uscita (output).
• L'insieme dei processi, routine e operazioni da eseguire deve essere comunicato all'elaboratore attraverso un linguaggio comprensibile ed eseguibile dall'elaboratore stesso.
• Algoritmo: procedura per risolvere un generico problema (se risolvibile) con un numero finito di passi ovvero attraverso un set finito di istruzioni che, applicate ai dati in ingresso, li trasformano nei risultati del problema in uscita.
• Programma: implementazione di un algoritmo in un linguaggio comprensibile ed eseguibile dall'elaboratore, utilizzando dei linguaggi di programmazione.

Passi necessari per creare un programma (algoritmo eseguibile dal calcolatore) per risolvere un generico problema:

1. Analisi e modellazione del problema
2. Implementazione dell'algoritmo attraverso un linguaggio formale, definendo:
   • operazioni (operatori, funzioni, procedure)
   • oggetti sui quali effettuare le operazioni (dati)
3. Codifica dell'algoritmo nel linguaggio di programmazione

I linguaggi di programmazione sono detti "simbolici e di alto livello"

• uso di simboli per rappresentare variabili e operatori
• elevato livello di astrazione

Per essere eseguiti dal calcolatore, le istruzioni di alcuni programmi scritti in linguaggi di alto livello (come in C) devono essere tradotte in linguaggio a "basso livello" da un programma dedicato, chiamato compilatore.

Poi, per essere eseguite, le istruzioni in linguaggio di basso livello devono essere tradotte in "linguaggio macchina" da un programma assemblatore.

Diagramma di flusso

• operazioni da compiere sui dati => blocchi
• la sequenza nella quale devono essere compiute le suddette operazioni => frecce

Blocchi

• blocco di inizio (start) e blocco di fine (end)
• blocco di azione e elaborazione output
• blocco di input/output (I/O) e lettura/scrittura
• condizionale o decisionale

Condizioni di validità generale

• deve essere sempre presente un blocco di inizio e uno di fine
• ogni freccia deve entrare in un blocco
• dal blocco di inizio deve essere possibile raggiungere qualsiasi altro blocco dell’algoritmo
• da ogni blocco dell’algoritmo deve essere possibile raggiungere il blocco di fine

Condizioni di validità specifiche

• blocco azione o blocco di input/output
• ogni azione o I/O ha 1 sola freccia entrante e 1 sola uscente
• blocco condizionale ha 1 sola freccia entrante e 2 frecce uscenti

esempio: calcolo del fattoriale di un numero intero n

1. Rappresentazione
• Tipi: linguaggio C rappresenta i dati attraverso tipi
• Tipi elementari del C:
  • int: numeri interi rappresentati mediante un numero di byte dipendenti dall'architettura del processore (32, 64 bit)
    • ES. numeri interi (con segno) su 4 Byte (32 bit): [-2³¹ ; 2³¹-1]
  • Float: numeri razionali a virgola mobile (floating point)
  • double: con precisione doppia rispetto ai FLOAT
  • char: caratteri rappresentati su 8 bit (256 caratteri set del codice ASCII)
  • void: tipo nullo usato quando la sintassi del linguaggio richiede di specificare un tipo di dato ma la semantica non lo prevede

Diagramma di flusso

int sum;

int count;

sum = 0;

1. For (count = 1; count <= 10; count = count + 1)
2. sum = sum + count

Se qua metto una = è come se facessi una "lista"

1. For (int count = 0; int sum = 0; count < 5; count++)

Indica che quello dopo è un'altra espressione di assegnamento

Ciclo WHILE

Esecuzione ripetitiva di un corpo di istruzioni fintantochè un'istruzione di guardia restituisce un valore vero

1. int count, sum;
2. count = 1;
3. sum = 0;
4. while (count <= 10) {
5. sum = sum + count;
6. count = count + 1;
7. }

oppure scrivo solo count++

scrivo:

1. count++
2. count = count + 1

Ciclo Do-WHILE

Esecuzione simile al ciclo WHILE, ma con la condizione di guardia in coda al corpo delle istruzioni

1. int count, sum;
2. count = 1;
3. sum = 0;
4. do {
5. sum = sum + count;
6. count = count + 1;
7. } while (count <= 10)
8. espressione di guardia

Tabella per la conversione tra base 16, 10, 2

• Base 10: 0 | Base 16: 0 | Base 2: 0000
• Base 10: 1 | Base 16: 1 | Base 2: 0001
• Base 10: 2 | Base 16: 2 | Base 2: 0010
• Base 10: 3 | Base 16: 3 | Base 2: 0011
• Base 10: 4 | Base 16: 4 | Base 2: 0100
• Base 10: 5 | Base 16: 5 | Base 2: 0101
• Base 10: 6 | Base 16: 6 | Base 2: 0110
• Base 10: 7 | Base 16: 7 | Base 2: 0111
• Base 10: 8 | Base 16: 8 | Base 2: 1000
• Base 10: 9 | Base 16: 9 | Base 2: 1001
• Base 10: 10 | Base 16: A | Base 2: 1010
• Base 10: 11 | Base 16: B | Base 2: 1011
• Base 10: 12 | Base 16: C | Base 2: 1100
• Base 10: 13 | Base 16: D | Base 2: 1101
• Base 10: 14 | Base 16: E | Base 2: 1110
• Base 10: 15 | Base 16: F | Base 2: 1111

Conversione di parti frazionarie

Una parte frazionaria è un numero razionale minore dell'unità; anche per convertire la parte frazionaria si possono seguire i 2 diversi approcci. Cioè usando la base di partenza o di arrivo.

1. Algoritmo di conversione che impiega l'algoritmo della base di arrivo.

_[0.7]10 = _[7]10 = _[0.101110]2

2. Algoritmo di conversione che applico la base di partenza.

Considiamo un numero razionale X minore di 1:

0 ≤ X ≤ 1 ^=⇒ X = ∑ _k a_k ⋅ 2^-k a_k ∈ {0,1}

a_k può assumere solo il valore 0 oppure il valore 1

La caratteristica c si rappresenta in forma polarizzata (anziché in complemento a 2 come gli interi con segno)

Questa rappresentazione è detta anche rappresentazione in eccesso 127

c ∈ [-(2^e-1), 2^e-1] = [-127, 128] , e = c + (2^e-1) = c + 127

⇒ e ∈ [0, 255]

• Il caso e = 0 (c = -127), m = 0, s = 0 codifica il valore +0;
• Il caso e = 0 (c = -127), m = 0, s = 1 codifica il valore -0;
• Il caso e = 0 (c = -127), m ∈ (0, 1], rappresenta numero denormalizzato;
• Il caso e = 255 (c = 128), m ∈ (0, 1], rappresenta un valore non accettabile (NaN: Not a Number);
• Il caso e = 255 (c = 128), m = 0, s = 0 codifica +∞;
• Il caso e = 255 (c = 128), m = 0, s = 1 codifica -∞;
• c ∈ [1, 254] (c ∈ [-126, 127]), m ∈ [1, 2), s ∈ {0, 1}, rappresenta un numero normalizzato;

I numeri con caratteristica c ∈ [-126, 127] (⟺ e ∈ [1, 254]) prendono il nome di numeri normalizzati.

Il minimo ordine di grandezza rappresentabile per i numeri normalizzati è: 2^-126

⇒ 1 ⋅ 2^-126 = 2^-126

Il massimo ordine di grandezza rappresentabile è: 2¹²⁷ (un valore molto elevato, che di fatto risolve il problema dell'overflow)

Un numero normalizzato codifica il seguente numero decimale:

(-1)^s ⋅ (1 + 0.m) ⋅ 2^c

ovvero

m ∈ [1, 2), e ∈ [1, 254] ⇒ c ∈ [-126, 127] ⇒ m ⋅ 2^c ∈ [2^-126, 2¹²⁸]

Considerando che s ∈ {0, 1} l'intervallo di numeri rappresentati è dato da:

[-2¹²⁸, -2^-126] ∪ [2^-126, 2¹²⁸]

I valori che stanno oltre questi intervalli sono numeri troppo grandi per essere rappresentati ⇒ appartengono all'intervallo di overflow: (-∞, -2¹²⁸] ∪ [2¹²⁸, +∞)

I valori che rientrano tra questi due intervalli sono numeri troppo piccoli per essere rappresentati ⇒ appartengono all'intervallo di underflow: (-2^-126, 2^-126)