\nuovoarticolo{Daniele Finocchiaro, Gianluca Marcoccia e Giuseppe
Sacco}{KnapDisk}{%
Daniele Finocchiaro \\
Via P.~Scuderi 1 \\
I-95015 Linguaglossa CT \\
Tel.:~(095)643014 \\
\medskip \\
Gianluca Marcoccia \\
Via Garibaldi 78 \\
I-56100 Pisa PI
\medskip \\
Giuseppe Sacco \\
Via Eduardo De Filippo 44 \\
I-30038 Spinea VE \\
Tel.:~(041)5411925
}{%
Internet:~marcocci@cli.di.unipi.it~(Marcoccia) \\
FIDO:~~~~~2:332/620.13~~~~~~~~~~~~~(Sacco)}
{italian}{%
It is practically impossible to teach good programming style to
students that have had prior exposure to BASIC: as
potential
programmers they are mentally mutilated beyond hope of
regeneration.}{E.W.~Dijkstra}

%\section*{KnapDisk(tm)}

%	Idee e implementazione: Gianluca Marcoccia
%	Ottimizzazione combinatoria e algoritmi: Daniele Finocchiaro
%	Interfaccia e interazione utente: Giuseppe Sacco


\sez{Introduzione}

Con la gestione di archivi di software di dominio pubblico sempre più
grandi, capita spesso di avere la necessità di archiviare
software, che si vuole tenere per necessità future, su memoria di massa.
Ci si scontra, però, con il problema di minimizzare il numero di dischi
usati per l'archiviazione. La soluzione che ci garantisce il minimo numero
di dischi è sicuramente l'utilizzo di un programma di backup, ma ciò
rende poco pratico il recupero dei dati, in quanto è necessario riutilizzare
per questa operazione lo stesso programma, quindi spesso è più comodo
sprecare un po' di spazio pur di avere i file immediatamente disponibili.
Il programma in questione si occupa, appunto, di trovare la migliore
disposizione possibile dei file, minimizzando il numero di dischi usati
per contenerli.

\sez{Il problema algoritmico}

I tempi di elaborazione dipendono dalla complessità dell'algoritmo usato per
la risoluzione di un problema. Sono state individuate diverse classi di
complessità, che raggruppano problemi di difficoltà si\-mi\-li tra loro e che
quindi hanno tempi di elaborazione comparabili. La classe NP comprende
problemi per i quali non è (ancora?) stato trovato un algoritmo polinomiale
(facile), ma per i quali non è nemmeno stato dimostrato che non è possibile
trovarne uno. Questa classe di pro\-ble\-mi deve essere risolta in tempo
esponenziale, e ciò significa che le risorse di calcolo e il tempo necessario
per la loro risoluzione sono notevoli. Il problema che ci si pone si riconduce a
un caso particolare del problema detto ``dello zaino'' (ricerca operativa)
che è gia stato dimostrato essere NP-completo (cioè essere tra i pro\-ble\-mi
più difficili di NP). Perciò, anche per istanze relativamente piccole del
pro\-ble\-ma, i tempi di calcolo sono impraticabili. Sono stati però studiati
diversi approcci, alcuni con soluzione approssimata, altri con soluzione
esatta, che permettono di trovare una soluzione al problema in tempi
abbastanza ragionevoli.


\sez{Approccio greedy (ingordo)}

Questo tipo di algoritmi consiste nel creare un ordinamento degli oggetti che
in\-te\-res\-sa trattare e scegliere gli oggetti in serie, prendendo sempre
l'oggetto che ha la massima probabilità di portarci più vicino alla soluzione
(oggetto più appetibile), nel nostro caso il file più lungo che entra nel
dischetto. Gli schemi di questo tipo sono polinomiali, ma possono portare a
soluzioni che si discostano nel caso peggiore del 33\% dalla soluzione ottima
(soluzione ottima: 10 dischi, soluzione greedy: 13 dischi). In ogni caso il
nostro obiettivo era una soluzione ottima, quindi un algoritmo di questo tipo
non era in\-te\-res\-san\-te.


\sez{Approccio branch \& bound}

Un altro approccio proposto in letteratura consiste nell'utilizzo di
algoritmi {\em branch \& bound}. Questo tipo di algoritmi consiste nel
generare l'albero delle possibili scelte ($2^n$ nodi!), ma esplorare solo i
sottorami che possono contenere la soluzione che ci interessa (una stima di
quali rami scartare si ottiene con una funzione ``bound'' {\em ad hoc};
migliore è la funzione, più rami verranno scartati, più sarà veloce la
convergenza dell'algoritmo). La complessità di questo tipo di algoritmi è
esponenziale nel caso peggiore, in quanto non si può e\-sclu\-de\-re di dover
visitare tutti i sottorami dell'albero, anche se questa possibilità è molto
remota. Abbiamo studiato e implementato alcuni schemi branch \& bound, ma
questi si sono rivelati molto più lenti di quanto sperato.


\sez{Approccio pseudopolinomiale}

Ci siamo quindi rivolti alla ricerca di algoritmi pseudopolinomiali
praticabili (ipotesi che avevamo all'inizio scartato per via della ingente
richiesta di memoria di questo tipo di algoritmi).
Gli algoritmi di questo tipo sono polinomiali secondo la cardinalità
dei dati in ingresso: se il numero di dati in ingresso relativo al numero
$n$ di elementi da considerare nell'algoritmo è limitato da una funzione
polinomiale in $n$, allora l'algoritmo è polinomiale, altrimenti è
esponenziale. Lo zaino ricade, purtroppo, in quest'ultimo caso.

Alla luce di quanto detto sopra, i pro\-ble\-mi principali avuti con un
approccio di questo tipo sono stati appunto relativi alla quantità di
memoria utilizzata durante l'esecuzione; dopo aver creato uno schema di
algoritmo generale, che però ancora richiedeva più di un megabyte di tavole
per la sua esecuzione, lavorando sul precondizionamento delle soluzioni,
e specialmente con l'utilizzo di strutture dati abbastanza efficienti,
siamo riusciti a ottenere una occupazione di circa 20~K di RAM per ogni
megabyte del device destinazione.
Il suddetto algoritmo si basa sull'utilizzo di una tabella in cui le
soluzioni vengono costruite in maniera incrementale a partire dalle
soluzioni precedenti. Quando nella tabella vengono riempiti gli elementi
relativi alla soluzione cercata, si opera una ricerca all'indietro
per sapere quali elementi hanno contribuito a costituire la soluzione.


\sez{Stime dell'occupazione del file system}

Un'altra parte dell'algoritmo che ha portato via molto tempo per la sua
implementazione è stata quella relativa alla stima dell'occupazione di
un file sul device destinazione. Infatti, il nostro programma prevede di
operare in diverse modalità:

\begin{enumerate}
\item copia dei file non preservando l'albero delle directory;
\item preservando l'albero delle directory, ma assumendo che
   ogni directory sia non divisibile;
\item preservando l'albero delle directory, ma permettendo la divisione di
   una directory su più dischi.
\end{enumerate}

Mentre i primi due casi ricadono in quello più generale, ed è relativamente
facile stimare quanto sarà l'occupazione dell'oggetto in questione sul
file system destinazione (anche se i file system sono abbastanza variati),
nel terzo caso ci troviamo di fronte a una serie di eventi condizionali
che complicano di molto il calcolo delle soluzioni.

Un esempio chiarirà la problematica: copiando un file sul disco, se la
directory in cui è contenuto il file non esiste sul disco è necessario
conteggiare nella lunghezza del file anche i blocchi necessari per la
creazione della directory, ma se già fa parte della soluzione un file
contenuto in quella directory non è più necessario considerare blocchi
addizionali, e così via. Purtroppo l'insieme di eventi da considerare è
tutt'altro che banale e aggrava notevolmente la complessità dell'algoritmo
che calcola le soluzioni. È stato infatti necessario, in alcuni casi,
ricorrere a operazioni di tipo {\em backtrack\/} (ricostruzione delle soluzioni
trovate fino a quel momento). I tempi di calcolo sono rimasti, in ogni caso,
nell'ordine di pochi secondi, come ci eravamo proposti all'inizio del
progetto. (Sono previste estensioni per il supporto dei file system \msdos{}
e \macintosh, che sono attualmente in fase di beta test avanzato e verranno
incluse nella prossima versione del programma.)

\sez{Interfaccia utente}

L'interfaccia utente sfrutta a fondo la {\em Amiga User Interface Style
Guide\/} e il sistema operativo 2.0 e 3.0 (se disponibile).

Tutta l'interfaccia è stata realizzata utilizzando le librarie Intuition e
Graphics. Non è stata utilizzata alcuna libreria di livello superiore come la
GadTools o la ReqTools: quasi tutti gli oggetti della interfaccia sono
BOOPSI. Tutta l'interfaccia è sensibile al font utilizzato nel sistema. Ciò
ha creato qualche problema con i caratteri sottolineati che indicano gli
shortcut. Utilizzando un font prestabilito non proporzionale avremmo potuto
usare il carattere underscore per sottolineare il carattere in questione, ma
non sapendo nulla a priori sul font da utilizzare si presentano due
soluzioni: utilizzare lo stile sottolineato tramite la libreria grafica o
fare a mano una linea sotto i caratteri in questione. È chiaramente la prima
soluzione quella più semplice che è stata scelta e che sarà implementata,
spero, in tempo per \IPISA{} '94. Una caratteristica non usuale per \amiga{} è
l'uso delle icone dei file rimpicciolite accanto al nome del file stesso.
Queste sono ottenute grazie alla funzione di scalatura della Release 2. Non
è stato semplice capire se un file fosse o meno un file Icona: la prima idea
fu: ``se chiedessimo l'icona di un file ¶{.info} otterremmo un errore'';
questo, purtroppo è {\em falso\/}: l'icona di un file ¶{.info} esiste. La
seconda fu: ``utilizziamo l'estensione del file''; anche questa una pessima idea.
Così attualmente il file viene aperto per vedere se ha l'identificatore
``magico'' all'inizio. Questa soluzione ha il grave svantaggio di rallentare
moltissimo la lettura della directory poiché occorre aprire il file e
leggerne una parte.

\sez{Guida ai riferimenti bibliografici}

[1] contiene la descrizione di decine di algoritmi di utilizzo generale con
molte routine in simil-Pascal. Particolarmente interessanti le strutture
dati, gli algoritmi di ricerca ed ordinamento e la sezione sulla
NP-completezza. Vengono, inoltre, descritte le pro\-ble\-ma\-ti\-che relative
alle tipologie di programmazione ``divide et impera'', ``greedy'',
``backtrack'', ecc. [2] è un libro completissimo di ricerca operativa.
Ab\-ba\-stan\-za complesso, fa grande uso di notazioni matematiche; rimane
comunque un indispensabile libro di riferimento per chi si occupa di
algoritmi di ottimizzazione combinatoria, mentre [3] è un testo enciclopedico
sull'NP-completezza, con centinaia di problemi NP-completi in appendice.


\begin{thebibliography}{0}

\bibitem[1]{}
A.A.~Bertossi.
\newblock {\em Strutture, Algoritmi, Complessit{\`a}}.
\newblock ECIG, Genova, 1990.

\bibitem[2]{}
C.~Papadimitriou and K.~Steilig.
\newblock {\em Combinatorial Optimization: Algorithms and Complexity}.
\newblock Prentice-Hall, Englewood Cliffs, NJ, 1982.

\bibitem[3]{}
M.~Garey and D.~Johnson.
\newblock {\em Computers and Intractability: A Guide to the Theory of
  {N}{P}-Completeness}.
\newblock Freeman, San Francisco, CA, 1979.

\end{thebibliography}

\finearticolo