Attenzione: questo sito viene mantenuto in linea per ragioni storiche, ma non viene più aggiornato. Riferitevi al nuovo sito ufficiale degli allenamenti.
Questa pagina contiene informazioni utili per la preparazione alle Olimpiadi Internazionali di Informatica, a cui l'Italia ha iniziato a partecipare nel 2000. La pagina è in costruzione (perenne), ed è gestita da alcuni allenatori che hanno preparato i partecipanti alle IOI del 2000, svoltesi a Pechino, del 2001, svoltesi a Tampere (Finlandia), del 2002, svoltesi a Yong-In (Corea) e del 2003, svoltesi a Parkside (Wisconsin, USA).
Sulla destra potete vedere la foto della premiazione di Alessandro Arzilli (il primo da sinistra), che ha guadagnato una delle medaglie di bronzo assegnate proprio nel 2000 (la prima medaglia italiana!). Più sotto, la squadra italiana del 2000 al completo, Alessandro Maconi (medaglia di bronzo nel 2001) e la squadra italiana del 2001, Stefano Maggiolo (medaglia di bronzo nel 2002) e la squadra italiana nel 2002. Infine, la squadra del 2003, che ha vinto due medaglie d'argento (Giuseppe Ottaviano e Gilberto Abram) e una di bronzo (Matteo Bruni). Ci sono anche delle foto che documentano la partecipazione alle IOI 2002 e alle IOI 2003.
Nel 2004, Luca Barbieri ha vinto la prima medaglia d'oro italiana. Inoltre, nella stessa gara, la squadra ha per la prima volta portato a casa quattro medaglie (Giorgio Audrito, Dario Cazzaro e Alessandro Piva hanno vinto una medaglia di bronzo).
Informazioni generali
Che cosa sono le olimpiadi di informatica?
Il sito dell'AICA contiene numerose informazioni di carattere generale. Se ve la cavate con l'inglese anche il sito ufficiale delle IOI è piuttosto interessante.
Ogni paese iscritto invia alle IOI quattro (o meno) partecipanti provenienti da scuole medie superiori (se siete più grandi, potete provare a gareggiare nell'ACM Programming Contest). La gara consiste nel risolvere tre (difficili) problemi di programmazione in cinque ore. I problemi in tutto sono sei, e sono divisi in due giornate di gara. Se volete avere un'idea dei problemi, c'è una serie di problemi tradotti, risolti e commentati e alcune testimonianze di ex-atleti.
La scelta dei partecipanti avviene tramite una serie di selezioni a livello locale, regionale e nazionali, in cui i candidati devono svolgere alcuni esercizi.
Come mi posso preparare alle olimpiadi di informatica?
Occorre unire una robusta base di conoscenze algoritmiche con una conoscenza perfetta del linguaggio di programmazione scelto (C, C++ o Pascal) e con una lunga esperienza sul campo dell'ambiente di programmazione. Un buon libro di algoritmi in italiano è Algoritmi in C, di Robert Sedgewick, pubblicato dalla Addison-Wesley italiana. Per quanto riguarda la programmazione da un punto di vista generale, Programmazione nella pratica di Kernighan e Pike (sì, quel Kernighan), pure pubblicato dalla Addison-Wesley, è da conoscere a memoria. Esiste una lista di prerequisiti per partecipare agli allenamenti che può indirizzarvi sulla strada giusta.
Che cosa devo conoscere per partecipare alle gare?
Le conoscenze fondamentali sono quelle algoritmiche. Dando per scontato che un partecipante sa utilizzare perfettamente tutte le strutture di basi fondamentali (vettori, liste ecc.), è necessaria anche una conoscenza reale di alberi, tavole di hashing, grafi orientati e non e dei relativi algoritmi di base.
Fino al 2000 si gareggiava sotto DOS (sic): il sistema operativo era quindi essenzialmente irrilevante. Nel 2001 sono stati resi disponibili Linux e Windows (in particolare, la correzione dei programmi avveniva comunque sotto Linux). Nel 2003 (come nel 2002) l'ambiente ufficiale di gara sarà Linux (Windows verrà messo a disposizione, ma correzione e valutazione saranno in ogni caso sotto Linux).
In ogni caso, il modo migliore per misurare la propria abilità e colmare le proprie lacune è risolvere problemi di olimpiadi precedenti, e, meglio ancora, partecipare a competizioni di programmazione in rete (per esempio, l'Internet Problem Solving Contest o la USA Computing Olympiad). Per fare questo è necessario avere un buon ambiente di sviluppo in C: un certo numero di ambienti scaricabili da rete è indicato nella pagina di programmazione 1 presso il corso di laurea in matematica. In ogni caso è consigliabile cercare di installare Linux, che porta con sé lo GNU C.
Ci sono anche siti che raccolgono problemi da varie competizioni simili alle IOI, come il Programming Contest Problems Archive.
Materiale didattico
Stiamo accumulando alcune dispense su temi di algoritmica e combinatorica che possono risultare utili.
- La programmazione dinamica, fondamentale per numerosi problemi (uno o due all'anno).
- Massima sottosequenza comune, un caso importante di programmazione dinamica utile per risolvere "Palidrome" (IOI 2000).
- L'algoritmo di Dijkstra, utile per risolvere "I semafori" (IOI 1999).
- Heap, heap indiretti e code di priorità, utile per implementare l'algoritmo di Dijkstra.
- Nozioni di base sulle permutazioni, utile per risolvere "Il parcheggio" (IOI 2000).
- La strategia MiniMax e le sue varianti, utile per risolvere i problemi che riguardano i giochi, come "Ioiwari" (IOI 2001) e "Punteggio" (IOI 2001).
- Linux per le IOI.
Le dispense possono essere lette con Ghostscript o con Adobe® Acrobat® Reader.
Come già detto, c'è una serie di problemi tradotti, risolti e commentati. In particolare, gli organizzatori delle IOI 2001 hanno messo a disposizione un libretto che descrive in dettaglio i problemi proposti (in inglese).