Perles de Dijkstra
# Perles de Dijkstra

Les perles de Dijkstra sont un problème de retour sur trace en programmation énoncé par Edsger Dijkstra dans les Communications of the 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 goto, 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, blanc et rouge, couleurs du drapeau néerlandais, mais on peut dans une formulation 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 d'abord avec un peu de réflexion préalable : chaque choix de perle est un choix parmi trois. Le degré de liberté dans la construction est de l'ordre de $3^N.$ La contrainte, elle, semble diminuer plutôt en $N^{3/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.

### 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. 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

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 de l'instruction GO TO, qui interdit toute prédiction facile sur les invariants valides en chaque point du programme.

### Méthode mathématique

On peut construire une telle chaîne arbitrairement longue. Soit $\ f$ le morphisme (vérifiant $\ f(ab)=f(a)f(b)$) sur l'alphabet $\ \{0,1\}$, défini par $\ f(0)=01$ et $\ f(1)=10$. Notons $\ 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éfinit 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 est la suivante : on peut prouver que le mot ne comporte pas de facteur 000 ou 111. Ceci permet de décomposer le mot en produit de facteurs de la forme $\ 0.1^{*}$. Si l'on remplace ensuite chacun de ces facteurs par le nombre de 1 qu'il contient (toujours inférieur a 2), on obtient le mot $\ v=210201210120210201202.....$

On peut montrer que ce mot est un mot sans facteur carré.

## Implémentation

### JavaScript

**Fonction de vérification de validité de la chaine**

**Décomposée en trois fonctions**

La première, renvoie un booléen, indiquant si les deux séquences passées en argument sont identiques.

La seconde teste toutes les sous-chaines qui partent du premier caractère qu'on lui envoie.

La troisième exécute la seconde sur chacun des caractères de la chaine.

**Fonction de vérification de validité de la chaine**

**Optimisation**

Cette implémentation naïve, peut être fortement optimisée si on prend en compte qu'à chaque étape on ne fait que concaténer un élément à une chaine déjà valide :

**Récursivité**

La fonction récursive va tester chacune des trois couleurs et vérifier si la chaine produite est valide. La première condition de la fonction utilise une variable globale "iterations" initialisée au début du programme pour éviter le dépassement de pile, et le Do While fait appel a la fonction de Backtracking décrite dans la section suivante, quand on constate qu'on ne peut plus ajouter de perle, et ce tant que la chaine obtenue n'est pas valide.

**Backtracking**

La première condition tente d’incrémenter la valeur de la dernière perle, et si elle a atteint son maximum (2), elle retire la dernière perle.

### C

La solution en Javascript est rapide à concevoir et écrire, mais ses performances sont très faibles. Il est donc conseillé de réécrire le programme en C afin d'obtenir des résultats bien plus rapides.

À titre indicatif, cette solution s’exécute environ 100 fois plus rapidement que celle en JS. (Pour 10000 itérations, le JS prends 17,5s, contre 0,18s en C)

