J-0
00m
00j
00h
00min
00s

Version interactive avec LaTeX compilé

Télécharger PDF

ENS Informatique MP 2009

Notez ce sujet en cliquant sur l'étoile
0.0(0 votes)
Logo ens
🔗 Explorer
Banque
X-ENS
Année
2009
Filière
MP
Matière
Info
X-ENS MPX-ENS 2009MP InfoInfo 2009
2025_08_29_584da1cd8836acdbf2d0g

Filière MP (groupe I)
Épreuve commune aux ENS de Paris, Lyon et Cachan

INFORMATIQUE

Durée : 4 heures
L'usage de calculatrices électroniques de poche n'est pas autorisé.

Rotations et repliages de mots

Ce problème s'intéresse à diverses propriétés des mots soumis à des rotations et des repliages, ainsi qu'à certains algorithmes relatifs à ces transformations de mots.
Les deux parties sont indépendantes, ainsi que dans une certaine mesure les différentes sous-sections. Les questions non traitées peuvent être admises pour aborder les questions ultérieures.
La qualité de la rédaction ainsi que les justifications (corrections des algorithmes, complexités) seront des éléments d'appréciations. Il est également rappelé que les schémas ne sauraient à eux seuls tenir lieu de justification, mais qu'ils peuvent constituer une aide appréciable à la compréhension de la situation décrite et des notations employées.

Préliminaires

Conventions sur les mots.

On considère un alphabet , c'est-à-dire un ensemble fini non vide, que l'on munit d'un ordre total < sur les lettres de cet alphabet. Un certain nombre de questions utiliseront un alphabet particulier à deux éléments , muni de l'ordre suivant sur les lettres : . Pour les questions mentionnant l'écriture binaire d'un nombre entier, l'alphabet servira à noter les chiffres d'une telle écriture binaire.
Un mot formé sur l'alphabet est une suite d'éléments de indicée soit par (pour un mot infini), soit par une partie de de la forme (pour un mot fini). On note (respectivement ) l'ensemble des mots infinis (respectivement finis) formés sur l'alphabet . Pour tout mot fini ou infini, désignera la -ème lettre de ce mot (en numérotant à partir de 0 ). À partir de maintenant, tous les mots seront considérés finis sauf mention explicite du contraire.
Le mot vide sera noté . On note la longueur d'un mot. Pour deux mots et , on note le mot obtenu par concaténation de et . Cette opération est associative et admet comme élément neutre (autrement dit, muni de cette opération est un monoïde).
Un mot est un préfixe d'un autre mot s'il existe un mot tel que . Un début de est un préfixe de distinct de et de . Similairement, un mot est un suffixe de lorsqu'il existe un mot tel que , et une fin de est un suffixe distinct de et de . On notera respectivement , Fin les ensembles de préfixes, de débuts, de suffixes et de fins du mot .

Algorithmes et complexité.

Pour les questions demandant l'écriture d'un algorithme en pseudo-code, on utilisera un langage ou pseudo-langage au choix, avec les structures usuelles de données (tableaux, listes, etc.) et de contrôle (si, tant que, pour, etc.). Les calculs de complexité comptabiliseront le nombre d'opérations élémentaires effectuées dans le cas le pire : lecture ou écriture dans une variable ou une case de tableau, ajout ou suppression en tête de liste, opération arithmétique de base, etc. Sauf mention contraire, on ne cherchera pas à estimer les complexités exactement, mais seulement à en donner un ordre de grandeur en utilisant la notation asymptotique . Les indices d'un tableau de taille vont de 0 à , et ses éléments sont notés . Un tableau peut être de taille 0 . On dispose d'une primitive Longueur de complexité 1 retournant la taille d'un tableau, et d'une primitive CONCAT de complexité linéaire en ses arguments prenant deux tableaux en entrée et retournant un nouveau tableau formé par leur concaténation. La représentation des mots par des tableaux est encouragée, mais l'usage d'autres représentations est autorisé tant que cela ne pénalise pas les complexités obtenues.

Partie 1 : Rotation de mots et minimalité

Ordre lexicographique sur les mots. À partir de l'ordre total < sur les lettres de l'alphabet, on obtient un ordre sur les mots comme suit :
  • Pour deux mots et , on note lorsqu'il existe un entier naturel tel que et , ainsi que pour tout .
  • On note ensuite lorsque ou .
  • Enfin lorsque ou .
On parlera d'ordre lexicographique (strict ou large) pour ces relations et sur les mots.
Question 1.1 Montrer que la relation est une relation d'ordre totale sur les mots. Admet-elle de plus petit et de plus grand élément? Écrire en pseudo-code un algorithme EstPlusPetit prenant en argument deux mots et et déterminant si . Donner sa complexité.
Rotation et minimalité. Un mot est une rotation d'un autre mot lorsqu'il existe deux autres mots non-vides et tels que et . Un mot sera dit minimal s'il est non-vide et que pour toute rotation de . On remarquera en particulier qu'un mot de longueur 1 est minimal.

1.1 Tests de minimalité

Question 1.2 Écrire en pseudo-code un algorithme EstMinimal1 testant si un mot est minimal. Justifier sa correction et donner sa complexité.
Question 1.3 Soit u un mot tel que . Montrer que ne peut être minimal. Cette propriété suffit-elle à caractériser les mots non-minimaux?
Question 1.4 Montrer qu'un mot non-vide u est minimal si et seulement si toute fin de est telle que .
Question 1.5 En utilisant cette caractérisation, écrire en pseudo-code un algorithme EstMinimal2 qui teste si un mot u est minimal. Par rapport à EstMiNIMAL1, déterminer le gain en nombre de comparaisons de lettres nécessaires dans le cas le pire.

1.2 Énumération des mots minimaux

Question 1.6 Montrer que l'ordre restreint aux mots minimaux admet un plus petit élément et un plus grand.
Pour , on appelle -minimal tout mot minimal de longueur inférieure ou égale à , et on note le nombre de mots -minimaux.
Question 1.7 Soient et deux mots minimaux tels que . Montrer alors que vw est également minimal.
Question 1.8 Réciproquement, pour un mot u minimal tel que , prouver l'existence de deux mots minimaux et tels que et .
Question 1.9 À l'aide des questions précédentes, écrire en pseudo-code un algorithme EnumMinimaux prenant en entrée la liste des lettres de l'alphabet dans l'ordre, ainsi que l'entier , et retournant en sortie la liste de tous les mots minimaux dans l'ordre lexicographique. Justifier la correction de EnumMinimaux et donner sa complexité.
Pour le reste de cette section, on utilise l'alphabet .
Question 1.10 Calculer alors pour . Montrer que tous les mots minimaux de longueur au moins 2 partagent la même première lettre, ainsi que la même dernière lettre. Pour , prouver l'encadrement suivant : .
Il existe en fait un algorithme direct permettant de passer d'une étape dans l'énumération des -minimaux à l'étape suivante :
MinimalSuivant(entiers $n$ et $m$, tableau $T$ de taille $n$ )
    $\triangleright$ Les $m$ premières cases de $T$ doivent former un mot $n$-minimal $u \neq b$
    Pour $i \leftarrow m$ à $n-1$ Faire
        $T[i] \leftarrow T[i$ modulo $m]$
    Fin Pour
    $p \leftarrow n-1$
    Tant Que $T[p]=b$ Faire
        $p \leftarrow p-1$
    Fin Tant Que
    $T[p] \leftarrow b$
    Retourner $p+1$
    $\triangleright$ Les $p+1$ premières cases de $T$ forment maintenant le mot
    $n$-minimal qui suit $u$
Question 1.11 Montrer que toute utilisation de MinimalSuivant conforme aux conditions de la ligne 1 termine en retournant un entier tel que . Déterminer la complexité de MinimalSuivant.
Question 1.12 Pour et un mot -minimal différent de , montrer que MinimalSuivant permet bien d'obtenir un mot -minimal , puis montrer que est le mot n-minimal le plus petit (au sens de ) tel que .

1.3 Factorisation en mots minimaux

Soit un mot non-vide. Une factorisation minimale de est une suite finie de mots minimaux tels que et pour tout .
Question 1.13 Écrire en pseudo-code un algorithme Factorise permettant d'obtenir une factorisation minimale de u. On pourra partir d'une décomposition de en mots minimaux et faire progressivement évoluer cette décomposition vers une factorisation minimale. Déterminer la complexité de Factorise
Question 1.14 Démontrer que tout mot non-vide possède une unique factorisation minimale.

Partie 2 : Repliage de mots

Pour une lettre de l'alphabet , on appelle renversement de la lettre telle que et . On étend cette opération de renversement à tout mot sur l'alphabet de la manière suivante:
  • .
  • pour toute paire d'entiers naturels et tels que .
On s'intéresse désormais à une suite particulière de mots sur l'alphabet , que l'on appellera suite des repliages. Cette suite est définie de la manière suivante :
Question 2.1 Écrire en pseudo-code une procédure NiemeRepliage prenant en entrée un entier et retournant le mot . Donner la complexité de cette procédure.

2.1 Une caractérisation alternative

Question 2.2 Montrer que pour tout entier , le mot est exactement constitué des lettres d'indices impaires du mot (prises de gauche à droite). Montrer également que les lettres d'indices pairs de sont une alternance de a et de b. En déduire une procédure NiemeRepliageBis basée sur ces constatations et produisant le même résultat que NiemeRepliage.

2.2 Repliages infinis

Chaque étant un début du mot suivant , il existe alors un mot infini dont tous les sont des préfixes : on peut par exemple le définir via la relation pour tout entier .
Question 2.3 À l'aide de la question précédente, écrire en pseudo-code un algorithme RepliageInfini calculant directement en fonction de sans passer par le calcul complet des . Quelle est la complexité de RepliageInfini?
Pour les trois prochaines questions, on considère l'alphabet . On identifie tout entier naturel avec le mot sur l'alphabet correspondant à l'écriture binaire de . Pour la question qui vient, les bits de poids faibles sont placés à gauche. Par exemple, le nombre 6 correspond au mot 011 , tandis que le nombre 0 correspond au mot vide.
Question 2.4 Dessiner un automate fini déterministe (de transitions étiquetées par 0 et 1) acceptant précisément les mots correspondant aux entiers i tels que . Justifier brièvement la correction de cet automate.
On suppose désormais que la représentation des nombres se fait avec les bits de poids faibles à droite (6 correspond maintenant à 110).
Question 2.5 Dessiner et justifier brièvement l'automate fini déterministe correspond à cette nouvelle situation.
Pour la question suivante, on fixe une certaine longueur , et l'on considère des entiers -bornés : est -borné si et seulement si . Une fois choisi un ordre sur les bits, un nombre -borné peut être identifié avec un mot sur de longueur . Par exemple, pour et les bits de poids faibles à droite, le nombre 6 correspond au mot 00000110 . On suppose disposer de plus des opérations primitives suivantes sur ces entiers -bornés :
  • incr : ajout de 1 modulo à un nombre -borné
  • double : doublement modulo d'un nombre -borné
  • non : inversion de tous les bits d'un nombre -borné
  • et : calcul du "et" bit-à-bit de deux nombres -bornés
  • estnul : vérification de la nullité d'un nombre -borné
On notera que ces définitions sont indépendantes du choix de l'ordre des bits.
Question 2.6 En composant les seules primitives précédentes, comment peut-on obtenir une fonction qui pour tout nombre -borné i détermine si ou non? On pourra tout d'abord chercher à construire le nombre ayant un bit 1 à l'emplacement du 0 de plus faible poids dans i (s'il existe), et des bits 0 partout ailleurs.

2.3 Repliages et géométrie

Soit la fonction qui à la lettre associe le nombre complexe et à la lettre associe . À partir de , on définit une suite de points du plan complexe comme suit :
On s'intéresse désormais aux propriétés de la courbe obtenue en reliant les points successifs de cette suite.
Question 2.7 On suppose donnée une primitive TraceLigne prenant les coordonnées cartésiennes et des extrémités d'un segment à afficher. Écrire en pseudo-code un algorithme TraceCourbe qui pour un entier trace la courbe jusqu'au point .
Question 2.8 Soit une puissance de deux. Déterminer quelle transformation géométrique permet d'obtenir la portion de comprise entre et à partir de celle comprise entre et .
Question 2.9 Montrer qu'il existe une similitude qui pour tout entier envoie sur . En déduire en particulier que pour tout entier , si alors .
On appelle point de contact de la courbe tout point pour lequel il existe deux indices tels que . De tels points de contact existent, par exemple .
Question 2.10 Soit un point de contact avec . Montrer que et sont de même parité. En déduire que si est non nul, alors .
Question 2.11 Soit un point de contact avec . Montrer que et sont non nuls et que les segments et sont les diagonales d'un carré de centre .
Question 2.12 En déduire qu'un segment de la courbe ne peut apparaître qu'une unique fois, et que ne passe qu'au plus deux fois par un point donné.
*
Note historique. Les mots minimaux de la partie 1 sont également appelés mots de Lyndon. L'algorithme MinimalSuivant a été conçu par Duval en 1988. En 1992, Berstel et Pocchiola ont établi que le coût moyen de MinimalSuivant est constant : visiter successivement tous les mots -minimaux via utilisations de cet algorithme a un coût proportionnel à (on ne compte pas ici d'actions de sauvegarde ou d'affichage des mots -minimaux rencontrés lors de ces itérations). Duval a par ailleurs proposé également un algorithme permettant d'effectuer la factorisation minimale d'un mot en temps linéaire, ce qui permet également de résoudre la question du test de minimalité en temps linéaire.
La courbe de la partie 2 est nommée courbe du Dragon ou courbe de HarterHeighway. Un article de Martin Gardner dans le Scientific American l'a fait plus largement connaître en 1967. Cette courbe fractale possède de nombreuses propriétés d'autosimilarité et de pavage du plan. À noter qu'il est possible de fabriquer son début simplement : il suffit de replier en deux une bande de papier plusieurs fois, toujours dans le même sens, puis d'ouvrir chaque pli à angle droit.
ENS Informatique MP 2009 - Version Web LaTeX | WikiPrépa | WikiPrépa