Voir les cours et résoudre les problèmes en :
Le C est un langage de programmation impératif conçu pour la programmation système. Inventé au début des années 1970 avec UNIX, C est devenu un des langages les plus utilisés. De nombreux langages plus modernes se sont inspirés de sa syntaxe. Il privilégie la performance sur la simplicité de la syntaxe. [En savoir plus]
Le C++ est un langage de programmation impératif. Inventé au début des années 1980, il apporte de nouveaux concepts au langage C (les objets, la généricité), le modernise et lui ajoute de nombreuses bibliothèques. C++ est devenu l'un des langages les plus utilisés. Sa performance et sa richesse en font le langage de prédilection pour les concours. [En savoir plus]
Pascal est un langage de programmation impératif inventé dans les années 1970 dans un but d'enseignement. Quoiqu'encore utilisé à cette fin, l'absence de bibliothèque standard en limite son utilisation malgré une grande efficacité. Sa syntaxe a été reprise par d'autres langages plus modernes avec plus ou moins de succès. [En savoir plus]


Remarque : Les cours pour ce langage ne sont disponibles que jusqu'au chapitre 4, « Lecture de l'entrée ». Les corrections sont toutefois toujours fournies.
OCaml est un langage de programmation fonctionnel inventé au milieu des années 1990. Il permet aussi une programmation impérative ou objet. Il permet d'écrire des programmes courts et faciles à vérifier et est ainsi utilisé pour certains systèmes embarqués très sensibles comme ceux des avions. Il est utilisé dans l'enseignement en classes préparatoires aux grandes écoles. [En savoir plus]


Remarque : Les cours pour ce langage ne sont disponibles que jusqu'au chapitre 4, « Lecture de l'entrée ». Les corrections sont toutefois toujours fournies.
Java est un langage de programmation impératif et orienté objet. Inventé au début des années 1990, il reprend en grande partie la syntaxe du langage C++ tout en la simplifiant, au prix d'une performance un peu moins bonne. S'exécutant dans une machine virtuelle, il assure une grande portabilité et ses très nombreuses bibliothèques en font un langage très utilisé. On lui reproche toutefois la « verbosité » de son code. [En savoir plus]


Remarque : Pour un débutant souhaitant apprendre Java, nous conseillons fortement de commencer par JavaScool, plus facile à apprendre, bien que fortement similaire.
Java's Cool (alias JavaScool) est conçu spécifiquement pour l'apprentissage des bases de la programmation. Il reprend en grande partie la syntaxe de Java sur laquelle il s'appuie, mais la simplifie pour un apprentissage plus aisé. La plateforme JavaScool est accompagnée d'un ensemble d'activités diverses de découverte de la programmation. [En savoir plus]
Python est un langage de programmation impératif inventé à la fin des années 1980. Il permet une programmation orientée objet et admet une syntaxe concise et claire qui en font un langage très bien adapté aux débutants. Étant un langage interprété, il n'est cependant pas aussi performant que d'autres langages. [En savoir plus]

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.

Pensez à vous inscrire pour valider les cours et résoudre les exercices.