Appunti Informatica

Fondamenti di informatica 28/02

Elaboratore, algoritmi, programmi e linguaggi

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).

Algoritmo: procedura per risolvere un generico problema (se risolvibile) 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 una specifica sintassi che dipende dal linguaggio di programmazione.

Infatti, l'insieme dei processi, routine e operazioni da eseguire deve essere comunicato all'elaboratore attraverso un linguaggio comprensibile ed eseguibile dall'elaboratore stesso.

Solitamente i linguaggi di programmazione sono quello:

• Simbolico: uso di simboli per rappresentare variabili e operatori
• Di alto livello: elevato livello di astrazione, maggiore espressività.

Per essere eseguiti dal calcolatore, le istruzioni di alcuni programmi scritti in linguaggi di alto livello devono essere tradotte in linguaggio a basso livello dal compilatore. Successivamente le istruzioni in linguaggio di basso livello, per poter essere eseguite, devono essere ulteriormente tradotte in linguaggio macchina dall’assemblatore.

Formalizzazione di un problema attraverso algoritmi

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...), dati e codifica dell'algoritmo nel linguaggio di programmazione.

Condizioni di validità per un diagramma di flusso (flow-chart)

Condizioni di validità generale:

• Deve esistere 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 e da ogni blocco deve essere possibile raggiungere il blocco di fine

Condizioni specifiche:

• Il blocco di elaborazione (rettangolo) e di input/output (parallelogramma) devono avere una sola freccia in entrata e una sola freccia in uscita
• Il blocco di controllo (romboidale) deve avere una sola freccia in entrata e due frecce in uscita
• Vedi ex. fattoriale del numero intero N –

La rappresentazione dà ad un algoritmo una forma che può essere eseguita su un elaboratore. In questo assume un ruolo fondamentale il linguaggio di programmazione (come il linguaggio C).

Rappresentazione: tipi, variabili e costanti

Il linguaggio C rappresenta i dati attraverso tipi. Un tipo è caratterizzato dall’insieme dei valori che rappresenta e dall’insieme delle operazioni che si possono effettuare su tali valori. I tipi sono invariabili.

I tipi elementari del C sono:

• unsigned int, int = numeri interi rappresentati mediante un numero di byte dipendente dall'architettura del processore (32, 64 bit) - Vedi interi a 32 bit -
• float = numeri razionali in virgola mobile (floating point)
• double = numeri razionali in virgola mobile 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

In C non esistono valori booleani ma sono sostituiti da numeri interi: lo zero O codifica il valore booleano “false”, qualsiasi altro intero con valore diverso da zero (tipicamente 1) codifica il valore booleano “true”.

Variabile: locazione di memoria che contiene un valore di un tipo. Il valore può variare durante la computazione. Una variabile è associata anche ad un nome che permette di riferirsi ad essa senza doverne specificare l’indirizzo fisico in memoria. Il nome della variabile può essere una qualsiasi sequenza di caratteri alfabetici e/o numerici (con uso di _ ) a patto che il primo carattere del nome della variabile non sia numerico. La lunghezza della sequenza è arbitraria ma il compilatore non distingue tra variabili i cui nomi sono formati da sequenze che non differiscono sui primi 32 caratteri.

Il nome viene associato alla variabile tramite una dichiarazione. (ex. int n; ex2. float media; )

Per associare un valore ad una variabile si ricorre ad un'assegnazione. (ex. n=10; ex2. media=25.5f; )

Variabile array: insieme di variabili dello stesso tipo che possono essere referenziate tramite un nome collettivo e un indice che le identifica (denotandone lo scostamento, od offset, rispetto all'inizio dell'array).

Ex. int V[10];

V[0] è il riferimento alla prima variabile dell'array

V[9] è il riferimento all'ultima variabile dell'array

V, oltre ad essere il nome della variabile array, rappresenta anche l'indirizzo di memoria a partire dal quale l'array è memorizzato. – Vedi ex variabile array –

Costante: valore di un certo tipo che non cambia durante la computazione. Le costanti non possono essere modificate all'interno del programma e sono rappresentate in maniera diversa a seconda del tipo:

int: 10 float: 43.25f double: 43.25

#define PI 3.141592 (no ; dopo) const int max speed = 130;

In particolare, #define è una direttiva a livello di pre-processore: prima di eseguire la compilazione, il compilatore sostituisce tutte le istanze delle costanti con il loro valore. Viene così definito un identificatore tramite cui la costante sia utilizzabile da tutto il codice del programma.

const definisce una variabile di sola lettura che non può essere modificata all'interno del programma.

Rappresentazione: operatori ed espressioni

Espressione: combinazione di variabili e costanti attraverso degli operatori. Il calcolo di un’espressione restituisce un valore e produce un effetto sui dati

Side-effect (effetto collaterale): effetto sui dati prodotto dal calcolo di un’espressione; sono una componente del linguaggio. Un esempio è l’assegnamento (=). In C i dati sono elaborati proprio attraverso i side-effects.

Operatori: sono classificati per tipo di operazione:

• Aritmetici: + - * / %
• Relazionali: < <= == >= > !=
• Logici: && || !
• Incremento e decremento: ++ -- - Vedi operatori –

Rappresentazione: istruzioni

Istruzioni: determinano la sequenza delle espressioni da eseguire e quindi il flusso di lavoro del programma.

L'esecuzione di un'istruzione consiste nel calcolare l'espressione, producendone i side-effects, e poi passare il controllo del flusso del programma all'istruzione successiva.

L’esecuzione di un’istruzione avviene:

• Tramite sequenza di istruzioni semplici: un'espressione seguita da punto e virgola ( ; )
• Con istruzioni Compound: un’espressione raccolta entro parentesi graffa { … }, la sua utilità è di trattare le istruzioni in maniera unitaria. - Vedi ex. rappresentare le istruzioni –

Rappresentazione: istruzioni condizionali

Istruzioni condizionali: permettono di decidere direzioni diverse nel flusso di esecuzione di un’istruzione (corpo) del programma in base al valore restituito da un’espressione di controllo (guardia).

Sono: - Vedi ex. –

• La Clausola IF: condiziona il corpo alla guardia (se il corpo restituisce un vero allora viene eseguita l’istruzione, in caso contrario si passa all’istruzione successiva);
• La Clausola IF-ELSE: permette di avere due corpi alternativi che vengono eseguiti a seconda che la guardia restituisca un vero o un falso. 1/3

Rappresentazione: istruzioni di iterazione (loop)

Sono le istruzioni che permettono di rieseguire in maniera ripetitiva un corpo di istruzioni fino al verificarsi di una certa condizione sui valori delle variabili del programma. Sono tre (equivalenti dal punto di vista semantico):

• Ciclo FOR: esecuzione ripetitiva di un corpo di istruzioni sotto il controllo di una guardia costituita da 3 espressioni: assegnamento, guardia, incremento. L’assegnamento viene eseguito una sola volta, ad ogni iterazione viene testata l’espressione di guardia e, se la condizione è verificata, viene eseguito il corpo, l’espressione incremento e si torna al punto di ingresso dell’iterazione. Se restituisce falso, l’iterazione termina e si passa all’istruzione successiva.
• Ciclo WHILE: esecuzione ripetitiva di un corpo di istruzioni fintanto che un’espressione di guardia restituisce un valore VERO. La guardia viene eseguita, poi se il valore è vero viene eseguito il corpo e l’esecuzione ritorna all’ingresso della guardia; se è falso il controllo passa all’istruzione successiva.
• Ciclo DO – WHILE: esecuzione simile al ciclo WHILE, ma con la condizione di guardia in coda al corpo delle istruzioni invece che in testa. Prima si esegue il corpo, poi se la guardia restituisce un vero si torna ad eseguire il corpo, se restituisce un falso si passa all’istruzione successiva.

- Vedi esempi –

Quando in un programma troviamo i simboli:

• /* e */ tutto quello racchiuso tra essi è irrilevante ai fini dell’esecuzione del programma;
• // tutto quello che appare fino alla fine della linea è un commento. Se si estende su più linee si deve ripetere il simbolo su ciascuna di esse.

Rappresentazione dei dati: numeri, codifica posizionale, rappresentazione binaria

Numero: ente caratterizzato da un suo significato intrinseco e che può essere descritto tramite rappresentazioni differenti che dipendono dalla combinazione di più convenzioni:

• Posizionalità della codifica: un numero rappresentato con una codifica posizionale è un numero nel quale il peso di ciascuna cifra dipende dalla posizione che quella cifra occupa nella rappresentazione del numero;
• Base di rappresentazione;
• Numero di cifre che si hanno a disposizione per la rappresentazione;
• Codifica del segno;
• Rappresentazione di parti frazionarie e valori razionali.

Codifica posizionale: la codifica di un insieme di numeri avviene attraverso una base finita di cifre (nella codifica decimale le cifre da 0 a 9), che serve a rappresentare anche tutti gli altri numeri combinando più cifre sulla base di una notazione posizionale (il peso delle cifre dipende dalla loro posizione).

Differenti convenzioni/notazioni:

• Little Endian: in ultima posizione si trova la cifra meno significativa (Least Significant Digit LSD).
• Big Endian: in ultima posizione si trova la cifra più significativa (Most Significant Digit MSD).

- Vedi ex. codifica posizionale –

La base di numerazione a cui siamo abituati è quella in base 10 ma l’elaboratore utilizza la base 2.

Rappresentazione binaria: è la minima base che include cifre diverse (0 e 1), e che quindi può rappresentare i numeri in maniera posizionale, semplificando inoltre l’implementazione di algoritmi da parte dell’unità aritmetico logica del processore.

L’algoritmo di conversione della base di rappresentazione di un numero si basa su:

• 1. Ottenere la rappresentazione polinomiale del numero nella base di partenza
• 2. Effettuare la conversione di coefficienti e potenze nella base di arrivo
• 3. Eseguire somme e prodotti nella base di arrivo

La conversione base di rappresentazione può avvenire sfruttando l’aritmetica della base di arrivo o con l’algoritmo dei resti successivi.

• Aritmetica base di arrivo: per effettuare la conversione da base 10 a base 2, il numero iniziale viene sviluppato in forma polinomiale nella base di partenza, i singoli coefficienti e le potenze che ne risultano sono convertiti nella base di arrivo e successivamente si sommano e si moltiplicano i dati ottenuti nella base di arrivo.
• Algoritmo dei resti successivi: algoritmo di codifica della base di rappresentazione che sfrutta l’aritmetica della base di partenza e si usa per convertire. 0 da base 10 a base 2 un numero Avremo che: = 1 se e solo se è dispari, quindi 0 /2. rappresenta il resto della divisione intera Si procede in maniera analoga per determinare gli altri coefficienti finché il quoziente della divisione per due è zero. La sequenza dei resti sono i coefficienti in ordine inverso (dal LSB al MSB).

- Vedi esempi conversione –

Rappresentazione dei dati: codifica esadecimale

La base esadecimale: 16 cifre: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F. Questa è tipicamente utilizzata per rappresentare gli indirizzi di memoria, permettendo di esprimere in maniera più compatta i numeri.

• Per convertire da base 2 a base 16, si formano gruppi da 4 bit del numero in base 2, dopodiché si convertono i numeri rappresentati da ognuno dei gruppi;
• Per convertire da base 16 a base 2, si converte ogni cifra in base esadecimale nella rappresentazione a 4 bit in base 2. - Esempio base esadecimale –

7/3

Rappresentazione dei dati: conversione di parti frazionarie

Una Parte Frazionaria è numero razionale minore dell’unità. Per convertire la parte frazionaria si possono seguire i due diversi approcci:

• Algoritmo di conversione che impiega l’aritmetica della base di arrivo: la parte frazionaria è sviluppata in forma polinomiale nella base di partenza, i termini vengono convertiti nella base di arrivo e infine si eseguono le operazioni in base di arrivo.
• Algoritmo di conversione di parti frazionarie che impiega la base di partenza: viene eseguito un algoritmo di moltiplicazioni per 2 sulla parte frazionaria, si sottrae dal risultato ottenuto la sua parte intera e si continua. La sequenza delle parti intere sottratte fornisce la rappresentazione voluta. - Vedi ex. -

Rappresentazione dei dati: numeri interi senza segno

unsigned int: serve a rappresentare una variabile dichiarata in C. Viene rappresentato su N bit di memoria che variano a seconda dell’architettura del processore (tipicamente, 32 o 64 bit). Per = 32 bit si possono rappresentare gli interi compresi tra 0 e 2³² − 1. - Vedi interi senza segno –

Rappresentazione dei dati: caratteri

Caratteri: codifica posizionale in base 2 su 8 bit (con i quali è possibile rappresentare numeri interi senza segno da 0 a 255). Sono rappresentati in C dal tipo char (char c; )

La corrispondenza tra caratteri e numeri naturali compresi nell’intervallo 0, … , 255 è definita dalla Tabella dei Caratteri ASCII, che include la codifica per:

• Caratteri alfanumerici: cifre decimali, lettere dell’alfabeto maiuscole e minuscole
• Segni di interpunzione e parentesi: ( ) , . ; : ? ! + - [ ] { }
• Simboli aritmetici: + - * /
• Caratteri di vario genere: @ # …
• Caratteri di controllo: il segno di a capo, lo spazio di tabulazione, …

N.B. Il carattere 0 è codificato da 48 e l’1 da 49. All’intero 0 è associato un carattere speciale, ovvero '\0’ che non codifica un carattere utile ma è utilizzato come segno di terminazione nella codifica delle stringhe.

Rappresentazione dei dati: numeri interi con segno

Int: rappresenta una variabile dichiarata in C e vengono rappresentati su V bit tramite la rappresentazione «Complemento a 2» (simile allo sviluppo polinomiale), in cui però il Most Significant Bit ha peso negativo. Teniamo a mente che un numero è negativo se e solo se = 1. Il suo opposto si determina determinando il suo complemento a 2, ovvero complementando i bit uno ad uno e sommando 1 al risultato.

Eccezione: l'opposto del minimo numero rappresentabile cade fuori dalla dinamica dei valori, quindi non possibile rappresentarlo con bit in complemento a 2. Il complemento a 2 del minimo numero rappresentabile è quindi il numero stesso.

- Vedi ex. interi con segno e opposto di un intero con segno –

Rappresentazione dei dati: overflow

La condizione di overflow si verifica quando il risultato dell'operazione eccede la dinamica dei valori rappresentabili.

• Interi senza segno: si verifica overflow se e solo se è presente un bit di riporto nella somma dei MSB.
• Interi con segno: si verifica overflow se e solo se i due addendi sono concordi ma il segno del risultato è opposto a quello dei due addendi.

In fase di programmazione, quando si verifica overflow tipicamente viene generata un'eccezione che porta ad un risultato tipico di un'aritmetica modulare: sommando 1 al massimo valore positivo si ottiene il minimo valore negativo. - Ex. overflow –

Rappresentazione dei dati: sottrazione in complemento a 2

CASO 1) Minuendo maggiore del sottraendo: il risultato è positivo; non si considera eventuale riporto sul MSB.

CASO 2A) Minuendo minore del sottraendo: il risultato è negativo; si considera l'eventuale riporto sul MSB. Non si ha overflow se il riporto su MSB è 0. Il modulo del risultato è il complemento a 2 (cioè l'opposto) del risultato.

CASO 2B) Minuendo minore del sottraendo: il risultato è negativo; si considera l'eventuale riporto sul MSB. Si ha overflow se il riporto su MSB è 1. - Ex. sottrazione nei vari casi –

Rappresentazione dei dati: numeri in virgola mobile

Viene utilizzata nel linguaggio C per rappresentare i numeri float e double. Un generico numero può essere rappresentato in forma esponenziale: S * m *

• s = ± 1 è il segno;
• m è la mantissa, un valore reale non negativo;
• c è la caratteristica, un intero con segno;
• B è la base di rappresentazione.

Poiché esistono più rappresentazioni in forma esponenziale dello stesso numero, è necessario stabilire una rappresentazione univoca. Lo standard IEEE 754 stabilisce che la rappr