Laboratorio di Programmazione 2
proff. A. Andreazza, E. Spoletini
Universita' degli Studi di Milano
Anno Accademico 2000/2001
Lezione 2
Introduzione
Scopo della seconda sessione di laboratorio e' utilizzare alcuni costrutti
del C (funzioni ricorsive e puntatori a funzioni) per costruire un programma
che faccia uno studio di funzione.
Durante questa sessione dopo aver effettuato il download di un file
di archivio compresso Lezione2.tar.gz,
si procedera' a:
-
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.
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 e' quello di implementare degli algoritmi, in
modo tale da avere un programma funzionante funzionante.
Il programma principale e' stato reso apposta poco flessibile: nella
prossima lezione vedremo come aggiungere delle caratteristiche al programma,
in modo da renderlo piu' potente e, se ci sara' tempo, anche piu' facile
da usare, attraverso un'interfaccia migliore.
In ogni caso il programma costruito sara' sufficientemente potente
da permettere di risolvere buona parte dei problemi di ricerca di minimi
o di soluzioni di equazioni in una dimensione.
Perche' una shared library?
Una shared library (quelle note come .dll in ambiente Windows)
e' una libreria di funzioni per cui il link viene fatto al momento dell'esecuzione
del programma. Questo ha due vantaggi:
-
il vantaggio principale e' che il programma eseguibile rimane di dimensioni
molto ridotte, poiche' non contiena al suo interno una copia di tutte le
funzioni di libreria che utilizza. Lo svantaggio principale e' che il programma
non e' piu' 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 perche'
non trova una .dll!). Percio' e' 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, sara' 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 cio' avrebbe causato
la ricompilazione di studio ogni volta che .funzione.so
viene cambiata, che e' 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 1: decomprimere e estrarre tutti i file dell'esercizio da Lezione2.tar.gz
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 e' scelto correttamente e si prestano bene ad utilizzare
la possibilita' 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 consistera' 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 puo' 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
Il programma studio e' 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 (cliccate con l'orecchio destro
del topo e selezionate Save Link As... per scaricarlo):
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.
La caratteristica principale di questo punto e' che il numero di sottointervalli
non e' noto al momento della compilazione, ma solo al momento dell'esecuzione.
D'altra parte e' 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 sara' da lavorare con studio su diverse funzioni!