Come Prepararsi per le Olimpiadi di Informatica
Le Olimpiadi di Informatica sono una competizione scientifica rivolta agli studenti delle superiori, che si focalizza sulla risoluzione di problemi algoritmici. Questo articolo vuole servire da raccolta di risorse utili per preparsi per queste Olimpiadi.
Le Basi
Per iniziare ad avvicinarsi alle Olimpiadi di Informatica, è importante avere una base di programmazione, preferibilmente in C o C++. Non è importante essere esperti dei linguaggi, ma semplicemente avere familiarità su come scrivere ed eseguire un programma, e su costrutti come if, for, while, e funzioni.
Risorse per avvicinarsi a C sono:
I Primi Algoritmi
Una volta ottenuta una base di programmazione, si può passare a risolvere i primi problemi algoritmici.
Durante questa fase, si consiglia di seguire la guida per le selezioni territoriali, che è praticamente un libro che spiega tutti i concetti necessari per arrivare almeno fino alle fasi nazionali delle olimpiadi, e accompagna questi concetti con problemi pratici e le loro soluzioni. Temi ricoperti includono:
- Complessità Computazionale
- Vettori, Ordinamento e Ricerca
- Algoritmi Greedy
- Ricorsione
- Programmazione Dinamica
- Grafi
Durante questa fase, è importante anche familiarizzarsi e iniziare a risolvere problemi sul cms, la piattaforma ufficiale italiana di allenamento per le Olimpiadi. Il cms contiene centinaia di problemi di ogni difficoltà. Ogni volta scritto il vostro codice, potrete inviarlo sulla piattaforma che poi vi dirà il risultato della vostra soluzione in pochi secondi. C'è anche un ranking che rende il tutto più competitivo.
Prepararsi per i Nazionali
Se avete completato i precedenti step nel dettaglio, significa che il vostro livello è quello da selezioni nazionali. Per conquistare una medaglia, consultare libri più avanzati si può rivelare molto utile.
La cosiddetta bibbia degli algoritmi per le gare è il libro Competitive Programming, il cui pdf della prima versione può essere scaricato gratuitamente qui. La versione più recente (terza) può essere comprata qui. Questo libro è in inglese, ma anche quelli con più difficoltà nella lingua non devono scoraggiarsi in quanto è un inglese molto semplice e limitato che può essere facilmente compreso.
Il Competitive Programming contiene alla fine di ogni capitolo una serie di problemi da risolvere. Parallelamente, può essere molto utile continuare a risolvere problemi di crescente difficoltà sul cms.
Altra risorse molto utili sono:
Uno Sguardo alle IOI
Le IOI sono la fase internazionale delle Olimpiadi di Informatica. Ogni anno, solo 4 studenti Italiani vengono selezionati per partecipare alle IOI. La selezione avviene tramite una serie di stage a cui partecipano solitamente i primi 20 classificati alle fasi nazionali.
Prepararsi per qualificarsi, poi fare bene, alle IOI, è estremamente più ad-hoc delle fasi precedenti, e probabilmente, se sei arrivato a questo punto, sei in grado di scegliere da solo come prepararti.
In ogni caso, una serie di risorse interessanti sono:
- Coci: Gare di Informatica Croate, che si ripetono ogni mese, e il cui livello è simile a IOI. Partecipazione aperta a tutti