Devoir Surveillé 
“Calcul Symbolique”
Licence 2 Informatique
Lundi 15 décembre 2014

Durée 2 heures. Le barème est donné de manière purement indicative. Il est demandé d’écrire les solutions dans ce document, n’hésitez pas à utiliser le format texte pour expliquer votre démarche.

Différentes définitons de la suite de Thue-Morse (10 points)

1. Une première récurrence

La suite de Thue-Morse est est la suite de 0 et de 1 définie par récurrence de la manière suivante 
	 (Subscript[t, 0])= 0, 
	 (Subscript[t, 2n])=(Subscript[t, n]) et
	 (Subscript[t, 2n+1])=1-(Subscript[t, n]) 
Programmer une fonction TM[n] qui retourne le n-ième terme de la suite de Thue-Morse

Clear[TM]
TM[0]=0;
TM[n_]:=TM[n]=If[EvenQ[n],TM[n/2],
1-TM[(n-1)/2]]

Map[TM,Range[100]-1]

2.  Une récurrence sur les (2^n) premiers termes.

La suite des (2^n) premiers termes de  la suite de Thue Morse est obtenue en concaténant la suite des (2^(n-1)) premiers termes de  la suite de Thue Morse suivie  de son complémentaire.  On a donc
{0}->{0,1}->{0,1,1,0}->{0,1,1,0,1,0,0,1}->...
Ecrire la fonction STM[n] qui retourne la liste des (2^n) premiers termes de la suite de Thue Morse.

Bar[liste_]:=1-liste
STM[0]={0};
STM[n_]:=STM[n]=Join[STM[n-1],Bar[STM[n-1]]]

STM[5]

3. Définition par morpisme

On part de la liste {0} et on itère la fonction qui remplace 0 par 0,1 et 1 par 1,0. Ecrire la fonctio, ThueMorse[n] qui retourne, par cette méthode, les (2^( n ))premiers termes de la suite de Thue Morse.

Morphisme[0]=Sequence[0,1];
Morphisme[1]=Sequence[1,0];
Morphisme[liste_List]:=Map[Morphisme,liste]

ThueMorse[n_]:=Nest[Morphisme,{0},n]
ThueMorse[5]

4. Avec la somme des entiers.

Une autre manière de construire les n premiers termes de la suite de Thue Morse est de considérer la suite des congurences modulo 2 des sommes des entiers de 1 à n. Par exmple
	0⟶ 0
	1⟶ 1
	2=10 ⟶ 1
	3=11 ⟶ 0=Mod[1+1,2]
	...
	10=1010=0=Mod[1+1,2]
	...
Ecrire une fonctionTM2[n]  qui retourne le n-ième terme de la suite de Thue Morse grace à cette méthode.

TM2[n_]:=TM2[n]=Table[Mod[Total[IntegerDigits[k,2]],2],{k,0,n}]

TM2[50]

5. Vérification

Vérifier pour les premiers termes, que  les quatres fonctions précédentes définissent bien la même suite.

u=Map[TM,Range[2048]-1];
v=STM[11];
w=Nest[Morphisme,{0},11];
s=TM2[2047];
Map[Length,{u,v,w,s}]
u==v==w==s

Propriétés de la suite de Thue-Morse (10 points)

1. Complexité de la suite de Thue Morse (5 points)

La complexité d’une suite infinie w est la fonction (sur l’ensemble des entiers) qui à n associe le nombre de facteurs différents de longueur n. On va vérifier ici que la suite de Thue-Morse a une complexité égale à a(n), définie par
	 a(1)=2,
	 a(2)=4, 
	 a(3)=6 et  
	 a(2n)=a(n)+a(n+1), pour n>1
	 a(2n+1)=2a(n+1) pour n>1

1.1 Facteurs d’un mot

Ecrire la fonction Facteurs[w,n] qui retourne l’ensemble des facteurs de longueur n de la liste w. Par exemple Facteurs[{1,0,0,1,0},2] doit retourner {{1,0},{0,0},{0,1}}.

Facteurs[w_,n_]:=Union[Partition[w,n,1]]

1.2 Programmer la suite a.

Clear[a]
a[1]=2;
a[2]=4;
a[3]=6;
a[n_]:=a[n/2]+a[n/2+1]/;EvenQ[n]
a[n_]:=2a[(n-1)/2+1]/;OddQ[n]

1.3. Vérification

Vérifier sur les premières valeurs de n que a(n) est bien le nombre de facteurs de longueur n du mot de Thue Morse. On pourra tester pour n<=20 sur les 500  premières valeurs de la suite de Thue Morse.

Table[Length[Facteurs[TM2[500],i]],{i,1,20}]
Table[a[n],{n,1,20}]

2. Carres dans le mot de Thue Morse (3 points)

2.1 La fonction CarreQ.

Ecrire un prédicat qui teste si une suite est un carré (une liste répétée deux fois, comme par exemple {1,0,0,1,0,0}.

CarreQ[w_List]:=EvenQ[Length[w]]&&Take[w,Length[w]/2]==Take[w,-Length[w]/2]

CarreQ[{1,0,0,1,0,0}]
CarreQ[{1,0,0,1,0,1}]

2.2 Les facteurs carrés du mot de Thue Morse

Ecrire une fonction Carres[n] qui retourne tous les carrés de longueur 2n que l’alphabet {0,1}

Carres[n_]:=Map[Join[#,#]&,Tuples[{0,1},n]]

Carres[3]

2.3 Carrés de longuer 12 du mot de Thue Morse

Trouver tous les facteurs carrés de longueur 12 de la suite de Thue Morse.

Select[Facteurs[TM2[10000000],12],CarreQ]

3. Le mot de Thue Morse ne contient pas de cube (2 points)

3.1 Ecrire un prédicat CubeQ qui teste si une suite est un cube (une liste répétée trois fois, comme par exemple {1,0,0,1,0,0,1,0,0}.

CubeQ[w_]:=Block[{n=Length[w]},Mod[n,3]==0&&(Take[w,n/3]==Take[w,-n/3]==Take[w,{n/3+1,-n/3-1}])]

CubeQ[{1,0,0,1,0,0,1,0,0}]
CubeQ[{1,0,0,1,0,0,1,0,1}]

3.2 Vérifier (pour les petites valeurs) que la suite de Thue Morse ne contient aucun  facteur cube.

Table[Select[Facteurs[TM2[1000000],3i],CubeQ],{i,1,6}]

Thue Morse et courbe de Koch (6 points)

On dessine une suite de 0 et de 1 en lisant chaque caractère et en dessinant successivement des segments unités formant un angle qui dépend de la lettre lue : α si on lit un 0 et β si on lit un 1.

1. Ecrire une fonction Dessine[liste_List, α,β] qui retourne la suite de points correspondant au dessin de la liste.

Indication. On utilisera la fonction RotationTransform[angle,centre][point].  Et on supposera que le dessin d’une  liste  de deux éléments  est un pas horizontal.

Clear[Dessine]
Dessine[{i_,j_},α_,β_]:={{0,0},{1,0}}
Dessine[liste_,α_,β_]:=Block[{chemin=Dessine[Drop[liste,-1],α,β],dernier, avantdernier,nouveau,x=Last[liste]},
dernier=chemin[[-1]];
avantdernier=chemin[[-2]];
nouveau=RotationTransform[If[x==0,α,β],dernier][avantdernier];
Return[Append[chemin, nouveau]]]

Clear[Dessine]
Dessine[liste_,α_,β_]:=Block[{chemin={{0,0},{1,0}},dernier, avantdernier,nouveau,x=Last[liste]},
If[Length[liste]<3,Return[chemin]];
For[i=3,i≤Length[liste],i++,
dernier=chemin[[i-1]];
avantdernier=chemin[[i-2]];
x=liste[[i]];
nouveau=RotationTransform[If[x==0,α,β],dernier][avantdernier];
chemin=Append[chemin, nouveau]];
Return[chemin]]

ListLinePlot[Dessine[{1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1},Pi/2,-Pi/2],AspectRatio->Automatic,Axes->False]

2. En déduire la courbe Koch à partir du mot de Thue Morse. On prendra α=π/3 et β=0.

ListLinePlot[Dessine[STM[12],Pi/3,0],AspectRatio->Automatic,Axes->False]

2. BONUS. Pliage de papier. On définit la suite (Subscript[p, n]) obtenue à partir de {0} en concaténant (Subscript[p, n-1]), 0,  et le miroir du complement de (Subscript[p, n-1]) c’est à dire
0⟶001⟶0010011⟶001001100011011...
Retrouver la courbe du dragon (on prendra α=π/2 et β=-π/2).

pliage[1]={0};
pliage[n_]:=pliage[n]=Join[pliage[n-1],{0},Reverse[Bar[pliage[n-1]]]]

pliage[4]

ListLinePlot[Dessine[pliage[12],Pi/2,-Pi/2],AspectRatio->Automatic,Axes->False]