Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Corrigé entrée Septembre 2019 QUESTION 1.1 tous les mots de Lukasiewicz de long

Corrigé entrée Septembre 2019 QUESTION 1.1 tous les mots de Lukasiewicz de longueur ≤3 sont : • [-1] • [1,-1,-1] QUESTION 1.2 Supposons qu’il existe un mot de Lukasiewicz u de taille paire. Puisque le mot est de Lukasiewicz alors p(u)=-1, ce qui veut dire que si le nombre de 1 dans le mot est N, alors le nombre de -1 est N+1 nécessairement,alors le mot serait de taille 2N+1, en d’autres termes de taille impaire, ce qui contredit le fait que u est de taille paire QUESTION 1.3 [1]: def estLukasiewicz(u): s=0 n=len(u) for e in u[:n-1]: s+=e if s<0: return False s+=u[n-1] if s==-1: return True else : return False le coût des lignes 2,3,5, 8 et 9 est O(1) Donc le coût total est O(1)+O(1) + Σn−2 i=0 O(1) + O(1) = O(n) Remarque: il sufﬁt de répondre que le coût est O(n) sans justiﬁcation la réponse sera considérée juste QUESTION 1.4 Soit u et v deux mots de Lukasiewicz de taille respectivement N et M, Montons que (+1).u.v est un mot de Lukasiewicz *) On a p((+1).u.v) = 1+p(u)+p(v) = 1-1-1=-1, donc la première propriété est vraie *) Soit w un préﬁxe strict du mot (+1).u.v: • 1er cas : w= (+1), On a p(w) =1 ≥0 • 2ème cas : w=(+1)u’ tel que u’ préﬁxe strict de u alors puisque u est un mot de Lukasiewicz p(u’)≥0 donc p(w) =1+p(u’) ≥0 1 • 3ème cas : w=(+1)u alors p(w) =1-1=0 ≥0 • 4ème cas : w=(+1)uv’ tel que v’ préﬁxe strict de v alors puisque v est un mot de Lukasiewicz p(v’)≥0 donc p(w) =1-1+p(v’) =p(v’)≥0 Donc dans tous les cas la 2ème propriété est vériﬁée, D’où (+1).u.v est un mot de Lukasiewicz QUESTION 1.5 Soit un mot (w = w1...wn) de Lukasiewicz de longueur supérieure ou égale à 3 Montrons qu’il admet une décomposition unique de la forme (+1).u.v, où u et v sont des mots de Lukasiewicz. Puisque w est un mot de Lukasiewicz, alors certainement il s’écrit sous la forme (+1).w0 car sinon s’il s’ecrit sous la forme (-1).w0 alors il ne sera pas un mot de Lukasiewicz puisque le préﬁxe strict (-1) ne respectera la propriété que tout préﬁxe strict son poids doit être supérieure ou égale à 0 et aussi certainement il existe un préﬁxe strict w′ de w0 tel que p(w′) =-1 car sinon s’il n’existe tel préﬁxe vériﬁant ceci, puisque w′ est préﬁxe strict de w0 alors (+1)w′ est préﬁxe strict de w et comme w de Lukasiewicz donc p((+1).w′) ≥0 càd 1 + p(w′) ≥0, d’où p(w′) ≥−1 > 0, donc même si w_n sera égale à (1) alors p(w) sera supérieure ou égale à 0 ,contradiction car il devrait être égale à -1 parce w est un mot de Lukasiewicz, d’où l’existence d’un tel préﬁxe strict w′ de w0 tel que p(w′) =-1 Considérons u le plus préﬁxe strict de w0 tel que p(u) = −1, et soit v tel que w = (+1)u.v et montrons que u et v sont des mots de Lukasiewicz Commençons par u : • u vériﬁe la première propriété p(u) = −1 • soit u’ un préﬁxe strict de u alors (+1).u est préﬁxe de w, donc p((+1).u′) ≥0, càd p(u′) ≥ −1, mais p(u’) ne peut pas être égale à -1 car ça sera une contradicition avec ce qu’on a supposé et il sera le plus petit préﬁxe strict de w0 tel que sons égale -1, donc p(u’) ≥0, D’où on conclut que u est un mot de Lukasiewicz Maintenant montrons que v est un mot de Lukasiewicz: • On a p(w) = p((+1).v.w = 1 + p(u) + p(v) alors p(v) = p(w) −1 −p(u) = −1 −1 − (−1) = −1 • soit v’ un préﬁxe strict de v alors (+1).u.v’ est préﬁxe de w, donc p((+1).u.v′) ≥0, alors 1 + p(u) + p(v′) = 1 −1 + p(v′) = p(v′) ≥0 D’où on conclut que v est un mot de Lukasiewicz Montrons maintenant l’unicité Supposons que w admet deux décompositions différentes (+1).u.v et (+1).u′.v′ tels que u,u’,v et v’ sont des mots de Lukasiewicz Alors on a deux cas soit u est préﬁxe strict de u’ ou bien u’ préﬁxe strict de u Supposons par exemple que u est préﬁxe strict u’, alors comme u’ est un mot de Lukasiewicz p(u) ≥0 et comme u est un mot de Lukasiewicz p(u) = −1, donc −1 ≥0 contradiction De la même manière on montre que u’ ne peut pas être préﬁxe de u, D’où l’unicité de la décompostion 2 QUESTION 1.6 [1]: #solution 1 def decompose(w): n=len(w) for i in range(2,n): if estLukasiewicz(w[1:i])==True: return w[1:i],w[i:] #solution2 def decompose(w): n=len(w) s=0 for i in range(1,n): s+=w[i] if s==-1: return w[1:i+1],w[i+1:] QUESTION 1.7 On essaiera d’exploiter le fait que si u et v sont des mots de Lukasiewicz alors (+1).u.v sera un mot de Lukasiewicz d’après la question 1.4, donc pour chercher les mots de Lukasiewicz de taille n il sufﬁt de chercher de le précéder par un (+1) et chercher les mot de taile k et n-1-k et concaténer toutes les possibilités [2]: def Luka_rec(n): if n==1: return [[-1]] L=[] for k in range(1,n-1,2): L1=Luka_rec(k) L2=Luka_rec(n-1-k) for u in L1: for v in L2: L.append([1]+u+v) return L QUESTION 1.8 Le problème avec la fonction récursive Luka_rec c’est qu’elle fait des calculs redondants ce qui rend la complexité exponentiel , par exemple pour n=9 on besoin de trouver par exemple les mots de taille 3 et de taille 5, et à son tour pour trouver les mots de taille 5 on a besoin de trouver par exemple les mots de taille 3 et de taille 1, donc les mots de taille de 3 on va les calculer 2 fois, imaginez si n est grand 3 QUESTION 1.9 la solution est de mémoriser les calculs faits ainsi avant de calculer des mots d’une taille donée on vériﬁe si on a déjà effectué les calculs, si oui on a pas besoin de recalculer. [3]: dico={1:[[-1]]} def Luka_rec_PD(n): if n==1: return dico[n] L=[] for k in range(1,n-1,2): if k in dico: L1=dico[k] else: L1=Luka_rec(k) dico[k]=L1 if n-1-k in dico: L2=dico[n-1-k] else: dico[n-1-k]=Luka_rec(n-1-k) L2=dico[n-1-k] for u in L1: for v in L2: L.append([1]+u+v) return L QUESTION 1.10 [4]: def conjugue_1(u): for i in range(len(u)): if estLukasiewicz(u[i+1:]+u[:i+1]): return u[i+1:]+u[:i+1] QUESTION 1.11 [ ]: def conjugue_2(u): n=len(u) min=n+1 p=-1 s=0 for i in range(n): s+=u[i] if s<min: min=s p=i return u[p+1:]+u[:p+1] 4 QUESTION 1.12 Soit un mot u de Lukasiewicz tel que |u| = n pour la fonction conjugue_1 la boucle for fait O(n) itérations au pire des cas et la coût de la fonction estLukasiewicz est O(n) donc le coût total est de O(n)xO(n)=O(n2) pour la fonction conjugue_2 la boucle for fait O(n) itérations pour chercher l’indice tel que la somme soit minimale puis après le return a un coût de O(n) le coût de la concaténation donc le coût total est O(n)+O(n)=O(n) D’où on conclut que conjugue_2 est plus efﬁcace que conjugue_1 QUESTION 1.13 [ ]: def rho(u): n=len(u) for i in range(n-2): if u[i:i+3]==[1,-1,-1]: return u[:i]+u[i+2:] return u QUESTION 1.14 [ ]: def rholim(u): v=rho(u) while(u!=v): u=v v=rho(u) return v QUESTION 1.15 Montrons que tout mot de Lukasiewicz de longueur ≥3 contient au moins une capsule. Procédons par récurrence cas de base : pour n =3, le seul mot de Lukasiewicz de longueur 3 est [+1,-1,-1] et il se voit bien qu’il contient une capsule induction: Supposons que le propriété est vraie tous les mots de Lukasiewicz de longueur 3 ≤k ≤n tel que n est impair Soit un mot w de Lukasiewicz de taille n+2 ( il ne peut pas exister un mot de Lukasiewicz de taille n+1 car n+1 est pair et d’après la question 1.2 il n’existe aucun mot de taille paire) D’après la question 1.5 w une décomposition unique de la forme (+1).u.v, où u et v sont des mots de Lukasiewicz. Et certainement l’un des mots u et v, sa taille est comprise entre 3 et n, alors d’après l’hypothèse de récurrence il contient une capsule donc le mot w contient une capsule 5 QUESTION 1.16 : Soit u = [u1, ..., un] • cas 1 : Si ρ(u) = u, alors l’équivalence est évidente • cas 2 : Si ρ(u) = [u_1, . . . u_{i −1}, u_{i + 2}, . . . , u_n] Supposons que u est un mot de Lukasiewicz *) p(ρ(u)) = p([u1, ...ui−1, ui+2, ..., un]) = p(u) −p(ui) −p(ui+1) = −1 −1 −(−1) = −1, donc la première propriété est vériﬁée *) soit u’ un préﬁxe strict de p(ρ(u)), • si |u’|<i, alors u’ est préﬁxe strict aussi de u donc p(u’)≥0 • sinon donc u’=[u1, ...ui−1, ui+2, ..., uk], soit u“= [u1, ..., uk], u” est préﬁxe strict de u alors p(u“)≥0 et on a p(u’)=p(u”)-p(ui)-p(ui+1)=p(u“)-1-(-1)=p(u”), donc p(u’)≥0 Alors la deuxième propriété est vériﬁée D’où on conclut que ρ(u) est un mot de Lukasiewicz La réciproque se montre de uploads/s3/ corrige-entree-septembre-2019.pdf