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.
