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]

Description d'une épreuve aux IOI

Arthur Charguéraud et Mathias Hiron pour www.france-ioi.org

Déroulement

Les olympiades se composent de deux épreuves, à deux jours d'intervalle. Chaque épreuve, d'une durée de 5 heures, est composée de 3 problèmes. Différents types de problèmes peuvent être proposés, tous de nature algorithmique. On distingue trois types d'exercices :

  1. Sujet évaluation sur une série de test : la solution est constituée d'un unique fichier source d'un programme qui lit des données sur l'entrée standard, qui calcule un ou plusieurs résultats, et les écrit sur la sortie standard.
  2. Sujet interactif : la solution est constituée d'un unique fichier source d'un programme qui interagit avec une librairie fournie par les organisateurs.
  3. Sujet avec sortie uniquement : la solution est formée d'un ensemble de fichiers correspondant aux solutions que vous avez déterminées.

Détaillons chacun de ces trois cas.

1. Sujet évaluation sur une série de test. Le source de votre programme est compilé, puis l'exécutable généré est soumis à une série de tests, en général une vingtaine. Chaque test doit être exécuté en un temps limité avec une mémoire limitée, et sans erreur fatale ; les limites sont précisées pour chaque sujet. Les premiers tests sont là pour vérifier que le programme fonctionne, mais on passe très rapidement à des fichiers de test immenses, dont le but est de vérifier les performances de votre algorithme. Chaque test correctement résolu donne un certain nombre de points (en général 5 points pour chacun des 20 tests), le but est donc de résoudre un maximum de tests (pour obtenir 100 points sur 100).

2. Sujet interactif. Le source de votre programme est compilé avec la bibliothèque fournie, et votre programme est lancé plusieurs fois, toujours avec les limites de temps et de mémoire données dans le sujet. La bibliothèque calcule votre score pour chacune des exécutions, et ne vous donne aucun point si votre programme ne termine pas correctement. La bibliothèque sert à interagir avec votre programme, par exemple en incarnant l'adversaire dans un jeu à deux joueurs, ou bien à limiter les données disponibles, par exemple pour des problèmes où l'on ne peut trier des entiers qu'en les comparant deux à deux sans accéder à leur valeur.

3. Sujet avec sortie uniquement. Cette fois le problème est sensiblement différent : on vous donne un sujet et des fichiers d'entrées, et on vous demande de soumettre directement les fichiers de sortie. Il n'est pas demandé de soumettre le source ni l'exécutable de votre programme, ce qui fait que vous pouvez même résoudre certains tests à la main ! Pour ces sujets, il n'y a pas de contrainte de temps autre que la durée de l'épreuve, ni de contrainte de mémoire autre que la limitation de la machine qui se trouve devant vous.

Remarque générale : la plupart du temps, on vous demande de fournir un résultat exact, qui doit correspondre mot pour mot à la sortie attendu pour obtenir les points. Dans certains cas cependant, le sujet accorde un score partiel pour des réponses proches de la réponse idéale. Parfois certains problèmes sont tellement difficiles que les points sont attribués en fonction du score du meilleur candidat, qui obtient la totalité des points.

Langages de programmation

Aux IOI, les langages autorisés sont : C, C++, et Pascal.

Les compilateurs associés sont gcc, g++ et Free Pascal (tous libres). Pour connaître les versions exactes, reportez-vous au site des IOI à venir.

Si vous êtes motivé par les IOI mais que vous ne connaissez que Caml, sachez que vous pouvez apprendre en un temps tout à fait raisonnable à coder vos algorithmes en C++. En effet, apprendre un second langage de programmation est incomparablement plus rapide qu'apprendre le premier.

Environnement de développement

Les PC fournis aux olympiades sont tous sous Linux. Si vous travaillez sous Linux vous n'aurez aucun problème. Si vous utilisez une autre plateforme, vous pouvez apprendre tout ce qu'il faut savoir pour les IOI en moins de 2 heures.

Lors des olympiades, vous n'aurez pas forcément à votre disposition vos outils de développement habituels. Pensez donc à vous renseigner sur les outils disponibles lors des prochaines olympiades, choisissez ceux que vous préférez utiliser, et utilisez-les régulièrement pour vous y habituer.

Dans le même ordre d'idées, vous n'aurez pas le droit d'apporter le fichier de configuration de votre éditeur préféré. Si vous ne pouvez pas être à l'aise avec Vim ou Emacs sans votre conf perso de 5 pages, essayez un éditeur graphique configurable rapidement (Kate pour ne citer que lui).

Là encore, pour connaître les distributions et les versions des logiciels disponibles, reportez-vous au site des IOI à venir.

Clavier américain

Aux IOI, des claviers US sont fournis, et vous n'aurez donc pas votre habituel clavier français. Cela peut beaucoup vous gêner, être une source d'erreurs, et surtout de perte de temps et de concentration. Trois solutions s'offrent à vous :

  1. Configurer aux IOI votre clavier en azerty (mauvaise solution).
  2. Configurer chez vous votre clavier en qwerty pour vous habituer.
  3. Acheter un clavier US, et coder avec.

Commentaires sur chacune des solutions :

  1. Le problème lorsqu'on émule un clavier français sur un clavier américain, c'est qu'il manque la touche avec les caractères < et >, et comme ces deux caractères servent souvent, c'est pas super pratique. Bien sûr, on peut toujours bidouiller pour obtenir ces symboles avec des raccourcis clavier, mais c'est pas super simple.
  2. Émuler un clavier américain avec un clavier français est assez efficace. Cela pousse à apprendre par cœur la position des caractères spéciaux sur le clavier (à moins de coller des petites étiquettes !), ce qui permet de coder plus vite. En plus, sur le clavier US contrairement au clavier FR, tous les caractères qui servent à programmer sont d'un accès très facile (pas besoin d'utiliser la touche Alt gr).
  3. Acheter un clavier US, ça ne coûte pas grand chose et peut permettre de gagner en confort. Vous risquez cependant de devoir rebrancher régulièrement votre clavier FR pour pouvoir taper du texte en français, à moins que vous ne décidiez d'apprendre la disposition du clavier international.

Techniquement, pour émuler un clavier on utilise :

  • sous Linux : les commandes setxkbmap us et setxkbmap fr,
  • sous Windows : Panneau de configuration / Options régionales / Langues / Détails.
Pensez à vous inscrire pour valider les cours et résoudre les exercices.