Laboratorio di Algoritmi e Strutture Dati
Marco Tarini
“Il Campus dei Puffi”
Consegna Progetto: entro Dom 31 Gennaio 2010 - ore 24.00
Il problema
Il campus universitario dei puffi, abitato in ogni dato momento da un certo numero di puffi studenti, accetta sempre nuovi iscritti. Al momento dell’iscrizione, ogni puffo riceve un numero di matricola, crescente (a partire da 0, e in sequenza). Ogni puffo coltiva molti hobby, che lo distolgono dagli studi.
Infatti i puffi non studiano molto e non si laureano mai.
Nei fine settimana, avvengono delle feste nelle quali nascono delle amicizie fra puffi. Le amicizie sono sempre reciproche, e una volta formate sono eterne. I puffi scelgono i propri amici in base alla similarit`a degli hobby coltivati (vedi dopo). Ogni puffo gode di un certo grado di popolarit`a: la popolarit`a di un puffo `e determinata semplicemente da quanti amici diretti ha (in un dato momento).
Oltre agli amici, ogni puffo possiede anche dei conoscenti. Non tutti i puffi si conoscono fra loro: ogni puffo conosce tutti i propri amici, naturalmente, e anche tutti quelli che i propri amici e i propri conoscenti conoscono (i puffi sono Socratici ed dunque ogni puffo conosce anche se stesso). Inoltre, a volte puffi che non si conoscevano prima fanno conoscenza reciproca fuori dalle feste, quando vanno a lezione (cio`e raramente), ma non per questo diventano amici.
Nel campus succede ogni tanto che si elegga un rappresentante degli studenti. Ogni puffo vota quello pi`u popolare fra tutti i conoscenti, scegliendo quello che appartiene al campus da meno tempo (le facce nuove fanno simpatia) in caso di ugual grado di popolarit`a. Il puffo pi`u votato viene eletto: in questo caso, a parit`a di voti vince quello presente nel campus da pi`u tempo.
Hobby e amicizie
Nel campus, esiste un hobby per ogni lettera dell’alfabeto: Arte, Bricolage, Cinema, Danza, Equitazione...
Ogni puffo coltiva i suoi hobby durante la settimana (almeno uno, e, spesso, alcuni hobby anche pi`u volte).
La sequenza di hobby coltivati durante la settimana `e dunque rappresentabile da una successione di lettere (anche ripetute).
Ad esempio, se un puffo coltiva durante la settimana gli hobby “anna” e un altro coltiva gli hobby
“amanda”, fra loro condividono due volte l’hobby ‘a’ e una volta quello ‘n’, per un totale di tre condivisioni.
L’ordine in cui ciascun puffo coltiva i propri hobby `e ininfluente.
Ogni fine settimana si svolgono delle feste a cui partecipano tutti gli studenti. Le amicizie si formano solo nelle feste e solo fra puffi che condividono almeno un hobby.
In ogni festa nasce al massimo (e di solito) un’amicizia, sempre fatalmente fra due puffi (non ancora amici) col massimo numero di hobby condivisi (cio´e, tale che nessuna altra coppia di puffi non ancora amici ne condivida un numero maggiore).
Nel caso in cui pi`u di una coppia di potenziali amici possa essere scelta secondo questo criterio, l’amicizia nasce fra i due puffi coi numeri di matricola pi`u vicini (sono accumunati da un simile ritardo nel laurearsi e, quindi, sono solidali). In caso di ulteriore parit`a, `e la coppia di pi`u vecchia immatricolazione.
1
Specifiche
Se al programma viene dato come argomento il nome di un file, il suo input deve essere il contenuto di questo file (di testo). Altrimenti, l’input sar`a letto dallo standard input (stdin).
Il programma deve leggere una sequenza di righe, ciascuna delle quali codifica un evento (che avviene nel campus) oppure una domanda sullo stato attuale. La sequenza `e terminata da una riga col carattere F (Fine).
Quando legge una domanda, il programma deve scrivere, in una riga dello standard output (stdout), la codifica della domanda stessa, seguita da ‘:’, seguita dalla risposta. Nient’altro deve essere scritto nell’output. Le domande vanno intese come relative al momento in cui sono poste (cio`e considerando come avvenuti solo gli eventi che le precedono).
Gli eventi e le domande possibili appaiono nella tabella 1 e 2 rispettivamente.
Evento Codifica Descriz
Iscrizione I <hobby> si iscrive un nuovo puffo, che coltiva
gli hobby specificati nella sequenza di lettere (minuscole, senza spazi) <hobby>
Lezione L <a> <b> i due puffi con matricola <a> e <b>
si conoscono a lezione Weekend W <n> avvengono <n> feste,
e si formano (fino a) altrettante amicizie Elezione E viene eletto un nuovo rappresentante
degli studenti
Tabella 1: Eventi
Dimensioni tipiche del problema
Dalle statistiche effettuate dal Grande Puffo, si sa che ogni settimana si iscrive di solito un numero circa costante di puffi. Si sa anche che, di solito, pi`u puffi ci sono pi`u feste organizzano, dunque ci si attende che il numero delle feste in ogni fine settimana sia, di solito, grossomodo proporzionale al numero di puffi presenti.
Le elezioni di rappresentante invece sono rare: in ogni istanza del problema, di solito avvengono al pi`u qualche volta.
Altri vincoli
Si pu`o supporre che il numero di puffi non sia superiore ad una mezza dozzina di migliaia. Nessun puffo coltiva pi`u di 100 hobby.
Si suppone che l’input sia sempre conforme alle specifiche (v. Tabelle), per cui non `e necessario control- larne la correttezza.
2
Domanda Codifica Risposta attesa:
Numero puffi? N numero di puffi presenti
attualmente nel campus
Hobby condivisi? H <x> <y> numero di hobby condivisi fra i puffi di matricola <x> e <y>
Quale dei due? Q <x> <a> <b> ‘A’ se il puffo di matricola <x> farebbe amicizia ad una festa con quello di matricola <a>
anzich´e quello di matricola <b>;
‘B’ altrimenti
Ultima amicizia? U Numeri di matricola dei due puffi che hanno stretto amicizia per ultimi,
[aggiunta:] e il numero di hobby da loro condiviso.
quante Amicizie? A numero totale dei rapporti di amicizia (reciproci) Popolarita? P <x> popolarit`a del puffo
con matricola n. <x>
sono Conoscenti? C <x> <y> ‘S’ se i due puffi di matricola <x> e <y> si conoscono
‘N’ altrimenti
Rappresentante? R numero di matricola dell’attuale rappresentante (-1 se non `e stato eletto), seguito dal numero di voti che ha ottenuto nell’ultima elezione
Tabella 2: Domande
Esempi
Dal sito del corso `e possibile scaricare esempi di input (file di testo) di difficolt`a crescente.
Per ogni esempio, `e anche fornito il corrispondente output corretto.
La correttezza `e un requisito necessario. Un progetto sar`a considerato pi`u o meno valido rispetto all’ef- ficienza (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). Un progetto pienamente valido dovr`a essere in grado di risolverle tutte in tempi ragionevoli.
Suggerimenti
1. Per leggere l’input e scrivere l’output si possono usare le funzioni standard ANSI C fscanf() e printf(). Il primo parametro della fscanf() sia una variabile posta a stdin oppure ad un FILE*
aperto in lettura (a seconda del numero di argomenti).
2. Soluzioni che impiegano un tempo cubico (o peggio) nel numero di puffi NON saranno abbastanza efficienti da risolvere le istanze grandi del problema. Saranno accettabili soluzioni di complessit`a spaziale quadratica?
3
3. Le domande compaiono in Tabella 2 con difficolt`a crescente, e nessuna domanda richiede, per la propria soluzione, di risolvere una domanda che la segue. Quindi le domande possono essere imple- mentate in quell’ordine. Molte domande sono buone candidate per diventare altrettante funzioni.
Inoltre, non tutti gli eventi servono a rispondere a tutte le domande...
4. Similmente, gli input forniti sono in ordine. Meglio non passare all’input successivo prima che il precedente venga risolto correttamente (con alcune eccezioni: per es il test 4 e 5 possono essere fatti prima o dopo il 2 e 3).
5. Nota: dati due puffi, la matricola determina l’ordine di ingresso nel campus.
6. La relazione “A conosce B” `e transitiva? E’ riflessiva? E’ simmetrica? Quindi...? Come si pu`o tenere traccia di chi conosce chi?
7. L’ordine degli hobby in una lista non conta. Cos’`e che conta allora?
8. La relazione “A conosce B” `e la chiusura della relazione “A `e amico di B” (pi`u le conoscenze fatte a lezione). Serve tener traccia di quale puffo `e amico di chi? Come tener traccia altrimenti di quanto sia popolare ogni puffo?
9. Si pu`o pensare ad una struttura per memorizzare le coppie di amici potenziali?
10. Leggere con attenzione la descrizione del problema e le specifiche. Ogni frase potrebbe mettere in luce un aspetto cruciale del problema.
11. SEMPRE: pensare bene sulla carta prima di cominciare a scrivere codice!
Presentazione del progetto
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.
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 da un mio messaggio. Per favore, il soggetto della mail includa la stringa “algo2009a”.
I progetti che non hanno ricevuto un mio messaggio di conferma non saranno considerati validi.
Occorre presentare, oltre al il codice sorgente, una sintetica relazione (formato pdf o ps) che illustri le strutture dati utilizzate e analizza il costo delle diverse operazioni richieste dalla specifica.
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.
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.
La realizzazione del progetto `e una prova d’esame da svolgersi individualmente.
Per ogni ulteriore chiarimento, e-mail: marco.tarini@isti.cnr.it
4
