Laboratorio di Algoritmi e Strutture Dati
Marco Tarini
“Tasselli e malta”
Consegna Progetto: entro Dom 28 Nov 2010 - ore 24.00
1 Il problema
Si vuole rivestire un pavimento rettangolare con un mosaico di tasselli e di malta a presa rapida.
Ogni tassello ha la stessa grandezza ma `e delimitato da quattro bordi frastagliati di forma (in generale) diversa. I bordi di un tassello possono collimare pi`u o meno bene con i bordi degli altri tasselli. I tasselli hanno un orientamento predefinito e devono essere collocati con quell’orientamento, a causa della fantasia disegnata nella parte superiore. Quindi ogni tassello ha un bordo Nord, uno Sud, uno Ovest e uno Est.
I tasselli inizialmente sono dentro a delle scatole dall’identico contenuto. Queste scatole sono sempre disponibili in numero sufficiente per terminare il lavoro. Ciascuna scatola contiene un numero prefissato k di tasselli numerati da 1 a k, sempre gli stessi in ogni scatola. Ad esempio, il tassello con numero di serie 3 della prima scatola ha la stessa forma (gli stessi bordi) del tassello numero 3 di tutte le altre scatole. Il numero di ordinamento `e scritto sul retro di ogni tassello, in piccolo. I tasselli possono essere estratti dalle scatole solo in tal ordine, da quello con numero di serie 1 a quello con numero di serie k.
Il pavimento, delimitato dalle quattro pareti, si pu`o immaginare come una griglia regolare di caselle quadrate, ciascuna delle quali dovr`a alla fine del lavoro contenere un tassello o essere riempita di malta.
All’inizio del lavoro, ogni casella della griglia `e vuota.
2 Costruzione del mosaico
Ecco come si procede alla costruzione del pavimento.
Per cominciare, si apre la prima scatola, e si mette il suo primo tassello nel mezzo del pavimento, nell’orientamento prescritto (i pavimenti hanno una numero dispari di caselle per lato, quindi esiste una casella centrale). Si rovescia il resto del contenuto della scatola in una apposita cesta di lavoro. Si apre una scatola di riserva, se ne estrae il primo tassello e lo si pone nella cesta, in modo che questa contenga ora tanti tasselli quanti ce ne sono in una scatola.
A questo punto, si procede sempre nello stesso modo, fino a quando l’intero pavimento sia completato, cio`e non vi siano pi`u caselle vuote: si incolla un tassello alla volta sul pavimento, e talvolta, dopo averlo fatto, si usa la malta liquida per riempire alcune zone del pavimento delimitate da tasselli gi`a posizionati.
Ad ogni passaggio, si deve prendere un tassello dalla cesta per incollarlo sul pavimento, sempre accanto ad un tassello gi`a posizionato, in una casella ancora libera adiacente lato a lato a quest’ultimo. La scelta del tassello e della casella viene effettuata in modo da far collimare il pi`u possible il bordo del nuovo tassello con quello del tassello gi`a posizionato (vedi sotto).
Nell’estrarre il tassello dalla cesta di lavoro, lo si rimpiazza immediatamente col prossimo tassello preso dalla scatola di riserva, in modo che durante l’intero lavoro la cesta contenga sempre lo stesso numero di tasselli (tanti quanti ce ne sono in una scatola). Se la scatola di riserva rimane vuota, si apre semplicemente la scatola successiva, che servir`a da nuova scatola di riserva.
Dopo aver posto un tassello, si controlla se il pavimento presenta delle zone completamente delimitate da tasselli gi`a incollati: queste zone vengono subito riempite con la malta a presa rapida. Per “zona completamente delimitata” si intende un qualunque sottoinsieme di caselle vuote ciascuna delle quali sia adiacente lato a lato solo ad altre caselle di questo sottoinsieme oppure a tasselli gi`a incollati (ma non alle pareti che delimitano la stanza). La malta viene versata nella zona (o le zone) fino a riempirla, dopodich`e si indurisce. Le caselle piene di malta indurita non possono pi`u accogliere alcun tassello.
2.1 Bordi che collimano e bordi che non collimano
Come detto, i bordi dei tasselli sono frastagliati. Ognuno dei quattro bordi `e infatti caratterizzato da un certo numero n di dentellature in sequenza (n `e lo stesso per tutti i bordi di tutti i tasselli di un dato problema). Ciascuna dentellatura pu`o essere piatta, oppure rientrante, oppure sporgente. Rientranze (e sporgenze) possono essere profonde (o estroflesse) di una lunghezza variabile. Le rientranze sono descritte da numeri negativi, le sporgenze da numeri positivi: tanto maggiore il modulo del numero tanto pi`u profonda o estroflessa `e la rientranza o la sporgenza; una dentellatura piatta `e descritta dal numero zero.
Le rientranze rappresentate dal numero −k (con k naturale) collimano perfettamente con sporgenze della stessa entit`a, rappresentate dal numero opposto +k, e viceversa. In generale, il mismatch fra due dentellature k1k2`e un numero che rappresenta quanto quelle due dentellature sono lontane dal collimare perfettamente. E’ calcolato semplicemente con (k1+ k2)2. Il mismatch fra un intero bordo e un altro `e la somma dei mismatch delle rispettive dentellature, in ordine.
Un tassello viene descritto da tutte le dentellature che si trovano sui suoi bordi, in ordine orario (n per lato cio`e 4n), a partire da quelle pi`u a Ovest del bordo Nord.
2.1.1 Esempio
Ad esempio, si supponga n = 3, e che il primo tassello A posto nel pavimento abbia le dentellature:
(1, 3, −3, 9, 2, −1, 0, 0, 1, 3, −2, 3). Si dia un secondo tassello B ancora nella cesta con le dentellature:
(5, −2, 3, 1, 0, 3, −4, −5, 3, −1, 3, 1). Vale, cio`e, il seguente schema:
+1 +3 -3 +5 -2 +3
+3 +9 +1 +1
-2 A +2 +3 B 0
+3 -1 -1 +3
+1 0 0 +3 -5 -4
Se si pone il tassello B a Est del tassello A, il bordo Est di A (9,2,-1) avr`a un mismatch col bordo Ovest di B (+1, 3, -1) di (1 + 9)2+ (2 + 3)2+ (−1 + −1)2= 100 + 25 + 4 = 129. Ponendo il tassello B a Sud del tassello A, si otterrebbe invece un mismatch fra bordo Sud di A e bordo Nord di B di (1 + 5)2+ (0 + −2)2+ (0 + 3)2= 36 + 4 + 9 = 49, minore e dunque preferibile al primo.
2.1.2 Scelta del tassello e della casella
Quando si deve scegliere il tassello fra quelli contenuti nella cesta, e il bordo libero a cui attaccarlo, bisogner`a preferire quel tassello e quel bordo libero che ottengano fra di loro un mismatch minore, fra tutte le scelte valide possibili di questo tipo (per “bordo libero” si intende il bordo di un tassello gi`a posizionato adiacente ad una casella ancora vuota). In caso di parit`a fra due o pi`u alternative, si sceglier`a di posizionare il tassello che presenti il numero di serie minore. Se il tassello scelto pu`o essere messo in due caselle diverse con lo stesso valore di mismatch, si scelga la posizione pi`u a Nord delle due, e in caso di ulteriore parit`a, quella pi`u a Est.
Nota: puo succedere che alcune caselle vuote saranno adiacenti a pi`u di un tassello gi`a incollato, cio`e che pi`u bordi liberi siano adiacenti ad una stessa casella vuota. Il criterio di scelta per`o valuta sempre ogni bordo separatamente, e nel sceglierne uno non conta quanto bene o quanto male gli altri bordi liberi collimino col tassello che viene eventualmente posto accanto ad essi. Ad esempio, si consideri la seguente situazione, dove in un minuscolo pavimento 2 × 2 siano stati collocati i tasselli A, B e C in questo modo:
A B C .
Un nuovo tassello D sar`a posizionato nella casella vuota rappresentata dal puntino a condizione che il bordo Ovest di D abbia un mismatch col bordo Est di C minore di quello ottenuto con qualunque altra scelta – e se questo si verifica non conta il mismatch fra il bordo Nord di D e il bordo Sud di B (se il mismatch minore possibile si trovasse fra il bordo Sud di B e il bordo Nord di D, ugualmente il tassello D sar`a posizionato nella casella vuota – indipendentemente dal valore di mismatch fra il bordo Ovest di D e quello Est di C.)
3 Input e Output
Il file deve prendere dalla riga di comando il nome del file di input. Deve produrre in risposta un file di output, con un nome uguale a quello del file di input, giustapposto alla stringa .pnm. (ad esempio, se prende in input il file test.txt dovr`a produrre in output il file: test.txt.pnm
3.1 Dati in input
L’input consiste in file di testo, in cui il problema viene descritto con una serie di numeri interi (separati da spazi, caratteri di accapo, etc).
Per prima cosa compare la dimensione orizzontale e verticale del pavimento (sempre due numeri dispari). Segue il numero di tasselli contenuti in ogni scatola, e il numero di dentellature che compaiono in ognuno dei quattro lati di ogni tassello. Dopodiche’ compare la descrizione di ciascun tassello, uno dopo l’altro. La descrizione di un tassello consiste nella sequenza dei i valori numerici che rappresentano ciascuna dentellatura di ciascun lato (nell’ordine sopra descritto).
3.2 Dati in output
Il file di output deve consistere in un file di testo. All’inizio di questo file, nella sua prima riga, deve comparire la stringa di due caratteri “P1”. Nella seconda riga, devono comparire la larghezza e la lunghezza del pavimento, separate da uno spazio.
Di seguito, deve comparire la descrizione di come appare il pavimento alla fine del lavoro, a partire dalla fila pi`u a Nord del pavimento, fino alla riga piu’ a Sud, con una riga di testo per ogni fila. Ogni fila viene descritta da un numero binario per ogni casella, separati da uno spazio: 0 se la casella contiene un tassello, 1 se contiene malta.
3.3 Altri vincoli
La correttezza delle soluzioni `e un requisito necessario. Un progetto sar`a considerato pi`u o meno valido rispetto all’efficienza (tempo di calcolo) nel risolvere le istanze del problema di dimensioni via via crescenti (non solo le istanze fornite, ovviamente, ma anche altre del tipo di quelle fornite).
La sfida consiste nel fornire una soluzione che riesca a risolvere in tempi ragionevoli le istanze pi`u complesse possibili. Quali delle istanze proposte sar`a possibile risolvere?
4 Dimensioni e natura delle tipiche istanze del problema
I pavimenti possono essere molto grandi (o equivalentemente, i tasselli molto piccoli). Pavimenti composti di migliaia di tasselli per lato non sono incomuni. Anche il numero di tasselli diversi presenti nelle scatole pu`o essere
assai grande. Il numero di dentellature per ogni lato di tassello e’ di solito contenuto.
Dati di esempio di input sono disponibili in rete alla pagina del corso.
5 Suggerimenti
1. Per leggere l’input e scrivere l’output si possono usare le funzioni standard ANSI C fscanf() e fprintf().
2. Chiediti: nel posizionare un tassello su una casella vuota del pavimento, basta osservare la configurazione delle K × K caselle intorno a quella per determinare se sia arrivato il momento di mettere mano alla malta, o meno (per un qualche intero K)?
3. Trucco generale spesso utile (ma non necessariamente in questo caso, e non certo per tutte le soluzioni possibili): non sempre `e necessario implementare la rimozione di elementi non pi`u validi dalle strutture dati che si sono scelte. Qualche volta `e sufficiente sapere riconoscere gli elementi non pi`u validi solo quando si estraggono dalle strutture dati, oppure marcarli come tali.
4. Domanda-trucchetto: `e possibile, secondo il candidato, che gli algoritmi e le strutture dati insegnati durante il corso non abbiano alcuna relazione col progetto assegnato??
5. Ancora pi`u chiaramente: soluzioni basate solo su ricerche esaustive NON risolveranno i problemi in maniera soddisfacentemente efficiente.
6. SEMPRE: ragiona bene sulla carta prima di cominciare a scrivere codice! Il problema potrebbe essere riformulato in modi pi`u semplici. Strutture dati adeguate vanno identificate correttamente. Mezz’ora in pi`u di ragionamento pu`o far risparmiare giornate di implementazione fuori rotta.
6 Cosa, come, quando consengare
Occorre presentare, oltre al codice sorgente, una sintetica relazione (formato pdf o ps) che illustri le strutture dati utilizzate e analizzi il costo della propria soluzione.
La realizzazione del progetto `e una prova d’esame da svolgersi individualmente. Progetti che saranno ritenuti semplici varianti uno dell’altro non verranno corretti, a prescindere di quale sia stato l’originale e quale il lavoro derivato.
6.1 Note sul Codice
Il progetto deve essere implementato in C (si faccia riferimento allo standard ANSI). Vi `e piena libert`a sulla scelta dell’ambiente di sviluppo, ma il codice deve poter essere compilato con gcc e funzionare correttamente se eseguito da linea di comando. Puo’ consistere in un solo file sorgente .c oppure in un piccolo insieme di files .c e .h.
Il codice deve essere ben documentato: per esempio, laddove non sia immediatamente chiaro dal contesto, ogni funzione deve essere preceduta da una breve descrizione del suo scopo, del significato dei suoi parametri, etc.
6.2 Note sulla Relazione
La relazione deve essere sintetica, ma deve descrivere le strutture dati adoperate, e quali algoritmi noti sono stati utilizzati su di esse (per risolvere quale sottoproblema). Si pu`o includere una breve analisi della complessit`a delle principali sottofunzioni implementate, ma e’ importante includere una stima asintotica della complessit`a totale (spaziale e temporale) della soluzione proposta (ricordandosi anche di specificare cosa si intende con gli argomenti delle funzioni).
La relazione non deve invece includere una ripetizione della descrizione del problema. A cosa servirebbe?
6.3 Modalit` a di consegna
L’elaborato deve essere inviato per posta elettronica all’indirizzo marco.tarini@isti.cnr.it entro e non oltre la data indicata. L’avvenuta ricezione del progetto sar`a confermata con un mio messaggio. Per favore, il soggetto della mail includa la stringa “algo2009g”.
Tutti i file spediti dal sorgente devono chiamarsi col proprio nome e cognome, per es ‘francorossi’. Solo l’estensione cambia: ‘.c’ per il file sorgente, se unico, ‘.zip’ se il progetto comprende pi`u di un file sorgente (e allora tale zip conterr`a solo alcuni file ‘.h’ ‘.c’), ‘.pdf’ o ‘.ps’ per la relazione.
Non inviare file eseguibili, neanche in cartelle compattate.
I progetti che non hanno ricevuto un mio messaggio di conferma non saranno considerati validi.
6.4 Discussione
Il progetto deve essere discusso nella sessione di consegna.
La versione aggiornata del progetto `e pubblicata sul sito del corso (cercare la mia pagina con google – “Marco Tarini”, seguire “teaching” in fondo, seguire “lab di algoritmi 2009/2010”). Si consiglia di consultare periodica- mente il sito per eventuali correzioni e/o precisazioni relative al testo del progetto.
Per ogni ulteriore chiarimento, e-mail: marco.tarini@isti.cnr.it
