Programmazione e Strutture Dati

Programmazione e strutture dati

Programma del corso

• Algoritmi e programmi
• Complementi di programmazione in C
  • Strutture, strutture autoreferenziate, strutture dinamiche (liste, alberi)
  • Puntatori e allocazione dinamica della memoria
• Algoritmi di ordinamento
• Tipo di dati astratti (ADT): progettazione e realizzazione
• Strutture dati
  • Lineari: liste, stack e code
  • Non lineari: alberi, heap e Tabelle Hash
• Ricorsione ed algoritmi ricorsivi
• Cenni di complessità computazionale

Algoritmi e programmi

Per realizzare un programma si devono seguire determinati passi. Per prima cosa si individua il problema, successivamente si scrive l'algoritmo che lo risolve e in seguito si implementa il programma nel linguaggio che più preferiamo (C, C#, Java, Swift, ecc.).

Problema → Algoritmo → Programma

Si procede per gradi:

• Definizione del problema
• Dati iniziali (input)
• Dati intermedi (se necessari)
• Dati finali (output)
• Definizione di un insieme di passaggi logici che trasformano i dati iniziali in dati finali
• Il risultato è un algoritmo, un insieme finito di istruzioni che, se eseguite ordinatamente, sono in grado di risolvere il problema di partenza.
• Analisi:
  • Comprensione del problema
  • Definizione dei vincoli e delle specifiche
• Progettazione:
  • Scelta della strategia
  • Formulazione di un algoritmo
• Implementazione:
  • Codifica della soluzione
  • Test e debugging
• Esecuzione:
  • Applicazione su dati reali

Analisi

In questa fase dobbiamo capire cosa deve fare il programma, in particolare dobbiamo individuare i dati di ingresso e di uscita con i loro relativi vincoli. Dobbiamo quindi rispettare delle precondizioni e delle postcondizioni.

• Precondizione: condizione definita sui dati di ingresso che deve essere soddisfatta affinché la funzione sia applicabile
• Postcondizione: condizione definita su dati di uscita e dati di ingresso e che deve essere soddisfatta al termine dell'esecuzione del programma

È buona norma utilizzare un dizionario dei dati da riempire durante le varie fasi del ciclo di vita. Si tratta di una tabella il cui schema è:

• Identificatore, tipo, Descrizione

La descrizione serve a specificare meglio l'identificatore e a descrivere il contesto in cui il dato viene usato.

Esempio: ordinamento di una sequenza di interi

• Dati di ingresso: sequenza s di in interi
• Precondizione: n > 0
• Dati di uscita: sequenza s1 di n interi
• s1 è una permutazione di s dove ∀ i ∈ [0, n-2], s1[i] ≤ s1[i+1]

Progettazione

Questa fase consiste nel decidere come il programma deve effettuare la trasformazione specificata. La progettazione dell'algoritmo si divide in:

• Definizione degli step
• Decomposizione funzionale

Esempio: ordinamento di una sequenza di interi

1. Input sequenza s in un array a di dimensione n
2. Ordina array a di dimensione n (unico array)
3. Output sequenza s1 contenuta in array a di dimensione n

Una volta individuati i passi che il nostro algoritmo deve compiere, scriviamo una funzione per ogni passo e se necessario anche più di una. Le funzioni che scriveremo potrebbero aver bisogno dell'aiuto di altre funzioni, per cui dobbiamo mettere in conto anche queste.

Nello specifico questo programma si divide in:

• input_array(a, n)
• ordina_array(a, n)
• output_array(a, n)

Per ognuna di queste tre funzioni dobbiamo fare la specifica, la progettazione, la codifica e la verifica.

Funzione ordina_array

Analisi

• Dati in ingresso: array a di interi di dimensione n
• Precondizione: n > 0
• Dati di uscita: array a di interi di dimensione n
• Postcondizione: l'array a in output contiene una permutazione degli elementi dell'array a in input tale che ∀ i ∈ [0, n-2], a[i] ≤ a[i+1]

Selection sort

Per questa soluzione utilizzeremo l'algoritmo di ordinamento selection sort, ecco come funziona:

• Effettua una visita totale delle posizioni dell'array
• Visita totale: visita in sequenza tutti gli elementi dell'array
• Per ogni posizione visitata individua l'elemento che occupa la posizione con quello che la dovrebbe occupare
• In questo modo, se i è la posizione corrente (0 <= i < n), tutti gli elementi nelle posizioni comprese tra 0 ed i-1 rispettano l'ordinamento
• L'elemento che deve occupare la posizione i sarà il minimo tra quelli nelle posizioni comprese tra i ed n-1

Posizione corrente:

4 6 7 24 20 10 15 12 30 18

I numeri dal 4 al 7, cioè le posizioni dallo 0 al 2, sono già ordinati, bisogna quindi ragionare sulla parte dell'array che non è ancora ordinato. In questo momento il ciclo dell'algoritmo si trova sulla posizione 3, ovvero il numero 24. Il funzionamento è molto semplice, si trova il numero più piccolo nella parte di array che non è stata ancora analizzata e si scambia quel numero con la posizione corrente.

Il risultato sarà il seguente:

Posizione corrente:
4 6 7 10 20 24 15 12 30 18

L'algoritmo continuerà il suo lavoro fino alla fine dell'array e ci restituirà un array ordinato in senso crescente. Avremo ogni volta come risultato che la parte sinistra dell'array è già stata ordinata e non necessita di essere analizzata altre volte.

Implementazione dell'algoritmo: funzione ordina_array

Questa funzione è composta da un ciclo for, vediamo come funziona:

for (i = 0; i < n; i++)

Questo ciclo serve per scorrere tutto l'array ed analizzare ogni elemento. Per ogni elemento abbiamo bisogno di:

1. Individuare la posizione dell'elemento minimo compreso tra le posizioni i e n-1 dell'array a
2. Scambiare gli elementi di a

Come già detto prima, se necessario dobbiamo scrivere delle funzioni che verranno utilizzate dalle nostre funzioni, così facendo potremmo riutilizzare le funzioni per altri scopi, rendendo il codice riutilizzabile. Abbiamo quindi bisogno di due funzioni:

• minimo(a, n)
• scambia(i, j)

La prima serve per trovare il minimo e la seconda per scambiare l'elemento corrente con il minimo (ovviamente).

Funzione minimo

• Dati di ingresso: array a di interi di dimensione n
• Precondizione: n > 0
• Dati di uscita: array a di interi di dimensione n
• Postcondizione: ∀ i ∈ [0, n-1], a[min] ≤ a[i]

Funzione scambia

• Dati di ingresso: indirizzi degli elementi da scambiare
• Precondizione: gli elementi devono essere indirizzi di memoria
• Dati di uscita: valori degli indirizzi di memoria invertiti
• Postcondizione: gli elementi sono ancora indirizzi di memoria

Implementazione

Questa fase consiste in:

• Codifica dell'algoritmo nel linguaggio scelto
• Verifica (testing) del programma (individuazione di malfunzionamenti)
• Scelta dei casi di prova
• Esecuzione del programma
• Verifica dei risultati rispetto ai risultati attesi
• Utilizzo del software di base e di un ambiente di sviluppo

Codifica

Ecco un esempio di algoritmo in C:

int minimo (int *array, int lunghezza) {
    int min = 0;
    for (i = 1; i < n; i++) {
        if (a[i] < a[min])
            min = i;
    }
    return min;
}

void scambia (int *a, int *b) {
    int temp = *x;
    *x = *y;
    *y = temp;
}

void selection_sort (int *array, int lunghezza) {
    int i;
    for (i = 0; i < n-1; i++) {
        int min = minimo(&array[i], n-1) + i;
        scambia(&array[i], &array[min]);
    }
}

Il + i nella posizione evidenziata serve perché ogni volta che viene chiamata la funzione minimo, gli viene passato un array sempre più corto, perché gli viene passato l'indirizzo di array[i], ma i viene incrementato man mano nel ciclo. La funzione minimo non sa che quell'array che gli viene passato è solo una parte del nostro array, per cui all'indice che ci restituisce dobbiamo aggiungere il numero di elementi che la funzione non ha preso in considerazione, quindi +i.

Algoritmi di ordinamento (insertion sort e bubble sort)

Gli algoritmi di ordinamento servono per elencare gli elementi di un insieme secondo una sequenza stabilita da una relazione d'ordine. Per esempio:

• Ordinare una breve sequenza di numeri
• Mettere un elenco di nomi in ordine alfabetico
• Ordinare i record degli studenti secondo la data di nascita

Nel terzo punto vogliamo ordinare i dati secondo un criterio diverso, una chiave, cioè la data. La chiave può essere un singolo campo o la combinazione di più campi. Due elementi che presentano la stessa chiave mantengono lo stesso ordine con cui si presentavano prima dell'ordinamento. In ogni istante al più è allocato un numero costante di variabili, oltre all'array da ordinare. Il numero di operazioni da effettuare dipende dall'input. L'algoritmo può essere interno se i dati sono contenuti nella memoria RAM, o esterno se sono contenuti su un HDD.

Ci sono due categorie di algoritmi, quelli semplici e quelli avanzati. Gli algoritmi che vedremo ora ordinano tutti per controlli. Gli algoritmi semplici hanno un numero di operazioni quadratico rispetto alla taglia dell'input (n²), e sono:

• Selection sort
• Insertion sort
• Bubble sort

Alcuni esempi di algoritmi avanzati (più efficienti) invece sono:

• Merge sort (Von Neumann, 1945)
  • Numero di operazioni rispetto alla taglia dell'input: n log n
• Quicksort (Hoare, 1961)
  • n log n, nel caso medio
  • Quadratico nel caso peggiore

Selection sort

L'algoritmo selection sort consiste nello scorrere tutto l'array, elemento per elemento e cercare quello minore (o quello maggiore) per metterlo nella posizione attuale. È importante ad ogni ciclo non considerare i numeri che sono stati già ordinati.

Esempio

Posizione corrente:

15 4 7 20 1

Prima iterazione: Nella prima iterazione stiamo considerando il primo elemento, potrebbe essere o non essere quello minore, in questo caso non è quello minore (possiamo vedere subito che l'elemento minore è l'1). Avendo prima scritto la funzione minimo, la utilizzeremo per sapere qual è l'indice del numero minore. int min = minimo(&array[i], lunghezza-1)+i;

Abbiamo scritto anche la funzione scambia, quindi ci avvarremo di essa per scambiare di posizione l'elemento minore con quello che stiamo analizzando. Attenzione! La funzione scambia prende in input due puntatori, ed è per questo che riesce a scambiare i valori dell'array, la funzione minimo invece prende solo il primo parametro come puntatore. Occhio a passare l'indirizzo (&array[i]) e non il valore (array[i]).

Posizione corrente:

1 4 7 20 15

Come possiamo vedere, gli elementi 1 e 15 sono stati invertiti di posto.

Seconda iterazione: Nella seconda iterazione non dovremmo considerare l'elemento 1, perché è il minimo assoluto, ed è già stato messo al suo posto. A questo punto però la variabile i è stata incrementata di 1, per cui alla funzione minimo verrà passato sempre &array[i], ma visto che la i ora vale 1, è come se scrivessimo &array[1], e quindi l'elemento che sta in posizione 1. Le iterazioni continueranno fino alla lunghezza dell'array-1 (perché le numerazioni degli array partono da 0 e quindi vanno da 0 a n-1). Ad ogni ciclo quindi gli passeremo un array sempre più piccolo.

Questo esempio è perfetto, perché ci troviamo ad analizzare l'elemento in posizione 1, che poi è anche il più piccolo, quindi la funzione ci restituirà 0, perché ci restituirà l'indice in cui si trova l'elemento minore. La funzione non è a conoscenza del fatto che c'è un altro elemento prima, perché le abbiamo passato come inizio dell'array &arra[1], e quello per lei è l'origine dell'array, quindi l'indice 0. Per risolvere questo problema aggiungiamo alla riga che cerca il minimo +i, in questo modo sommeremo gli elementi che la funzione non sapeva ci fossero.

Avendo già scritto le due funzioni che ci serviranno non ci resta che scrivere l'iterazione (che è già scritta insieme alle funzioni a pagina 6).

Dobbiamo scansionare tutto l'array, e quindi:

void selection_sort (int *array, int lunghezza) {
    int i;
    for (i = 0; i < n-1; i++) {
        int min = minimo(&array[i], n-1)+ i;
        scambia(&array[i], &array[min]);
    }
}

Insertion sort

L'algoritmo insertion sort consiste nell'analizzare elemento per elemento tutto l'array, ogni elemento che si analizza viene inserito nella sua posizione. Gli elementi alla sinistra dell'elemento che si analizza sono già ordinati.

Esempio

Posizione corrente:

10 20 30 18 6 4 15 12 7 24

Nell'esempio si sta analizzando l'elemento 18, bisogna trovare una posizione per questo numero. Si scansiona l'array solo nella parte ordinata, e se si trova un elemento maggiore allora procediamo con l'inserimento prima di esso, altrimenti si mette alla fine.

Posizione corrente:

10 18 20 30 6 4 15 12 7 24

Per l'implementazione abbiamo bisogno di una funzione inserisci che deve individuare spostare tutti gli elementi verso destra (a partire dalla fine) e poi inserire il numero.

Funzione inserisci

• Dati di ingresso: array di interi, posizione, numero da inserire
• Precondizione: 0 ≤ n ≤ n-1
• Dati di uscita: array di interi ordinato
• Postcondizione: ∀ i ∈ [0, n-1], a[i] ≤ a[i+1]

Algoritmo in C:

void inserisci(int *a, int *n, int pos, int elemento) {
    int i;
    for (i = *n-1; i >= pos; i--) {
        a[i+1] = a[i];
    }
    a[pos] = elemento;
    (*n)++;
}

void insertion_sort(int *a, int n) {
    int i;
    for (i = 0; i < n; i++) {
        int j;
        for (j = 0; j < i; j++) {
            if (a[i] < a[j])
                inserisci(a, &n, j, a[i]);
        }
    }
}

Bubble sort

L'algoritmo bubble sort consiste nel confrontare gli elementi a due a due e sostituirli nel caso in cui quello di sinistra sia maggiore (o minore) di quello alla sua destra. Nel caso in cui non fosse maggiore, si passa all'elemento successivo.

10 20 7 18 6 4
10 7 20 18 6 4
10 7 18 20 6 4
10 7 18 6 20 4
10 7 18 6 4 20

Per questo algoritmo riutilizzeremo la funzione scambia scritta in precedenza.

Funzione bubble_sort

void bubble_sort(int *a, int n) {
    int i, j;
    for (i = 0; i < n; i++) {
        for (j = 0; j < n-1; j++) {
            if (a[j] > a[j+1])
                scambia(&a[j], &a[j+1]);
        }
    }
}

Organizzazione del codice

È buona norma suddividere il programma in moduli. Suddividere un programma in moduli offre alcuni vantaggi. Innanzitutto si rendono inaccessibili pezzi di codice che non si vogliono far modificare all'utente. L'utente deve sapere solo come si usa una funzione, non deve interessarsi del come è scritta. Suddividendo il programma in moduli è possibile importare i moduli in altri progetti evitando ogni volta di riscrivere la funzione. È inoltre più comodo e veloce individuare l'errore nel codice e correggerlo sostituendo solamente il modulo opportuno.

I moduli non sono altro che i famosi file ".h" (header file). Vediamo come crearne uno. Per prima cosa abbiamo la necessità di creare due file di testo, uno con estensione ".h" e uno con estensione ".c". Nel file ".h" ci scriveremo tutte, e sole, le dichiarazioni delle funzioni, mentre nel file ".c" scriveremo soltanto la funzione. Una volta fatto ciò basterà includere nel nostro programma principale, quello dove c'è il main, il nostro header, in modo analogo a quando si includono le altre librerie come <stdio.h>, <stdlib.h> ecc. L'unica accortezza che dobbiamo avere è quella di utilizzare i doppi apici ("lib.h") invece del minore e maggiore (<lib.h>).

Esempio

Header file (utils.h)

void scambia (int *a, int *b);

File .c (utils.c)

#include <stdio.h>

void scambia (int *a, int *b) {
    int temp = *x;
    *x = *y;
    *y = temp;
}

Notiamo che nel file utils.c abbiamo incluso la libreria <stdio.h>, questo perché il modulo potrebbe richiamare a sua volta funzioni che sono presenti in altre librerie, e che quindi devono essere incluse.