Informatica e laboratorio di programmazione I 1

Informatica e laboratorio di programmazione

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 scrivere il codice bisogna capire come risolvere il problema.

Detto ciò l’algoritmo è un metodo generale che risolve con una sequenza 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 entrambi 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 consente di ottenere, partendo dai dati in ingresso, i risultati che risolvono il problema: → (metodo problema risolutivo) → algoritmo (risoluzione del problema) → (linguaggio di programmazione) → programma

5

Un algoritmo è costituito da: passi elementari, ovvero azioni non più scomponibili in azioni più semplici (ciò va legato anche al linguaggio 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’algoritmo è 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 individuare l’algoritmo adatto a risolvere il problema. Per individuare questo algoritmo è necessario: analizzare attentamente il problema, suddividere il problema in altri sottoproblemi meno complessi, definire 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 corretta 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 struttura 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 problemi 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 caratteristiche 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’architettura 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 istruzioni;

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 alto, medio e basso livello. Il linguaggio macchina invece è l’insieme 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 maschera 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 permettendo di creare gli ”oggetti” e creare applicazioni più complesse.

8

4 Rappresentazione dei numeri

4.1 Memoria

La memoria del computer, memoria alla quale anche accedono i programmi, è 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’informazione 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 indipendentemente dalla posizione (esempio numerazione romana);
• 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 informatica si usano diversi sistemi:

• Binario;
• Esadecimale;
• Ottale.

4.2.1 Rappresentazione decimale

È la rappresentazione che usiamo normalmente, un sistema posizionale in base 10:

N = d_n10ⁿ + d_n−110ⁿ⁻¹ + ... + d₂10² + d₁10¹ + d₀

d ∈ {0, 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 = b_n2ⁿ + b_n−12ⁿ⁻¹ + ... + b₂2² + b₁2¹ + b₀

b ∈ {0, 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, accumularlo 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 partendo dal meno significativo e si sostituiscono con la cifra esadecimale corrispondente.

10

Conversione esadecimale a binario: si sostituisce alle cifre esadecimali 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 per qualunque altra base.

4.4 Proprietà della rappresentazione binaria

Una parola binaria di ’n’ bit, permette di rappresentare tutti i numeri interi ’N’ tali che: 0 ≤ N ≤ 2ⁿ − 1.

Dato invece un numero ’N’, la sua rappresentazione binaria richiederà un numero ’n’ di bit tale che: n > log₂N.

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:

X se 0 ≤ X < 2ⁿ / 2

2ⁿ − |X| se X < 0 ≤ 2ⁿ / 2

Per effettuare questa operazione si lasciano inalterati gli 0 a partire dal bit meno significativo, si lascia inalterato il primo 1, si complementa 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 si possono rappresentare tutti i numeri nell’intervallo [−2ⁿ⁻¹, 2ⁿ⁻¹ − 1].

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 istruzioni scritte nel linguaggio di programmazione in istruzioni di un altro linguaggio (il codice macchina).

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.

#include <stdio.h>
#include <stdlib.h>

int main(){
    printf("Hello 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