Chaque année l'Association for Computing Machinery (ACM) organise un concours mondial de programmation pour étudiants. Ce concours se déroule en deux phases. Un ensemble de concours régionaux se disputent en automne; les équipes gagnantes de chaque groupe régional s'affrontent ensuite dans un concours mondial organisé aux Etats-Unis à la fin de l'hiver. Cette année, cinq concours régionaux se sont déroulés en Europe, trois en Asie, deux en Océanie, douze en Amérique du Nord, un en Amérique du Sud et aucun en Afrique. Une université peut envoyer une, deux ou éventuellement trois équipes de trois étudiants au concours régional correspondant. Une cinquantaine d'équipes sont retenues pour le concours final. Des précisions supplémentaires sur ce concours peuvent être obtenues en consultant le Web à partir de l'adresse:
Ces deux dernières années, une équipe a défendu les couleurs de l'EPFL au concours régional de l'Europe du Sud-Ouest. J'ai eu l'honneur d'accompagner ces équipes en qualité de conseiller académique; sa fonction consiste en particulier à certifier que les membres de l'équipe sont admissibles au concours. Le concours régional 1996 a eu lieu les 15-16 novembre à l'EPFZ; l'équipe de l'EPFL était composée de Jörg Kienzle, Adrian Perrig, Bernhard Ruch et Christoph Ruch (remplaçant), diplômants Info.
Le concours régional de cette année a eu lieu les 22 et 23 novembre à Ulm; l'équipe suivante de l'EPFL y a participé:
De gauche à droite: Christophe Weibel, 5e semestre Math,
Alessandro Vernet, diplômant Info, Philippe Altherr, diplômant Info
Le ballon au dessus de la station de travail signifie
que l'équipe a résolu son premier problème.
La ville d'Ulm est située sur le bord du Danube dans le sud de l'Allemagne; son monument le plus caractéristique est sa cathédrale gothique dotée d'une flèche d'une hauteur record. L'université, qui date d'une trentaine d'années, est orientée uniquement vers les branches scientifiques et techniques; elle est située un peu en dehors de la ville; le bus traverse une petite forêt pour y parvenir.
Le voyage à Ulm s'est déroulé en train par un temps splendide le vendredi 21 novembre. Nous avons traversé la Suisse en diagonale jusqu'à St. Margrethen, puis après un rapide passage en Autriche à Bregenz nous avons traversé une partie de la Bavière jusqu'à Memmingen avant de rejoindre Ulm.
À part quelque petits accrocs, l'organisation du concours était bonne. L'hôtel retenu était très bien situé, près de la gare (et de la cathédrale); le bus à destination de l'université y avait un arrêt. Arrivés vers 18h, nous avons dû attendre une heure pour nous enregistrer alors que l'enregistrement était en principe prévu dès 18 heures. Par contre une bonne surprise. Contrairement à ce qui avait été annoncé, pas de finance d'inscription, cette dernière, ainsi que les frais de repas à la cafétéria de l'université ont été pris en charge par le sponsor. Le badge donnait de plus la gratuité du transport sur les bus, ce qui fait que nous n'avons eu à payer que les frais de voyage et d'hôtel, ainsi que le repas du premier soir que nous avons pris dans une pizzeria sympathique dans le quartier de la gare. Un petit bémol sur les repas à la cafétéria de l'université qui tournaient tous autour du thème pâtes préparées il est vrai de différentes façons; en particulier, les spaghettis gratinés du banquet final manquaient quelque peu de saveur! Heureusement que j'ai commandé une pizza et non des spaghettis lors du souper du vendredi soir (ce que j'avais hésité à faire)!
Samedi matin, fin du beau temps; jusqu'à notre départ, Ulm était plongé dans la grisaille automnale. Suite à une lecture trop superficielle du programme, nous avons manqué le discours de bienvenue du maire d'Ulm et sommes arrivés trop tôt à l'Université. Après les discours de bienvenue d'usage et la présentation des membres du jury, les organisateurs ont prévu trois exposés très vivants sur les activités de recherche en informatique de l'université d'Ulm; ces exposés ont porté sur le contrôle d'un réseau ferré par internet, la robotique et la musique virtuelle. Dans l'exposé sur la robotique, les contributions du LAMI dans le déminage ont été citées. Tous ces exposés ont été accompagnés de démonstrations très instructives.
L'après-midi du samedi a débuté par deux exposés de représentants d'IBM. Ceux-ci avaient une tenue plus décontractée que ce n'était le cas pour les membres de cette importante firme dans le temps. Le premier exposé, de nature technique, a porté sur les travaux en cours sur le système OS/390; le second sur les possibilités et les conditions de recrutement de jeunes ingénieurs au sein d'IBM. Après-çà, entrée dans le vif du sujet. Après une brève description des modalités du concours, les équipes se sont rendues aux salles de travail, équipées d'une station de travail pour chaque équipe, pour une session d'essai. Elles y ont trouvé trois disquettes (C++, Java et Smalltalk) et les T-shirts offerts par le sponsor; ces derniers portent les dates et lieu du concours et le nom du sponsor: on peut éventuellement regretter qu'ils ne font pas mention de l'université de rattachement des concurrents individuels. Les membres de chaque équipe ont reçu cinq problèmes simples à programmer dans un délai de 2h30 en interagissant avec les membres du jury de la même façon que lors du concours proprement dit. Beaucoup d'équipes, dont celle de l'EPFL, ont réussi à programmer les cinq problèmes dans le temps requis. Un petit bémol cependant; le programme d'enregistrement des résultats avait encore quelques faiblesses: pour l'un des problèmes, l'équipe de l'EPFL avait reçu le courier signifiant que ce problème avait été résolu correctement, ce résultat n'avait cependant pas été enregistré par la suite. Dans la discussion qui a suivi cette session, il est apparu qu'une autre équipe a eu le même problème.
Le concours proprement dit a eu lieu le dimanche. Trente-six équipes se sont affrontées. Ces équipes représentaient vingt-deux universités en provenance de huit pays différents (Allemagne, Espagne, France, Italie, Maroc, Portugal, Suisse et Tchéquie). Certaines universités étaient représentées par deux, voire trois équipes. Trois universités suisses étaient représentées: l'EPFZ avec trois équipes, l'université de Berne et l'EPFL avec une équipe chacune. Après les dernières indications, les équipes se sont rendues à leurs stations de travail respectives. Elles y ont trouvé neuf problèmes à programmer pendant le délai de cinq heures. Par rapport au concours de l'année passée, la difficulté des problèmes était mieux répartie. Il y une année, la majorité des équipes, dont celle de l'EPFL, n'avait pu résoudre qu'un seul problème, les autres étant trop longs ou difficiles. Cette année, la majorité des équipes a résolu entre deux et cinq problèmes. Deux des problèmes étaient très simples, trois de difficulté moyenne, deux assez difficiles et deux difficiles ou longs.
Un des problèmes était trivial. Il consistait à égaliser les hauteurs d'un ensemble de piles de briques en déplaçant le moins de briques possible. Il était garanti, pour chaque donnée, que le nombre total de briques était divisible par le nombre de piles; il suffisait d'indiquer le nombre minimum de briques à déplacer. Chaque équipe est venue à bout de ce problème, certaines très rapidement.
Le problème le plus difficile consistait à pousser une lourde boîte dans un labyrinthe jusqu'à une destination donnée en évitant de coïncer la boîte dans un coin et en minimisant l'effort nécessaire. Seulement deux équipes ont abordé ce problème, sans réussir à le terminer.
Pendant que les équipes s'affrontaient, les accompagnants, dont le soussigné, pouvaient suivre le déroulement de l'épreuve via une page internet, ceci jusqu'à une heure avant la fin du concours. Des sandwichs et boissons étaient disponibles, de même que pour les concurrents. L'équipe de l'EPFL a fort bien commencé, après trois heures de travail, elle avait résolu quatre problèmes, dont un relativement difficile, et se trouvait au sixième rang du classement provisoire. Malheureusement, elle n'a pas réussi à résoudre d'autres problèmes dans le temps qui restait, bien que deux ou trois autres étaient près d'aboutir. Pendant la dernière heure d'attente, pendant laquelle il n'était plus possible de suivre la progression du concours, j'ai cité l'école prédoctorale du DI et laissé à disposition plusieurs brochures d'information et affiches. La journée s'est terminée par l'explication de solutions possibles des problèmes, le banquet, la proclamation des résultats et une soirée qui pouvait se prolonger jusqu'à deux heures du matin pour les plus enthousiastes.
La meilleure équipe a résolu huit problèmes (tout sauf le labyrinthe), les deux suivantes sept:
Les deux premières équipes pourront participer au concours final qui aura lieu à Atlanta (USA) à la fin février. L'équipe de l'EPFL a terminé au quinzième rang, la mieux classée des équipes ayant résolu quatre problèmes. L'année passée, les deux équipes de l'Université d'Ulm étaient sorties en tête, suivie de la deuxième équipe de l'Université Technique de Prague. Les étudiants tchèques et d'Ulm sont vraiment très forts!
On notera, pour la petite histoire, que dans le classement proclamé le soir du concours, les deux premières équipes étaient inversées. Le classement définitif les a interverti suite à la découverte après coup d'une erreur dans les données utilisées pour tester l'un des problèmes. Heureusement, cette erreur n'a pas changé les équipes admises à participer au concours final!
Les membres de l'équipe de l'EPFL ont participé à cette épreuve avec enthousiasme. Ils regrettent un peu de n'avoir pu faire mieux; quelques problèmes de video et de triangle continuent à courir dans la tête de certains d'entre eux. L'un d'entre eux se rappellera certainement de l'utilité d'initialiser correctement les variables et de se méfier des variables globales! Par contre, la présence d'un étudiant de la section de mathématiques s'est révélée précieuse pour la résolution de certain problème policier faisant appel à la programmation dynamique. Ils sont très satisfaits d'avoir vécu cette expérience enrichissante.
Le site Web du concours permet d'obtenir tous les détails supplémentaires voulus sur le concours et son déroulement, y compris les énoncés des problèmes, les données de test, des solutions programmées en C, des photos et les résultats officiels:
http://www.informatik.uni-ulm.de/acm/
D'autres renseignements intéressants sont disponibles en surfant à partir de ce site: informations sur les concours des années précédentes, séries de problèmes de test avec solutions possibles...
Encore une remarque générale. Les problèmes pouvaient être programmés, à choix, en Pascal, C et C++ . La grande majorité des équipes a choisi C ou C++ tandis que Pascal a de plus en plus tendance à être considéré comme "obsolete". Mon choix personnel, s'il fallait offrir trois langages largement connus pour un tel concours, serait Ada (au lieu de Pascal), C++ (inclut C comme sous-ensemble) et Java. Il serait évidemment aussi intéressant d'autoriser des langages fonctionnels ou logiques tels que Haskell ou Prolog, qui conviendraient peut-être mieux à certains des problèmes proposés; ces langages sont cependant moins largement répandus (encore que dans les universités?).
Lundi, avant le retour, nous avons profité de visiter la cathédrale d'Ulm. Pour la modique somme de 3.50 DM, il a été possible de faire sa gymnastique matinale en grimpant le premiers tiers de la fameuse flèche au moyen d'un étroit escalier en colimaçon. Depuis là, nous avons eu une vue d'ensemble sur la ville et la campagne avoisinante. Ensuite nous avons complété notre voyage circulaire en rentrant par un autre itinéraire: Stuttgart-Karlsruhe-Bâle, pour arriver à Lausanne en fin d'après-midi.
Ce concours donne l'occasion à des étudiants doués pour la programmation de recontrer des étudiants provenant d'autres universités et de se mesurer avec eux dans un esprit sportif. Je ne peux donc qu'espérer que l'EPFL n'en restera pas là. Par la force des choses, le corps estudiantin évolue rapidement. Deux des membres de l'équipe de cette année arrivent à la fin de leurs études; un certain renouvellement s'impose si l'École veut participer à ce concours l'année prochaine. Je ne peux qu'encourager les étudiants attirés par la programmation à tenter leur chance. S'il y a beaucoup d'intéressés, il y a possibilité de constituer deux, éventuellement trois équipes; s'il y en a vraiment beaucoup, cela peut être l'occasion de faire un concours interne afin de retenir les meilleurs comme c'est le cas dans certaines universités. Et qui sait? Peut-être qu'un jour, une équipe de l'EPFL pourra arriver jusqu'au concours final?
J'invite les étudiants intéressés à s'informer sur les concours futurs. Ils peuvent le faire, et s'inscrire pour recevoir les renseignements requis, en partant de la page Web:
http://acm.baylor.edu/acmicpc/Regionals/RegionalsInfo.html
J'ai eu plaisir à accompagner, ces deux dernières années, des étudiants motivés au concours de programmation de l'ACM. Cette participation s'inscrit dans la politique d'ouverture de l'École, tout comme la possibilité offerte à des étudiants méritants d'effectuer une année d'études ou leur travail pratique de diplôme dans une autre université.
Merci encore aux membres des équipes EPFL 1996 et 1997 pour leur enthousiasme, pour avoir été des compagnons très agréables et à Alex pour ses contributions photographiques. Je remercie aussi le DI pour sa participation financière à ce voyage.
| retour au sommaire du Flash informatique no 1/98 |
| retour à la page principale des Flash informatique |
| Vos commentaires |
| © FI-1 du 3 février 1998 |