Perles de Dijkstra
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

Les Perles de Dijkstra sont un problème de backtracking en programmation énoncé par Edsger Dijkstra dans les Communications de l'ACM au début des années 1970.

L'intérêt du problème vient du fait qu'il est difficile de le programmer sans instruction (Une instruction est une forme d'information communiquée qui est à la fois une commande et une explication pour décrire l'action, le comportement, la méthode...) GO TO, mais que si on le programme avec une telle instruction, on a de fortes chances aussi de se tromper, et de rendre le programme très dur à corriger.

Il a donné lieu aussi à des développements mathématiques simples.

Le problème

Soit un fil sur lequel on désire enfiler des perles de trois couleurs. Dijkstra propose bleu (Bleu (de l'ancien haut-allemand « blao » = brillant) est une des trois couleurs primaires. Sa longueur d'onde est comprise...), blanc (Le blanc est la couleur d'un corps chauffé à environ 5 000 °C (voir l'article Corps noir). C'est la sensation visuelle obtenue avec un spectre lumineux continu, d'où...) et rouge (La couleur rouge répond à différentes définitions, selon le système chromatique dont on fait usage.), couleurs du drapeau néerlandais, mais on peut dans une formulation (La formulation est une activité industrielle consistant à fabriquer des produits homogènes, stables et possédant des propriétés spécifiques, en mélangeant...) plus neutre les nommer 0, 1 et 2.

Une seule contrainte existe : il ne doit pas y avoir sur le fil deux séquences adjacentes identiques.

Questions :

  • Combien de perles peut-on ainsi enfiler ?
  • Écrire l'algorithme qui réalise la plus longue séquence possible, ou le cas échéant celui qui pourra continuer indéfiniment.

L'analyse

Plausibilité

Elle commence tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) d'abord avec un peu de réflexion préalable : chaque choix de perle (Les perles sont de petites billes, généralement de couleur blanche, créées par certains mollusques, principalement les huîtres. Quand un objet irritant passe à...) est un choix parmi trois. Le degré de liberté (La notion de degré de liberté recouvre plusieurs notions en sciences et ingénierie :) dans la construction est de l'ordre de 3N. La contrainte, elle, semble diminuer plutôt en N3/2, ce qui conduit à se dire que passé un certain cap, on a assez de marge de manœuvre pour continuer indéfiniment. Mais impression n'est pas démonstration (En mathématiques, une démonstration permet d'établir une proposition à partir de propositions initiales, ou précédemment démontrées à partir de propositions initiales, en s'appuyant sur un ensemble de...).

Familiarisation simple

Elle contient ensuite avec un peu de simulation à la main :

  • 0 est correct
  • 00 serait incorrect
  • 01 est correct
  • 010 est correct
  • 0100 et 0101 seraient incorrects
  • 0102 est correct
  • ...
  • 0102010 est correct

Nous avons ensuite un souci pour placer une perle supplémentaire :

  • 01020100 ne convient pas (répétition du 0)
  • 01020101 ne convient pas (répétition du 01)
  • 01020102 ne convient pas davantage (répétition du 0102)

Est-ce la chaîne la plus longue cherchée ? Non. Nous pouvons toujours remettre en cause un de nos choix (arbitraires) antérieurs pour voir si cela ne débloque pas la situation (En géographie, la situation est un concept spatial permettant la localisation relative d'un espace par rapport à son environnement proche ou non. Il inscrit un lieu dans un cadre plus général afin de le qualifier à travers...). Et de fait :

0102012 débloque les choses et permet de continuer. Cette procédure se nomme le backtracking.

Il n'y a plus qu'à programmer.

Programmation (La programmation dans le domaine informatique est l'ensemble des activités qui permettent l'écriture des programmes informatiques. C'est une étape importante de la conception de logiciel (voire de matériel, cf. VHDL).)

Mais attention aux programmeurs négligents : si leur programme ne prévoit pas qu'il puisse y avoir de nombreux backtrackings successifs depuis la même position, ils sont partis pour rencontrer de sérieux ennuis. Ennuis qui deviennent vite inextricables si de surcroît ils ont fait usage (L’usage est l'action de se servir de quelque chose.) de l'instruction GO TO, qui interdit toute prédiction facile sur les invariants valides en chaque point (Graphie) du programme.

Méthode mathématique (Les mathématiques constituent un domaine de connaissances abstraites construites à l'aide de raisonnements logiques sur des concepts tels que les nombres, les figures, les...)

L'on peut construire une telle chaîne arbitrairement longue. Si l'on considère le morphisme \ f (verifiant \ f(ab)=f(a)f(b) ) sur l'alphabet \ \{0,1\} vérifiant \ f(0)=01 et \ f(1)=10 et que l'on note \ u_n=f^n(0). On a alors: \ u_1=01; \ u_2=0110; \ u_3=01101001; \ u_4=0110100110010110; \ u_5=01101001100101101001011001101001. Ainsi l'on défini le mot de Thue et Morse, en prenant la limite de cette suite(car chaque élément de la suite est préfixe des autres). Ce mot possède plusieurs particularités mais ici celle qui nous intéresse ici est la suivante: On remarque que le mot ne comporte jamais de facteur 000 ou 111, ainsi si on factorise la mot en facteur 0.1* et l'on remplace chacun de ces facteurs par le nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) de 1 qu'il contiens (toujours inférieurs a 2). On obtient ainsi le mot: \ v=210201210120210201202..... L'on sait alors montrer que ce mot vérifie la condition de ne pas contenir de carré (Un carré est un polygone régulier à quatre côtés. Cela signifie que ses quatre côtés ont la même longueur et ses quatre angles la même mesure. Un carré est à la fois un rectangle et un losange.).

Page générée en 0.153 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique