di ROBERTO GROSSI
Le Olimpiadi Internazionali di Informatica (IOI: International Olympiad in Informatics) nascono in Bulgaria nel 1989 con il patrocinio dell’UNESCO (United Nations Educational, Scientific and Cultural Organization) e si svolgono con cadenza annuale. È la più importante e prestigiosa gara di Informatica rivolta agli studenti delle scuole medie superiori e si affianca alla gara ACM International Collegiate Programming Contest rivolta agli studenti universitari. La tipologia della gara permette di far emergere i talenti di questa disciplina, mettendoli in contatto con le realtà culturali di circa 80 Paesi, attraverso una competizione di alto livello scientifico.
Le prossime edizioni si terranno in Thailandia (2011), Italia (2012), Australia (2013), Taiwan (2014) e Kazakhstan (2015). Ogni Paese può partecipare con una squadra di non più di quattro studenti. La gara è individuale: il concorrente affronta in due giorni distinti, avendo a disposizione cinque ore al giorno, quattro problemi di natura algoritmica e di problem solving. Trascorre poi i restanti giorni in attività socio-culturali. La premiazione avviene a fasce per cui la metà dei partecipanti ottiene una medaglia: precisamente, un quarto dei partecipanti vince la medaglia di bronzo, un sesto quella d’argento e un dodicesimo la medaglia d’oro. Il sito ufficiale delle IOI è http://www.ioinformatics.org/.
Lo studente italiano interessato alle nostre selezioni per far parte della nazionale italiana può allenarsi presso il nostro sito (http://correttore.olimpiadi-informatica.it/) in vista delle quattro fasi di selezione:
– Scolastica: vengono scelti un migliaio di studenti tra gli oltre 10.000 partecipanti.
– Territoriale: vengono scelti 80 studenti tra il migliaio a disposizione.
– Nazionale: viene svolta la gara nazionale, denominata Olimpiadi Italiane di Informatica, individuando i vincitori nazionali e selezionando in totale un gruppo di 15-20 studenti chiamati “Probabili Olimpici”.
– Olimpica: vengono scelti i 4 componenti della squadra italiana per partecipare alle IOI, più 2 riserve, tra i Probabili Olimpici dopo un periodo di allenamento e formazione residenziale e telematica con i Selezionatori Nazionali.
Ecco un assaggio di problema impegnativo, denominato Fish e dato nell’edizione internazionale delle IOI 2008 in Egitto. Partiamo dalla situazione iniziale in cui ci sono un certo numero N di pesci, ciascuno con una perla nel proprio stomaco. Non tutte le perle sono dello stesso tipo, ma ci sono P tipi differenti di perle. Pesce grande mangia pesce piccolo: la regola qui si applica quando la taglia del pesce grande è almeno il doppio della taglia di quello piccolo, altrimenti non può mangiarlo. Poiché le perle non vengono mai digerite, il pesce ingerisce anche le perle del pesce piccolo che mangia. Con il tempo, i pesci accumulano perle quando mangiano via via i pesci più piccoli. Le combinazioni mediante cui questo evento accade sono moltissime e generano configurazioni per cui lo stesso numero di perle, divise per ciascuno dei P tipi, possono apparire più volte. Il problema richiede di contare quante configurazioni distinte di perle è possibile ritrovare all’interno dei pesci. La soluzione è piuttosto complessa ma veloce a fronte del fatto che ci sia un’esplosione combinatoria delle possibili configurazioni e può essere reperita in http://ioinformatics.org/locations/ioi08/contest/IOI2008Booklet1.0.pdf.
Roberto Grossi (Università di Pisa)
coordinatore Gruppo Selezionatori e Allenatori (GSAN)
