Laboratorio di Algoritmi e Strutture Dati
Marco Tarini
“Ne rimarr` a soltanto uno.”
Consegna Progetto: entro Lun 19 Ago 2010 - ore 24.00
Il professor De Pescis, biologo, si sta trattenendo in vacanza per qualche giorno di troppo, e ha lasciato la sua gigantesca vasca dei barracuda senza alcuna supervisione. Le piccole uova si schiudono ogni notte, e di giorno i feroci animali, rimasti senza alcuna fonte di nutrimento, si sbranano a vicenda. Al suo ritorno, il prof. trover`a un solo, ben pasciuto sopravvissuto: ma quale?
Descrizione del problema
La vasca `e rettangolare e, al momento della partenza del De Pescis, contiene solo uova. Ogni uovo si trova in una posizione x, y sul fondo della vasca (la x rappresenta la distanza dal bordo Est della vasca e la y quella dal bordo Nord). Ogni notte se ne schiudono un certo numero. Il pesciolino pesa di solito assai poco all’inizio della propria vita; ci sono comunque alcune variazioni casuali in questo peso iniziale.
Appena nato, il pesciolino elegge a propria tana il punto dove `e nato. Da questo punto si guarda intorno, e per lui ogni cosa che si muova (non le uova, dunque, ma solo altri pesci) `e una potenziale preda.
Di giorno avvengono un certo numero di attacchi fra barracuda. Gli attacchi sono rapidissimi: pratica- mente istantanei. Il pesce attaccante, scelta una vittima, gli si precipita addosso, divorandola o venendone divorato. Se sopravvive, torna subito alla propria tana. L’esito dello scontro `e determinato dalla pi`u anti- ca regola del mare: il pesce pi`u grande (cio`e il pi`u pesante) mangia quello pi`u piccolo. Attaccare fornisce tuttavia un vantaggio: quando attacca, un pesce combatte come se avesse un peso maggiorato del 50%.
Nel raro caso di parit`a, vince comunque l’attaccante.
Dopo ogni pasto fratricida, un pesce incrementa il proprio peso di un decimo di quello della vittima che ha appena divorato.
Gli attacchi avvengono prevalentemente fra pesci vicini di casa. I barracuda sono infatti creature molto prevedibili: infallibilmente, sono sempre i due pesci pi`u vicini ad attaccarsi per primi. Fra questi, `e sempre l’individuo pi`u giovane, cio`e il pi`u irruento, ad attaccare l’altro (per pi`u giovane si intende quello nato dopo, fosse pure di pochi minuti). Fra diversi pesci potenzialmente attaccanti con prede altrettanto distanti, si muover`a per primo il pi`u giovane. Se lo stesso pesce deve scegliere fra prede altrettanto vicine, si muover`a prima verso quella pi`u giovane.
Le vacanze del professore
Il professore si assenta per un gran numero di giornate. Come sappiamo, ogni notte di assenza si possono schiudere alcune uova, e ogni giorno avvengono alcuni attacchi. L’ordine e il numero delle nascite, i dati relativi, il numero degli attacchi che avvengono durante ogni giorno, eccetera sono tutti descritti in un file che il programma prende in input, fino alla notte in cui si schiude l’ultimo uovo. Anche dopo questa notte, cio`e anche quando tutte le uova inizialmente presenti si sono schiuse, l’assenza del professore si prolunga e i pesci continuano a divorarsi reciprocamente, giorno dopo giorno, fino a che non ne rimane uno solo.
1
La domanda
Si vuole sapere la posizione e il peso dell’ultimo pesce rimasto cos`ı come lo ritrova il distratto De Pescis al ritorno dalle sue troppo prolungate vacanze.
Inoltre si vuole tener traccia del susseguirsi delle fortune dei vari barracuda. In particolare, si vuole sapere in ogni momento quale sia il pesce dominante, cio`e quello di peso massimo. Per fare questo, ogni volta che emerge un nuovo pesce dominante, si vuole sapere la sua posizione (cio`e quella della sua tana) e il suo peso, al momento del “sorpasso”.
Nota: ci sono tre casi in cui ci`o pu`o accadere.
A) quando un pesce, dopo un pasto, supera nel peso (i pareggi non contano) il pesce precedentemente pi`u grande;
B) quando nasce un pesce particolarmente vigoroso, gi`a in partenza pi`u grosso del precedente pesce di peso massimo; notare che questo succede anche quando nasce il primo pesce.
C) quando il pesce attualmente pi`u grosso viene pappato, e un altro gli subentra.
Input e output
Il progetto dovr`a prendere da riga di comando il nome di un file in Input da leggere. Dovr`a scrivere la risposta sullo standard output.
Input
L’input `e un file di testo che descrive una serie di notti alternate a giorni, iniziata e terminata da una notte. Nella prima riga compare il numero di notti presenti nel file.
Una notte `e segnalata da una riga contenente la lettera N seguita dal numero di uova che si schiuderanno quella notte. Ogni lieto evento `e descritto, in ordine di tempo, da una riga successiva dove vengono specificati tre numeri: le posizioni x e y dell’uovo che si schiude, in metri (precise al millimetro), e il peso iniziale del pesciolino w in decine di grammi (con una precisione del centesimo di grammo).
Un giorno `e segnalato da una riga contenente la lettera G seguita dal numero di attacchi che si manifestano, al massimo, quel giorno. Il numero effettivo potrebbe essere inferiore perch`e, quando rimane un solo pesce, non sono possibili ulteriori attacchi prima della notte successiva.
Output
L’output deve consistere in una o pi`u righe. Ogni riga corrisponde all’emergere di un nuovo pesce di dimensione massima, oppure al ritorno del prof. De Pescis (che avviene troppo tardi, quando ormai `e rimasto un solo pesce, probabilmente affamatissimo). La riga deve cominciare dalla lettera che identifica il tipo di evento: A, B o C, col significato descritto sopra, oppure D, che corrisponde al ritorno del professore.
Dopo la lettera che identifica l’evento, deve comparire nella stessa riga: il numero di pesci presenti attualmente nell’acquario, e la posizione (sia x che y) e il peso attuale del pesce dominante.
Vincoli
Anche le istanze pi`u grandi devono venire risolte entro un mezzo minuto (circa). Soluzioni che presentano complessit`a asintotiche molto peggiori di quelle ottimali non saranno ritenute in nessun caso sufficienti.
2
Anche se si pu`o assumere che i dati in input siano sempre nel formato descritto, e non `e dunque necessario verificarne la correttezza, il programma deve essere pi`u robusto possibile, nel senso che deve funzionare e dare buone prestazioni con input anche diversi da quelli forniti come esempio.
Istanze del problema
Esempi di varia grandezza sono disponibili nella pagina del corso, con le soluzioni.
Le istanze pi`u grandi possono comprendere intorno alla decina di migliaia di uova, o anche pi`u, che si schiudono nel corso di centinaia di giornate. Si sa che tanto pi`u un acquario `e affollato, tanto maggiore sar`a il numero di attacchi che i pesci effettueranno uno contro l’altro. Si sa inoltre che le uova con un tempo di gestazione pi`u lungo tendono a produrre pesci in media pi`u grandi. Si noti che i barracuda possono variare molto di dimensione, da pochi decimi di grammo degli individui pi`u piccoli appena nati da uova precoci (sono poco pi`u di placton) a svariati chili negli esemplari adulti pi`u grandi.
Suggerimenti
1. Per leggere l’input e scrivere l’output si possono usare le funzioni standard ANSI C fscanf() e fprintf().
2. Dati due punti A e B nel piano aventi coordinate, rispettivamente, (xA, yA) e (xB, yB), la distanza che li separa si trova banalmente col teorema di Pitagora: p(xA− xB)2+ (yA− yB)2.
3. I vari eventi che possono succedere (nascita e morte dei pesci) non sono ugualmente frequenti.
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. SEMPRE: pensare 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.
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 la copia derivata.
Note sul Codice
Il progetto va 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.
3
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?
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 “algo2009e”.
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.
Discussione
Il progetto deve essere discusso nella sessione di consegna. Si ricorda di presentarsi alla prova orale con una copia stampata della relazione e del codice.
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 periodicamente il sito per eventuali correzioni e/o precisazioni relative al testo del progetto.
Per ogni ulteriore chiarimento, e-mail: marco.tarini@isti.cnr.it
4
