Laboratorio di Programmazione 2
proff. A. Andreazza, E. Spoletini
Universita' degli Studi di Milano
Anno Accademico 2000/2001
Lezione 3
Introduzione
Scopo di questa sessione di laboratorio è utilizzare alcuni costrutti
del C (funzioni ricorsive e puntatori a funzioni) per costruire un programma
che faccia uno studio di funzione. Inoltre apprenderemo come utilizzare
degli archivi in Linux.
Durante questa sessione dopo aver copiato il file di archivio compresso
studio.tar.gz
dalla vostra home directory alla directory di lavoro ed aver proceduto
a decomprimerlo, si dovrà:
-
implementare degli algoritmi generali per la ricerca di zeri, massimi e
minimi di una funzione;
-
interfacciare la funzione da studiare al programma mediante la creazione
di una shared library;
-
utilizzare il programma completato per studiare alcune funzioni;
-
come parte opzionale, si potra' modificare il programma per utilizzare
l'allocazione dinamica della memoria.
L'esercizio
Il file di archivio contiene una libreria (interfaccia.c) concepita
per fare da interfaccia ad un generico programma per l'analisi delle funzioni.
Essa si propone come strato intermedio tra il programma principale (in
studio.c)
e gli algoritmi di ricerca dei punti caratteristici di una funzione.
Questa struttura ha il vantaggio di permettere facilmente di cambiare
gli algoritmi di ricerca, senza dover modificare altre parti del programma.
Scopo dell'esercizio è quello di implementare degli algoritmi,
in modo tale da avere un programma funzionante.
Il programma principale è stato reso apposta poco flessibile:
come parte opzionale, vedremo come aggiungere delle caratteristiche
al programma, in modo da renderlo più potente e, se ci sarà
tempo, anche più facile da usare, attraverso un'interfaccia migliore.
In ogni caso il programma costruito sarà sufficientemente potente
da permettere di risolvere buona parte dei problemi di ricerca di minimi
o di soluzioni di equazioni in una dimensione.
Utilizzo di file di archivio
In ambiente UNIX, la procedura standard per distribuire pacchetti di file
(per esempio i sorgenti di programmi) è di utilizzare file di archivio
gestiti tramite il comando tar.
Per ridurre le dimensioni dei file di archivio, lo strumento più
comune è il programma di compressione gzip, che si utilizza
nel modo seguente:
gzip NomeFile per
comprimere un file
gunzip NomeFile per decomprimere
un file.
Per completezza, sono allegati le pagine del man di tar
e gzip.
Passo 1: decomprimere e estrarre tutti i file dell'esercizio da studio.tar.gz
A questo punto dovreste avere una sottodirectory Lezione3 con
tutti i file necessari.
Dovreste notare che ogni file .c è accompagnato da
un file .h, detto header file. In questo file sono messe le dichiarazioni
di tutte le funzion costruite all'interno del file .c e gli #include
necessari alla compilazione. In questo modo, se vogliamo comunicare ad
un altro programma come interfacciarsi con le nostre funzioni, basterà
includere questo header file, senza necessità di guardare il codice
vero e proprio.
Nell'esercizio 2, sarebbe stato più
consono allo standard della programmazione in C avere un file algoritmo.h
contenente la dichiarazione di ordina:
int ordina(int NumeroDiComponenti, float vettore[]);
ed inserire all'interno di ordinamenti.c e algoritmo.c
la direttiva:
#include "algoritmo.h"
Perche' una shared library?
Una shared library (quelle note come .dll in ambiente Windows)
è una libreria di funzioni per cui il link viene fatto al momento
dell'esecuzione del programma. Questo ha due vantaggi:
-
il vantaggio principale è che il programma eseguibile rimane di
dimensioni molto ridotte, poiché non contiena al suo interno una
copia di tutte le funzioni di libreria che utilizza. Lo svantaggio principale
è che il programma non è più autoconsistente: per
essere eseguito richiede di avere le librerie disponibili sul computer
in cui viene fatto girare (quante volte capita di scaricare un programma
per Windows che si rifiuta di partire perchè non trova una .dll!).
Perciò è particolarmente comodo usare shared library se il
programma utilizza librerie di sistema che sono sicuramente installate
su ogni macchina.
-
un altro vantaggio consiste nel fatto che e' possibile cambiare la shared
library senza per questo dover ricompilare il programma principale (se
non si cambia la dichiarazione delle funzioni utilizzate): quando cambieremo
la funzione da studiare, sarà sufficiente modificare il file funzione.c
e ricompilare la libreria .funzione.so, senza ricompilare studio.
Un'occhiata al Makefile
Per creare una shared library e' necessario fornire l'opzione -shared
al momento della compilazione. Nel nostro caso in piu, ci aspettiamo che
la funzione contenga riferimenti alla libreria matematica. Per includerla
e' necessario fornire il comando -lm al compilatore.
Per utilizzare la libreria shared, bisogna specificarla sulla linea
di comando di gcc, alla pari di tutti gli altri file oggetto.
Per questo e' stato aggiunto un test per verificare che .funzione.so
esista prima di compilare studio. In teoria sarebbe stato possibile
mettere .funzione.so nelle dipendenze di studio, ma ciò
avrebbe causato la ricompilazione di studio ogni volta che .funzione.so
viene cambiata, che è proprio quelle che vogliamo evitare.
LD_LIBRARY_PATH
Nel momento in cui studio viene invocato, il sistema operativo
cerca tutte le shared library di cui ha bisogno. Le shared library sono
cercate in una serie di directory di sistema piu' le directory definite
nella variabile di ambiente LD_LIBRARY_PATH. Per vedere se la variabile
e' definita e quale valore ha, bisogna dare il comando:
echo $LD_LIBRARY_PATH
Di default la directory di lavoro non fa parte di LD_LIBRARY_PATH,
che quindi deve essere definita esplicitamente con il comando:
setenv LD_LIBRARY_PATH ${LD_LIBRARY_PATH}:. se la variabile
e' gia' definita
setenv LD_LIBRARY_PATH .
se la variabile non e' ancora definita.
Passiamo ora all'esercizio vero e proprio.
Passo 2: leggere il file README per comprendere come bisogna utilizzare
il programma studio
Passo 3: leggere la descrizione delle interfacce agli algoritmi in algoritmi.h
e scriverne una implementazione in algoritmi.c
Come implementazione vi suggerisco di utilizzare i seguenti algoritmi di
ricerca di minimi e zeri, che garantiscono la convergenza se l'insieme
iniziale di punti è scelto correttamente e si prestano bene ad utilizzare
la possibilità di invocare funzioni ricorsivamente in C.
Metodo della bisezione
Se in un'intervallo una funzione continua cambia di segno, allora ci deve
essere almeno uno zero nell'intervallo.
Data la posizione iniziale in cui la funzione ha segno differente nei
punti A e B, si procede a valutarla in un punto intermedio C.
A seconda del segno di della funzione in C, possiamo stabilire se lo zero
si trova nell'intervallo AC o in CB.
Nel nostro caso l'intervallo contenente lo zero sara' AC, dato che
la funzione e' positiva in A e negativa in C.
La seconda iterazione quindi consisterà nel valutare di nuovo la
funzione in un punto D tra A e C e decidere se lo zero si trova in AD o
in DC. Il sezionamento può essere continuato fino a quanto gli estremi
dell'intervallo sono entro la precisione della ricerca.
Sezionamento per massimi e minimi
Una condizione sufficiente per avere un minimo locale nell'intervallo AC
e' avere un punto B tale che f(B)<f(A) e f(B)<f(C).
A questo punto, la valutazione della funzione su due punti intermedi D
ed E permette di ridurre l'intervallo di ricerca ad uno dei sottointervalli
AB, DE, o BC.
Nel nostro caso l'intervallo preferito e' chiaramente BC.
Un'ulteriore suddivisione dell'intervallo permette di ridurre ulteriormente
l'intervallo di ricerca a FG.
Passo 4: Utilizzare il programma per risolvere equazioni o problemi di
minimizzazione.
Miglioramento dell'interfaccia utente (parte opzionale)
Il programma studio è molto poco flessibile: accetta solo una chiamata
del tipo:
./studio x_minimo x_massimo
ma non permette di cambiare la precisione. Inoltre, l'intervallo iniziale
viene diviso in 10 sottointervalli prima di procedere alla ricerca dei
massimi e dei minimi in un sottointervallo. Per funzioni che oscillano
molto, potrebbe essere utile poter suddividere l'intervallo iniziale in
sottointervalli piu' piccoli.
Magari sarebbe interessante anche studiare la funzione diverse volte
in intervalli diversi o cambiando la precisione o la segmentazione in sottointervalli.
Queste funzioni sono parzialmente implementate nella seguente versione
del programma principale studio.c : se
studio viene invocato con due argomenti, questi vengono considerati
gli estremi dell'intervallo da studiare, il programma effettua lo studio
e poi termina. Altrimenti il programma chiede come input l'intervallo da
studiare, effettua lo studio e chiede un nuovo intervallo, fin tanto che
l'utente non esce dal programma con CTRL-D.
Passo 5: Modificare il nuovo studio.c in modo che il programma
possa essere invocato con quattro parametri:
./studio xminimo xmassimo numero_sottointervalli precisione
oppure con la forma
./studio
nel qual caso il programma richiede all'utente di fornire i parametri
interattivamente.
Per svolgere questo punto, bisogna sapere che la definizione completa della
funzione main è:
int main( int argc, char* argv[] )
dove argc è il numero di argomenti sulla riga
di comando (il nome del programma e argc-1 parametri). Il
vettore di stringhe argv contiene tali argomenti. Nel nostro
caso:
-
argc vale 5,
-
argv[0] è la stringa contenente il nome del
programma: ".\studio",
-
argv[1] è il valore di xminimo espresso come
stringa, per esempio "-2.00",
-
argv[2] è il valore di xmassimo espresso
come stringa,
-
argv[3] è il numero di sottointervalli espresso
come stringa,
-
argv[4] è la precisione da raggiungere, espressa
come stringa.
Per convertire una stringa nel suo valore numerico, la si può leggere
come se fosse un file, usando però la funzione sscanf:
sscanf(argv[1],"%f",&xmin);
dove il primo argomento di sscanf è la stringa
da cui leggere, seguito dal formato in cui leggerne il contenuto, con le
stesse regole usate per scanf, ed infine la lista delle
variabili in cui mettere il risultato della lettura.
La caratteristica principale di questo punto è che il numero
di sottointervalli non è noto al momento della compilazione, ma
solo al momento dell'esecuzione. D'altra parte è necessario dimensionare
un vettore di lunghezza pari a
numero_sottointervalli+1.
La soluzione che il C fornisca a questo problema e' l'allocazione dinamica
della memoria attraverso la chiamata alla funzione malloc
(la memoria utilizzata deve poi essere rilasciata con la funzione free!).
Relazione
Per riempire il formulario
ci sarà da lavorare con studio su diverse funzioni!