FLASH INFORMATIQUE FI



Ingéniosité en ingénierie


... il en a fallu une bonne dose à la délégation EPFLienne pour atteindre la médaille d’argent en s’imposant contre ses concurrents espagnols, français, israéliens, italiens, portugais et suisses lors des finales régionales sud-ouest européennes du concours de programmation universitaire ICPC.



A good dose of ingenuity in engineering was necessary for the EPFL delegation to win a silver medal in the southwestern European regional finals of the international collegiate programming contest, welcoming teams from France, Israel, Italy, Portugal, Spain and Switzerland.


Christian KAUTH


Mission accomplie à Valencia

L’entraînement fut sans compromis : nos concurrents ont résolu quatre défis hebdomadaires, participé à six séminaires, un concours de sélection, quatre concours de préparation avant d’être finalement envoyés à Valencia le 18 novembre passé pour porter haut les couleurs de l’EPFL lors des finales sud-ouest européennes de l’ACM ICPC [1]. Johannes Wüthrich, Mario Geiger, Nikolay Ulyanov, Samuel Grütter, Tam Nguyen et Titus Cieslewski ont tout demandé à leur matière grise ces deux derniers mois – à commencer par la compréhension des problèmes, puis le développement d’une solution algorithmique performante, jusqu’à son implémentation en C/C++ ou Java. À l’issue des cinq heures captivantes de concours, c’est une médaille d’argent qui récompensa les efforts de Nikolay, Samuel et Tam, fruit d’une infatigable motivation et d’un audacieux engagement de la part des participants tout aussi bien que de l’association PolyProg, qui a proposé à tous les étudiants du campus une préparation conséquente à ce concours, dirigée par Christian Kauth et ses assistants Jonas Wagner et Andrei Giurgiu.



Une fois n’est pas coutume, je vous propose de passer sous la loupe un des problèmes de notre concours de sélection. Le concours a demandé aux participants de connaître une grande variété d’algorithmes. Il fallait par exemple calculer des flux maximaux et des chemins minimaux, connaître les lignes de balayage, la géométrie, l’algèbre modulaire et la théorie des nombres, savoir détecter des cycles, etc.
Le problème choisi portera sur la prédiction de l’avenir par une approche meet-in-the-middle [2].

Générateur de nombres pseudo-aléatoires

Les nombres aléatoires sont les compagnons quotidiens de chacun (bruit, loterie, chiffrages carte crédit pour n’en nommer que quelques-uns) et des outils fort utiles de chaque ingénieur (pour toutes sortes de simulations, analyses, statistiques...). Est-ce que vous sauriez générer une suite de nombres qui a l’air aléatoire ? La figure suivante en montre une méthode étonnamment simple qui génère une suite de nombres aléatoires à 8 bits (de 0 à 255).


Il s’agit d’un registre à décalage à rétroaction linéaire (LFSR) dont le principe de fonctionnement est de décaler à chaque coup d’horloge les bits d’une position vers la droite. Le bit de poids fort (MSB) est déterminé par la somme binaire (XOR) de quelques positions. L’état actuel 01100101 (101) sera ainsi suivi de l’état 00110010 (50), puis 10011001 (153). La suite de nombres ainsi générée aura l’air aléatoire à toute personne ne connaissant pas la structure interne du LFSR. En réalité la suite est inhérente à la structure du LFSR et déterministe dès que l’état actuel est connu, raison pour laquelle on parle de nombres pseudo-aléatoires.

Simulation de l’avenir

Au concours de sélection, co-organisé avec l’ETH Zurich, on demandait aux participants combien de coups d’horloge seraient nécessaires pour passer d’un état A vers un état B (ou d’indiquer si cela n’est pas possible). Intuitivement, on peut répondre à cette question en simulant le LFSR donné. Un LFSR à N bits peut avoir des cycles contenant jusqu’à 2 N-1 états différents (l’état 0 étant sans issue). Le LFSR proposé ci-dessus forme effectivement un cycle de longueur maximale 2 8-1, soit 255 et sa simulation est envisageable dans la contrainte du temps. En compétition, les algorithmes doivent être non seulement corrects, mais aussi suffisamment rapides pour rapporter des points. Pour être sélectionnés, les participants devaient fournir une solution en moins d’une seconde et N valait 32, ce qui disqualifie l’approche par la simulation, trop lente. Un processeur actuel tournant à quelques GHz mettra des minutes pour itérer à travers les quelque 4 milliards états (2 32-1) de chacun des cent LFSR proposés. Je vous invite à imaginer N=64 pour une petite expérience mentale. Le cycle peut alors passer par plus de 10 19 états, et la simulation durera environ deux siècles sur votre ordinateur personnel actuel !

Meet-in-the-middle

Plutôt que de lancer la simulation de suite pour ne connaître la réponse que dans deux siècles, creusons un peu plus profond. Il faut savoir qu’un LFSR et ses changements d’état peuvent être modelés par des multiplications de matrices, dites de transition. Nommons F la matrice de transition du LFSR, X et Y des vecteurs d’état. Si Y est l’état suivant l’état X, alors Y=F . X. Cette matrice de transition peut être construite facilement à partir de la description du LFSR et nous sommes à la recherche de l’entier q tel que B=F q ⋅ A [3]. L’astuce consiste ensuite à exprimer q comme q=i ⋅ M+j avec j<M. On choisira M=⎡\sqrt{(2^{N})}⎤ et il faudra ensuite trouver la paire (i,j) solution de F j ⋅ A= (F -M) i ⋅ B. Cette paire se trouvera par une approche meet-in-the-middle nommée baby-step giant-step. Le baby-step consiste dans le calcul des \lbrack (\sqrt{2^{N}})\rbrackétats F  j ⋅ A qu’on stocke ensuite dans une structure de données à temps d’accès rapide (par exemple une table de hachage). Cette procédure est illustrée par la figure suivante, visitant les (\sqrt{2^{6}})=8 premiers états en partant de l’état A.


Il faudra ensuite construire la matrice inverse F -1, correspondant à un décalage à gauche des bits et la restitution du bit de poids faible (LSB) [3]. Cette matrice est ensuite prise à la puissance M, notons G=F -M. Multiplier l’état B par G correspond à reculer de M états dans le cycle - on fait un giant-step. Nous allons en faire autant qu’il faut pour arriver dans un état qu’on avait déjà visité avec un baby-step, et au maximum (\sqrt{2^{6}})=8. Si après ce nombre d’étapes on n’a pas encore trouvé un état déjà visité, ceci implique que A et B ne font pas partie du même cycle et que l’état B ne sera jamais atteint en partant de A. Nous profitons du grand giant-step pour nous approcher rapidement de l’état initial A. Étant donné que ce giant-step est néanmoins plus petit que la somme des baby-steps, on ne risque pas de sauter trop loin sans s’apercevoir d’une collision. Une collision entre un baby-step et un giant-step est rapidement détectée par lecture dans la table de hachage. S’il a fallu j baby-steps et i giant-steps pour se rencontrer dans cet état, les états A et B sont éloignés de q=i . M+j , la solution du problème.
Voyons combien de temps de calcul cette brève acrobatie nous économise. À condition d’avoir à portée de main 100GB de mémoire (pour une table de hachage rapide pour M=2 32 états) et en réalisant la multiplication d’un vecteur binaire par une matrice binaire en complexité O(N), par encodage en entiers à 64 bits, la multiplication de matrices binaires en O(N2), leur exponentiation jusqu’à 2N en O(N3) et le calcul du baby- et giant-step en complexité O(N ⋅ 2N/2), l’impact de cette amélioration de l’algorithme par rapport à O(2N ) est considérable  ! Rendons-nous compte que pour N=64, le temps d’attente est diminué de deux siècles à quelques minutes seulement ! Impressionnant, n’est-ce pas  ?

Meet at hc2

Si cette brève ballade à travers le monde de l’algorithmique a suscité votre curiosité, je vous invite à nous rejoindre lors d’un de nos prochains événements, que ce soit un des séminaires hebdomadaires ou un concours. Après l’excellente 17e place de Titus Cieslewski et Nikolay Ulyanov lors du IEEEXtreme avec presque 2’000 équipe et une vive participation au concours Facebook organisé par Polyprog sur notre campus, le prochain grand événement sera la quatrième édition de l’Helvetic Coding Contest le 16 mars 2013. Durant ce concours, près de 130 gymnasiens, étudiants et doctorants des quatre coins de la Suisse se donneront rendez-vous à l’EPFL en équipes de 3 pour s’attaquer à une vague de problèmes algorithmiques variés, de tous niveaux et très amusants ! Si vous voulez vivre cette journée d’ambiance conviviale, compétitive et sympathique, ne tardez pas à motiver vos coéquipiers et à réserver votre chaise dès le 21 janvier 2013 ! PolyProg bouillonne déjà d’idées novatrices, et les sponsors Open Systems et AdNovum se raviront de vous offrir une journée mémorable à l’EPFL !

Références

  1. icpc.baylor.edu et swerc.eu
  2. C’est en lisant la suite que vous comprendrez :)
  3. Pour l’exemple donné, on a


Cherchez ...

- dans tous les Flash informatique
(entre 1986 et 2001: seulement sur les titres et auteurs)
- par mot-clé

Avertissement

Cette page est un article d'une publication de l'EPFL.
Le contenu et certains liens ne sont peut-être plus d'actualité.

Responsabilité

Les articles n'engagent que leurs auteurs, sauf ceux qui concernent de façon évidente des prestations officielles (sous la responsabilité du DIT ou d'autres entités). Toute reproduction, même partielle, n'est autorisée qu'avec l'accord de la rédaction et des auteurs.


Archives sur clé USB

Le Flash informatique ne paraîtra plus. Le dernier numéro est daté de décembre 2013.

Taguage des articles

Depuis 2010, pour aider le lecteur, les articles sont taggués:
  •   tout public
    que vous soyiez utilisateur occasionnel du PC familial, ou bien simplement propriétaire d'un iPhone, lisez l'article marqué tout public, vous y apprendrez plein de choses qui vous permettront de mieux appréhender ces technologies qui envahissent votre quotidien
  •   public averti
    l'article parle de concepts techniques, mais à la portée de toute personne intéressée par les dessous des nouvelles technologies
  •   expert
    le sujet abordé n'intéresse que peu de lecteurs, mais ceux-là seront ravis d'approfondir un thème, d'en savoir plus sur un nouveau langage.