Informatica e laboratorio di programmazione I 1

Informatica e laboratorio di

programmazione

1

Indice

1 Algoritmi 5

1.1 Problem solving . . . . . . . . . . . . . . . . . . . . . . 6

2 Architettura e sistemi di elaborazione 7

3 Linguaggio di programmazione 8

4 Rappresentazione dei numeri 9

4.1 Memoria . . . . . . . . . . . . . . . . . . . . . . . . . . 9

4.2 Sistemi di rappresentazione . . . . . . . . . . . . . . . 9

4.2.1 Rappresentazione decimale . . . . . . . . . . . . 9

4.2.2 Rappresentazione binaria . . . . . . . . . . . . . 10

4.2.3 Rappresentazione esadecimale . . . . . . . . . . 10

4.3 Aritmetica . . . . . . . . . . . . . . . . . . . . . . . . . 11

4.4 Proprietà della rappresentazione binaria . . . . . . . . 11

4.5 Numeri negativi . . . . . . . . . . . . . . . . . . . . . . 11

4.6 Numeri con la virgola . . . . . . . . . . . . . . . . . . . 12

5 Il C 13

5.1 Header files . . . . . . . . . . . . . . . . . . . . . . . . 13

5.2 Commenti . . . . . . . . . . . . . . . . . . . . . . . . . 13

5.3 Variabili . . . . . . . . . . . . . . . . . . . . . . . . . . 14

5.3.1 Nome di una variabile . . . . . . . . . . . . . . 14

5.3.2 Tipi di dato . . . . . . . . . . . . . . . . . . . . 15

5.3.3 Definizione delle variabili . . . . . . . . . . . . . 15

5.3.4 Segno delle variabili . . . . . . . . . . . . . . . . 16

5.3.5 Indirizzo delle variabili . . . . . . . . . . . . . . 16

5.3.6 Visibilità di una variabile . . . . . . . . . . . . . 16

5.4 Tipi di dato compositi . . . . . . . . . . . . . . . . . . 16

5.4.1 Struct . . . . . . . . . . . . . . . . . . . . . . . 16

5.5 Stringhe . . . . . . . . . . . . . . . . . . . . . . . . . . 17

5.6 Funzioni . . . . . . . . . . . . . . . . . . . . . . . . . . 17

5.6.1 Funzione printf() . . . . . . . . . . . . . . . . . 17

5.6.2 Funzione scanf() . . . . . . . . . . . . . . . . . 19

5.6.3 Funzione sizeof() . . . . . . . . . . . . . . . . . 20

5.7 Valutazione di condizioni . . . . . . . . . . . . . . . . . 21

5.7.1 if() . . . . . . . . . . . . . . . . . . . . . . . . . 21

5.7.2 switch()-case . . . . . . . . . . . . . . . . . . . 21

5.8 Cicli . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

5.8.1 while() . . . . . . . . . . . . . . . . . . . . . . . 22

5.8.2 do-while() . . . . . . . . . . . . . . . . . . . . . 22

5.8.3 for() . . . . . . . . . . . . . . . . . . . . . . . . 22

2

5.9 break e continue . . . . . . . . . . . . . . . . . . . . . . 23

5.10 Espressioni e operatori . . . . . . . . . . . . . . . . . . 23

5.11 Operatore ternario ’ ?’ . . . . . . . . . . . . . . . . . . 24

5.12 Array . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

5.12.1 Inizializzazione . . . . . . . . . . . . . . . . . . 24

5.13 Puntatori . . . . . . . . . . . . . . . . . . . . . . . . . 25

5.13.1 Aritmetica dei puntatori . . . . . . . . . . . . . 25

5.13.2 Array e puntatori . . . . . . . . . . . . . . . . . 26

5.13.3 NULL . . . . . . . . . . . . . . . . . . . . . . . 26

5.13.4 Puntatore a void* . . . . . . . . . . . . . . . . . 26

5.13.5 Puntatore a puntatore . . . . . . . . . . . . . . 26

5.14 Allocazione dinamica della memoria . . . . . . . . . . . 27

5.14.1 Aree di memoria . . . . . . . . . . . . . . . . . 28

5.14.2 Errori . . . . . . . . . . . . . . . . . . . . . . . 29

5.15 Stringhe . . . . . . . . . . . . . . . . . . . . . . . . . . 30

5.15.1 strlen(str) . . . . . . . . . . . . . . . . . . . . . 31

5.15.2 strcmp(str1,str2) . . . . . . . . . . . . . . . . . 31

5.15.3 strcpy(str2,str1) . . . . . . . . . . . . . . . . . . 31

5.15.4 strcat(str2,str1) . . . . . . . . . . . . . . . . . . 31

5.15.5 strncpy(str2,str1,int) . . . . . . . . . . . . . . . 31

5.15.6 strchr(str,char) . . . . . . . . . . . . . . . . . . 32

5.15.7 strrchr(str,char) . . . . . . . . . . . . . . . . . . 32

5.15.8 strstr(str,”stringa”) . . . . . . . . . . . . . . . . 32

5.15.9 Esempi . . . . . . . . . . . . . . . . . . . . . . . 32

5.16 I parametri della main . . . . . . . . . . . . . . . . . . 33

5.17 Funzioni . . . . . . . . . . . . . . . . . . . . . . . . . . 34

5.17.1 Ricorsione . . . . . . . . . . . . . . . . . . . . . 35

5.17.2 rand() . . . . . . . . . . . . . . . . . . . . . . . 35

5.17.3 srand() . . . . . . . . . . . . . . . . . . . . . . . 36

5.17.4 time(0) . . . . . . . . . . . . . . . . . . . . . . . 36

5.18 INPUT/OUTPUT . . . . . . . . . . . . . . . . . . . . 37

5.18.1 fopen() . . . . . . . . . . . . . . . . . . . . . . . 37

5.18.2 fclose() . . . . . . . . . . . . . . . . . . . . . . . 38

5.18.3 fscanf() . . . . . . . . . . . . . . . . . . . . . . 38

5.18.4 fprintf() . . . . . . . . . . . . . . . . . . . . . . 38

5.18.5 fgets() . . . . . . . . . . . . . . . . . . . . . . . 39

5.18.6 File .csv . . . . . . . . . . . . . . . . . . . . . . 39

5.18.7 fread() . . . . . . . . . . . . . . . . . . . . . . . 39

5.18.8 fwrite() . . . . . . . . . . . . . . . . . . . . . . 39

5.18.9 fseek() . . . . . . . . . . . . . . . . . . . . . . . 40

5.18.10 ftell() . . . . . . . . . . . . . . . . . . . . . . . 40

5.18.11 Stream predefiniti . . . . . . . . . . . . . . . . . 40

5.19 Ricerca . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

3

5.19.1 ricerca lineare . . . . . . . . . . . . . . . . . . . 41

5.19.2 ricerca binaria . . . . . . . . . . . . . . . . . . . 42

5.20 Ordinamento . . . . . . . . . . . . . . . . . . . . . . . 44

5.20.1 Ordinamento per selezione . . . . . . . . . . . . 44

5.20.2 Ordinamento per inserzione . . . . . . . . . . . 47

5.20.3 Bubblesort . . . . . . . . . . . . . . . . . . . . . 49

5.20.4 Shellsort . . . . . . . . . . . . . . . . . . . . . . 51

5.20.5 Quicksort . . . . . . . . . . . . . . . . . . . . . 53

5.20.6 Mergesort . . . . . . . . . . . . . . . . . . . . . 54

5.20.7 Funzione qsort() . . . . . . . . . . . . . . . . . 56

5.21 Struttura a stack . . . . . . . . . . . . . . . . . . . . . 58

5.22 ctype.h . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

4

1 Algoritmi

Tutto nasce dal dover risolvere un problema: si hanno dei dati in

ingresso che andranno manipolati per avere dei dati in uscita (una

risposta, un risultato atteso).

L’informatica è il trattamento automatico delle informazioni (i

dati). Il computer (calcolatore) si limita ad eseguire gli ordini; è il

programmatore che deve risolvere il problema.

Il programma è quindi la soluzione al problema, ma prima di scri-

vere il codice bisogna capire come risolvere il problema.

Detto ciò l’algoritmo è un metodo generale che risolve con una se-

quenza finita di azioni un problema dato, queste sequenze finite devono

essere precise (non ambigue).

Si possono cosı̀ classificare i problemi in:

- non risolvibili→ non si trova un algoritmo: o non si sa cosa

fare, o la sequenza di azioni non è finita;

- non affrontabili→ il numero finito di azioni è talmente elevato

che non ci permette di risolverlo;

- risolvibili;

Il codice sorgente è il testo scritto in accordo alla sintassi del

linguaggio di programmazione usato, importante dire anche che il

programma non può essere un algoritmo (un programma che non

termina).

A seconda del linguaggio utilizzato inoltre si ha:

- interpretazione

- compilazione (crea un eseguibile)

In entrambe i casi viene eseguita la traduzione del codice per il

computer.

Un programma che viene eseguito fa esattamente ciò che gli si dice

di fare.

L’esecuzione delle azioni nell’ordine specificato dall’algoritmo con-

sente di ottenere, partendo dai dati in ingresso, i risultati che risolvono

il problema: →(metodo

problema risolutivo)→ algoritmo (risoluzione del pro-

→(linguaggio

blema) di programmazione)→ programma

5

Un algoritmo è costituito da: passi elementari, ovvero azioni non

più scomponibili in azioni più semplici (ciò va legato anche al linguag-

gio utilizzato); e il processo, ovvero l’ordine di esecuzione dei passi

elementari.

Le proprietà di un algoritmo sono:

- finitezza→ numero finito di passi;

- determinismo→ risultati non dipendenti dall’esecuzione: l’al-

goritmo è generale;

- realizzabilità→ deve essere compatibile con le risorse e deve

funzionare;

- efficienza→ uso del minimo numero di operazioni.

1.1 Problem solving

La parte più complicata è dunque il problem solving ovvero indi-

viduare l’algoritmo adatto a risolvere il problema. Per individuare

questo algoritmo è necessario: analizzare attentamente il problema,

suddividere il problema in altri sottoproblemi meno complessi, defini-

re i dati di ingresso e uscita, definire le strutture dei dati e definire la

sequenza dei passi da svolgere.

Un algoritmo si rappresenta con i passi necessari e la loro corret-

ta sequenza; per fare ciò si può usare o lo pseudocodice oppure un

diagramma di flusso.

Lo pseudocodice non è un linguaggio di programmazione (ma vi

assomiglia) e sintetizza la struttora di un programma.

Il diagramma di flusso è invece un effettivo grafico che serve a

descrivere l’algoritmo.

Un approccio specifico al problem solving (e consigliato) è l’approccio

top-down. Con questo tipo di approccio vengono identificati i proble-

mi principali e vengono decomposti in sottoproblemi sino ad ottenere

problemi elementari. 6

2 Architettura e sistemi di elaborazione

Per un programmatore è importante conoscere l’architettura e le ca-

ratteristiche del sistema che usa, in modo da variare le scelte di stesura

del codice in base a queste.

Ogni sistema ha delle funzioni che sono:

- elaborazione (calcolo);

- memorizzazione;

- trasmissione;

- controllo.

Queste funzioni vengono svolte da diversi elementi, in particolare:

la CPU (Central Processing Unit), la memoria (che può essere fisica

o di massa), i sistemi di I/O e i bus.

Il modello più utilizzato per rappresentare questi elementi è l’ar-

chitettura di Neumann [Figura 1].

Figura 1: Architettura di Neumann

Questo modello ha tre elementi principali:

- CPU: controlla il funzionamento ed esegue dei conti;

- PCU che interagisce con la memoria andando a leggere le istru-

zioni; 7

- PCU che controlla anche l’unità di calcolo: prende i dati dalla

memoria, li rielabora e li rispedisce indietro dandoci il risultato.

Quindi la CPU legge (dalla memoria) ed esegue (le istruzioni).

3 Linguaggio di programmazione

Il linguaggio di programmazione è utilizzato per sviluppare il software

che ci serve, questo è caratterizzato da:

- sintassi : è l’insieme delle regole per la stesura corretta del

programma;

- semantica: è l’attribuzione del significato, ciò che viene scritto

deve avere un senso.

Esistono diversi tipi di linguaggi e possono essere suddivisi in al-

to, medio e basso livello. Il linguaggio macchina invece è l’insie-

me delle operazioni elementari che può eseguire un calcolatore (per

questo è diverso per ogni processore), inoltre è di difficile utilizzo e

comprensione.

Un esempio di linguaggio a basso livello è l’assembly, il più vicino

al linguaggio macchina. A differenza un linguaggio ad alto livello ma-

schera il calcolatore, è più leggibile e comprensibile e più compatibile

con i diversi tipi di processori.

Ci sono diversi tipi di linguaggi ad alto livello:

- imperativi : sono un elenco di istruzioni che vengono eseguite

in sequenza (trasferimento dati, operazioni aritmetiche, controllo

di flusso, variabili);

- orientati ad oggetti : estendono le capacità del linguaggio per-

mettendo di creare gli ”oggetti” e creare applicazioni più com-

plesse. 8

4 Rappresentazione dei numeri

4.1 Memoria

La memoria del computer, memoria alla quale anche accedono i pro-

grammi, è una memoria ad accesso casuale RAM (Random Access

Memory) che è caratterizzata da un indirizzo ed una dimensione;

questo permette al programma di accedere direttamente all’informa-

zione desiderata.

L’elemento base della memoria è il bit, che può assumere i valori

0 o 1; ciò che viene memorizzato nella memoria è la combinazione di

più bit.

4.2 Sistemi di rappresentazione

Esistono due tipi di rappresentazione:

- non posizionali: ogni simbolo ha un significato preciso indi-

pendentemente dalla posizione (esempio numerazione roma-

na);

- posizionali: i simboli hanno un significato che dipende dalla

posizione (esempio numerazione araba -quella che usiamo noi

oggi-).

Inoltre sono presenti rappresentazioni con basi diverse; in informa-

tica si usano diversi sistemi:

• binario;

• esadecimale;

• ottale.

4.2.1 Rappresentazione decimale

È la rappresentazione che usiamo normalmente, un sistema posiziona-

le in base 10:

( n n−1 2

N = d 10 + d 10 + ... + d 10 + d 10 + d

n n−1 2 1 0

∈ {0,

d 1, 2, 3, 4, 5, 6, 7, 8, 9}

Questo sistema però non è adeguato a sistemi informatici.

9

4.2.2 Rappresentazione binaria

È un sistema posizionale a base 2:

( n n−1 2

N = b 2 + b 2 + ... + b 2 + b 2 + b

n n−1 2 1 0

∈ {0,

b 1}

Per convertire un numero da binario a decimale si usa questo

algoritmo:

1) posizionarsi sulla sinistra del numero da convertire (parte piú

significativa);

2) inizializzare N a 0;

3) leggere la cifra binaria che segue procedendo verso destra;

4) moltiplicare N per 2 e sommarvi la cifra letta;

5) se ci sono ancora cifre tornare al punto 3);

6) fine della procedura, N contiene il risultato.

Per convertire invece un numero da decimale a binario:

1) inizializzare N come il numero da convertire

2) inizializzare una sequenza di caratteri S come vuota

3) si divide N per 2

4) il resto è la cifra meno significativa ancora da calcolare, accumu-

larlo in S verso destra

5) il risultato è 0?

sı̀: fine

no: porre N = risultato e ripetere da 3

4.2.3 Rappresentazione esadecimale

È una rappresentazione in base 16 con cifre che vanno da 0 a 9 e da

A a F; in pratica una cifra codifica 4bit.

Conversione binario a esadecimale: si prendono i bit 4 a 4 par-

tendo dal meno significativo e si sostituiscono con la cifra esadecimale

corrispondente. 10

Conversione esadecimale a binario: si sostituisce alle cifre esa-

decimali la corrispondente sequenza di 4 bit in binario.

4.3 Aritmetica

Per quanto riguarda i calcoli valgono le stesse regole dell’aritmetica in

base 10 ber qualunque altra base.

4.4 Proprietà della rappresentazione binaria

Una parola binaria di ’n’ bit, permette di rappresentare tutti i numeri

n

≤ ≤ −

interi ’N’ tali che: 0 N 2 1.

Dato invece un numero ’N’, la sua rappresentazione binaria richie-

derà un numero ’n’ di bit tale che: n > log N .

2

4.5 Numeri negativi

Per quanto riguarda i numeri negativi in binario viene utilizzato il

complemento a 2, in quanto ha il vantaggio di mantenere invariate le

operazioni. In particolare dati ’n’ bit, il valore ’X’ lo rappresentiamo

come: n

 2

≤

X se0 X <



 2

n

2

n − |X| ≤

2 se X < 0



 2

Per effettuare questa operazione si lasciano inalterati gli 0 a partire

dal bit meno significativo, si lascia inalterato il primo 1, si complemen-

ta tutto il resto.

In questo modo si ha una sola rappresentazione dello zero, il bit più

significativo è 1 per i numeri negativi e 0 per quelli positivi, dati ’n’ bit

n−1 n−1 −1].

si possono rappresentare tutti i numeri nell’intervallo [−2 , 2

11

4.6 Numeri con la virgola

I numeri con la virgola possono essere rappresentati a virgola fissa

oppure a virgola mobile.

Nei numeri a virgola fissa viene posto noto e fisso il numero di

bit per la parte intera del numero e per la parte frazionaria.

Per quanto riguarda invece i numeri a virgola mobile la questione

è più complicata. 12

5 Il C

Il C è un linguaggio di programmazione di basso-medio livello, che

non nasconde la macchina (ovvero la complessità delle sue operazioni

e del suo funzionamento).

Il C è un linguaggio compilato. Il compilatore traduce le istru-

zioni scritte nel linguaggio di programmazione in istruzioni di un altro

linguaggio (il codice amcchina).

Generalmente si ha il preprocessore che traduce le direttive che

iniziano per #; il compilatore vero e proprio che converte il sorgente

in linguaggio macchina; e il linker che unisce tutti i file necessari e

dà come risultato l’eseguibile.

#i n c l u d e <s t d i o . h>

#i n c l u d e < s t d l i b . h>

i n t main ( )

{ \

p r i n t f ( ” H e l l o world ! n ” ) ;

return 0;

}

5.1 Header files

Sono file che contengono definizioni di funzioni e di costanti; questi,

in C, hanno sempre l’estensione ”.h”.

Gli header files che si andranno ad utilizzare principalmente, e che

sono necessari per poter utilizzare le funzioni