Liste des connaissances requises pour les IOI

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é.

Notions préalables

Notions de complexité

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.

• complexité en temps
• complexité en mémoire
• complexité en pire cas
• complexité moyenne

Principe de la récursivité

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.

Structures de données

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.

Pile et file

• principes
• implémentation à l'aide d'un tableau

Arbres

• vocabulaire des arbres
• représentations d'un arbre
• parcours en profondeur
• parcours en largeur
• arbres binaires
• arbres de recherche

File à priorité

• principe
• implémentations
  • sous forme d'un tableau trié
  • sous forme d'un tas
• utilisation des bibliothèques standards

Table de hachage

• principe
• implémentation
• utilisation des bibliothèques standards

Graphes

• vocabulaire des graphes
• représentations d'un graphe
• parcours en largeur et en profondeur
• détection des cycles
• composantes connexes, et fortement connexes
• fermeture transitive
• circuit eulérien
• minimum vertex cut (nœuds essentiels)
• minimum (edge) cut (arcs essentiels)
• graphes orientés acycliques
• tri topologique
• graphes bipartis
  • algorithme de maximum-matching.
    (a priori pas indispensable pour les IOI, mais très souvent utilisé dans les concours régionaux, mieux vaut donc le connaître.)

Autres algorithmes

Arbre recouvrant minimal d'un graphe

• algorithme de Prim
• algorithme de Kruskal

Recherche du plus court chemin dans un graphe

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.

• Dijkstra
• Ford-Bellman
• Roy Warshall

Nombres

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.

• recherche des nombres premiers
• calcul de PGCD (Plus Grand Commun Diviseur)
• calcul de PPCM (Plus Petit Commun Multiple)

Algorithmes de tri

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.

• tri par insertion
• tri par sélection
• tri rapide
• tri fusion
• tri par tas
• tri postal

Algorithmes dynamiques

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.

Géométrie

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.

• distance entre deux points
• intersections de droites, de segments
• distance d'un point à une droite, d'un point à un segment
• appartenance d'un point à un polygone
• manipulation d'angles
• construction de l'enveloppe convexe d'un ensemble de points

Recherche par dichotomie

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.

Backtracking et Branch & Bound

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".

Algorithme min-max

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.

Algorithmes stochastiques (optimisation)

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.

• algorithme de Monte Carlo
• recuit simulé

Arbres de décision

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.

Utilisation des bibliothèques standards

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.

La bibliothèque standard C

• 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.

La bibliothèque C++ (STL)

• 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.