Service : ULB
Algorithmes al´eatoires en combinatoire des
mots
Brieuc Barth´elemy
M´emoire r´ealis´e sous la direction de Monsieur le Professeur Gwena¨el Joret en
vue de l’obtention du Master en Sciences de l’Informatique
“The best things in life are often
waiting for you at the exit ramp of
your comfort zone.”
Karen Salmansohn
Remerciements
Au terme de la r´edaction de ce m´emoire, je tiens tout particuli`erement `a remer-
cier :
Mon directeur de m´emoire, Mr Gwena¨el Joret, pour ses nombreux conseils
mais aussi et surtout pour son incroyable disponibilit´e.
Le corps enseignant de l’UMons et les professeurs de l’ULB qui m’ont appris,
apr`es 15 ans de carri`ere, bien plus qu’ esp´er´e. Un petit apart´e pour Mme V´eronique
Bruy`ere qui m’a permis, grˆace `a la Validation des acquis de l’exp´erience, de reprendre
ces ´etudes. Je remercie ´egalement messieurs Laurent Duez et Vincent Callut, pour
leurs conseils et encadrement durant le stage en entreprise.
Ma famille toujours pr´esente pour me soutenir et m’aider dans la gestion de mon
planning surcharg´e.
Mes amis depuis plus de 3 d´ecennies : Pierre, Antoine, Margay, Mathieu, Laurent,
Lionel, Fr´ed´eric, Olivier, et Sarah qui m’ont ´epaul´e , conseill´e, avis´e et qui ont pris
le temps de corriger mes travaux.
Annick Sartenaer et Gille Gomand pour leurs pr´ecieux conseils avant la reprise
des ´etudes.
Tous mes coll`egues de DigitasLBi qui se sont montr´es compr´ehensifs, qui m’ont
lib´er´e du temps, afin de mener `a bien ces ´etudes.
Et pour terminer, principalement ma co´equipi`ere de tous les jours , Annabelle,
qui a ´et´e un appui inestimable durant ces ´etudes grˆace `a ses conseils, son ´energie,
ses corrections, sans elle rien n’aurait ´et´e possible.
Table des mati`eres
1 Introduction 4
2 Terminologie et fondamentaux 5
2.1 Le travail d’Axel Thue . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Les algorithmes al´eatoires . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Trouver un facteur carr´e . . . . . . . . . . . . . . . . . . . . . . . . . 7
3 Outils combinatoires 9
3.1 Les Nombres de Catalan . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2 Les mots de Dyck . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4 Une nouvelle approche des mots sans carr´e 13
4.1 Algorithme en combinatoire des mots, alphabet fixe . . . . . . . . . . 13
4.1.1 Quelques r´esultats de l’algorithme n
o
3 . . . . . . . . . . . . . 14
4.2 Algorithme en combinatoire des mots avec listes sp´ecifiques . . . . . . 16
4.2.1 Quelques r´esultats de l’algorithme n
o
4 . . . . . . . . . . . . . 17
4.3 Preuve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.3.1 Hypoth`ese . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.3.2 Preuve : comptage . . . . . . . . . . . . . . . . . . . . . . . . 20
4.3.3 D´eveloppement de la preuve . . . . . . . . . . . . . . . . . . . 24
4.4 Un symbole ajout´e en fin de mot peut-il terminer 2 facteurs carr´es de
longueurs diff´erentes ? . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5 Mot sans carr´e `a progression arithm´etique 27
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5.2 Algorithme cr´eation du mot sans carr´e `a progression arithm´etique . . 28
5.2.1 Pr´esentation des algorithmes . . . . . . . . . . . . . . . . . . . 28
5.2.2 Exp´erimentation sur les algorithmes . . . . . . . . . . . . . . . 31
5.3 Preuve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.3.1 Hypoth`ese . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.3.2 Preuve par contradiction . . . . . . . . . . . . . . . . . . . . . 33
5.3.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
6 Conclusion 38
A Annexes 40
Algorithmes al´eatoires en combinatoire des mots
1 Introduction
En math´ematique combinatoire, un mot est une suite de symboles qui peuvent
ˆetre assembl´es afin de construire une chaˆıne de caract`eres potentiellement infinie.
Ce travail ´etudiera deux publications capitales qui, plus de cent ans apr`es le
travail d’Axel Thue en 1906, ont permis d’apporter des r´eponses au nombre de sym-
boles requis afin de cr´eer un mot infini, avec un alphabet de x symboles pr´ed´efinis,
qui ne comporte pas de facteur carr´e, c’est-`a-dire de r´ep´etition avec le mod`ele XX,
X repr´esentant un bloc de symboles. Tout d’abord, la premi`ere publication montre
comment il est possible de cr´eer des mots sans carr´e quand les symboles sont `a cˆot´e
des autres. Ensuite, dans la seconde publication, nous ´etudierons comment il est
possible d’´eviter un facteur carr´e dans un sous mot compos´e de symboles qui sont `a
k sauts des symboles adjacents.
Il sera aussi question d’aborder et d’expliquer certains outils des math´ematiques
combinatoires qui seront utilis´es dans les preuves de ce travail.
Le but de cette analyse est d’expliquer, d’exp´erimenter et de montrer comment se
comportent ces constructions de mots lorsqu’elles sont ´elabor´ees par un algorithme
qui prendra des d´ecisions al´eatoires `a chaque fois qu’il devra placer un symbole dans
le mot en cours de composition.
Le travail comportera aussi des r´esultats d’exp´eriences qui montreront le nombre
moyen d’it´erations de l’algorithme pour constituer des mots finis.
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 4 de 43
Algorithmes al´eatoires en combinatoire des mots
2 Terminologie et fondamentaux
Afin de faciliter la compr´ehension du pr´esent travail, commen¸cons par ´etablir
un vocabulaire pour tout le document. Tout d’abord, les facteurs d’un mot sont les
sous-chaˆınes qui composent ce mot telles que les facteurs d’un mot w = a
1
···a
n
sont les mots a
i
···a
j
pour 1 ≤ i ≤ j ≤ n [1]. Un carr´e est une suite de deux blocs
cons´ecutifs qui ont la mˆeme s´erie de symboles. La taille de la r´ep´etition sera d`es lors
le nombre de caract`eres qui compose un bloc.
Le mot ABCBA ne contient pas de r´ep´etition alors que le mot ABB contient deux
blocs cons´ecutifs form´es de B et est de taille 1, ainsi, ABCABC est donc un carr´e
de taille 3.
Si nous utilisons un alphabet binaire, compos´e des symboles 1 & 0, il est impos-
sible de cr´eer un mot sans carr´e de longueur sup´erieure `a 3. En effet, dans le mot
suivant 010 ., le prochain symbole ∈ {0, 1} et donc un carr´e d’une taille de 1 (resp.
2) si le symbole suivant est 0 (resp. 1) apparaitra.
Un mot sans carr´e est un mot ne contenant pas de facteur carr´e.
2.1 Le travail d’Axel Thue
En 1906, Axel Thue (Math´ematicien Norv´egien 1863-1922 [2] ) cr´ee une m´ethode
par induction qui g´en`ere un mot infini sans carr´e avec un alphabet de taille 3 [3].
Le principe est le suivant : prenons l’alphabet a, b, c et pour tout mot sans carr´e,
rempla¸cons les symboles comme suit :
• a → abac
• b → babc
• c → bcac si la lettre pr´ec´edant c est a
• c → acbc si la lettre pr´ec´edant c est b
Si nous commen¸cons par le symbole a nous aurons alors cette suite :
• a
• abac
• abacbabcabacbcac
• . . .
Il est prouv´e que cette suite infinie est sans carr´e [4].
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 5 de 43
Algorithmes al´eatoires en combinatoire des mots
2.2 Les algorithmes al´eatoires
Dans ce travail nous utiliserons plusieurs algorithmes qui seront utiles dans nos
preuves et exp´eriences, par exemple pour l’automatisation de cr´eation de mots, pour
la v´erification ainsi que lors du traitement en cas de carr´e.
Le principe des algorithmes al´eatoires est de cr´eer un mot en partant d’une chaˆıne
vide. Cet algorithme est compos´e d’une boucle principale qui choisit un symbole
al´eatoire et le place en fin de mot ainsi jusqu’`a atteindre la taille du mot d´esir´ee.
Prenons l’algorithme 1 prenant en entr´ee la longueur du mot souhait´ee (un entier n)
ainsi qu’un alphabet contenant les symboles qui peuvent ˆetre choisis pour construire
le mot, e.g. ”a”, ”b”, ”c”.
La ligne 1 de l’algorithme d´efinit la variable CurrentPosition `a 0, c’est elle qui sera
test´ee avec la variable n afin de savoir si l’algorithme doit s’arrˆeter ou non. Puisque
CurrentPosition est incr´ement´e `a chaque it´eration (ligne 4 ), l’algorithme testera s’il
doit s’arrˆeter ou non.
Un choix de caract`ere al´eatoire est effectu´e `a chaque it´eration (ligne5) ; la fonction
Random retourne ici un nombre al´eatoire compris entre le premier et le deuxi`eme
argument. Par exemple, le r´esultat de Random(0, 3) ∈ {0, 1, 2, 3}, c’est pourquoi
nous calculons le nombre d’´el´ements de ”L” −1, grˆace `a la fonction Longueur pour
que nous ayons l’index du symbole choisi. Si nous reprenons l’exemple d’un alphabet
L[”a”, ”b”, ”c”], alors l’index ”0” est celui du symbole ”a”, ”1” est quant `a lui l’index
du symbole ”b”, etc.
Algorithm 1: Cr´eation d’un mot al´eatoire
Data: Int n, String L[]
Result: String word
1 Int CurrentP osition ← 0;
2 String word ← ””;
3 while CurrentPosition < n do
4 CurrentP osition ← CurrentP osition + 1;
5 Int r = Random(0, Longueur(L) − 1);
6 word ← word + L[r];
7 end
8 Return word;
Cet algorithme est somme toute rudimentaire et peu utile dans un premier temps,
mais il permet de cerner ce que sont les algorithmes en combinatoire de mot. Il sera
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 6 de 43
Algorithmes al´eatoires en combinatoire des mots
notre base de d´epart pour construire les algorithmes utiles dans ce travail.
2.3 Trouver un facteur carr´e
Dans cette sous section, nous allons pr´esenter un algorithme qui sera n´ecessaire
dans la suite du document. En effet, le travail portant sur les facteurs carr´es d’un
mot, il est utile de comprendre comment nous les d´etecterons. Nous allons expliquer
l’algorithme n
o
2 que nous avons cr´e´e, permettant de d´etecter un facteur carr´e plac´e
en fin de chaˆıne. Celui-ci v´erifie si le dernier symbole fait partie d’un carr´e. Il est
utile pour tester un mot qui est en construction. Sa complexit´e est en O(n
2
).
Le principe est de se d´eplacer lin´eairement dans le mot en commen¸cant par le
dernier caract`ere et nous allons ajouter un caract`ere au test `a chaque it´eration.
Puisque nous voulons d´etecter un carr´e, au pire cas, le nombre d’it´erations sera de
la moiti´e de la longueur de la chaine (arrondi en dessous). En d’autres termes, si le
mot est d’une longueur de 9 caract`eres, le nombre d’it´erations sera de 4 (ligne 3).
D´efinissons que s
1
est le premier symbole du mot, alors que s
n
est le dernier.
La premi`ere fois, nous testerons si s
n
est ´egal `a s
n−1
, si oui c’est un carr´e de taille
1. Dans la deuxi`eme it´eration, nous allons tester le mot form´e de s
n−1
s
n
que nous
allons comparer `a s
n−3
s
n−2
, etc.
Prenons un exemple concret avec le mot ABACABAC :
• A la premi`ere it´eration, nous allons tester le dernier symbole ”C” avec l’avant
dernier A : pas de r´ep´etition.
• A la deuxi`eme it´eration comparons le mot form´e des deux derniers symboles
AC avec les deux symboles qui les pr´ec´edent ”AB” : pas de r´ep´etition.
• Ensuite BAC avec les trois symboles qui les pr´ec´edent ”ACA” : pas de
r´ep´etition.
• Et pour finir ABAC avec les quatres symboles qui les pr´ec´edent ABAC : un
carr´e de taille 4 apparait.
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 7 de 43
Algorithmes al´eatoires en combinatoire des mots
Algorithm 2: Retourner la r´ep´etition trouv´ee `a la fin du mot.
Data: String word
Result: Retourner une chaˆıne
1 Int lastCharP os ← Length(word) − 1;
2 Int nbrCharT oT est ← 0;
3 Int nbrIteration ← RoundingDown(Length(word)/2) ;
4 while nbrIteration > 0 do
5 String firstSubstring ← word.substring(lastCharP os −
((nbrCharT oT est ∗ 2) + 1), lastCharP os −nbrCharT oT est);
6 String
secondSubstring ← word.substring(lastCharP os − nbrCharT oTest);
7 nbrIteration − −;
8 nbrCharT oT est + +;
9 if firstSubstring == secondSubstring then
10 return firstSubstring;
11 end
12 end
13 return NIL;
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 8 de 43
Algorithmes al´eatoires en combinatoire des mots
3 Outils combinatoires
Dans cette sous section, nous allons nous arrˆeter sur deux outils qui nous se-
ront utiles dans la preuve du Th´eor`eme dans l’article [5]. Ainsi, nous parlerons des
nombres de Catalan et des mots de Dyck.
3.1 Les Nombres de Catalan
Les nombres de Catalan sont une suite d’entiers naturels permettant de r´esoudre
des probl`emes de d´enombrements. Leur nom provient du math´ematicien belge Eug`ene
Charles Catalan (1814-1894) sp´ecialis´e dans la th´eorie des nombres [6]. Dans les
points suivants, nous allons montrer trois exemples dans lesquels nous pouvons re-
trouver cette suite de nombres.
Triangulation des polygones
La s´equence a ´et´e d´efinie par Leonard Euler [7] au 18`eme si`ecle lorsqu’il s’est
int´eress´e `a la triangulation des polygones et au fait de savoir combien il pouvait y
avoir de fa¸cons de trianguler un polygone divis´e par des segments. Le principe est le
suivant : dans un polygone `a n cot´es, on trace n − 3 segments reliant des sommets
sans se croiser, on d´ecoupe alors le polygone en pi`eces triangulaires.
Sur la Figure 1, qui est un polygone `a 4 cot´es, autrement dit un rectangle, nous
allons tracer 4 −3 segments. Nous pouvons remarquer que, dans ce cas, seules deux
triangulations sont possibles. Pour le pentagone de la Figure 2, nous tracerons donc
2 segments qui donneront 3 triangles. Nous pouvons alors constater que pour un
polygone `a 5 cot´es et donc de 3 triangles, il existe 5 fa¸cons possibles de trianguler.
Ainsi, pour un hexagone, il y aura 4 triangles et 14 possibilit´es, alors que pour un
heptagone, il y aura 5 triangles et 42 fa¸cons de le d´ecouper.
Figure 1 – Triangulation d’un carr´e. 2 Possibilit´es
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 9 de 43
Algorithmes al´eatoires en combinatoire des mots
;
Figure 2 – Triangulation d’un pentagone. 5 Possibilit´es
Chemins sous-diagonaux dans le carr´e
Un autre comptage qui suit la mˆeme s´erie se trouve dans une grille de n X n
carr´ee. La question est de connaˆıtre le nombre de chemins monotones qu’il peut y
avoir en dessous de la diagonale partant du bas gauche vers le haut droit. Un chemin
monotone est, dans une grille, le fait qu’`a chaque intersection, nous puissions prendre
soit `a droite, soit monter, `a condition de rester dans la grille.
La Figure 3 nous montre un exemple de grille allant de 1 X 1 carr´ee jusqu’`a 3 X
3 carr´ee. Pour la grille de 1 X 1, un seul chemin possible, pour 2 X 2 , 2 chemins
possibles et pour 3 X 3, 5 chemins possibles. Dans les annexes 12, nous pouvons
constater que pour une grille de 4 X 4, il y a 14 possibilit´es et pour une grille de 5
X 5, il y en a 42.
1.
2.
3.
Figure 3 – Nombre de chemins monotones d’une grille 1x1 `a 3x3. G´en´eration
automatique dans Latex [8]
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 10 de 43
Algorithmes al´eatoires en combinatoire des mots
Parenth´esage d’une expression
Dans cette section, nous allons d´eterminer le nombre de parenth´esages corrects
d’une expression pour un nombre donn´e de parenth`ese. Par exemple, s’il n’y a qu’une
seule parenth`ese (), il n’y a qu’une seule fa¸con de bien la placer ´etant donn´e que
cette expression serait fausse : )(. Pour deux couples de parenth`eses, nous pouvons
constater qu’il existe deux mani`eres de les placer correctement : ()() et (()). Pour
trois couples, 5 mani`eres : ()()(), (())(), ((())), ()(()), (()()). Ainsi pour 4 couples,
14 mani`eres ; pour 5 il y en aura 42, etc. Eux aussi sont compt´es grˆace aux nombres
de Catalan [9].
Formules et listes
Suite `a tous ces comptages, Eug`ene Catalan trouve plusieurs formules pour cal-
culer les nombres de Catalan `a partir d’un entier n ≥ 0 :
C
n
=
1
n + 1
2n
n
!
=
2n
n
!
−
2n
n + 1
!
=
(2n)!
(n + 1)!n!
=
n
Y
k=2
n + k
k
La suite de Catalan grandit asymptotiquement tel que C
n
≤
4
n
√
πn
3/2
pour tout
n ≥ 1 [7]
Le Tableau 1 suivant montre les 12 premiers nombres de la suite de Catalan en
fonction d’un entier n.
n Les nombres de Catalan
0 1
1 1
2 2
3 5
4 14
5 42
6 132
7 429
8 1430
9 4862
10 16796
11 58786
Table 1 – Les 12 premiers nombres de Catalan
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 11 de 43
Algorithmes al´eatoires en combinatoire des mots
3.2 Les mots de Dyck
Un mot de Dyck, tenant son nom du math´ematicien allemand Wather von Dyck
(1856-1934) [10], est un mot qui a comme propri´et´e d’ˆetre compos´e de deux symboles
(par exemple 0 et 1), de contenir autant de symboles 0 que de 1, et que pour tous
les pr´efixes du mot, le nombre de 0 est ≥ que le nombre de 1.
Exemple : 010110 n’est pas un mot de Dyck, puisque si l’on regarde le pr´efixe
du mot s’arretant avant le dernier symbole, le nombre de 1 est > que le nombre de
0. Par contre, 001011 est un mot de Dyck puisqu’en regardant tous les pr´efixes du
mot, le nombre de 0 sera toujours ≥ au nombre de fois que l’on retrouve 1.
Nous pouvons compter le nombre de possibilit´es de la structure d’un mot de
Dyck en fonction du nombre de 0 que nous rencontrons, et nous allons sp´ecifier une
fa¸con de donner la valeur `a un mot de Dyck par T
x
qui est le nombre de mots de
Dyck ayant x fois le symbole 0. Donc, si nous rencontrons le premier symbole une
seule fois dans un mot de Dyck valide, nous savons que la seule structure existante
est 01, ainsi T
1
vaut 1. Si nous en rencontrons 2, les structures valides sont aux
nombres de 2 : 1100 et 1010, par cons´equent T
2
vaut 2. Si nous en rencontrons 3, les
mots valides sont alors : 000111, 001011, 001101, 010101, 010011 ; T
3
= 5. Pour 4
fois le premier symbole, nous aurons alors 14 possibilit´es de cr´eer un mot de Dyck,
d`es lors T
4
= 14, T
5
= 42, T
6
= 132, etc. La valeur des mots de Dyck ´evolue en
fonction de la suite de Catalan [7].
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 12 de 43
Algorithmes al´eatoires en combinatoire des mots
4 Une nouvelle approche des mots sans carr´e
Dans l’article de Jaros Law Grytczuk, Jakub Kozik, and Piotr Micek [5], il est
montr´e via une approche probabiliste, qu’il est possible de cr´eer un mot sans carr´e
pour un alphabet de 4 symboles. Dans la section 2.1 nous montrions le mot infini
de Thue avec un alphabet de 3 symboles. La m´ethode pour 4 symboles est moins
optimale mais plus flexible, puisqu’il y aura une g´en´eralisation du probl`eme grˆace `a
l’algorithme qui s’adaptera, adaptation que la preuve de Thue ne fait pas. De plus, la
preuve inclut que la liste dans laquelle le choix du symbole est effectu´e al´eatoirement
(Algorithme 1 Ligne 4) peut ˆetre diff´erente `a chaque position du mot. Nous verrons
plus tard dans le document une impl´ementation avec des listes diff´erentes [4].
Avant de passer `a la preuve, d´eterminons les algorithmes utiles ainsi que quelques
tests de performances.
4.1 Algorithme en combinatoire des mots, alphabet fixe
L’algorithme 3 retourne un mot sans carr´e avec un alphabet qui est fix´e : c’est `a
dire que l’algorithme fait un choix de symboles al´eatoirement sur l’alphabet d´efini
au d´epart et l’ajoute `a la fin de la chaine de caract`eres word (ligne 3). Les symboles
disponibles sont fix´es d`es le d´epart et sont les mˆemes pour toutes les positions. La
valeur L[] est un vecteur comprenant les symboles que l’algorithme peut choisir.
L’entier ”n” est la longueur souhait´ee.
Le but ´etant de ne pas avoir de r´ep´etition, nous allons donc devoir les d´etecter
et les traiter. Pour cela, si une r´ep´etition se produit, il faut retirer tout le pattern de
r´ep´etition et non uniquement le dernier caract`ere car nous pourrions alors ˆetre dans
une boucle infinie si cela est mal g´er´e. Voici un exemple de cette situation : dans
”ABACABA ”, si le dernier caract`ere peut ˆetre choisi entre les symboles suivants :
{A, B, C}, une r´ep´etition ne peut ˆetre ´evit´ee.
La m´ethode ”getRepetitionLength” (ligne 4) retourne un entier qui repr´esente la
longueur de la r´ep´etition caus´ee par le dernier symbole. Si la valeur est ”0” alors,
il n’y a pas de r´ep´etition. Par contre, si cette derni`ere d´etecte une r´ep´etition, et
donc la valeur de retour est > ”0”, la condition de la ligne 5 sera vraie. Alors, nous
enlevons les ”n” derniers caract`eres ; ”n” ´etant la longueur de la r´ep´etition (Ligne
6). Pour la partie qui d´etecte une r´ep´etition, nous utiliserons l’algorithme n
o
2.
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 13 de 43
Algorithmes al´eatoires en combinatoire des mots
Une fois un mot sans carr´e construit, celui-ci est retourn´e `a la fin de l’algo-
rithme(Ligne 9).
Algorithm 3: Algorithme al´eatoire en combinatoire de mot
Data: String L[], Int n
Result: Retourner un mot qui ne contient pas de r´ep´etition
1 String word ;
2 while length(word) < n do
3 word ← word + randomElementOf(L);
4 Int repetitionLength ← getRepetitionLength(word);
5 if repetitionLength > 0 then
6 word ← removeEndCharacters(word, repetitionLength)
7 end
8 end
9 Return word ;
4.1.1 Quelques r´esultats de l’algorithme n
o
3
La tableau 2 est le r´esultat de l’exp´erimentation sur l’algorithme n
o
3.
Rappelons que la fonction demande 2 arguments : un alphabet et la longueur du
mot que nous voulons construire.
La tableau de r´esultats montre les r´esultats des exp´erimentations r´ealis´ees.
La description des colonnes :
1. La longueur du mot que l’algorithme doit g´en´erer
2. Le nombre d’it´erations que l’algorithme a r´ealis´e pour cr´eer un mot sans
carr´e.
Taille It´erations
10 30
20 112
30 237
40 388
50 553
60 728
70 924
80 1097
90 1288
100 1462
Table 2 – Pour un choix de 3 symboles - algorithme lanc´e 10.000 fois par taille
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 14 de 43
Algorithmes al´eatoires en combinatoire des mots
10 20 30 40 50 60 70 80 90 100
0
500
1,000
1,500
Longueur du mot
Nombre d’it´eration
Nombre moyen d’it´erations
Figure 4 – Visualisation du nombre d’it´erations pour la cr´eation d’un mot sans
carr´e pour un choix de 3 symboles
Reprenons le mˆeme algorithme mais au lieu d’utiliser 3 symboles, nous en utili-
serons 4, le tableau 3 ´etant le r´esultat de l’exp´erimentation.
Taille It´erations
10 16
20 34
30 53
40 72
50 91
60 109
70 128
80 147
90 166
100 184
Table 3 – Pour un choix de 4 symboles - algorithme lanc´e 10.000 fois par taille
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 15 de 43
Algorithmes al´eatoires en combinatoire des mots
10 20 30 40 50 60 70 80 90 100
0
50
100
150
200
Longueur du mot
Nombre d’it´eration
Nombre moyen d’it´erations
Figure 5 – Visualisation du nombre d’it´erations pour la cr´eation d’un mot sans
carr´e pour un choix de 4 symboles
4.2 Algorithme en combinatoire des mots avec listes sp´ecifiques
Dans cette section, nous allons introduire le choix d’une liste sp´ecifique pour
chaque position du mot. Nous allons donc reprendre l’algorithme n
o
3 cr´e´e dans la
section pr´ec´edente et y ajouter pour chaque position du mot une liste de symboles ;
ces derniers ´etant potentiellement diff´erents. Il est important de noter qu’une fois
la liste fix´ee pour une position, celle-ci sera gard´ee mˆeme en cas d’effacement du
symbole. Le r´esultat de cette modification est l’algorithme n
o
4. Les diff´erences sont
dans les donn´ees que nous donnons `a l’algorithme. Puisque nous fournissons `a celui-
ci un ensemble de listes compos´ees pour chacune d’elles de symboles potentiellement
diff´erents, c’est la variable listByposition.
A la ligne4, nous prenons un symbole al´eatoirement dans la liste pour la position
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 16 de 43
Algorithmes al´eatoires en combinatoire des mots
actuelle.
Algorithm 4: Algorithme al´eatoire en combinatoire de mot, la liste de sym-
boles est potentiellement diff´erente `a chaque position du mot
Data: Int n,String[][] listByposition
Result: Retourner un mot qui ne contient pas de r´ep´etition
1 String word ; String[] currentList;
2 while length(word) < n do
3 word ← word + randomElementOf(listByP osition[length(word) − 1]);
4 Int repetitionLength ← getRepetitionLength(word);
5 if repetitionLength > 0 then
6 word ← removeEndCharacters(word, repetitionLength)
7 end
8 end
9 Return word ;
Apr`es exp´erimentations de l’algorithme 4, nous pouvons visualiser les r´esultats
de celles-ci dans le tableau 4. La premi`ere colonne repr´esente la longueur du mot
g´en´er´e. Les autres colonnes sont sous cette forme : r parmi l. r repr´esente le nombre
de symboles choisi al´eatoirement pour chaque it´eration et l est le nombre de symboles
disponibles pour g´en´erer cette liste. Autrement dit, dans un choix parmi l symboles,
l’algorithme en choisit r pour chaque position dans le mot.
4.2.1 Quelques r´esultats de l’algorithme n
o
4
Faisons quelques tests sur l’algorithme n
o
4. Nous allons d´efinir 2 alphabets de
longueurs 4 & 5 et l’algorithme puisera l symboles dans ceux-ci. Les titres des co-
lonnes indiquent le nombre de symboles s´electionn´es parmi la longueur de l’alphabet
disponible.
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 17 de 43
Algorithmes al´eatoires en combinatoire des mots
0 100 200 300 400 500 600 700 800 900 1,000
0
500
1,000
1,500
2,000
Longueur du mot
Nombre d’it´eration
3 parmi 4
4 parmi 4
3 parmi 5
4 parmi 5
5 parmi 5
Figure 6 – R´esultats du nombre moyen d’it´erations n´ecessaires de la boucle prin-
cipal de l’algorithme n
o
4 ex´ecut´e 10.000 fois
Taille 3 parmi 4 4 parmi 4 3 parmi 5 4 parmi 5 5 parmi 5
10 16 15 14 13 13
20 36 34 30 28 28
30 56 53 45 43 42
40 76 72 61 58 57
50 96 90 76 73 72
60 116 109 92 88 86
70 135 128 107 103 101
80 155 147 123 118 116
90 175 166 139 133 130
100 195 184 154 148 145
500 991 935 778 745 731
1000 1984 1874 1559 1491 1465
Table 4 – R´esultats du nombre moyen d’it´erations n´ecessaires de la boucle princi-
pale de l’algorithme n
o
4 ex´ecut´e 10.000 fois
Dans le Tableau 4, nous pouvons constater que plus il y a de choix pour l’al-
gorithme, c’est `a dire que plus l’alphabet grandit ou que la liste `a disposition par
position grandit , moins il a besoin d’it´erations pour former le mot.
Taille maximum de r´ep´etitions
Le Tableau 5 est le r´esultat de l’algorithme ex´ecut´e 10.000 fois pour chaque
r´esultat, et reprend la longueur maximum de carr´es effac´es par l’algorithme. Nous
pouvons constater que la taille maximum de r´ep´etition n’augmente pas lin´eairement
en fonction de la taille de la r´ep´etition mais qu’au contraire, la taille maximum
grandit logarithmiquement. Par exemple, pour la colonne 3parmi4, pour la taille
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 18 de 43
Algorithmes al´eatoires en combinatoire des mots
d’un carr´e d’une longueur de 10 symboles, la taille maximum de la r´ep´etition est de
5, ce qui repr´esente la moiti´e du mot demand´e. Cependant pour un mot sans carr´e
d’une longueur de 1000, la taille maximum du bloc de r´ep´etition est de 18.
Taille 3 parmi 4 4 parmi 4 3 parmi 5 4 parmi 5 5 parmi 5
10 5 5 5 5 5
20 9 9 7 7 9
30 12 10 8 8 9
40 12 11 8 9 10
50 12 13 10 8 8
60 16 12 9 10 8
70 13 12 12 9 10
80 13 13 9 9 8
90 14 14 10 9 9
100 13 12 10 9 10
500 16 16 12 11 12
1000 18 16 12 13 12
Table 5 – R´esultats de la taille maximale d’une r´ep´etition de l’algorithme n
o
4
ex´ecut´e 10.000 fois pour chaque r´esultat
La figure 7 reprend deux colonnes du Tableau 5 : la ”3 parmi 4” et la ”3 parmi
5”. Cette figure repr´esente le rapport entre la taille maximum de r´ep´etition et la
taille du mot demand´e. Par exemple, pour la colonne 3 parmi 4 de taille 10, nous
pouvons calculer : 5/10 = 0.5.
Nous pouvons constater que le rapport d´ecroit exponentiellement et qu’il s’agit de
la tendance pour l’ensemble des r´esultats du Tableau 5.
0 100 200 300 400 500 600 700 800 900 1,000
0
0.1
0.2
0.3
0.4
0.5
Longueur du mot
Dur´ee en ns
3 parmi 4
3 parmi 5
Figure 7 – Comparaison graphique du rapport de la taille maximum de la r´ep´etition
par la taille du mot demand´ee. Pour les colonnes ”3 parmi 4” et ”3 parmi 5”
.
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 19 de 43
Algorithmes al´eatoires en combinatoire des mots
Nous pouvons constater que plus l’algorithme a des disponibilit´es, plus il est
facile pour lui de trouver un mot sans carr´e. Cependant, le but de ce travail est de
le d´emontrer rigoureusement.
4.3 Preuve
4.3.1 Hypoth`ese
Pour chaque mot de longueur n >= 1 et pour chaque position du mot, une liste
(L
1
, L
2
, L
3
, ..., L
n
) est disponible et est compos´ee de 4 symboles diff´erents ; les listes
des symboles sont potentiellement diff´erentes entre elles et pour chaque position, un
symbole sera choisi.
Revendication : Il existe un mot sans carr´e avec ces listes.
4.3.2 Preuve : comptage
Supposons qu’il n’est pas possible de trouver un mot sans carr´e avec les listes
(L
1
, L
2
, L
3
, ..., L
n
). Cela signifie donc que l’algorithme 4, d´efini pr´ec´edemment dans
le document, ne s’arrˆete pas. Nous allons donc arrˆeter artificiellement l’algorithme
en nous fixant un nombre t d’it´erations.
Les auteurs [5] r´ealisent alors 2 comptages : le premier qui d´efinit que pour 4
choix de symboles par position, le nombre de vecteurs al´eatoires est de 4
t
, o`u t est
le nombre d’it´erations avant l’arrˆet.
Pour le deuxi`eme comptage, nous allons d´etailler la fa¸con dont ils s’y sont pris.
Les auteurs du document vont commencer par modifier l’algorithme afin d’enregis-
trer le comportement complet de celui-ci :
Enregistrement du comportement de l’algorithme n
o
4
Nous allons modifier l’algorithme n
o
4 de la mani`ere suivante :
D´efinissons une nouvelle chaˆıne de caract`eres : log.
log est une chaˆıne qui va permettre de garder un historique de l’algorithme.
Explication :
A chaque fois que l’algorithme choisit un ´el´ement dans la liste de symboles pour
la position actuelle :
— On ajoute le symbole choisi `a ”mot”
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 20 de 43
Algorithmes al´eatoires en combinatoire des mots
— On ajoute 0 `a la chaine log
Lorsque une r´ep´etition est d´etect´ee :
— Nous d´efinissons k qui repr´esente la longueur de la r´ep´etition
— L’algorithme retire de word les k derniers symboles, ce qu’il faisait d´ej`a
— On ajoute k fois le symbole 1 `a log (Ligne 9 algortihme 5)
Algorithm 5: Algorithme al´eatoire en combinatoire de mot, la liste de sym-
boles est potentiellement diff´erente avec historique de comportement
Data: Int n, String[][] listByposition
Result: Retourner un mot qui ne contient pas de r´ep´etition
1 String word ; String log ;
2 while length(word) < n do
3 word ← word + randomElementOf(listByP osition[length(word) − 1]);
4 log ← log + ”0” ;
5 Int repetitionLength ← getRepetitionLength(word);
6 if repetitionLength > 0 then
7 word ← removeEndCaracters(word, repetitionLength) for
Int j = 0; j < repetitionLength; j + + do
8 log ← log + ”1”;
9 end
10 end
11 end
12 Return word ;
Nous aurons donc `a tout moment une paire (log, word). Cette paire n’est pas
finale puisque nous d´eterminons dans ce cas que l’algorithme ne s’arrˆete pas, ce
qui est notre hypoth`ese dans la preuve par contradiction que nous sommes en train
d’´elaborer. Cette d´emarche nous permet un historique complet des choix pris par
l’algorithme et donc de d´eterminer quelles sont toutes les actions pr´ec´edentes prises
par celui-ci.
Exemple d’un comportement
Faisons un test de l’algorithme 5. Arrˆetons le apr`es t = 10, c’est-`a-dire lorsqu’il
est pass´e 10 fois dans la boucle de la ligne 3. Le r´esultat alors obtenu est :
— Le mot : cbdcb
— Le log : 0001001100010
Nous avons donc la paire n´ecessaire pour ´etudier l’historique. Les num´eros com-
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 21 de 43
Algorithmes al´eatoires en combinatoire des mots
men¸cant chacune des lignes suivantes ici repr´esentent le parcours de la chaine log
en commen¸cant par la droite, et donc par la fin afin de remonter l’historique. Afin
de rester pertinent nous d´etaillerons les changements significatifs.
Les parties du log en bleu et gras sont ceux dont nous sommes en train de
discuter. Les parties rouges et italiques sont celles pr´ec´edemment trait´ees dans l’ex-
plication.
1. Le symbole du log est 0, nous pouvons en d´eduire que le dernier symbole
plac´e est bien le b. Nous l’enlevons ce qui donne cbdc
0001001100010
2. Les deux derniers symboles de log sont 01, il y a donc eu une r´ep´etition de
taille 1 lorsque l’algorithme a ajout´e le symbole : le mot ´etait donc cbdcc et
nous retirons le dernier symbole ce qui donne cbdc
0001001100010
3. Dans le dernier symbole de la chaine de caract`ere log, c’est un 0 qui est
affich´e, donc pas de r´ep´etition. Valeur du mot : cbd
0001001100010
4. Mˆeme ´etat que le point pr´ec´edent. Valeur du mot : cb
0001001100010
5. Pour la suite, nous rencontrons 011 ce qui signifique qu’en pla¸cant un sym-
bole, cela a provoqu´e un carr´e de longueur 2. Nous pouvons donc d´eterminer
qu’en partant de cb, le dernier symbole ajout´e ´etait b puisque pour avoir une
r´ep´etition de longueur 2, en partant de cb il fallait le mˆeme bloc : cb. Nous
pouvons en d´eduire que la partie 0011 a choisi les symboles cb
0001001100010
6. Nous en sommes maintenant `a la partie 0001, comme il s’agˆıt d’un 0 suivi
d’un 1 nous savons que le dernier caract`ere plac´e a provoqu´e un carr´e de taille
1. Nous pouvons en d´eduire, en partant de cb qu’il avait ajout´e le symbole b
0001001100010
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 22 de 43
Algorithmes al´eatoires en combinatoire des mots
7. Pour terminer, les deux derniers symboles de log `a v´erifier sont deux 0. Nous
savons donc que c’est cb qui a ´et´e produit par ce comportement
Ainsi, grˆace au log produit par l’algorithme, nous pouvons connaˆıtre le comporte-
ment complet de celui-ci.
Afin d’ˆetre plus visuel, le Tableau 6 nous montre le d´eroulement de l’algorithme
avec le mˆeme exemple d´ecrit ci-dessus. La premi`ere colonne repr´esente les it´erations
de l’algorithme. En effet, par exemple pour l’it´eration 3, nous ajoutons un symbole
b qui provoque une r´ep´etition de taille 1, l’algorithme va donc retirer le dernier
symbole ajout´e.
It´eration Mot Log
1 c 0
2 cb 00
3 cbb 0001
4 cbc 00010
5 cbcb 00010011
6 cbd 000100110
7 cbdc 0001001100
8 cbdcc 000100110001
9 cbdcb 0001001100010
Table 6 – R´esultats de l’exp´erience de l’algorithme n
o
5 avec le comportement pour
chaque it´eration
La s´equence log est un mot de Dyck partiel
Comme vu pr´ec´edemment dans le point 3.2, les mots de Dyck ont des propri´et´es
sp´ecifiques. Le log sorti `a la fin de l’exemple pr´ec´edent est 0001001100010. Ce dernier
a la propri´et´e que si l’on regarde tous les pr´efixes de la chaˆıne, le nombre de 0 sera
toujours ≥ que le nombre de 1. Cependant, pour que la propri´et´e du mot de Dyck
soit vraie, il faut que le nombre de 0 et de 1 soient ´egaux. Ajoutons les symboles
1 manquants afin d’avoir un mot de Dyck valide.
´
Etant donn´e que nous avons 9
caract`eres 0, il manque 5 symboles 1. Voici le log corrig´e pour ressembler `a un
mot de Dyck : 000100110001011111. Il est int´eressant de remarquer que le nombre
manquant de 1 pour compl´eter le mot de Dyck repr´esente la longueur du mot une
fois l’algorithme arrˆet´e. Autrement dit, si nous devons ajouter 5 1, c’est que le mot
est de longueur 5 `a l’emplacement o`u nous avons arrˆet´e l’algorithme.
Nous savons que, dans un mot de Dyck, le nombre de dispositions des symboles
peut ˆetre compt´e grˆace aux nombres de Catalan. Dans le tableau 1, nous pouvons
voir que pour T
9
, il existe 4862 fa¸cons diff´erentes de disposer les symboles tout en
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 23 de 43
Algorithmes al´eatoires en combinatoire des mots
conservant un mot de Dyck valide.
4.3.3 D´eveloppement de la preuve
Le nombre de possibilit´es `a l’it´eration t sera pour un premier comptage de 4
t
.
Concernant le deuxi`eme comptage, o`u nous avons d´efini que l’algorithme ne s’arrˆetait
pas, nous aurons une paire (D,S) donc D ´etant le log qui est un mot de Dyck partiel
et S le mot courant qui est en construction. Ainsi, nous pouvons compter le nombre
de combinaisons diff´erentes de D. En regardant le nombre de 0 dans ce dernier, nous
savons `a quelle it´eration nous nous trouvons : la t
`eme
. Par cons´equent, au moyen des
nombres de Catalan, nous pouvons compter en fonction de C
t
comme d´efini dans la
section 3.2 ; C
t
est le t
`eme
nombre de Catalan.
Nous ne connaissons pas la longueur du mot qui se construit, cependant nous
connaissons le nombre d’it´erations et le nombre de 1 `a ajouter au mot de Dyck partiel
pour qu’il soit complet ; le nombre de 1 manquant est exactement la longueur du
mot en cr´eation qui est au maximum de longueur n − 1.
Nous allons alors multiplier C
t
par la longueur maximum du mot que l’on veut
produire : n − 1 afin de couvrir le maximum de possibilit´es ; si le maximum ´etait
n, l’algorithme se serait arrˆet´e. Ainsi nous pouvons en d´eduire que le nombre de
possibilit´es pour D est au plus : C
t
∗(n−1), que nous pouvons borner sup´erieurement
par
4
t
√
πt
3/2
∗(n−1) (voir section 3.1, complexit´e). Nous allons aussi ajouter le facteur
5
n
au produit. En effet, nous devons aussi compter le nombre de possibilit´es du
mot en construction. Vu qu’il y a 4 symboles par position auxquels nous ajoutons le
symbole vide, puisque les positions qui ne sont pas encore trait´ees sont vides, cela
donne le nombre 5
n
.
Nous pouvons donc prouver par ce comptage, si on prend un t assez grand, que
4
t
√
πt
3/2
∗ (n − 1) ∗ 5
n
< 4
t
et que donc l’algorithme aurait du trouver une solution
pour une certaine s´equence de choix al´eatoires, c’est donc une contradiction.
La diff´erence de la preuve d´emontr´ee ici par rapport au travail d’Axel Thue, qui
utilisait un alphabet fixe de 3 symboles. C’est que dans son travail, les symboles
disponibles seront toujours les mˆemes et suivront la mˆeme s´equence de substitution
d´ecrite dans le point 2.1. Ici, nous utilisons 4 symboles par position, mais les symboles
disponibles par position peuvent ˆetre diff´erents.
Contrairement au tavail d’Axel Thue qui utilisait un alphabet fixe de 3 symboles
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 24 de 43
Algorithmes al´eatoires en combinatoire des mots
et un s´equence de substitution toujours identique (voir point 2.1), nous utilisons
dans cette preuve 4 symboles par position qui peuvent ˆetre diff´erents entre eux. Cette
preuve est plus g´en´eraliste, puisqu’elle permet d’obtenir des mots qui ne suivent pas
tous le mˆeme mod`ele.
4.4 Un symbole ajout´e en fin de mot peut-il terminer 2
facteurs carr´es de longueurs diff´erentes ?
Dans ce point, nous allons nous pencher sur une question que nous pourrions nous
poser : est-il possible que l’ajout d’un symbole dans l’algorithme puisse provoquer
deux facteurs carr´es de tailles diff´erentes ?
Nous allons tˆacher de d´emontrer dans cette section que cela n’est pas possible.
Hypoth`ese
L’ajout d’un symbole `a la fin d’un mot sans carr´e ne peut provoquer plusieurs
carr´es de tailles diff´erentes.
Preuve par contradiction
Dans un mot, nous d´etectons donc 2 facteurs carr´es de taille diff´erente apr`es
l’ajout d’un symbole en fin de mot. Le premier bloc du carr´e le plus grand est A, et
le deuxi`eme bloc de ce carr´e est B ; le deuxi`eme facteur carr´e de taille plus petite
est d´efini par les deux blocs A
0
et B
0
.
Prenons le mot commen¸cant par S
1
et se terminant par S
n
Figure 8. Le dernier
symbole S
n
termine un carr´e qui est compos´e des symboles S
1
S
2
S
3
S
...
. C’est-`a-
dire que le facteur B r´ep`ete la facteur A.
Concernant le deuxi`eme carr´e de taille plus petite, nous pourrions donc ´emettre
l’hypoth`ese qu’il se trouve compl`etement dans la partie B, repr´esent´ee ici par A
0
et B
0
dans la Figure 9. Mais, si c’´etait le cas, elle aurait aussi ´et´e pr´esente dans le
facteur A. Cette disposition est donc impossible puisque le carr´e aurait ´et´e d´etect´e
plus tˆot.
L’autre hypoth`ese, c’est que le deuxi`eme carr´e soit de longueur > |B|/2 et donc
commencerait avant le d´ebut du facteur B , c’est-`a-dire sur le facteur A Figure 10.
Un facteur mot qui termine le facteur A tout en ´etant identique `a celui de la fin de
la s´equence B et aussi qu’il soit le d´ebut d’A
0
(puisque A
0
est `a cheval entre A et B)
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 25 de 43
Algorithmes al´eatoires en combinatoire des mots
et donc aussi le d´ebut de B
0
(vu que B
0
serait une r´ep´etition de A
0
) est impossible `a
construire sans carr´e. En effet, le d´ebut de A
0
(S
3
S
...
) aura le mˆeme facteur compos´e
de symboles que la fin de A
0
(S
...
S
n−2
) et le d´ebut de B
0
, ainsi, il existera donc une
r´ep´etition entre ces deux derniers ´el´ements.
S
1
S
2
S
3
S
...
S
...
S
n−2
S
n−1
S
n
A B
Figure 8 – Une s´equence de symboles de S
1
`a S
n
avec une r´ep´etition de la s´equence
A par la s´equence B
S
1
S
2
S
3
S
...
S
...
S
n−2
S
n−1
S
n
A B
A’ B’
Figure 9 – Une s´equence de symboles de S
1
`a S
n
avec deux r´ep´etitions de taille
diff´erente. R´ep´etition A
0
et B
0
est plus petite que la s´equence B
S
1
S
2
S
3
S
...
S
...
S
n−2
S
n−1
S
n
A B
A’ B’
Figure 10 – Une s´equence de symboles de S
1
`a S
n
avec deux r´ep´etitions de taille
diff´erente. R´ep´etition A
0
et B
0
sont > que la longueur de A/2
Conclusion
Nous pouvons donc en conclure qu’il n’est pas possible que l’ajout d’un seul
symbole puisse provoquer deux carr´es de taille diff´erente sans que cela ne soit d´etect´e
pr´ec´edemment.
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 26 de 43
Algorithmes al´eatoires en combinatoire des mots
5 Mot sans carr´e `a progression arithm´etique
5.1 Introduction
Dans la section pr´ec´edente [4] ”Une nouvelle approche des mots sans carr´e” ,
nous avons d´emontr´e qu’il ´etait possible d’obtenir un mot sans carr´e avec des listes
potentiellement diff´erentes de longueur 4 pour chaque position dans le mot. Dans
cette section nous allons expliquer une version avec une contrainte plus forte : la
cr´eation d’un mot sans carr´e `a progression arithm´etique par JarosLaw Grytczuk,
Jakub Kozik, And Marcin Witkowski [11].
Nous avons d´ej`a d´efini ce qu’est un mot sans carr´e dans la section 2, dans cette
article, les auteurs d´emontrent qu’il est possible d’obtenir un mot sans carr´e par
saut de 1 `a k.
Dans le travail de Thue, le saut est de 1 puisque si une r´ep´etition survient, les
deux blocs sont adjacents. Lors d’un saut b tel que b > 1, quand nous ajoutons un
symbole, nous allons v´erifier qu’une r´ep´etition ne survient pas pour ce saut de b.
Autrement dit, pour le mot
s
1
s
2
s
3
, s
4
..., s
n−7
s
n−6
s
n−5
s
n−4
s
n−3
s
n−2
s
n−1
s
n
nous allons contrˆoler qu’il n’y a pas de r´ep´etition en partant, dans cet exemple, de
n’importe quelle position moins des sauts de b et plus des sauts de b .
De plus comme dit pr´ec´edemment, nous allons aussi prouver qu’il existe un mot
sans carr´e pour un saut allant de 1 `a k. C’est-`a-dire que b va avoir comme valeur
de 1 `a k dans le mˆeme algorithme. Autrement dit, nous allons tester b avec ces
valeurs : 1, 2, . . . , k − 1, k, . Cependant, la taille de la liste pour chaque position
sera plus grande que dans la preuve pr´ec´edente,qui ´etait de 4 symboles, puisque dans
cette preuve, la taille ´evoluera en fonction de k, et chaque liste par position sera de
2k + 10
√
k. Ainsi dans le tableau n
o
7 nous pouvons observer le nombre de symboles
disponibles pour chaque position du mot en construction.
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 27 de 43
Algorithmes al´eatoires en combinatoire des mots
k Taille de la liste
1 12
2 19
3 24
4 28
5 33
6 37
7 41
8 45
9 48
10 52
11 56
12 59
Table 7 – Pour un k donn´e, voici la correspondance du nombre de symboles
n´ecessaires pour ´eviter une r´ep´etition dans un mot sans carr´e `a progression
arithm´etique
5.2 Algorithme cr´eation du mot sans carr´e `a progression
arithm´etique
5.2.1 Pr´esentation des algorithmes
L’algorithme n
o
6 permet de construire un mot sans carr´e `a progression arithm´etique.
Nous allons ici expliquer les diff´erentes ´etapes afin de permettre de construire un
mot.
Tout d’abord, l’algorithme re¸coit en entr´ee 3 variables : un entier n repr´esentant
la longueur du mot d´esir´ee, listByP osition qui est un tableau compos´e de listes de
symboles par position du mot, comme l’algorithme n
o
5, la liste de symboles par
position et enfin le saut k d´efini dans l’introduction.
Nous allons d´efinir une variable word qui repr´esente le mot en construction
et une variable writingHeadP osition qui d´efinit un entier repr´esentant la posi-
tion de la tˆete d’´ecriture. En effet, la diff´erence ici dans l’algorithme `a progression
arithm´etique, c’est que la tˆete d’´ecriture, c’est-`a-dire l’endroit ou l’algorithme tente
de placer un symbole, ne se trouve pas toujours en fin de mot. Effectivement nous
serons amen´es `a effacer, comme dans l’algorithme n
o
6 le bloc du facteur carr´e, mais
ceci peut se produire n’importe o`u dans le mot puisqu’il y aura des sauts de k. Par
exemple si le mot en construction est : ADBECFAGBH , que le k = 3 et que
l’algorithme choisit le symbole C `a placer, il existe alors un facteur carr´e pour un
saut de 2 correspondant `a ABC.
La fonction haveEmptyP osition, la condition d’arrˆet de la boucle, permet de
savoir s’il existe dans le mot un emplacement vide. S’il n’y a plus d’emplacement
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 28 de 43
Algorithmes al´eatoires en combinatoire des mots
vide, c’est que le mot est construit et que l’algorithme a termin´e.
Ensuite, nous aurons la variable currentList qui repr´esente la liste des symboles
disponibles `a la position de la tˆete de lecture writingHeadP osition. Pour fournir
cette liste, nous utilisons la fonction removeSquareOfOne qui retire de la liste
de d´epart tout symbole qui pourrait provoquer un carr´e de taille 1. En reprenant
l’exemple pr´ec´edent, avec un k = 3, lorsque l’algorithme doit faire un choix sur
la derni`ere position comme ici : pour ADBECFAGBH , il enl`evera de la liste
`a disposition, s’il sont pr´esents, les symboles G, B et H qui repr´esenteraient s’ils
´etaient choisis un carr´e de taille 1 pour un saut respectivement de 3, 2 et 1.
Une fois la liste ´elagu´ee pour ´eviter les carr´es de taille 1, l’algorithme choisira un
symbole al´eatoirement avec la fonction randomElementOf ligne 5.
Ensuite, l’algorithme fournira le mot en construction, la position de la tˆete de
lecture et le saut maximum `a une fonction findSquareW ithJump. Cette derni`ere
se chargera de chercher le plus long carr´e parmi les sauts de 1 `a k, et entre ceux-ci,
celui le plus `a droite dans le mot. Lorsqu’un carr´e avec les crit`eres cit´es est trouv´e,
l’algorithme supprimera tous les symboles du bloc de r´ep´etition o`u le dernier symbole
a ´et´e ajout´e.
Pour terminer la boucle principale, la tˆete d’´ecriture se placera, grˆace `a la
m´ethode getF irstEmptyElementInW ord au premier emplacement vide avec l’in-
dex, c’est-`a-dire la position, la plus faible. Par exemple pour A B CF, la tˆete
d’´ecriture se positionnera apr`es le symbole A.
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 29 de 43
Algorithmes al´eatoires en combinatoire des mots
A la fin de l’algorithme, ligne 12 l’algorithme retourne le mot construit.
Algorithm 6: Algorithme al´eatoire en combinatoire de mot `a progression
arithm´etique, la liste de symboles est potentiellement diff´erente
Data: Int n,String[][] listByposition, Int k
Result: Retourner un mot qui ne contient pas de r´ep´etition `a progression
arithm´etique
1 String word ;
2 int writingHeadPosition = 0;
3 while haveEmptyPosition(word) do
4 String[] currentList =
removeSquareOfOne(listByP osition[writingHeadPosition]);
5 word[writingHeadPosition] = randomElementOf(currentList);
6 word = f indSquareW ithJump(word, writingHeadP osition, k);
7 currentPositionOfhead = getF irstEmptyElementInW ord(word);
8 end
9 Return word ;
Dans l’algorithme n
o
7, nous utilisons le sous algorithme findSquareW ithJump
que nous allons un peu d´etailler dans l’algorithme n
o
7. Nous fournirons donc `a cet
algorithme un mot et un nombre maximum de sauts. Dans celui-ci, nous d´efinirons
une variable longestRepetition qui stockera le carr´e le plus long. Ensuite, nous en-
registrerons le saut courant que nous testerons grˆace `a la variable currentJump,
qui sera l’invariant de la boucle principale. A la ligne 4, nous allons cr´eer un mot
en fonction du saut. Pour le mot S
1
S
2
S
3
S
4
S
5
. . . si nous prenons un saut de
2, il construira le mot S
1
S
3
S
5
. . . . Nous allons soumettre ce dernier `a la fonction
findLongestRepetition qui permettra de r´ecup´erer la plus longue des r´ep´etitions
se trouvant le plus `a droite dans le mot cr´e´e et comparer sa longueur `a celle de
longestSquare afin de savoir s’il faut l’enregistrer dans le cas o`u il serait plus long
(ligne).
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 30 de 43
Algorithmes al´eatoires en combinatoire des mots
Algorithm 7: Algorithme al´eatoire en combinatoire de mot `a progression
arithm´etique, la liste de symboles est potentiellement diff´erente
Data: String[] word, int jump
Result: Retourne la plus longue r´ep´etition se trouvant `a droite parmi k mots
construits
1 String longestSquare ;
2 int currentJump = k;
3 while currentJump > 0 do
4 String[] currentWord = createW ordW ithJump(word, currentJump);
5 String[] repetition = findLongestRepetition(currentW ord);
6 if length(longestSquare) > length(longestSquare) then
7 word ← removeEndCaracters(word, repetitionLength)
8 end
9 currentJump = currentJump ← currentJump − 1;
10 end
11 Return word ;
L’algorithme n
o
8 dans les annexes d´etecte une r´ep´etition n’importe o`u dans
une chaine de mots, l’id´ee ´etant de lui fournir une s´equence de mots d´ej`a construite
et de v´erifier s’il existe une r´ep´etition dans celle-ci. S’il trouve une r´ep´etition, il la
retourne, sinon, il retourne une chaˆıne vide.
5.2.2 Exp´erimentation sur les algorithmes
Dans cette sous section nous allons expliquer les exp´eriences r´ealis´ees sur l’algo-
rithme n
o
6.
Nous avons demand´e `a l’algorithme de cr´eer un mot de 200 symboles sans carr´e
`a progression arithm´etique avec des sauts allant de 2 `a 12 et ceci 10000 fois pour
chaque test. Le tableau 8 nous montre le r´esultat de l’exp´erience et les en-tˆetes
qui ont la forme i / j signifiant que nous avons pris, pour chaque position du mot
(c’est-`a-dire 200 ici) i symboles parmi j symboles disponibles. Lorsqu’une cellule
de donn´ees est remplie par un X, c’est que l’algorithme n’a, au moins une fois,
pas trouv´e de mot sans carr´e `a progression arithm´etique en fonction des symboles
disponibles. Pour ´eviter de surcharger le tableau, nous avons raccourci la deuxi`eme
colonnes dont voici l’explication :
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 31 de 43
Algorithmes al´eatoires en combinatoire des mots
— AI : ”Average it´eration”, le nombre d’it´erations moyennes ;
— MI : ”Max It´eration”, le nombre d’it´erations maximum parmi les 10.000 essais
— ASL : ”Average Square length”, la longueur moyenne des carr´es rencontr´es
— MSL : ”Maximum Square Length”, le carr´e le plus long parmi les 10.000 essais
Comme expliqu´e pr´ec´edemment, le fait d’avoir un X dans la cellule d´etermine
qu’au moins, pour un des 10.000 tests dans cette cellule, l’algorithme n’a pas trouv´e
de mot sans carr´e. Les deux raisons sont :
1. Qu’apr`es 10.000 it´erations lors de la cr´eation d’un mot, l’algorithme n’a pas
trouv´e de solution
2. Que le nombre de symboles disponibles par position est ´egal `a z´ero (la taille
de currentList de la ligne 4 )
Nous pouvons constater que lorsque l’algorithme ne peut trouver une solution
pour un saut k, il ne le peut pas non plus pour un saut > k.
3 / 3 5 / 5 4 / 6 6 / 7 8 / 8 4 / 20 20 / 20
2k + k
√
10 /
2k + k
√
10
2 AI X 256,05 230,08 218,07 211,08 200,95 201 201,19
MI X 291 265 242 224 206 206 206
ASL X 4,11 3,33 3,18 2,86 0,71 1 0,93
MSL X 9 6 5 5 3 3 3
3 AI X X X 242,48 225,88 203,38 202,43 201,46
MI X X X 289 250 224 208 208
ASL X X X 3,13 2,98 1,52 1,39 1,09
MSL X X X 7 5 3 4 3
6 AI X X X X X X 204,07 200,91
MI X X X X X X 210 208
ASL X X X X X X 2,01 0,75
MSL X X X X X X 4 3
12 AI X X X X X X 211,16 200,88
MI X X X X X X 224 205
ASL X X X X X X 2,28 0,78
MSL X X X X X X 4 3
Table 8 – Exp´erience de l’algorithme n
o
6. AI : Average it´eration ; MI : Max
It´eration ; ASL : Average Square length ; MSL : Maximum Square Length.
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 32 de 43
Algorithmes al´eatoires en combinatoire des mots
5.3 Preuve
5.3.1 Hypoth`ese
Pour chaque mot de longueur n >= 1 et pour chaque position du mot, une
liste (L
1
, L
2
, L
3
, ..., L
r
) est disponible et est compos´ee de (2k + 10
√
k)
n
symboles
diff´erents ; les listes des symboles sont potentiellement diff´erentes entre elles et pour
chaque position, un symbole sera choisi. De plus pour un entier k, repr´esentant le
saut maximum `a v´erifier, la revendication est la suivante : Il existe un mot sans
carr´e `a progression arithm´etique.
5.3.2 Preuve par contradiction
Comptage
Nous nous appuierons sur certaines explications de la preuve pr´ec´edente lorsque
nous d´efinirons le comptage. Comme dans la preuve pr´ec´edente, s’il ne trouve pas
de solution, c’est que l’algorithme ne s’arrˆete pas. Nous allons donc arrˆeter celui-ci
par nous-mˆeme `a un moment et r´ealiser le nombre de possibilit´es maximum `a la
t
`eme
it´eration. Nous allons r´ealiser une preuve par contradiction en effectuant un
comptage de toutes les possibilit´es `a cette it´eration.
Afin de compter toutes les possibilit´es, nous ferons appel aux param`etres qui
repr´esentent toutes les diff´erences qui peuvent survenir :
D’abord, comme dans la preuve pr´ec´edente Un nouvelle approche des mots sans
carr´e [4], nous aurons un mot de Dyck partiel, repr´esent´e par la lettre R. Il peut ˆetre
compl´et´e par un nombre de 1 repr´esentant la taille du mot qui est construit comme
nous l’avons ´ecrit dans la preuve pr´ec´edente, le mot de Dyck ´evoluant comme la
suite de Catalan. A l’it´eration t, la valeur est de C
t
.
Ensuite, ´etant donn´e que l’algorithme teste tous les sauts de 1 `a k, lorsqu’une
r´ep´etition apparait, nous allons enregistrer dans une chaine D la valeur du saut test´e
lors de la d´etection de la r´ep´etition. Comme l’algorithme proscrit toute r´ep´etition de
longueur 1, algorithme n
o
6 ligne 4, et donc de minimum 2, le nombre de possibilit´es
est de k
t
2
.
Nous enregistrerons aussi une chaine O de longueur ´egale `a D de valeur 1 ou
−1. −1 se produit dans le premier bloc tandis que 1 signifie que la r´ep´etition s’est
produite dans le deuxi`eme bloc. Le nombre de possibilit´es sont 2
t
2
; l’exposant
t
2
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 33 de 43
Algorithmes al´eatoires en combinatoire des mots
´etant pour les mˆeme raisons que D.
´
Egalement, nous aurons une chaine P de longueur ´egale `a D qui d´etermine la
position du dernier symbole ajout´e dans le bloc. Pour ex´ecuter un comptage de ce log,
nous devons compter le nombre de possibilit´es qu’il peut y avoir. P
j
est la position du
symbole courant dans le bloc enlev´e au moment de la r´ep´etition correspondante, tel
que chaque P
j
est plus petit ou ´egal au nombre de symboles effac´es `a la r´ep´etition
correspondante. Appelons cette valeur V
q
, d`es lors nous savons que le nombre de
possibilit´es du vecteur P = V
1
· V
2
· V
3
· ··· · V
q
.
De plus, nous savons aussi que V
1
+ V
2
+ V
3
+ ··· + V
q
≤ t puisque pour chaque
symbole retir´e par l’algorithme, chacun a du ˆetre ´ecrit pr´ec´edemment par ce dernier.
Nous allons augmenter V
1
, nomm´e V
0
1
, de sorte `a avoir une ´egalit´e dans l’in´egalit´e,
ainsi nous avons : V
0
1
+ V
2
+ V
3
+ ···+ V
q
= t. Suite `a ceci, nous pouvons d´eterminer
que V
1
· V
2
· V
3
· ··· · V
q
≤ V
0
1
· V
2
· V
3
· ··· · V
q
. Nous savons que lorsque le membre
de droite de la derni`ere expression est maximis´e, la valeur pour chaque membre est
´egale comme ceci : V
0
1
= V
2
= V
3
= ··· = V
q
=
t
q
. Dans ce cas, le membre de droite
peut ˆetre r´e´ecrit comme ceci :
V
1
· V
2
· V
3
· ··· · V
q
≤
t
q
·
t
q
·
t
q
· ··· ·
t
q
et donc
V
1
· V
2
· V
3
· ··· · V
q
≤
t
q
!
q
Pour d´eterminer le maximum de (
t
q
)
q
, nous allons nous r´ef´erer au document dans
lequel ils vont chercher `a maximiser cette derni`ere expression. Pour ce faire, ils vont
calculer sa d´eriv´ee :
t
q
!
t
t
q
=
t
q
!
t
t
q
t
t
q
2
−
t · log
t
q
t
q
2
Ils vont r´esoudre l’´equation o`u la d´eriv´ee est ´egale `a 0 et obtenir la valeur :
t
q
= e, ce
qui correspond `a un maximum de l’´equation de d´epart qui est : ≈ 1.44467
n
< 1.5
n
.
Pour terminer, nous allons nous int´eresser `a la longueur du mot en construction :
S. Sa valeur est le nombre de symboles possibles par position exposant la longueur
du mot : (2k + 10
√
k)
n
. n ´etant la longueur du mot en construction.
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 34 de 43
Algorithmes al´eatoires en combinatoire des mots
Exemples de comportement
Ici, nous allons d´etailler une partie du comportement dans la cr´eation du mot,
ensuite, nous allons prendre un mot fini et lire ce qu’il s’est pass´e.
Partie de comportement
Apr`es avoir lanc´e l’algorithme n
o
6 pour un mot de 50 symboles, nous arrˆetons
l’algorithme `a un moment. Les param`etres que nous lui avons donn´es sont :
— Saut : 2
— Nombre de symboles disponibles en tout : 5
— Nombre de symboles disponibles par position : 5
— Longueur du mot : 200
Nous observons alors ceci :
— Le mot : daed
— R = 0000001110
— D = 1
— O = 1
— P = 3
Nous pouvons observer qu’il y a eu un carr´e de taille 3 grˆace au log R puisque apr`es
le 6
`eme
0 nous pouvons observer 3 nombres 1. L’algorithme a donc effac´e 3 symboles.
Si nous faisons le mˆeme exercice que dans la section 4.3.2 :
1. Le dernier symbole du log R est 0, nous savons donc que l’algorithme a
termin´e par ajouter un symbole. Etant donn´e que le mot est maintenant `a
daed, nous savons que le dernier symbole plac´e est d, nous allons alors le
retirer ce qui donne : dae.
0000001110
2. A cette it´eration, nous savons que l’algorithme a ajout´e un caract`ere qui a
provoqu´e un carr´e de taille 3. Cependant, nous ne pouvons pas savoir de quel
saut il s’agit, c’est pourquoi nous aurons besoin du log D qui nous informera
sur le saut de cette r´ep´etition : grˆace `a cela, nous savons que le saut test´e `a
ce moment est de 1, que le symbole ajout´e ´etait dans le deuxi`eme bloc cfr.
log O et que la position du dernier symbole ajout´e est la position 3. Nous
pouvons en d´eduire que le dernier symbole ajout´e ´etait e ce qui a donn´e le
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 35 de 43
Algorithmes al´eatoires en combinatoire des mots
mot daedae. Nous pouvons donc le retirer, ce qui donne daeda.
0000001110
3. Les 5 prochaines it´erations sont tous les symboles ajout´es pour donner daeda.
Le tableau 9 montre le comportement de l’algorithme, c’est-`a-dire les logs en
fonction de l’it´eration. repr´esente un log vide.
It´e Mot R D O P
1 d 0
2 da 00
3 dae 000
4 daed 0000
5 daeda 00000
6 daedae 000000111 1 1 3
7 daed 0001001110 1 1 3
Table 9 – R´esultats de l’exp´erience de l’algorithme n
o
6 avec le comportement pour
chaque it´eration
Donn´ees d’un mot
Dans cette partie, nous allons arrˆeter l’algorithme apr`es 55 it´erations et lire
quelques ´el´ements qui se sont pass´es durant la construction du mot courant. Les
donn´ees fournies `a l’algorithme sont les mˆemes que celles fournies dans l’exemple
pr´ec´edent, c’est-`a-dire :
— Saut : 2
— Nombre de symboles disponibles en tout : 5
— Nombre de symboles disponibles par position : 5
— Longueur du mot : 200
Ce qui a donn´e les logs suivants :
— Le mot : dcaedcbdaecbacebcedcadcbdecbadeacbedaecabedbcabcea
— R = 000000011000000000000000000011100000000000000000000000000000
— D = 2 1
— O = 1 1
— P = 2 3
Maintenant que nous avons arrˆet´e l’algorithme, nous savons que grˆace `a tout ces
logs, un mot avec ces conditions a ´et´e trouv´e. Nous savons ´egalement qu’il y a eu
deux carr´es, un d’une taille de 2 et l’autre d’une taille de 3. En effet, le premier est
apparu lors d’un test sur un saut de 2 tandis que le deuxi`eme est survenu pendant
un saut de 1. Les deux fois, le symbole qui a provoqu´e le carr´e ´etait dans le deuxi`eme
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 36 de 43
Algorithmes al´eatoires en combinatoire des mots
bloc, le log O est deux fois `a 1 : la premi`ere fois, le symbole avait la 2
`eme
position
et la deuxi`eme fois, la 3
`eme
position. Grˆace `a ces logs, nous pouvons reproduire le
comportement total de la construction du mot courant.
5.3.3 Conclusion
Nous allons ´enum´erer ici les diff´erents ´el´ements destin´es `a comptabiliser le nombre
de possibilit´es lorsque nous arrˆetons l’algorithme apr`es t it´eration. EN d’autres
termes, il n’a pas trouv´e de mot sans carr´e `a progression arithm´etique.
Nous obtenons donc la multiplication totale repr´esentant le comptage complet
suivant :
(2k + 10
√
k)
n
· C
t
· k
t
2
· 2
t
2
· 1.5
t
En le comparant au nombre total d’it´erations comme nous l’avons r´ealis´e dans
la preuve du premier article, le nombre de possibilit´es de symboles diff´erents par
position est de (2k + 10
√
k)
t
que nous pouvons simplifier par (10
√
k)
t
´etant donn´e
que la ligne 3 de l’algorithme ne permet pas l’ajout d’un caract`ere s’il se trouve en
position i − k et i + k et donc 2k.
Tout comme dans le premier article, nous allons remplacer dans la formule la
valeur du t
`eme
nombre de Catalan par sa valeur asymptotique : C
t
≤
4
t
√
πt
3/2
qui est
valable pour toute valeur de t. Ainsi, nous pourrons ´ecrire la comparaison suivante
lorsque t est assez grand pour le membre de gauche :
(2k + 10
√
k)
n
·
4
t
√
πt
3/2
· k
t
2
· 2
t
2
· 1.5
t
< (10
√
k)
t
Pour un t assez grand, l’algorithme aurait dˆu trouver un mot sans carr´e `a pro-
gression arithm´etique, ce qui est une contradiction.
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 37 de 43
Algorithmes al´eatoires en combinatoire des mots
6 Conclusion
Ce m´emoire avait pour but d’´etudier les algorithmes al´eatoires qui permettent
la cr´eation de mots sans facteur carr´e.
Nous avons vu les diff´erents moyens mis en œuvre afin de prouver la possibilit´e
de cr´eer un mot sans facteur carr´e avec des listes par position pour chaque empla-
cement du mot, qui sont potentiellement diff´erentes entre elles. Ainsi pour un mot
en construction, lorsque nous ajoutons le symbole en fin de s´equence, il est possible
d’obtenir un mot sans carr´e avec un alphabet de 4 symboles diff´erents. Axel Thue,
pionnier dans le domaine, avait d´ej`a mis en place une m´ethode par r´ecurrence afin de
cr´eer un mot sans carr´e `a l’aide de 3 symboles. Cependant, cette m´ethode b´en´eficiait
de moins de libert´e puisque les mots ´evoluent de la mˆeme fa¸con. En effet, la s´equence
´etait toujours la mˆeme ce qui n’est pas le cas dans la preuve ´etudi´ee dans ce travail.
Nous avons ´egalement prouv´e qu’un symbole ajout´e en fin de chaˆıne ne pouvait pas
provoquer deux carr´es de taille diff´erente.
Ensuite, nous nous sommes int´eress´es aux mots sans carr´e `a progression arithm´etique
qui permettent de cr´eer des mots sans carr´e avec un saut k entre les symboles. C’est-
`a-dire que non seulement aucun carr´e n’existera entre les symboles adjacents, mais
en plus il n’en existera pas non plus entre des symboles qui sont ´eloign´es entre eux
de k symboles. Pour cela, les listes par position doivent ´evoluer en mˆeme temps que
k.
De mani`ere empirique, et grˆace aux impl´ementations des algorithmes, nous pou-
vons voir qu’il est ´egalement possible de cr´eer un mot sans carr´e avec moins de
symboles disponibles. Cette m´ethode est contraignante mais se base sur des conjec-
tures qui ne peuvent d`es lors pas encore ˆetre prouv´ees math´ematiquement.
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 38 de 43
Algorithmes al´eatoires en combinatoire des mots
R´ef´erences
[1] Wikipedia Community. Mot (math´ematiques). https://fr.wikipedia.org/
wiki/Mot_(math%C3%A9matiques).
[2] Wikipedia Community. Axel thue. https://fr.wikipedia.org/wiki/Axel_
Thue.
[3] J. Berstel. Axel thue’s papers on repetitions in words :a translation, 1994.
[4] Wikipedia Community. Square-free word. https://fr.wikipedia.org/wiki/
Mot_sans_facteur_carr%C3%A9.
[5] Jaroslaw Grytczuk, Jakub Kozik, and Piotr Micek. New approach to nonrepe-
titive sequences. Random Struct. Algorithms, 42(2) :214–225, 2013.
[6] Wikipedia Community. Eug`ene charles catalan. https://en.wikipedia.org/
wiki/Eug%C3%A8ne_Charles_Catalan.
[7] Wikipedia Community. Les nombres de catalan. https://en.wikipedia.org/
wiki/Catalan_number.
[8] Paul Gaborit. How to draw a catalan number diagram
on tikz. https://tex.stackexchange.com/questions/63540/
how-to-draw-a-catalan-number-diagram-on-tikz.
[9] MIT Mathematics. Parentheses, catalan numbers and ruin. http://www-math.
mit.edu/
˜
djk/18.310/18.310F04/parentheses.pdf.
[10] Wikipedia Community. Walther von dyck. https://en.wikipedia.org/wiki/
Walther_von_Dyck.
[11] J. Grytczuk, J. Kozik, and M. Witkowski. Nonrepetitive sequences on arithme-
tic progressions. ArXiv e-prints, February 2011.
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 39 de 43
Algorithmes al´eatoires en combinatoire des mots
Algorithme
Algorithm 8: Retourner un facteur carr´e trouv´ee dans un mot.
Data: une chaine de caract`ere
Result: Retourner une chaˆıne
1 Int TailleDeRepetition;
2 Int RepetitionMaximum;
3 Int CaractereCourant ← 1;
4 String ChaineBaseDeTest;
5 String ChaineATester;
6 Int i;
7 while CaractereCourant != NIL do
8 T ailleDeRepetition ← 1;
9 RepetitionMaximum ← ArrondirEnBas(CaractereCourant/2);
10 while T ailleDeRepetition ≤ RepetitionMaximum do
11 ChaineBaseDeT est ← ””;
12 ChaineAT ester ← ””;
13 i ← T ailleDeRepetition;
14 while i > 0 do
15 ChaineBaseDeT est+ = Chaine[CaractereCourant − i];
16 ChaineAT ester+ =
chars[CaractereCourant − T ailleDeRepetition − i];
17 i ← i − 1;
18 end
19 if ChaineBaseDeT est = ChaineAT ester then
20 retourner ChaineBaseDeTest;
21 end
22 T ailleDeRepetition ← T ailleDeRepetition + 1;
23 end
24 CaractereCourant ← CaractereCourant + 1;
25 end
26 Return ChaineVide ;
Brieuc Barth´elemy
M´emoire du master Sciences Informatiques
Page 41 de 43
