Laboratorio di Calcolo 2
proff. A. Andreazza, D. Galli, E. Spoletini, G. Tiana, A. Vairo
Università degli Studi di Milano
Anno Accademico 2004/2005
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.
N.B.: siccome sotto Cygwin, le librerie si chiamano con l'estensione
.dll, il Makefile è diverso tra il laboratorio e quello che
da usarsi in Cygwin. Se fate degli esercizi a casa ricordate che tutti i
riferimenti a funzione.so, sono da sostituirsi con riferimenti a
funzione.dll
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:
export
LD_LIBRARY_PATH=${LD_LIBRARY_PATH}:. se la variabile
e' gia' definita
export 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!