1
00:00:08,000 --> 00:00:15,000
Chapitre 2 -- Le problème du mot

2
00:00:20,000 --> 00:00:28,000
Dans le premier chapitre, nous avons vu que toute tresse peut être codée
par un mot composé de tresses élémentaires, les générateurs.

3
00:00:28,200 --> 00:00:34,800
Puis nous avons décrit toutes les relations, c'est-à-dire les transformations de mots
qui ne changent pas la tresse correspondante.

4
00:00:35,000 --> 00:00:38,000
Mais... cette description ne nous dit pas tout.

5
00:00:38,500 --> 00:00:44,500
Par exemple, les relations ne nous disent pas comment
vérifier si deux mots sont équivalents ou non.

6
00:00:45,000 --> 00:00:50,500
Prenons deux mots.
Ici, on peut trouver une suite de relations qui les relient entre eux.

7
00:00:51,000 --> 00:00:59,000
A chaque étape, on remplace la partie du mot dans la boite jaune
par une partie équivalente...

8
00:00:59,200 --> 00:01:08,000
...obtenue en utilisant les relations du groupe de tresses,
ou en insérant ou simplifiant un générateur et son inverse.

9
00:01:12,000 --> 00:01:18,000
A chaque étape on change le mot,
mais la tresse qu'il représente reste la même.

10
00:01:26,000 --> 00:01:32,000
Il n'est pas si facile de voir immédiatement
que les deux mots sont équivalents!

11
00:01:32,200 --> 00:01:36,200
Cela ne devient évident qu'une fois
qu'on a construit la suite de mots intermédiaires.

12
00:01:47,000 --> 00:01:53,000
Et que dire de ces deux mots?
Comme avant, on essaie de les relier par une suite.

13
00:01:57,000 --> 00:02:02,000
Mais cette tentative est hasardeuse:

14
00:02:02,200 --> 00:02:07,000
on pourrait passer toute notre vie à la chercher, sans jamais la trouver.

15
00:02:07,200 --> 00:02:12,000
Même après nos innombrables essais,
on ne saurait toujours pas si une telle suite existe ou non.

16
00:02:12,200 --> 00:02:18,000
Peut être que nous n'avons simplement pas été assez chanceux pour la trouver?

17
00:02:22,000 --> 00:02:28,000
C'est pourquoi on a besoin d'un autre moyen
pour résoudre le problème de l'équivalence des mots.

18
00:02:42,000 --> 00:02:51,000
Plus précisément, on aimerait construire une procédure qui, étant donnés deux mots quelconques...

19
00:02:51,200 --> 00:02:54,800
...fait des calculs...

20
00:02:55,000 --> 00:03:02,000
...et renvoie la réponse "oui" si les deux mots sont équivalents...

21
00:03:04,000 --> 00:03:15,000
...ou la réponse "non" si les deux mots représentent deux tresses différentes.

22
00:03:16,000 --> 00:03:20,000
Une telle procédure s'appelle un algorithme.

23
00:03:24,000 --> 00:03:30,000
Nous avons de la chance: pour les tresses, il existe un tel algorithme.
Regardons à l'intérieur...

24
00:03:37,000 --> 00:03:40,000
Mais avant tout, simplifions un peu le problème:

25
00:03:40,200 --> 00:03:54,000
Dire que deux mots représentent la même tresse revient à dire que
si l'on compose le premier avec l'inverse du deuxième, on obtient la tresse triviale.

26
00:03:55,500 --> 00:04:03,000
On peut donc reformuler notre problème:
déterminer si un mot donné représente oui ou non la tresse triviale.

27
00:04:03,500 --> 00:04:08,500
Autrement dit, si l'on peut, grâce aux relations, transformer notre mot en "1".

28
00:04:11,000 --> 00:04:17,000
Regardons cette tresse. La disposition des couleurs aux extrêmités
nous indique de quelle façon les points sont reliés entre eux.

29
00:04:18,000 --> 00:04:24,000
Si cette disposition est exactement la même à gauche qu'à droite,
on dit que la tresse est "pure".

30
00:04:27,000 --> 00:04:32,000
Bien sûr, l'équivalence des tresses préserve l'ordre des couleurs aux extrêmités.

31
00:04:32,500 --> 00:04:40,000
Donc une tresse équivalente à la tresse triviale est nécéssairement pure.

32
00:04:43,000 --> 00:04:47,000
Toute tresse pure peut être décomposée en blocs de la façon suivante.

33
00:04:47,200 --> 00:04:56,500
Dans le premier bloc, tous les brins sont droits sauf le dernier,
le brin vert, qui peut s'emmêler avec les autres.

34
00:04:56,700 --> 00:05:05,000
Dans le deuxième bloc, tous les brins sont droits sauf l'avant-dernier,
le brin jaune, qui peut seulement s'emmêler avec les brins du dessous.

35
00:05:05,200 --> 00:05:12,000
Et ainsi de suite... jusqu'au dernier bloc,
dans lequel le deuxième brin peut seulement s'emmêler avec le premier.

36
00:05:13,000 --> 00:05:17,000
On sait que chaque tresse peut être représentée par de nombreux mots différents.

37
00:05:17,200 --> 00:05:28,200
Pour chaque tresse, on aimerait en choisir un en particulier,
qu'on appellera sa forme normale.

38
00:05:30,000 --> 00:05:37,000
Nous allons décrire un algorithme qui met chaque tresse sous sa forme normale.

39
00:05:37,500 --> 00:05:43,000
Cette procédure, dûe à Artin, s'appelle le peignage des tresses.

40
00:05:43,200 --> 00:05:45,000
Commençons par recopier la tresse...

41
00:05:45,200 --> 00:05:52,000
...et supprimer le dernier brin, que l'on remplace par un brin horizontal.

42
00:05:53,000 --> 00:05:57,500
En composant cette tresse avec son inverse, on obtient la tresse triviale.

43
00:05:57,700 --> 00:06:02,000
Donc, en composant le tout avec la tresse originale,
nous ne changeons pas celle-ci.

44
00:06:03,000 --> 00:06:10,000
Du côté gauche, on peut dégager un premier bloc qui a bien la forme voulue:

45
00:06:10,200 --> 00:06:15,200
tous les brins sont droits sauf le dernier.

46
00:06:17,000 --> 00:06:21,000
On peut encore déformer les brins de telle façon que...

47
00:06:21,200 --> 00:06:28,000
...le brin vert entoure successivement un seul brin à la fois,
en remontant à sa position initiale entre chaque tour.

48
00:06:31,000 --> 00:06:35,000
On dit alors que cette partie a été "peignée".

49
00:06:37,000 --> 00:06:42,000
On répète la même procédure avec la partie restante à droite:
on copie la tresse...

50
00:06:43,000 --> 00:06:47,000
...remplace le brin jaune par un brin horizontal...

51
00:06:51,000 --> 00:06:56,000
...compose la tresse avec son inverse...

52
00:06:57,000 --> 00:07:01,000
...puis on compose la tresse triviale ainsi obtenue avec la tresse originale...

53
00:07:03,000 --> 00:07:07,000
...ce qui nous permet d'arranger le deuxième bloc.

54
00:07:13,000 --> 00:07:22,000
On peut en effet déformer cette partie pour la peigner comme précédemment,
de façon à ce que le brin jaune s'emmêle seulement avec le bleu et le rouge.

55
00:07:47,000 --> 00:07:52,000
Il ne reste plus qu'un dernier bloc, qui est facile à peigner.

56
00:07:53,000 --> 00:07:57,000
Nous avons mis la tresse sous sa forme normale.

57
00:07:58,000 --> 00:08:05,000
Artin a démontré qu'une tresse est triviale si et seulement si,
une fois peignée, chacun de ses blocs est trivial...

58
00:08:05,200 --> 00:08:09,000
...c'est-à-dire, tous les brins sont droits.

59
00:08:09,200 --> 00:08:13,000
Ici, notre tresse n'est donc pas triviale.

60
00:08:14,500 --> 00:08:17,500
Ainsi, l'algorithme d'Artin permet de décider
si une tresse donnée est triviale ou non.

61
00:08:18,500 --> 00:08:25,500
Bien sûr cette tresse doit être pure.
On la peigne en suivant la méthode d'Artin.

62
00:08:25,700 --> 00:08:31,000
Si on tombe sur un bloc non trivial, l'algorithme répond "non".

63
00:08:31,200 --> 00:08:34,000
Sinon, on continue avec le bloc suivant.

64
00:08:34,200 --> 00:08:44,000
Si tous les blocs sont triviaux, alors la tresse est triviale
et l'algorithme répond  "oui".

65
00:08:55,000 --> 00:09:01,000
Mais bien que cet algorithme fonctionne,
Artin lui-même n'en était pas très satisfait!

66
00:09:05,000 --> 00:09:08,000
Dans son article "théorie des tresses", il écrit:

67
00:09:08,200 --> 00:09:14,000
"L'auteur est convaincu que toute tentative de mise en pratique sur une personne vivante
ne conduirait qu'à de violentes protestations et discriminations envers les mathématiques."

68
00:09:14,200 --> 00:09:18,000
"Il dissuade donc de conduire une telle expérience."

69
00:09:19,000 --> 00:09:24,000
En effet, le peignage des tresses peut être un travail extrêmement long!

70
00:09:24,200 --> 00:09:27,000
La complexité de l'algorithme est très élvée:

71
00:09:34,000 --> 00:09:44,000
si l'on trace un graphique représentant le temps moyen nécessaire
pour peigner une tresse en fonction du nombre de croisements, la courbe croît très vite.

72
00:09:46,000 --> 00:09:55,000
Augmenter un peu la taille de la tresse peut donc faire exploser le temps de calcul,
qui peut devenir très long, même pour un ordinateur.

73
00:09:55,200 --> 00:10:01,000
C'est porquoi les mathématiciens cherchent d'autres algorithmes plus rapides.

74
00:10:04,000 --> 00:10:14,000
Le plus rapide que l'on connaisse actuellement est probablement celui
qui a été introduit en 1995 par Dehornoy, un mathématicien Français.

75
00:10:16,000 --> 00:10:21,000
Il s'agit de l'algorithme de "la réduction des poignées".

76
00:10:25,000 --> 00:10:32,000
Voici une poignée: le brin rouge passe devant le brin qui est juste au-dessus,
puis devant le brin juste en-dessous.

77
00:10:32,700 --> 00:10:39,000
Une poignée peut aussi passer deux fois derrière les autres brins:
voici une autre poignée.

78
00:10:44,000 --> 00:10:48,000
Une poignée est toujours tournée vers le haut;
ceci n'est donc pas une poignée.

79
00:10:52,000 --> 00:10:57,000
Ceci non plus, car le brin bleu passe
une fois par devant et une fois par derrière.

80
00:10:59,000 --> 00:11:06,000
L'algorithme de réduction des poignées
consiste à retourner les poignées pour les faire disparaître.

81
00:11:07,000 --> 00:11:15,000
Ces transformations changent le mot, mais pas la tresse qu'il représente.

82
00:11:34,000 --> 00:11:44,000
Un théorème de Dehornoy affirme qu'un mot sans poignée différent de "1"
représente forcément une tresse non triviale.

83
00:11:51,000 --> 00:12:00,000
Regardons comment fonctionne l'algorithme.
Prenons une tresse pure.

84
00:12:01,000 --> 00:12:09,000
Si elle n'a pas de poignées et au moins un croisement,
alors la tresse n'est pas triviale et l'algorithme répond "non".

85
00:12:10,000 --> 00:12:16,000
S'il y a des poignées,
on trouve celle qui se termine en premier et on la réduit.

86
00:12:20,000 --> 00:12:24,000
On continue ainsi jusqu'à avoir éliminé toutes les poignées:

87
00:12:24,200 --> 00:12:29,000
si la tresse possède de croisement, l'algorithme répond "non".

88
00:12:29,200 --> 00:12:35,000
Sinon, l'algorithme répond "oui".

89
00:12:40,000 --> 00:12:45,800
Mais il y a un problème:
comment savoir si l'algorithme se termine toujours?

90
00:12:46,000 --> 00:12:52,000
En effet, si en réduisant une poignée on revient
à un mot que l'on avait déjà obtenu auparavant...

91
00:12:52,000 --> 00:12:59,500
...alors l'algorithme se mettra à tourner en boucle et ne donnera jamais de réponse.

92
00:13:01,000 --> 00:13:09,000
Heureusement, ce ne sera jamais le cas:
on peut démontrer que l'algorithme termine toujours.

93
00:13:21,000 --> 00:13:28,000
On ne connait pas encore la complexité de cet algorithme...

94
00:13:28,200 --> 00:13:33,000
...mais certaines estimations expérimentales semblent indiquer
qu'il est plus rapide que les autres algorithmes connus.

95
00:13:50,000 --> 00:13:58,000
Peignage, poignées... La formalisation des tresses
en termes de manipulations de mots est vraiment fructueuse!