Mots de Christoffel et rastérisation

Le projets s'articule autour d'un problème très ancien en informatique en effet le problème est de savoir comment tracer une droite discrète entre deux points d’un écran pixelisé.

Certains pistes nous permettent d'appréhender le problème en effet Les mots de Christoffel nous apportent une réponse à ce problème.

La combinatoire des mots a toujours était le fruit de plusieurs rechercher au cours du temps ainsi au fils du temps plusieurs familles de mots on été découverte certaine infinies d’autre non

Mêlant les notion de Combinatoire des mot ainsi que la construction de graphe les propriété ainsi que les caractéristique du mots de Christoffel porte un certain intérêt.

Notre principale objectif est de vulgariser ce problème et en expliqué les nuances.

Une des premières étapes primordiale et fastidieuse à été de bien interpréter les propriété du mots de Christoffel

En effet en premiers lieu nous avons commencer à énumérer tout les cas caractérisant le mot de christoffel( afin d'en deduire c'est proprieter ainsi que la probabilité d'obtenir un mot correspondant justement a un mots de christoffel )avant de ce rendre compte qu'il s'agissait d'un mauvais angle d'approche du problème demander

Car en effet nous avions au début décider d'en déduire que cela reviendrait a tirer a pile et face n pièce et avoir un nombre de pile y et nombre de face x sans prendre en compte l’ordre.
à partir de ce raisonnement erronée nous en avons déduit le raisonnement suivant:
|y| = n - |x|
<=> n - |x| != a* |x| avec a=!1
<=>n != (a+1) * |x| avec a >1
<=>n != (b) * |x| avec b> 2
Si n est premier, soit |x| =1 et x/y est irréductible donc le mot est un mot de Christoffel, soit b=1 et le mot est un mot de Christoffel))

Ce raisonnement erronée ne remplissez pas tout les condition permettent la résolution de notre problème

Car une des propriété principale que nous avions omis était l’ordre des lettres influer en effet la définition des mots de Christoffel comprenait l'ordre des lettres et celle ci avait son importance

On a ensuite procédé de manière inverse: nous avons décider de voir quels cas ne correspondaient pas et avons cherché les similitudes

En effet dans notre premiers approche du problème nous avions considérer que l'ordre n'influer pas sur la construction du mots de Christoffel.(Par ailleurs cela se traduit par notre fonction Chris2 de notre programme qui justement prend en compte l'ordre des lettres)

De plus nous pensions que si n était premier alors le mot de longueur de n était forcement un mot de Christoffel ors cela nous à induit en erreur

Car en effet la spécificité palindromique du mots de Christoffel ne corréler pas avec notre raisonnement

En effet une des caractéristique principale du mot de christoffel et le fait que l'ont peut retrouver un palindrome , si l'on enlève la première et dernière lettre d'un mots de Christoffel on obtient un palindrome

En effet si l'on enlève le premier et dernier caractère du mot xxyxxyxxyxy représenter par la figure géométrique suivante:

On remarque que l'on obtient bien un palindrome "xyxxyxxyx" respectant la condition du mot de christoffel

Nous avons ensuite déduit une des propriété du mots de Christoffel qui justement consistait dans le fait que le nombres de x (dans un mots de Christoffel) devait être premier avec la longueur du mots.

Soit le raisonnement suivant:

Soit n la longueur du mots et q et k deux caractère lambda.

Si x n'est pas premier avec n alors on peut écrire y sous la forme de aq et ak avec a = pgcd (x,n):
y = n-x <=> y= ak-aq <=> y= a(k-q) avec a=!1 Comme x = aq, on a x=aq et y=a(k-q)
Donc x/y est simplifiable par a. On en déduit donc que le mot n'est pas un mot de Christoffel puisque x et y ne sont pas premiers entre eux

Ainsi à partir de nos raisonnement précédent nous avons pus en déduire en quelque sorte une formule concernant la probabilité des mots de Christoffel

Nous avons donc en déduit la propriété suivante qui est la propriété respectant une des condition permettant la création d'un mots de Christoffel
Soit la probabilité p que un mot m de longueur n soit un mot dont le nombre de x et de y sont premiers entre eux est:
p1 = [Sum(1,n){(i parmi n) si pgcd(i,n)=1}]/2^n

Une des propriété principale des mots de Christoffel est l'aspect palindromique en effet comme dit plus haut sur tout mots de Christoffel si on enlève la premiers ainsi que la dernière lettre du mots nous obtenons un palindrome

Ainsi afin de pouvoir respecter cette condition du palindrome nous devons avoir un mots de Christoffel ou le nombre total de x et de y soit premiers entre eux et donc premier avec la longueur n de notre mots ce que nous avons démontrer plus tôt.

On peut donc se servir de cette propriété pour trouver la borne supérieure de la probabilité qu'un mot de longueur n choisi au hasard soit un mot de Christoffel

On sait que p < [Sum(1,n){(i parmi n) si pgcd(i,n)=1}]/2^n

Pour que notre mot soit un palindrome, il faut que ses n/2 premières lettres correspondent aux n/2 dernières lettres. Donc les n/2 premières lettres sont libres.
donc p2 = 2^(n/2 - 1)/2^n

Ainsi à partir de notre raisonnement précédent nous avons pus en déduire la probabilité qu’un mot sur x, y de longueur n pris au hasard soit un mot de Christoffel

p <= p1 inter p2

Avec P1 : la probabilité que un mot m de longueur n soit un mot dont le nombre de x et de y sont premiers entre eux
Et P2: la probabilité que notre mot soit un palindrome

Car en effet c'est deux condition doivent être validée afin d'obtenir un mots de Christoffel

A partir de là nous avions comme objectif la création d'un algorithme permettent de tester les condition du mot de Christoffel

L'algorithme proposer dispose d'un manuel et permet la verification des mots de Christoffel ainsi que des pentes.

Ci joint l'algorithme ainsi que quelques illustration attestant du fonctionnement du code:

class Main{
	
	static String man1="Programme de production et de détection de mots de Christoffel\nEntrees possibles:\n";
	static String man2="Production de mots:\n\t-\"int int\"\n\t-\"int,int\"\n\t-\"(int,int)\"\n";
	static String man3="Détection de mots:\n\t-\"String\"\n\t-\"String char char\"";
	static final String man = man1+man2+man3;

	static int pgcd(int a, int b){
		int r=a%b;
		while(r!=0){
			a=b;
			b=r;
			r=a%b;
		}
		return b;
	}

	static String chris(int a, int b){
		if(a==0)
			return "Erreur: Division par 0 (a=0)";
		if(pgcd(a,b)!=1)
			return a+" et "+b+" ne sont pas premiers entre eux";
		int x0=0;
		int x1=1;
		String w="";
		while(x1 != 0){
			x1=(x0+a) % (a+b);
			if(x1>=x0)
				w+="x";
			else
				w+="y";
			x0=x1;

		}
		return w;
	}

	static String isChris(String s){
		if(s.length()==0)
			return "Entrée de type invalide";
		if(s=="x")
			return "Ce mot est un mot de Christoffel de pente 0";
		if(s=="y")
			return "Ce mot est un mot de Christoffel de pente infini";
		char c0 = s.charAt(0);
		int n0 = 1;
		while(n0<s.length() && s.charAt(n0)==c0)
			n0+=1;
		if(n0 == s.length())
			return "Ce mot est un mot de Christoffel de pente 0 ou infini";
		char c1 = s.charAt(n0);
		int n1 = 1;
		while((n0+n1)<s.length())
			if(s.charAt(n0+n1)==c0)
				n0+=1;
				else
				if(s.charAt(n0+n1)==c1)
					n1+=1;
					else
						return "Entrée de type invalide";
		if(pgcd(n0,n1)==1)
			return isChris2(s, n0, n1);

		return "Ce mot n'est pas un mot de Christoffel puisque "+n0+" et "+n1+" sont divisibles par "+pgcd(n0,n1);		
	}

	static String isChris(String s, String s1, String s2){
		if(s.length()==0||s1.length()!=1||s2.length()!=1)
			return "Entrée de type invalide";
		char c0=s1.charAt(0);
		char c1=s2.charAt(0);
		int n0=0;
		int n1=0;
		for(int i=0; i<s.length(); i++)
			if(s.charAt(i)==c0)
				n0+=1;
			else
				if(s.charAt(i)==c1)
					n1+=1;
				else return "Entrée de type invalide";
		if(n0==0)
			return "Ce mot est un mot de Christoffel de pente infini";
		if(n1==0)
			return "Ce mot est un mot de Christoffel de pente 0";
		if(pgcd(n0,n1)==1)
			return isChris2(s, n0, n1);

		return "Ce mot n'est pas un mot de Christoffel puisque "+n0+" et "+n1+" sont divisibles par "+pgcd(n0,n1);		
	}

	static String isChris2(String s, String s1){
		String pal = "";
		for(int i=1; i<s.length()-1;i++)
			pal+=s.charAt(i);

		for(int j=0; j<pal.length()/2;j++)
			if(pal.charAt(j)!=pal.charAt(pal.length()-(j+1)))
				return "Ce mot contient le bon nombre de chaque lettre mais n'est pas un mot de Christoffel";
		return "Ce mot est un mot de Christoffel de pente "+s1;
	}

	static String isChris2(String s, int n0, int n1){
		String pal = "";
		for(int i=1; i<s.length()-1;i++)
			pal+=s.charAt(i);

		for(int j=0; j<pal.length()/2;j++)
			if(pal.charAt(j)!=pal.charAt(pal.length()-(j+1)))
				return "Ce mot contient le bon nombre de chaque lettre mais n'est pas un mot de Christoffel";
		return "Ce mot est un mot de Christoffel de pente "+n0+"/"+n1;
	}

	public static void main(String [] args){
		String s="";
		if(args.length == 0){
			System.out.println(man);
			return;
		} if(args.length == 1){
			s=args[0];
			if(s.equals("?")||s.equals("help")){
				System.out.println(man);
				return;
			}
			char c;
			int j=0;
			int k=s.length();

			if(s.charAt(0) == '(' && s.charAt(k-1) == ')'){
				j++; k--;
			}

			String s0="";	
			String s1="";
			boolean bool=false;
			
			for(int i=j; i<k; i++){
				if(s.charAt(i)== ',' ){
					bool=true;
					i++;
				}
				if(!bool)
					s0+=s.charAt(i);
				else
					s1+=s.charAt(i);
			}

			if(s1.length()==0){
				System.out.println(isChris(args[0]));
				return;
			}
			try{
				int a=Integer.parseInt(s1);
				int b=Integer.parseInt(s0);
				s=chris(a,b); 
			}catch(Exception e){
				s = isChris(args[0]);
			}

		} else
			if (args.length == 2){
				s=args[0];
				try{
				int a=Integer.parseInt(args[1]);
				int b=Integer.parseInt(s);
				s=chris(a,b); 
				}catch(Exception e){
					s = isChris(args[0]);
				}
			} else if(args.length == 3)
					s=isChris(args[0], args[1], args[2]);
				else 
					s = "Entree de taille invalide";
		System.out.println(s);
		return;
	}


}

De plus un rapprochement entre la construction de certaine gammes diatonique et le mots de Christoffel peut être mis en évidence

En effet nous pouvons en premier lieu remarquer une certaine similitude entre les gamme diatonique et le mots de Christoffel un certain point ce révèle lorsque nous faisons la comparaison entre la construction des gammes et en l’occurrence les mots de Christoffel (La construction est fait a partir du cycle diatonique soit la base de la musique occidental do ré mi fa so la si do )

En effet nous pouvons remarquer dans un point une certaine similitude sur la répartition des notes et des demi-tons avec la construction d'un mot de Christoffel.

En effet si l'ont remplace les ton et demi-tons (qui permettent la construction de la gamme) par x et y , certaine caractéristique du mot de Christoffel ce révèle

En effet nous remarquons que lorsque nous construisons notre gamme ( gamme diatonique classique) a partir de la note Ré Fa et Si ( en remplaçant les ton et demis ton par x et y) on obtient un mots respectant les propriété du mots de Christoffel.

Nous pouvons le voir à partir de la figure ci dessus exemple , en partant de Ré on obtient le mot suivant :abaaaba

on remarque que les condition du mot de Christoffel sont respecter en effet si l'ont enlève la dernier et premier lettre on obtient bien un palindrome (dans l'exemple on obtient "baaab")

Ors on remarque que ce n'est pas le cas pour les gammes construite à partir de Mi Do La et Sol. En effet la condition du palindrome n'est pas respecter l’or de la construction de c'est différente gamme.

Ainsi on observe donc que les mot de Christoffel lié a une gamme diatonique (standard ) ne se retrouve que dans quelque construction.

On en déduit donc que le mot de Christoffel n'est pas caracteristique de la gamme diatonique

Ors un certain rapprochement peutetre fait entre la disposition des touche d'un piano et le mot de christoffel.

En effet si l'on on considéré le «mode lydien», c’est-à-dire la suite des touches blanches du piano ( soit la gamme Fa : Fa Sol La Si Do Ré Mi Fa)

On remarque que si on fait le mème raisonnement comme cité précédemment en remplaçant les intervalles de ton par a et demi-ton par b on obtient le: mot aaabaab.

C’est-à-dire un mot de Christoffel de pente 2/5. De plus ce mot respecte la propriété palindromique du mots de christoffel " (a)aabaa(b)"

Nous pouvons donc observer une certaine similitude entre la répartition des touche blanche d'un piano et la construction du mot de Christoffel.

Ainsi à a partir de nos recherche nous avons pus mieux analyser les propriété et les caractéristique du mots de Christoffel.Dont notamment la propriété palindromique, une propriété très intéressante que l'ont peu retrouver dans de nombreux domaine dont justement la musique.

Bibliographie

http://ehess.modelisationsavoirs.fr/atiam/atiam10/2010%20Combinatoire.pdf

CARACTÉRISATIONS DES MOTS DE PAR MELODIE LAPOINTTE AOÛT 2016 https://archipel.uqam.ca/9001/1/M14562.pdf

1 Cliquer pour recommander cet article