Mathias Hiron pour www.france-ioi.org
Cette page a pour but d'établir une liste de ce qu'il est fortement conseillé de connaître parfaitement pour résoudre les problèmes de type IOI. Ceci est le minimum indispensable : pour résoudre ce type de problèmes, vous aurez rarement besoin de connaissances n'en faisant pas partie.
Il est cependant toujours utile d'apprendre d'autres algorithmes : ils ne vous serviront pas directement, mais pourront vous aider à trouver des idées. D'une manière générale, plus vous voyez d'algorithmes, plus il vous sera facile de trouver les vôtres.
Une bonne partie de ces notions peut être apprise en résolvant les problèmes des épreuves correspondantes sur ce site. Pour les autres, vous pourrez trouver facilement de la documentation sur internet, ou dans la plupart des livres d'introduction à l'algorithmique.
Vous pouvez bien sûr résoudre de nombreux problèmes sans connaître tout ce qui est présenté dans cette liste. Considérez celle-ci comme une liste de ce que vous devez maîtriser en priorité.
Vous devez être capables d'évaluer rapidement le temps et la mémoire nécessaires à l'exécution de vos programmes, pour déterminer s'ils peuvent fonctionner dans les limites imposées pour chaque problème.
Il est indispensable d'avoir bien compris la notion de récursivité, et d'être à l'aise avec l'écriture de fonctions récursives. Ceci nécessite d'avoir bien compris le fonctionnement de la pile, lors de l'exécution d'un programme.
Dans la plupart des cas, vous n'aurez pas besoin de déclarer des structures de données complexes dans votre code source, et vous pourrez vous contenter de simples tableaux à une ou plusieurs dimensions. Vous connaissez en effet les valeurs maximales des différents paramètres des problèmes, et n'avez pas besoin de structures dynamiques.
Vous aurez donc rarement à utiliser des pointeurs, listes chaînées, etc. Ce qui ne veut pas dire que vous ne pouvez pas utiliser les structures de données classiques : piles, files, arbres, graphes, etc. En effet, toutes ces structures peuvent être représentées par de simples tableaux. Vous devez les maîtriser parfaitement.
De très nombreux problèmes peuvent être vus comme de simples recherches de plus court chemin dans un graphe. Il est donc indispensable de connaître parfaitement, et de savoir implémenter rapidement les principaux algorithmes de recherche de plus court chemin.
De nombreux problèmes vous demandent de travailler sur les nombres et leurs propriétés. Il est bon de connaître certains algorithmes sur les nombres, qui peuvent être utiles dans certains problèmes.
Vous aurez rarement à implémenter vous-mêmes un algorithme de tri dans un problème. Si vous avez besoin de trier des données, vous pouvez tout simplement utiliser les fonctions de la bibliothèque standard, comme qsort
. Il est cependant important de connaître les principes des principaux algorithmes de tri, et la manière de les implémenter, car ils pourront être une source d'inspiration pour certains problèmes.
De très nombreux problèmes font appel à un algorithme dynamique. De nombreux problèmes de ce type, sur ce site, vous permettront d'apprendre à manipuler ce type d'algorithmes.
De nombreux problèmes portent sur la géométrie. Il n'est en général pas nécessaire de faire appel à des algorithmes complexes de ce domaine. Les algorithmes suivants sont assez souvent nécessaires, et doivent être connus parfaitement.
Cet algorithme permet de rechercher rapidement un élément dans un tableau trié. Il est souvent très utile, y compris dans des cas où vous ne disposez pas réellement des données sous la forme d'un tableau. Vous devez donc absolument savoir l'implémenter, même si dans de nombreux cas la fonction bsearch
de la bibliothèque standard peut suffire.
Dans de nombreux problèmes, vous n'avez pas d'autre choix que d'énumérer les différentes possibilités. Le faire par « backtrack » ne doit vous poser aucune difficulté.
Dans certains cas, lorsque le but est de minimiser ou maximiser une valeur, on peut réduire le nombre de possibilités testées en arrêtant la récursion dès que l'on sait que la voie en cours ne pourra pas donner mieux que le meilleur résultat obtenu. Cette technique s'appelle le "branch & bound".
Ceci est l'algorithme de base de la théorie des jeux. Son principe est très simple, mais à connaître parfaitement, si vous voulez avoir une chance de résoudre des problèmes portant sur des jeux à deux joueurs. Ce genre de problèmes est assez fréquent.
Dans de nombreux cas, on vous demandera de trouver les valeurs des paramètres d'un problème, telles qu'une valeur calculée à partir de ces paramètres soit la plus petite possible, où la plus grande possible. Quand vous ne trouvez pas d'algorithme qui donne à coup sûr les meilleures valeurs, vous pouvez utiliser des algorithmes stochastiques. Ces méthodes sont un moyen relativement simple et efficace de trouver des valeurs qui ont de grandes chances d'être les meilleures, ou proches des meilleures.
Dans certains problèmes, vous ne disposez pas de l'intégralité des données d'entrée au départ, mais vous les obtenez en posant un certain nombre de questions, par l'intermédiaire d'une bibliothèque. Souvent, le but du problème est d'obtenir une information particulière, en posant le minimum de questions possible. Il faut alors trouver quelle question apporte le plus d'informations, à chaque étape. De nombreux algorithmes fournissent des moyens plus ou moins efficace de résoudre ce genre de problèmes. Il n'est pas nécessaire de les connaître tous, mais il est important d'avoir une idée des principes de base.
Un certain nombre de fonctions des bibliothèques standards sont indispensables à connaître, et à savoir utiliser parfaitement. Il faut bien sûr maîtriser les fonctions d'entrées-sorties, d'allocation de mémoire, de manipulations de chaînes, etc. Les fonctions présentées ici sont celles qui correspondent à des algorithmes, dont vous aurez souvent besoin, et qu'il est bon d'éviter de recoder, alors qu'ils sont disponibles dans les bibliothèques.
qsort
: tri rapide d'un tableau
bsearch
: recherche dichotomique dans un tableau trié
rand
et srand
: génération de nombres aléatoires.
Remarque : toujours initialiser srand
avec une valeur fixe, pour que votre programme donne le même résultat à chaque exécution.
gettimeofday
: permet d'estimer le temps d'exécution restant, pour ne pas dépasser la limite.
priority_queue
: implémentation d'une file à priorité. Attention, cette implémentation ne permet pas de supprimer n'importe-quel élément, ni de mettre à jour sa priorité. Si vous avez besoin de ces opérations, vous devez implémenter votre propre file à priorité.
hash_map
: implémentation d'une table de hachage
Pour tout savoir sur l'utilisation de la librairie standard C++, reportez-vous au cours qui traite spécialement du sujet.