La Notation Siteswap (Concepts Avancés) (7/20)

Article proposé par Frédéric Roudaut

Le 15/11/2015.

❮

❯

VII - Etats & Caractéristiques des Siteswaps : fondamentaux, excités, premiers ...

VII-1 - Siteswaps fondamentaux & excités

a - Notation Vanille

En notation Vanille, on remarque des états particuliers constitués uniquement d'une suite de 1 en bits de poids faibles (éventuellement précédée de 0 uniquement en poids forts). Ces états sont les Etats de Base sur lesquels on boucle pour obtenir les différentes Cascades ou Fontaines selon la parité du nombre d'objet. Ainsi par exemple l'état de base à 3 objets est "111", utilisé dans la Cascade, à 4 objets il s'agit de "1111" pour la Fontaine, à 5 objets on a de nouveau une Cascade avec l'état "11111"...

 

Ces états sont qualifiés d'Etats Fondamentaux(Ground States en anglais) ou d'Etats de base en opposition aux Etats Excités (Excited States).

 

Par la suite, nous qualifierons par Figures ou Siteswaps de Base, les Figures/Siteswaps bouclant sur les états fondamentaux.

 

Dans la terminologie Siteswap, on qualifie la séquence de fondamentale lorsque cette séquence peut être effectuée directement à partir de l'état fondamental.

En d'autre terme un Siteswap est fondamental lorsqu'on peut l'amorcer et le finir directement, sans transition depuis la figure de base correspondant au nombre d'objets.

Dans le cas où une transition est nécessaire, on parle de Siteswap excité.

 

Si l'on prend pour exemple 423 ou 531 à 3 objets, on constate que ces Siteswaps s'amorcent depuis l'état fondamental "111" (Le nombre de 0 à gauche n'a pas d'impact). Il s'agit donc de Siteswaps fondamentaux que l'on peut donc enchaîner directement depuis la cascade ou l'un à la suite de l'autre sans besoin d'une transition quelconque.

 

 

 

En revanche, la douche à 3 objets 51, est un Siteswap excité. Une transition est donc nécessaire depuis et vers la Cascade. 4 est une transition possible pour y entrer et 2 en est également une pour en sortir.

 

Le caractère fondamental/excité n'a pas de raison d'être cantonné aux Siteswaps Vanilles. On peut en effet imaginer une classification équivalente quelque soit la famille de Siteswap. Dans la littérature on trouve peu d'éléments là-dessus. La définition d'un état fondamental se limite bien souvent en la simple explication qu'il s'agit de l'état de la figure de base à savoir donc celui de la Cascade ou de la Fontaine selon la parité impaire ou paire. Ce qui va suivre est donc une interprétation personnelle.

 

Avant d'aller plus loin concentrons nous sur les caractéristiques des états fondamentaux vanilles : il s'agit d'états dont les bits de poids faibles (à droite selon notre convention) sont tous à "1", les bits de poids forts s'ils existent sont à "0". Il s'agit de l'état de la figure de base d'un nombre d'objets égal au nombre de 1 de l'état. On lance donc un objet à chaque temps pour obtenir la Cascade, la Fontaine selon la parité. Le schéma ci-dessous montre la nomenclature d'un état fondamental Vanille :

Un Siteswap fondamental Vanille est donc un Siteswap que l'on peut amorcer et terminer par une figure de base sans transition, le cas échéant il est qualifié d'excité. Autrement dit on peut l'enchaîner depuis un état fondamental Vanille.

 

Il convient donc de rappeler les figures de base Vanille en fonction du nombre d'objets, tout en notant qu'elles ne peuvent s'exercer qu'à partir d'une certaine hauteur :

 

 

On retrouve donc bien là les Siteswaps des Fontaines dans le cas impair et des Cascades dans le cas pair.

b - Notation Multiplexe

On va conserver la sémantique précédente; un état fondamental n'est constitué que de 1 dans ses bits de poids faibles et 0 dans ses bits de poids forts s'ils existent. Les lancers d'un état fondamental sont donc obligatoirement Simplexes. Les Siteswaps Vanilles étant un sous-ensemble des Siteswaps Multiplexes (en tant que Multiplexe de lancers Simplexes), les figures de base correspondant à l'état fondamental seront donc les mêmes que celles des Siteswaps Vanille, à savoir donc Fontaines et Cascades.

 

Un Siteswap Fondamental Multiplexe sera donc un Siteswap que l'on peut amorcer ou enchaîner sans transition depuis une figure de base Vanille (ie Cascade/Fontaine).

c - Notation Synchrone

En Synchrone on poursuit dans le même schéma et un état fondamental sera uniquement constitué de 1 dans ses bits de poids faibles et 0 dans ses bits de poids forts s'ils existent. Si on se limite à cette définition précédente; concernant un nombre d'objets pairs, la figure de base serait une Fontaine synchrone ou un Wimpy, c'est à dire une "Fontaine" avec les objets changeant de main. Cependant avec cette définition on ne peut pas avoir de figure de base sur un nombre d'objets impairs. On va donc préciser qu'au sein d'un état fondamental Synchrone, dans le cas impair, une des mains de l'état comporte un bit de poids faibles de plus.

 

Les états fondamentaux Synchrones qui génèrent les figures de base sont donc :

• dans le cas d'un nombre d'objets pair : constitué d'un même nombre de "1" en Bits de poids faibles sur chacune des mains :
  
• dans le cas d'un nombre d'objets impair : constitué exactement d'un Bit "1" de poids faible de plus sur l'une des mains :
  

 

Pour 3 objets en Synchrone par exemple, les états fondamentaux seront donc multiples : 11,01 et 01,11. 11,01 est en fait associé aux Siteswaps (2,4) ou (2x,4x) tandis que 01,11 permet les Siteswaps (4,2) ou (4x,2x).

 

Un Siteswap Fondamental Synchrone sera donc un Siteswap que l'on peut amorcer ou enchaîner sans transition depuis une figure de base Synchrone.

 

Le tableau ci-dessous donne, selon notre interprétation, les Siteswaps de base Synchrones d'après le nombre d'objets:

 

 

On note donc qu'on a 2 Siteswaps de Base Synchrones pour un nombre pair d'objet : la Fontaine Synchrone et le Wimpy associé. Dans le cas impair on 4 Siteswaps de Base Synchrones : les symétries : Demi-Douche Synchrone et Fontaine Synchrone avec un trou d'un côté.

En ce qui concerne les états fondamentaux, on en a en fait 1 seul dans le cas pair (le "x" permet 2 Siteswaps de Base) et 2 dans le cas impairs (le "x" permet de doubler les Siteswaps encore une fois).

d - Notation Synchrone Multiplexe

On va réutiliser exactement le cheminement opéré avec les Siteswaps Multiplexes. En conséquence un Siteswap Fondamental Synchrone Multiplexe sera donc un Siteswap que l'on peut amorcer ou enchaîner sans transition depuis une figure de base Synchrone.

e - Notation MultiSynchrone

Pour le choix des états de base MultiSynchrone on pourrait imaginer trouver une compatibilité avec les adaptations MultiSynchrones des états fondamentaux Synchrones et Vanille. Cependant cette solution complexifie la définition des états fondamentaux. On va donc utiliser la même procédure que pour les Siteswaps Synchrones avec ou sans Multiplexe :

 

Les états fondamentaux MultiSynchrones sont donc :

• dans le cas d'un nombre d'objets pair : constitué d'un même nombre de "1" en Bits de poids faibles sur chacune des mains :
  
• dans le cas d'un nombre d'objets impair : constitué exactement d'un Bit "1" de poids faible de plus sur l'une des mains :
  

 

De ces états fondamentaux il en découle les Siteswaps de base :

 

 

On se retrouve avec des Figures de base assez proches au cas Synchrone à la différence qu'ici on compte tous les temps et pas uniquement les temps pairs. On a donc ici deux grandes familles selon la parité du nombre d'objets. Pour un nombre pair d'objet on retrouve une Fontaine Synchrone et son Wimpy associé. Dans le cas impair on 4 Siteswaps de Base avec les symétries : Demi-Douche Synchrone et Fontaine Synchrone avec un trou d'un côté. Le tout étant de hauteur moins élevée que dans le cas Synchrone puisque encore une fois on compte tous les temps en MultiSynchrone et de plus chaque lancer compte uniquement pour 1 temps (et 2 temps en Synchrone).

 

Voici à titre d'information les diagrammes en échelle des Siteswaps de base 1!2x, 1x!2, 2!3x, 2x!3 :

 

Un Siteswap Fondamental MultiSynchrone sera donc par conséquent un Siteswap que l'on peut amorcer ou enchaîner sans transition depuis une figure de base MultiSynchrone.

VII-2 - Siteswaps premiers

On rappelle qu'un Siteswap valide est un circuit au sein d'un diagramme Etats/Transitions. En d'autres termes le Siteswap dessine un chemin partant d'un état initial et retournant vers ce même état au sein d'un diagramme Etats/Transitions dimensionné selon le nombre d'objets et la hauteur maximum.

 

Un Siteswap est premier lorsqu'il ne peut être divisé en plusieurs Siteswaps indépendants. Si l'on se penche sur les états, un Siteswap est premier s'il n'emprunte pas plusieurs fois le même état. En théorie des graphes il s'agit en fait d'un circuit élémentaire.

 

Sur on revient sur les exemples précédent, 531 et 51 sont premiers mais 423 ne l'est pas dans la mesure où on repasse par l'état "0111". On a en effet la séquence : 0111 =4=> 1011 =2=> 0111 =3=> 0111 . 423 est en effet décomposable selon les 2 Siteswaps premiers 42 et 3.

 

Un Siteswap premier peut être fondamental (ex: 53) ou excité (ex: 741) :

 

 

 

 

 

 

 

 

 

 

 

 

 

De même un Siteswap non premier peut être fondamental (ex: 534) ou excité (ex: 12340) :

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

J'ai trouvé également le qualificatif de "Séquences non évidentes" pour qualifier les Siteswaps Premiers Excités.

 

En Théorie des Graphes, on qualifie :

• d'Eulérien, un circuit qui emprunte une et une seule fois tous les arcs du graphe;
• de Circuit Élémentaire, un circuit qui n'emprunte qu'une seule fois chacun de ses noeuds;
• d'Hamiltonien, un circuit élémentaire qui emprunte tous les noeuds du graphe.

Dans le cadre des Siteswaps, plusieurs mathématiciens se sont intéressés aux circuits élémentaires les plus longs. On peut citer en particulier Jack Boyce au travers des 2 papiers :

• The Longest Prime Siteswap Patterns : Démontre l'existence de motifs aux seins des plus longs Siteswaps premiers Vanilles permettant ainsi d'accélérer fortement les calculs de ceux-ci;
• Prime List : Une liste des plus longs Siteswaps premiers Vanilles.

 

La période maximum des Siteswaps Premiers est bien sûr limitée par le nombre d'états qui dépend lui-même du nombre d'objets et de la hauteur maximum. On pourra se reporter ici pour référence.

 

Cette caractéristique des Siteswaps n'est bien entendue pas restreinte aux Siteswaps Vanilles et on peut donc imaginer des Siteswaps :

• Multiplexes Premiers;
• Synchrones Premiers;
• Synchrones Multiplexes Premiers;
• MultiSynchrones Premiers.

 

Etant donné qu'on dispose des différentes matrices Etats/Transitions pour les différentes familles de Siteswaps, l'énumération des Siteswaps premiers est relativement logique : Il s'agit simplement d'y rechercher l'ensemble des circuits élémentaires. Plusieurs mathématiciens se sont penchés sur ce problème NP-Complet. On peut citer entre-autres :

• R. Tarjan, 1972;
• B. Johnson, 1975 : améliore la complexité de l'algorithme de Tarjan. Dans le plus mauvais scénario, l'algorithme de Tarjan donne une complexité en temps de l'ordre de O(n.e(c+1)), tandis que celui de Johnson reste en O((n+e)(c+1)); avec "n" le nombre d'états, "e" le nombre de transition et "c" le nombre de cycle du graphe;
• K. A. Hawick and H. A. James, 2008 : améliore l'algorithme de Johnson et s'affranchit de ses limitations puisqu'il est capable de gérer des graphes avec des transitions débutant et finissant sur le même état ou encore les transitions multiples entre états. Il a donc ma préférence dans la mesure où les transitions sur un même état sont possibles avec les diagrammes Etats/Transitions et on retrouve des transitions multiples dans les diagrammes Etats/transitions réduits (C'est l'algorithme que j'utilise en particulier sous jugglingTB).

 

Avant de poursuivre il est important de remarquer qu'étant donné que les Matrices Etats/transitions réduites n'ont pas d'impact sur les Siteswaps possibles, celles-ci peuvent très bien être utilisées dans la recherche des Siteswaps premiers. La réduction du nombre d'états et de transitions devrait permettre souvent une convergence plus rapide.

 

Par la suite on donnera pour chacune de ces familles différents tableaux donnant selon le nombre d'objets et la hauteur maximum :

• le Nombre de Siteswaps premiers disponibles;
• la Période du/des Siteswap(s) premier(s) le(s) plus long(s) et leur caractère Hamiltonien ou non;
• certains des Siteswaps premiers les plus longs.

On trouvera également souvent un lien listant les différents Siteswaps premiers, fondamentaux ou excités.

 

Ces Siteswaps premiers sont la clé de voûte des Siteswaps d'une famille donnée. En effet chaque Siteswap s'il n'est pas premier sera composé de Siteswaps premiers. Basé sur la structure des états on a donc une première idée de génération plus globale de Siteswaps. Encore s'agira t-il de trouver les Etats du Siteswap en question ! Ceci fera l'objet du prochain chapitre, n'anticipons pas!

 

De ces tableaux vous noterez ainsi par exemple que le Siteswap Vanille de 3 objets le plus long en se limitant à la hauteur 5 est : 55150530 de période 8. Si on augmente la limite de hauteur à 7 on tombe sur 773007071700706070074007706000 de période 30, peut-être plus dur à mémoriser également.

VII-2-1 - Notation Vanille

Jack Boyce démontre l'existence de motifs au sein de la majeur partie des Siteswaps Premiers (cf The Longest Prime Siteswap Patterns) et notamment pour les Siteswaps Premiers les plus longs. Sans entrer dans les détails ceux-ci respectent un format particulier Block Form. Un Siteswap Vanille d'un nombre d'objets b et de hauteur h, en format Block Form est composé de un ou plusieurs blocs; dont chacun :

• est constitué d'au plus h-2 lancers (nommés "Shift Throws"), de valeur 0 ou h, suivis par
• un lancer (nommé "Link Throw") supérieur à 0 et inférieur à h

De cette manière on a un format remarquable pour les Siteswaps Premiers les plus longs, permettant leur génération via un algorithme très optimisé. Pour faciliter la mise en évidence de ce format Block Form, Jack Boyce propose de remplacer les h par le symbole "+" et les 0 par "-". Ainsi par exemple, 730070060007060000 qui est le Siteswap Premier le plus long à 2 objets, de hauteur 7 se transforme en : +3--+--6---+-6----. Après cette transformation on y distingue aisément les Shifts Throws et les Links Throws.

 

Dans les tableaux ci-dessous les cases vertes représentent les Siteswaps Premiers Hamiltoniens

VII-2-2 - Notation Multiplexe

Dans les tableaux ci-dessous les cases vertes représentent les Siteswaps Premiers Hamiltoniens

a - Multiplexe : 0 objet

a - Multiplexe : 1 objet

Les Multiplexes d'un seul objet étant les simplexes Vanilles classiques, on se reportera aux tableaux Vanilles.

VII-2-3 - Notation Synchrone

Bien que je n'ai trouvé aucune trace concrête de recherche de motifs au sein des Siteswaps Premiers Synchrones, on peut supposer après observation de ceux-ci qu'ils suivent également un format Block Form pour une grande partie des plus longs d'entre-eux. Un Siteswap Synchrone d'un nombre d'objets b et de hauteur h, en format Block Form serait donc composé de un ou plusieurs blocs; dont chacun :

• est constitué de lancers (nommés "Shift Throws"), de valeur (0,0), (H,H), (0,H) ou (H,0) (H prenant la valeur h ou hx) suivis par
• un lancer synchrone "Link Throw"

Il ne s'agit bien entendu que d'une intuition mais qui demanderait à être approfondie pour en dériver un algorithme optimisé de génération de Siteswaps Premiers les plus longs.

 

Dans les tableaux ci-dessous les cases vertes représentent les Siteswaps Premiers Hamiltoniens

VII-2-4 - Notation Synchrone Multiplexe

Dans les tableaux ci-dessous les cases vertes représentent les Siteswaps Premiers Hamiltoniens

VII-2-5 - Notation Multisynchrone

Dans les tableaux ci-dessous les cases vertes représentent les Siteswaps Premiers Hamiltoniens

a - Multiplexe : 0 objet

VII-3 - Recherche des états d'un Siteswap

Si on se rappelle qu'un Siteswap est tout simplement un circuit dans un diagramme Etats/Réduction on a littéralement un algorithme pour calculer les états utilisés. Il suffit en effet de trouver l'état initial qui de surcroît est également l'état final et d'en dérouler le Siteswap. L'état final (et donc initial) se trouve aisément en suivant le parcours des objets.

VII-3-1 - Etats initiaux/finaux

 

Regardons ce que ça donne avec le Siteswap maintenant bien connu à 3 objets "423".

 

Sa hauteur maximum étant 4 on va regarder le Siteswap sur une période au moins 4. En doublant le Siteswap on obtient une période de 6. On s'intéresse donc à 423423. L'état est de longueur 4 et donc de la forme "- - - -". Après analyse des catchs on obtient l'état inversé 1110 qui donne donc l'état initial/final "0111". On notera qu'il s'agit d'un état fondamental.

 

Si on s'intéresse maintenant à 801, on comprend la règle initiale qui s'intéresse à un Siteswap de période supérieure ou égale au lancer de hauteur maximum. En effet si on s'intéressait uniquement à la section 801, on ne verrait pas les deuxième et troisième lancers de 8 qui interviennent sur un temps supérieur à la période 3 de 801. Avec la règle précédente on considérera parfois des périodes plus grandes que nécessaire mais elle a l'avantage d'être systématique et simple à retenir.

 

Finalement 801 possède pour état initial/final "00100101". Il s'agit d'un état excité.

 

Le mécanisme est déclinable quelque soit la famille de Siteswap. Voici pour exemple l'algorithme appliqué sur le Multiplexe [32]22, nous donnant l'état 012 pour état initial/final :

 

 

Poursuivons les exemples avec le Siteswap Synchrone (6x,2x) :

 

Il est à noter que les Siteswaps Synchrones doivent être répétés en utilisant leur format développé. C'est le cas pour (6x,2x)* par exemple. Sa hauteur maximum étant 6, il ne faut pas considérer uniquement la répétition (6x,2x)(2x,6x)(6x,2x) mais bien (6x,2x)(2x,6x)(6x,2x)(2x,6x). Cette précaution évite d'obtenir la symétrie de l'état initial/final :

 

La répétition des Siteswaps MultiSynchrones doit être telle que la période soit paire pour éviter d'obtenir l'état initial/final symétrique. Dans le cas du Siteswap MultiSynchrone 51x*, il s'agit donc de considérer la répétition 51x*51x*51x*51x* de période 8, paire et supérieure à la hauteur maximum 5 :

VII-3-2 - L'ensemble des états traversés

Une fois que l'on a obtenu l'état initial/final avec la méthode précédemment indiquée il est relativement simple d'en déduire l'ensemble des états traversés par le Siteswap. Il suffit simplement d'y appliquer les méthodes de transition évoquées au chapitre IV.

 

Si on reprend pour exemple 423 dont l'état initial est "0111", on trouve donc la séquence d'états traversés : 0111, 1011, 0111, 0111.

 

 

De même en reprenant le Siteswap Multiplexe précédent [32]22 dont l'état initial est "012", on trouve la séquence d'états traversés : 012, 111, 021, 012.

 

❮

❯