Riassunto esame Fondamenti di informatica, Prof. Bilotta Stefano, libro consigliato Fondamenti di programmazione. Linguaggio C, strutture dati, algoritmi elementari, C++ (Società Editrice Esculapio, Bologna, 2017.), S. Berretti, L. Carnevali, E. Vicario

Fondamenti di informatica

Introduzione

L’ informatica è la scienza che studia l’elaborazione delle informazioni e le sue applicazioni; più precisamente l’informatica si occupa della

rappresentazione, dell’organizzazione e del trattamento automatico delle informazioni.

L’elaborazione automatica è l’insieme dei processi eseguiti da un’unità elettronica/digitale automatica (elaboratore o calcolatore elettronico)

sui dei dati di ingresso (input) per ottenere dei dati in uscita (output).

L’insieme dei processi, routine o operazioni da eseguire deve essere comunicato all’elaboratore attraverso un linguaggio comprensibile ed

eseguibile dall’elaboratore stesso.

L’algoritmo è la procedura necessaria per risolvere un generico problema con un numero finito di passi, ovvero attraverso un set di

istruzioni finito che, applicate ai dati di ingresso, li trasformano nei risultati del problema in uscita.

Il programma è un implementazione di un algoritmo in un linguaggio comprensibile ed eseguibile dall’elaboratore, utilizzando una specifica

sintassi che dipende dal linguaggio di programmazione.

Il linguaggio di programmazione utilizzato in questo contesto è il C.

Formalizzazione di un problema attraverso algoritmo

I passi necessari per creare un programma (algoritmo eseguibile dal calcolatore) per risolvere un generico problema sono:

1. Analisi e modellazione del problema

2. Implementazione dell’algoritmo attraverso un linguaggio formale, definendo le operazioni (operatori, funzioni, procedure…) e gli oggetti

su cui effettuare le operazioni (dati)

3. Codifica dell’ algoritmo nel linguaggio di programmazione

Solitamente i linguaggi di programmazione sono cosiddetti “simbolici” e di “alto livello”, cioè uso di simboli per rappresentare variabili e

operatori ed elevato livello di astrazione.

Per essere eseguiti dal calcolatore, le istruzioni di alcuni programmi scritti in linguaggio di alto livello devono essere tradotti in linguaggio di

“basso livello” da un programma dedicato, chiamato compilatore.

Infine, per poter essere eseguire, le istruzioni in linguaggio di basso livello deve essere ulteriormente tradotto in “linguaggio macchina” da

un programma chiamato assemblatore.

Analisi e modellazione (diagrammi di flusso, Flowcharts)

n:

Calcolo del fattoria di un numero intero

Condizioni di validità per un diagramma di flusso:

• Deve esistere un blocco di inizio e un blocco di fine (condizione di validità generale)

• ogni freccia deve entrare in un blocco e dal blocco di inizio deve essere possibile raggiungere qualsiasi altro blocco

• Da ogni blocco deve essere possibile raggiungere il blocco di fine (condizione di validità generale)

• (Condizione specifica a seconda del blocco) Blocco di eleborazione e di input e output, questi blocchi devono avere 1 sola freccia in

entrata e 1 solo in uscita a

• Blocco di controllo deve avere 1 sola freccia di entrata e due frecce di uscita (Condizione specifica a seconda del blocco)

e

Rappresentazione

Tipi, variabili e costanti

Il c, come qualunque altro linguaggio, rappresenta dati secondo tipi. Un tipo è caratterizzato dai valori che può rappresentare e dalle

operazioni che è possibile eseguire sui suoi valori.

I tipi elementari del C sono:

• Unsigned int, int. Numeri interi rappresentati mediante un numero di byte dipendenti dall’architettura del processore (32, 64 bit)

• Float Numeri razionali in virgola mobile (floating point)

• Double Numeri razionali in virgola mobile con precisione doppia rispetto ai flop

• Char Caratteri rappresentati su 8 bit (256 caratteri set del codice ASCII)

• Void Tipo nullo, usato quando la sintassi del linguaggio Chiede di specificare un tipo di dato ma la semantica non lo prevede

Non esistono valori booleani, che vengono sostituiti dai numeri interi sotto la convenzione che 0 codifica un falso e qualunque valore

diverso da 0 codifica un vero.

La Variabile è una locazione di memoria che contiene un valore di un tipo. Il valore può variare nel corso della computazione, mentre il tipo è

invariante. In un linguaggio simbolico, come è il c, una variabile è associata anche ad un nome che permette di riferirsi alla variabile senza

doverne specificare l’indirizzo fisico in memoria. In c, il nome di una variabile è una qualunque sequenza di caratteri alfabetici, numerici, con

possibile uso del segno underscore (_). Il primo carattere non può essere un numero. La sequenza ha una lunghezza arbitraria anche se il

compilatore non distingue tra nomi che non differiscono sui primi 32 caratteri. Ogni variabile deve essere dichiarata prima dell’uso,

specificandone il nome e il tipo. Il nome viene associato alla variabile tramite una dichiarazione è per associare un valore ad una variabile si

ricorre ad un’assegnazione.

La variabile Array è un insieme di variabili dello stesso tipo che possono essere referenziate tramite un nome collettivo o un indice che le

identifica (denotandone lo scostamento, od offset, rispetto all’inizio dell’array):

int V[10];

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

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

◦

Oltre ad essere il nome della variabile Array, V rappresenta anche l’indirizzo di memoria a partire dal quale l’array è memorizzato. Le singole

locazioni sono referenziate attraverso un indice intero entro parentesi quadre che denota l’offset della particolare locazione dall’inizio

dell’arra6: V[0] denota la prima locazione, V[4] la quinta, V[9] l’ultima.

La costante é un valore di un certo tipo che non cambia durante la computazione. Esse 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 #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 n modo che la costante si

utilizzabile da tutto il codice del programma.

#define TRUE 1

◦ const int max_speed = 130 Const definisce una variabile di solo lettura che non può essere modificata all’interno del

◦ programma.

Operatori ed espressioni

Le espressioni sono combinazioni di variabili e costanti attraverso degli operatori. Gli operatori sono usualmente classificati per tipo di

operazione, distinguendo tra l’altro operatori aritmetici, relazionali e logici.

• Gli operatori aritmetici sono la somma (+), la differenza (-), il prodotto (*), la divisione (/), il modulo (%).

• Gli operatori relazionali sono gli operatori usati per comparare valori ovvero il minore (<), il minore uguale (<=), l’uguaglianza (==), il

maggiore o uguale (>=), il maggiore (>), il diverso (!=).

• Gli operatori logici sono la congiunzione (&&), la negazione (!), la disgiunzione (| |).

• L’assegnamento (=) è anche esso un operatore e l’assegnamento del risultato di un espressione a una variabile è a sua volta un

espressione.

Il calcolo di un espressione restituisce un valore e produce un effetto sui dati. L’effetto sui dati prodotto dal calcolo di una espressione è

chiamato side effect (effetto collaterale). Mentre il termine suggerisce l’idea di una questione minore, fastidiosa ma non evitabile, i side-

effects sono una componente strutturale dell’intero linguaggio . L’assegnamento, su cui in ultimo poggia qualunque elaborazione, è un

particolare side effects.

Istruzioni

Le istruzioni servono a dirigere il flusso dell’esecuzione: in c i dati sono elaborati attraverso i side effects prodotti dal calcolo delle

espressioni, e il ruolo delle istruzioni è quello di determinare la sequenza con cui le espressioni sono eseguite.

Il fatto che il significato delle istruzioni risieda nel controllo del flusso fa si che diventi conveniente descriverle usando i flow charts. Questi

non hanno alcuna utilità pratica nella progettazione di un algoritmo, ma hanno il pregio di evidenziare in maniera intuitiva il modo con cui le

diverse istruzioni sequenzializzano l’esecuzione delle espressioni.

Espressione, sequenza e compound

La più semplice istruzione è un espressione seguita da un punto e virgola:

a=b+125;

L’esecuzione consiste nel calcolare l’espressione, producendo i side effects, e poi procedere alla istruzione successiva.

int n;

n=10;

Sequenza di istruzione: Istruzione Compound: E

int a, b; { f y

6 5 b Si

b=5; int a,b; i

a=b+10; b=5;

10

0 io 10

a

a=b+10;

16 I e

}

Due istruzioni in sequenza sono a loro volta un’istruzione. compound.

Un istruzione raccolta entro parentesi graffe è un istruzione L’utilità, non immediatamente apparente, è quella di raccogliere

istruzioni in blocchi in modo che siano trattati in maniera unitaria. Questo in ultimo agisce sulla precedenza con cui sono associare le

istruzioni successive e diventa rilevante rispetto alle istruzioni di controllo condizionale e di iterazione.

Condizione

Le istruzioni condizionali permetto di decidere direzioni diverse nel flusso di esecuzione, in base al valore restituito da un espressione.

L’istruzione condizionale if condiziona l’esecuzione di una istruzione, detta corpo, al risultato restituito da una espressione, detta guardia.

IF:

Clausola

int a, b; int a, b;

… …

if ( a>b ) { if ( a>b )

b=5; b=5;

a=b+10; a=b+10;

} else

L’istruzione condizionale if può essere estesa con una clausola che permette di avere due corpi alternativi, eseguiti a seconda che la

guardia restituisca un valore vero o falso.

IF-ELSE:

Clausola

int a, b;

…

if ( a>b ) {

b=5;

a=b+10;

}

else

b=1;

Iterazione

Le istruzioni di iterazione permettono di eseguire ripetitivamente un corpo di istruzioni di o al verificarsi di una qualche condizione sui valori

delle variabili del programma. Esistono tre diverse istruzioni di iterazione: for, while e do-while.

-Ciclo FOR:

Nell’istruzione for, un corpo di istruzioni è seguito ripetitivamente sotto il controllo di una guardia costituita di tre espressioni di

inizializzazione (1), guardia (2) e incremento (3).

int sum;

int count;

sum=0;

for (count=1; count<=10; count=count+1)

sum=sum+count;

-Ciclo WHILE:

Nell’istruzione while, un corpo di istruzioni è eseguito ripetitivamente fintanto che (mentre) un espressione di guardia restituisce un valore

vero.

int count, sum;

count=1;

sum=0;

while (count<=10) {

sum=sum+count;

count=count+1;

}

-Ciclo DO-WHILE:

L’esecuzione do-while opera in maniera analoga a while sennonché in questo caso la condizione di guardia è posta in coda piuttosto che in

testa al corpo.

int count, sum;

count=1;

sum=0;

do {

sum=sum+count;

count=count+1;

} while (count<=10)

Rappresentazione dei dati

Esistono due tipi di dati che occorre rappresentare nella codifica di un programma: i tipi che codificano testo e quelli che codificano valori

numerici. int, float Double. char,

In c esistono tre diversi tipi dedicati a rappresentare valori numerici: e I caratteri sono rappresentati con il tipo che

poi è esso stesso codificato nella forma di un numero.

Numero

Il numero è un ente dotato di suo significato intrinseco, del quale è possibile dare rappresentazioni diverse. Il significato di un numero,

almeno quello di un intero, può essere definito operativamente in riferimento alla relazione di equi numerosità tra insiemi.

In generale, le diverse rappresentazioni sono caratterizzate dalla combinazione di più convenzioni: la 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), la base di rappresentazione, il numero di cifre (che si hanno a disposizione per la rappresentazione), la

del segno, là rappresentazioni di parti frazionarie e valori razionali.

codifica

Codifica posizionale

I numeri naturali sono codificati attraverso una base finita di cifre elementari. Nella esperienza quotidiana sono le cifre da 0 a

9 che formano la cosiddetta base decimale e codificano direttamente i primi 10 valori dell’insieme. I numeri successivi sono

codificati componendo più cifre secondo una convenzionio posizionale. Il che significa che il peso delle cifre dipende dalla

posizione in cui appaiono.

Differenti convenzioni o notazioni:

• Little Endian: in ultima posizione si trova la cifra meno significativa (LSD)

• Big Endian: in ultima posizione si trova la cifra più significativa (MSD)

Rappresentazione binaria

Il calcolatore utilizza la codifica in base 2. È 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.

Algoritmo di conversione della base di rappresentazione di un numero!

1. Ottenere la rappresentazione 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.

Conversione dalla base di rappresentazione

• Per effettuare la conversione da base 10 a base 2, per prima cosa

rappresentiamo in base 2 i numeri da 0 a 10 (ovvero le 10 cifre da 0

a 9 usate per la rappresentazione più la base di rappresentazione stessa

n

• Con un numero di bit si possono rappresentare 2n valori.

N

• Per rappresentare valori sono necessari

Base esadecimale cifre decimali A,

Per ottenere una codifica più compatta si usa spesso la base 16. In base 16 ci sono, ovviamente 16 cifre: le da 0 a 9 e poi

B, C, D, E, F che rappresentano i numeri che in base 10 sono rappresentati come 10, 11, 12, 13, 14, 15. La conversione da e verso la base

impaccando

2 si ottiene in maniera immediata i bit 4 a 4:

La rappresentazione esadecimale è il modo più consuetò di esprimere indirizzi della memoria, che sono composti di 32bit e quindi codificati

in 8 cifre esadecimale.

Parti frazionarie

Un parte frazionaria è un numero razionale inferiore all’unità. La conversione di una parte frazionaria da base decimale a base binaria e

base di partenza arrivo.

viceversa può essere effettuata applicando l’aritmetica dalla o quella di

Nel conto in base di arrivo, la parte frazionale è sviluppata in forma polinomiale nella base di partenza, poi i singoli termini sono convertiti

nella base di arrivo e infine sono eseguite le operazioni in base di arrivo.

Nel conto in base di partenza, viene eseguito un algoritmo di moltiplicazioni successive sostanzialmente uguale a quello delle divisioni

successive: la parte frazionaria viene ripetutamente moltiplicata per due sottraendo ogni volta la parte intera del risultato. La sequenza delle

parti intere sottratte fornisce da rappresentazione ricercata, la natura teorica del procedimento è giustificata dalla osservazione che se x<1

allora esiste una successione di valori binari

Da cui segue LI

E 1

2 che

e quindi, essendo 2471 1

an

segue

Numeri interi senza segno

Un intero senza segno serve a rappresentare una variabile dichiarata in C come istanza di tipo unsigned int”

unsigned int a;

Viene rappresentato su N bit di memoria ,in forma posizionale in base 2:

ai

'

La rappresentazione codifica tutti è soli i naturali tra 0 a 2-1 inclusi. Il numero di bits N può variare a seconda dell’architettura della

macchina, ma è comunemente uguale a 32. Il che significa che è possibile codificare i numeri da 0 a 2-1.

Caratteri

Un carattere serve a rappresentare una variabile in C come istanza di tipo char:

char c;

È rappresentato in memoria su 8 bit, che codificano un numero intero senza segno tra 0 e 255. La corrispondenza tra i valori numerici

dell’intervallo [0, 255] e i caratteri è stabilita da una tabella standard, la tabella dei codici ASCII, che include:

• I caratteri alfanumerici ( cifre decimali, lettere minuscole e maiuscole)

• I simboli di interpunzione e le parentesi

• I simboli aritmetici

• I caratteri di controllo ( il segno di a capo, lo spazio,…)

• All’intero 0 è associato un carattere speciale, ovvero ‘\0’ utilizzato segno di terminazione nella codifica delle stringhe.

Tabella codifica ASCII

Interi con segno

Un intero con segno serve a rappresentare una variabile dichiarata in c come istanza del tipo int:

int a; “complemento a 2”

Gli interi con segno sono rappresentati su N bit usando una rappresentazione in . In questa codifica , nello sviluppo

poliniomale il bit più significativo (most significant bit), ha peso negativo mentre gli altri hanno invece peso positivo.

Il numero codificato è negativo se è solo se il bit MSB vale 1. Assegnata la rappresentazione di un numero, il suo opposto può essere

determinato complimentando i bit uno a uno e sommando uno al risultato. uno

dit a

dei uno

complemento

11

somma

Overflow

In una operazione di somma, può verificarsi un condizione di overflow , ovvero il risultato può accedere la dinamica dei valori

rappresentabili.

Nel caso di valori codificati come interi senza segno, l’overflow è manifestato dalla presenza di un riporto nella somma dei bit MSB. Nel

caso di una codifica in complemento a 2, il riconoscimento dell’overflow è meno diretto, in quanto è possibile un overflow solo se i due

addendi hanno lo stesso segno.

In fase di programmazione, quando si verifica un overflow tipicamente viene generata un eccezione che vi