Prologin

Logo Prologin

Prologin est une association qui organise chaque année le Concours National d'Informatique français. Ce concours est ouvert à toute personne âgée de 20 ans ou moins et résidant dans l'Union européenne ou en Suisse.

Après une première sélection sur questionnaire, plusieurs centaines de candidats sont retenus pour les demi-finales, des concours régionaux organisés sur toute la France. Pendant ces épreuves qui durent une journée, divers problèmes d'algorithmique leur sont présentés. Une partie consiste en un sujet papier avec des questions de difficulté croissante gravitant autour d'une même problématique. Cette partie permet d'évaluer la capacité du candidat à définir une structure de données adaptée à un problème, à l'exploiter, à explorer un graphe de solutions, et enfin à évaluer la qualité de son propre algorithme. Une seconde partie consiste en une épreuve sur machine, et confronte le candidat à un système lui proposant des exercices de difficulté croissante. L'exercice final de chacune de ces deux parties est traditionnellement un problème complexe devant se résoudre par un algorithme de programmation dynamique.

À l'issue de ces épreuves, les 100 meilleurs candidats sont sélectionnés pour disputer la finale. Celle-ci se déroule dans les locaux de l'EPITA, une école d'ingénieurs en informatique située au Kremlin-Bicêtre, en région parisienne. Pour cette finale un jeu informatique avec ses règles, le serveur, est développé. Les programmeurs doivent créer de petites intelligences artificielles devant participer à ce jeu. L'évaluation se fait tout d'abord en confrontant les programmes des candidats entre eux au cours d'un tournoi. Par la suite, un jury se réunit pour départager les candidats arrivant en tête à l'issue de ce tournoi, ces derniers devant défendre leur réalisation au cours d'une soutenance. La particularité de cette partie de la compétition est sa durée, de trente-six heures ininterrompues, imposant aux candidats de gérer leur temps.

Les langages de programmation disponibles pour les épreuves se déroulant sur machine sont le C, C++, C#, Caml, Java, Pascal, PHP et le Python.

Historique

L'association est créée en 1991 par des élèves de l'École polytechnique et de l'EPITA, devant le constat d'absence de concours informatique destiné aux étudiants. La première édition a lieu en 1992, et est un succès. Le modèle se met en place, et sera gardé jusqu'à présent : une sélection par questionnaire, des épreuves régionales, et une épreuve finale de trente-six heures qui fait l'identité du concours.

Le concours se veut alors européen, et reçoit un accueil très favorable des institutions, avec entre autres le haut patronage du Président de la République. Cette attention politique disparaît cependant rapidement. En 2004 l'association reçoit le parrainage du ministère délégué à la Recherche et aux Nouvelles Technologies, puis en 2006 de la Délégation aux usages de l'internet, qui dépend du Ministère de l'éducation nationale, de l'enseignement supérieur et de la recherche.

En 1995, l'association s'intéresse aux Olympiades Internationales d'Informatique, un concours de très haut niveau auquel la France ne participe pas encore. Le concours Prologin semblant tout indiqué, il devient une voie de sélection : les candidats les plus brillants remarqués par les organisateurs se voient proposer un cours intensif de haut niveau en algorithmique, en vue de constituer l'équipe de France. En 2003 l'association France-IOI est créée afin de s'occuper exclusivement de cette activité.

Pour sa troisième année d'existence, du fait de l'absence de renouvellement de membres du côté de l'X, le concours Prologin devient de fait un concours organisé exclusivement par des élèves de l'EPITA. Cependant, en 2006 d'anciens candidats, devenus élèves de Polytechnique et motivés par l'organisation du concours, remettent en place très officiellement la participation de leur école pour l'édition 2007. L'une des épreuves a depuis lieu dans ses locaux à Palaiseau.

Liste des vainqueurs

• 2011 : Arnaud Delmotte, Université Catholique de Louvain, Belgique
• 2010 : Sébastien Doeraene, Université Catholique de Louvain, Belgique
• 2009 : Michael Mathieu, École normale supérieure
• 2008 : Antoine Amarilli, Lycée Kléber, École normale supérieure
• 2007 : Nicolas Boumal, Université Catholique de Louvain, Belgique
• 2006 : Corentin Chary
• 2005 : Karim Jouini, Institut National des Sciences Appliquées de Toulouse (INSA Toulouse)
• 2004 : Emmanuel Durin, École Nationale d'Ingénieurs de Brest (ENIB), Lycée de Marmande
• 2003 : Julien Brette
• 2002 : Olivier Serres, Lycée de Marmande
• 2001 : Antoine Jacquet
• 2000 : Michaël Rao
• 1999 : Gaël Le Mignot
• 1998 : Pol-Brieux Le Metayer
• 1997 : Sebastien Carlier
• 1996 : Sylvain Martinez
• 1995 : ?
• 1994 : Hadi Diallo
• 1993 : Pas d'édition
• 1992 : ?

Quelques exemples de sujets de finale

Tous ces sujets sont disponibles en intégralité dans la partie archives du site Prologin

2010 : L'armée des toons

Pour cette édition, deux armées de toons s'affrontaient. Une armée était composée de 10 unités réparties au choix du joueur entre des chats, des singes, des kangourous et de manière obligatoire, d'un unique perroquet. Le but du jeu étant de mettre KO le perroquet adverse.
Chaque unité possédait une attaque unique et ses propres forces et faiblesses. Ainsi le chat était très rapide mais ne pouvait attaquer qu'au corps à corps. Le singe se déplaçait lentement mais pouvait tirer à distance. Le kangourou était pour sa part chargé d'explosifs et se suicidait pour attaquer en mettant KO toutes les unités - alliées comme ennemies - dans la zone d'explosion. Il explosait aussi lorsqu'on l'attaquait et il était ainsi possible de faire des réactions en chaine entre plusieurs kangourous. Le perroquet, quant à lui, était très lent et ne possédait aucune capacité !
La difficulté du jeu venait du fait que vous n'aviez la possibilité d'effectuer que trois actions par tour - utiliser une unité/faire apparaitre une nouvelle unité/relever une unité.
Pour pimenter le tout, 4 cartes étaient à votre disposition pour influer sur le jeu. Potion magique relevait immédiatement une unité KO - en effet les toons ne mourraient jamais, ils étaient juste KO -, Banzaï offrait une attaque supplémentaire à une unité, Pacifisme vous permettait d'avoir 4 actions ce tour mais vous empêchait d'attaquer et enfin Déguisement transformait une de vos unités en un autre type jusqu'à la fin de votre tour. Attention cependant chaque carte utilisée était donnée à l'adversaire !
Le sujet a été conçu pour être entièrement jouable en version jeu de plateau et s'est avéré être particulièrement riche et amusant !

2009 : La conquête de l’est

Cette année, les candidats devaient participer à la construction d'une ville, dans un système capitaliste et mafieux, le but étant de s'enrichir le plus possible. Plusieurs actions étaient disponibles : construction, revente et destruction de maisons, construction de routes et réservation de terrains. À chaque tour de jeu, un monument était proposé par la mairie ; une phase de corruption, utilisant un système d'enchères sous plis scellés au premier prix, offrait au vainqueur la possibilité de placer la construction. Les habitations proches du monument gagnaient — ou perdaient, selon le type de construction — alors beaucoup de valeur. Le sujet a été conçu pour être entièrement jouable en version jeu de plateau.

2008 : Hamsters — ou la bataille des pommes

Ce jeu mettait en scène deux équipes contrôlant chacune trois hamsters, dont le but était de ramener le plus de pommes possible dans son camp. Les pommes étaient placées à l'avance sur le plateau. Le plateau de jeu possédait des murs infranchissables et des tranchées, desquelles on ne pouvait sortir sans aide externe. Fait assez rare dans le concours, le jeu était à information complète. Cependant, il n'était pas à information parfaite car les joueurs jouaient simultanément et devaient décider à l'avance de leurs trois prochains coups. La principale difficulté du sujet était donc de prévoir et anticiper les coups de l'adversaire. Les hamsters avaient plusieurs actions possibles : les déplacements, l'utilisation d'un grappin pour tirer ou faire sortir d'une tranchée un autre hamster et le lancer de trognons de pommes pour déstabiliser les ennemis.

2007 : Il était une fois la vie...

Ce sujet proposait au sein d'un modèle simplifié des mécanismes du système immunitaire de définir le comportement des globules blancs pour obtenir la meilleure réaction défensive. Dans une zone du corps humain, deux joueurs contrôlaient chacun un groupe de globules blancs complètement indépendants (espaces mémoires distincts) et doués de compétences pour certaines actions. En plus des actions dont est normalement capable un globule blanc (déplacement, reconnaissance du soi et du non soi, phagocytages des cellules mortes et corps étrangers, identification de nouveaux virus, émission d'anticorps...), une capacité limitée à communiquer avait été ajoutée. Le but était de défendre l'organisme contre les infections bactériologiques et virales : un aspect collaboratif, dû à un objectif commun, et un aspect compétitif s'opposaient donc dans ce sujet.

2006 : OutATime

Ce sujet s'inspire du film Retour vers le futur. Chaque joueur contrôle une équipe de trois personnages dont le but est de gagner le maximum d'argent, en pariant dans des casinos. Pour être sûr de gagner, il suffit de mettre la main sur l'almanach des sports, contenant tous les résultats. La subtilité du jeu vient de la De Lorean qui permet de voyager dans le temps. Il est ainsi entre autres possible de revenir dans le passé et de modifier les évènements, dans l'espoir qu'ils soient plus favorables.

2005 : Hatamis-Maun

Dans ce sujet, le but du jeu était de coloniser une planète à fort potentiel touristique, Hatamis-Maun. Disposant d'une poignée d'unités au départ, le candidat devait tirer judicieusement partie des ressources présentes pour construire des hôtels, et marquait d'autant plus de points que ses hôtels étaient bien placés. Pour y parvenir, il avait la possibilité d'exploiter des ressources naturelles en y construisant des complexes d'exploitations, et de créer de nouvelles unités en construisant des usines. Il pouvait d'autre part détruire des unités ennemies, mais cette possibilité n'avait été exploitée par aucun candidat.

2003 : Attraction étrange

Ce jeu se présentait sous la forme d'une sorte de damier géant, sur lequel les joueurs pouvaient pousser différentes pièces bout à bout. Chaque joueur avait des figures à réaliser, et le but était donc de parvenir à mettre en place ces figures, sachant que les joueurs agissaient sur le même jeu et interféraient donc entre eux. Ce sujet s'est révélé être l'un des plus difficiles de Prologin.

2002 : Les citrons

Les citrons étaient les unités que contrôlaient les joueurs dans ce jeu dont le but était de contrôler la plus grande surface possible de la carte. Les citrons pouvaient réaliser des actions de base, telles que se déplacer, attaquer, se diviser ... Ils pouvaient également s'allonger afin de jouer le rôle de pont pour permettre à d'autres citrons de passer par dessus un bras de mer, mais à l'issue de la finale aucun candidat n'avait tiré profit de cette possibilité. L'origine du terme citron est la vidéo réalisée pour la finale, devant laquelle tout le monde s'était écrié que les unités ressemblaient à des citrons.

2001 : Les pulsars

Le jeu cette année ressemblait beaucoup à un jeu de stratégie. Chaque joueur dispose de deux types de robot: les anakronox : gros tanks très peu mobiles. Armés d'un rayon énergétique leur servant aussi de radar les R4d2: mobile et pouvant capturer les anakronox. Les affrontements consistaient à balayer le plus efficacement la carte au moyen des radars pour repérer les troupes ennemis, puis diriger ces R4d2 vers les ennemis à capturer. Les R4D2 ennemis étant détruis au moyens de tirs précis d'énergie

Le code source du serveur a été diffusé, sous licence GPL sur http://prologin.sourceforge.net/

2000 : Laisse faire

Ce sujet est parmi les plus originaux qui aient été proposé. Le jeu se présentait sous la forme d'une île constituée d'un nombre limité d'éléments de base : la roche, le sable, et le coton. À l'aide d'unités, les sphères, pouvant se déplacer, se battre, et modifier le terrain, le but des joueurs était de cultiver des haricots. Toute la difficulté résidait dans la gestion de l'eau de pluie, dont l'écoulement suivait des règles strictes. La particularité de ce sujet est que tous les éléments du décor, y compris les unités, étaient représentés sous la forme de cubes.

1994 : World Lift : SOFA

Vous êtes le président de la WORLD LIFT Cie. Vos ascenseurs qui ont fait leurs preuves depuis longtemps subissent depuis peu une concurrence féroce. Vos concurrents proposent des produits moins chers et surtout moins fiables que les vôtres. Afin de convaincre vos clients du fait que vos produits font la différence par leur fiabilité et leur durée de vie exceptionnelle vous avez décidé de mettre au point un système de simulation de flux. Ce système vous permettrait d'une part d'optimiser les flux des ascenseurs dans les immeubles de vos clients et d'autre part de réaliser des simulations en temps réel pour les convaincre que votre solution est la meilleure et la plus adaptée à leurs besoins.

Nous appellerons ce système le Système d'Optimisation des Flux d'Ascenseurs : SOFA. Ce système est entièrement paramétrable avec possibilité d'adjonction d'un système expert basé sur une analyse calendaire des flux. Il permet à la fois de réaliser des économies de temps, de consommation et d'usure. Vous mettrez donc à la disposition de vos clients un simulateur d'entreprises qui comprend l'implémentation du SOFA.

Voir aussi

Liens internes

• Programmation
• C
• C++
• Java
• OCaml
• Algorithmique
• Programmation dynamique
• Théorie des jeux

Liens externes

• Site officiel
• Site de l'association France IOI