Remerciez-le!

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

Epreuveif copie Problème I Mots de Lukasiewicz Dans ce problème les mots considérés sont pris sur l ? alphabet ?? On appelle mots de Lukasiewicz toute suite ?nie u u u un à valeurs dans ?? qui véri ?e les deux propriétés suivantes n p u ui ?? et i k ui ?

Problème I Mots de Lukasiewicz Dans ce problème les mots considérés sont pris sur l ? alphabet ?? On appelle mots de Lukasiewicz toute suite ?nie u u u un à valeurs dans ?? qui véri ?e les deux propriétés suivantes n p u ui ?? et i k ui ? pour ? k ? n ?? i ?? On notera avec un point la concaténation de deux mots par exemple a b ?? Par la suite les mots de Lukasiewicz seront représentés en python par le type ? list ? ?? On désigne par u la taille longueur d ? un mots u Quelques propriétés Question Donner tous les mots de Lukasiewicz de longueur ? Question Prouver qu ? il n ? existe aucun mot de Lukasiewicz de taille paire Indication Utiliser un raisonnement par absurde Question Écrire une fonction estLukasiewicz qui renvoie True si un mot est de Lukasiewicz et puis donner sa complexité Question Montrer que si u et v sont des mots de Lukasiewicz alors u v est un mot de Lukasiewicz C Question Réciproquement montrer que tout mot w de Lukasiewicz de longueur supérieure ou égale à admet une décomposition unique de la forme u v o? u et v sont des mots de Lukasiewicz Indication Justi ?er que w w et considérer u le plus petit pré ?xe strict de w véri ?ant p u ?? Question Écrire une fonction decompose qui associe ce couple u v à un mot de Lukasiewicz de longueur supérieure ou égale à On ne demande pas de traiter les cas o? le mot fourni en entrée ne serait pas de Lukasiewicz Question En exploitant le résultat de la question écrire une fonction récursive Lukarec qui permet de renvoyer une liste de tous les mots de Lukasiewicz de taille n donné Question Justi ?er pourquoi cette solution récursive imposerait un coût de calcul exponentiel Question Proposer une autre solution plus e ?cace que la précédente Question Soit u u u un un mot tel que u un ?? Il existe un unique entier i ?? n tel que ui un u ui ?? ui soit un mot de Lukasiewicz Ce mot est appelé le conjugué de u Écrire une fonction conjugue qui calcule le conjugué d ? un mot u Question Soit u u u un un mot tel que u un ?? et soit i le plus petit des entiers i ?? n pour lesquels u ui est minimal alors le mot ui un u ui ?? ui est un mot de Lukasiewicz Écrire une fonction conjugue qui calcule le conjugué d ? un mot u en utilisant cette propriété sur l ? entier i Exemple Soit u ?? ?? ?? on a u u ?? i i i i i u u u u u u ?? u u u u u u u u u ?? Donc le plus petit des entiers pour lesquels u ui est minimal est i D ? o? le conjugué de