Esami del corso Algoritmi (Laurea Magistrale in Ingegneria e Scienze Informatiche) - Verona

Problemi Proposti in preparazione

Modalità Esame

In un'aula computer della facoltà (finora sempre aula delta) occupiamo un blocco contiguo di postazioni nelle quali vi collocate opportunamente distanziati. L'esame è una prova individuale. Ad inizio esame consegnate gli smartphone, chi viene sorpreso ad utilizzare un qualsiasi strumento elettronico (a parte il calcolatore assegnato) od a comunicare indebitamente, si ripresenterà una prossima volta. Si chiede a tutti di andare in bagno prima dell'inizio dell'esame, in modo da ridurre al minimo le impellenze. Si fa presente che, in estate, l'aula delta è fredda, e non abbiamo alcun controllo sulla sua temperatura. Consiglio pantaloni lunghi e golfino subito messo/tolto.

Accedete come "esame" ad un'account isolato dove avete gli applicativi che vi servono (terminale con bash, g++, gcc, ddd, editors quali emacs, kite, ...). All'apertura dell'account vi appare in finestra di browser la lista dei file da me messi a disposizione per quell'esame, tra cui:

i testi dei 3 problemi da affrontare;
codici di solutori di problemi precedenti da cui potete eventualmente copiare parti da riutilizzo (apertura/scrittura file, qualche struttura dati o procedura di base che non mi dispiace possiate riutilizzare nel contesto di quello specifico esame);
eventualmente alcune istanze o generatori di istanze per facilitarvi nel debug (ma tipicamente è lasciato a voi di ingegnarvi per produrvi da soli queste cose molto utili).

Su ciascuno dei 3 problemi sono in palio 20 punti, uno per ogni caso di prova che il vostro programma risolverà correttamente secondo le specifice ed entro i limiti di tempo e memoria assegnati. Il primo dei 20 casi di prova tipicamente coincide con il caso d'esempio nel testo dell'esercizio, ma gli altri casi vengono resi noti solo dopo l'esame. Se ad esempio uno dei problemi si chiama "pacman", allora il solutore da voi prodotto per questo problema si chiamerà pacman.c oppure pacman.cpp a seconda se volete che venga compilato con:

gcc -Wall -O2 -o pacman pacman.c

piuttosto che non con:

g++ -Wall -O2 -o pacman pacman.cpp

Per sottomettere tale soluzione (ad esempio il file "pacman.cpp") utilizzate il browser (l'interfaccia è immediata, vi apparirà un menù di tipo "Sfoglia File" per consentirvi di inviare il vostro file "pacman.cpp" in locale verso il mio archivio delle vostre sottomissioni). Rispettare questo standard per il nome del file è utile sia perchè la mia compilazione sia identica alla vostra sia per assegnare il vostro solutore al problema (dei 3 problemi proposti) che esso intende risolvere. Per ciascuno dei 3 problemi, verrà tenuta buona l'ultima soluzione sottomessa entro lo scadere del tempo limite, come meglio precisato a inizio esame (tipicamente verrà assegnato un tempo di circa 4 ore e mezza). Le vostre soluzioni debbono rispettare rigidamente le specifiche per poter essere adeguatamente valutate. Ad esempio, tipicamente non è consentito leggere o scrivere da standar input (in quanto non previsto nelle specifiche) ma dovete leggere l'istanza nel file "input.txt" e scrivere la risposta nel file "output.txt" in ottemperanza del formato precisato nel testo dell'esercizio. Grosso modo la struttura dell'esame è quella sopra riportata ma, se verrà ritenuto utile, ovviamente potranno aversi variazioni (istanze da risolvere note a priori, interazione del vostro programma contro avversari, ...). Comunque, specie in questa fase in cui cerchiamo di convergere rapidamente verso una standardizzazione dell'esame, ove si dovessero presentare tali modifiche nella struttura esse verranno opportunamente segnalate in corso d'esame, e si cercherà sempre di essere graduali e darci una continuità. Ad esempio, nel tema (2012.07.23) trovate tutti e 3 gli esercizi svolti. Nel tema (2012.06.20) trovate svolto solo l'esercizio del tournament. Poi, quando siamo passati al sistema con PortafoglioVoti, ho ridotto sugli svolgimenti ma rendo accessibile, per alcuni problemi, l'intero pacchetto problema (potete visulalizzare le nostre soluzioni ed anche la truttura del pacchetto).

Strategia Consigliata

Leggere tutti e 3 i testi dei problemi cercando di comprendere bene cosa venga richiesto e possibilmente di inquadrare a grandi linee le strategie risolutive che possano risultare adatte. Lavorare su carta e penna per mettere a punto degli algoritmi risolutivi. Aver individuato anche l'algoritmo ottimo non implica che convenga passare direttamente alla codifica, progettare a tavolino una adeguata strategia di codifica può salvare molto tempo e molti sforzi. Cercare solo algoritmi ottimi (od anche limitarsi ad algoritmi polinomiali può essere talvolta ingenuo), vuol dire rinunciare a sottoporre almeno una qualche soluzione per ciascuno dei tre problemi, mentre una parte di punti è messa in palio anche su istanze piccole e può risultare penalizzante rinunciare a tali punti. Dedicare una cartella diversa a ciascuno dei 3 problemi. Vedere il tutto come una sfida, tra l'altro non mi dispiacerebbe riuscissimo a mettere assieme una squadretta del nostro ateneo per partecipare alle ACM Contest.

created: 23 luglio 2012
updated: 24 febbraio 2016