Prerequisiti per gli allenamenti

Le settimane di allenamento della squadra nazionale consistono in una full immersion di teoria e pratica della soluzione di problemi algoritmici. Data la difficoltà sempre crescente dei problemi proposti alle olimpiadi, è necessario partire da una piattaforma comune, per cominciare ad affrontare subito problemi interessanti.

Conoscenza di un linguaggio

È importante avere una eccellente conoscenza del proprio linguaggio di programmazione, che può essere il Pascal, il C o il C++. È sì vero che i problemi olimpionici sono difficili dal punto di vista algoritmico, e presentano pochissime difficoltà di ingegnerizzazione (le tecniche di programmazione in grande sono completamente inutili); ciononostante, se non avete una completa dimestichezza con il linguaggio di programmazione che utilizzate e con l'editor con cui scrivete, perderete molto tempo prezioso.

Sebbene tutti i linguaggi che abbiamo indicato siano Turing-completi (e cioè in grado di risolvere qualunque problema risolubile in maniera algoritmica), essi mettono a disposizione strumenti molto diversi. In particolare, in C++ sono a disposizione strumenti molto semplici per l'input/output, e la Standard Template Library, una collezione di strutture dati pronte per l'uso. Per questa ragione consigliamo fortemente di utilizzare come linguaggio di programmazione il C++, dove però l'uso delle estensioni del C sia limitato all'input/output e alla STL. Classi, polimorfismo ecc. sono solo di disturbo in programmi che, se ben pensati, raramente eccedono le cinquanta righe, e spesso sono molto più corti.

Tecniche fondamentali di programmazione

È necessario conoscere l'input/output da file nei dettagli, essere in grado di gestire memoria dinamicamente (allocazione e deallocazione), e sapere scrivere funzioni ricorsive (funzioni che chiamano se stesse). La ricorsione è fondamentale per la soluzione di problemi enumerativi o di ricerca esaustiva di soluzioni ottime.

Strutture dati elementari

Liste (a singolo e doppio concatenamento), alberi binari e i relativi algoritmi di base devono essere noti.

Algoritmi fondamentali

È necessario conoscere bene almeno un algoritmo di ordinamento (meglio se di ordine nlogn) e la ricerca dicotomica in strutture ordinate.

Materiale didattico

C'è molto materiale didattico in linea sull'argomento; consigliamo, ad esempio, le completissime dispense di Giovanni Pighizzini (orientate al Pascal) e le dispense di Paolo Liberatore (orientate al C).