Jeudi 2 mai: 14 h-18 h
N.B. : le candidat attachera la plus grande importance à la clarté, à la précision et à la concision de la rédaction. Si un candidat est amené à repérer ce qui peut lui sembler être une erreur d'énoncé, il le signalera sur sa copie et devra poursuivre sa composition en expliquant les raisons des initiatives qu'il a été amené à prendre.
Les calculatrices sont interdites
Le sujet est composé de trois parties indépendantes.
Partie I - Inversions de permutations (Informatique pour tous)
Pour tout , une permutation de taille est une bijection de l'ensemble dans lui-même. Dans la suite, l'ensemble des permutations de taille est noté . Étant donné une permutation de taille , on la représente sous la forme où :
Par exemple, représente la permutation envoyant 0 sur 1,1 sur 0,2 sur 3 et 3 sur 2 .
Soit une permutation de taille . On dit que est une inversion de si et . On note le nombre d'inversions de . Tout d'abord, on relie ce nombre avec un algorithme de tri : le tri à bulles. Puis, on s'intéresse à la table d'inversions d'une permutation, un objet qui caractérise une permutation.
Dans la suite, une permutation de taille est représentée en Python par une liste sans répétition contenant tous les entiers compris entre 0 et . Par exemple, la liste représente la permutation .
Si est un ensemble fini, désigne le cardinal de l'ensemble . Pour tout entier , on pose . Par exemple, on a .
I. 1 - Tri et inversions
Q1. Déterminer l'ensemble des inversions de la permutation .
On rappelle l'algorithme de tri à bulles :
Algorithme 1 - Tri à bulles
Entrées: Une liste d'entiers L
pour $i$ allant de (taille de $L$ )-1 à 1 (bornes incluses) faire
pour $j$ allant de (taille de L)-1 à (taille de L)-i (bornes incluses) faire
si $L[j]<L[j-1]$ alors
Echanger L[j] et L[j-1]
fin
fin
fin
Q2. Écrire une fonction Python tri_bulle(L) qui prend en argument une liste d'entiers L et qui trie cette liste à l'aide du tri à bulles. À l'issue de la fonction, la liste est triée.
Dans la suite, on admet que l'algorithme du tri à bulles est bien un algorithme de tri.
Q3. Montrer que si on effectue exactement un échange dans une liste lors du tri à bulles, la nouvelle liste a exactement une inversion en moins.
Q4. En déduire une fonction Python nombre_inversions(L) qui prend en argument une liste L correspondant à une permutation et renvoyant le nombre d'inversions de celle-ci. Cette fonction sera une légère modification du tri à bulles.
I. 2 - Table d'inversions d'une permutation
Définition 1 (Table d'inversions). Soit une permutation de taille . La table d'inversions de est le -uplet tel que :
Elle est notée . De plus, pour tout désigne .
Pour tout , on désigne par Tab : l'application qui associe à une permutation de taille sa table d'inversions.
Q5. Déterminer la table d'inversions de la permutation .
Q6. Montrer que pour toute permutation de taille est bien un élément de .
Q7. Soit une permutation de taille . Montrer que .
Q8. Montrer que pour tout entier , l'application Tab est bijective.
Q9. Écrire une fonction Python permutation_vers_table(L) qui prend en argument une permutation représentée par la liste L et qui renvoie la table d'inversions correspondante.
Q10. Écrire une fonction Python table_vers_permutation(L) qui prend en argument une liste L qui correspond à une table d'inversions et qui renvoie la permutation qui lui est associée.
Partie II - Théorie des automates et des langages rationnels
Dans toute cette partie, la lettre désigne le mot vide, désigne un alphabet et l'ensemble des mots finis sur .
II. 1 - Définitions
Définition 2 (Automate déterministe). Un automate déterministe est un quintuplet , avec :
un ensemble d'états; un alphabet;
l'état initial ;
un ensemble d'états finaux; une application de transition.
Définition 3 (Langage). Un langage sur est une partie de .
Définition 4 (Application de transition étendue aux mots). Soit un automate déterministe. On définit de manière récursive par :
Cette application vérifie alors la propriété admise suivante :
Définition 5 (Langages rationnels). On rappelle que les langages rationnels sont définis de manière inductive par:
l'ensemble est un langage rationnel;
les langages où est une lettre, sont rationnels;
si et sont des langages rationnels, sont des langages rationnels;
si est un langage rationnel, est un langage rationnel.
Définition 6 (Carré d'un langage). Soit un langage sur . Le carré du langage est l'ensemble . Il est noté .
Définition 7 (Racine carrée d'un langage). Soit un langage sur . La racine carrée du langage est l'ensemble . Elle est notée .
On pourra utiliser sans démonstration le théorème ci-dessous :
Théorème 1. Soit un langage. Il est rationnel si et seulement s'il existe un automate déterministe et fini le reconnaissant.
Dans la suite, on décrit un langage rationnel par une expression rationnelle.
II. 2 - Racine carrée d'un langage
Exemples
Q11. Décrire lorsque et est décrit par l'expression rationnelle .
Q12. Décrire lorsque et est décrit par l'expression rationnelle .
Construction d'automates
Définition 8. Soient un automate fini déterministe, un élément de et une partie de . L'automate ( ) est noté . Si on note le langage reconnu par désigne le langage reconnu par .
Ici, désigne le langage reconnu par l'automate suivant :
Q13. Construire un automate reconnaissant en modifiant légèrement l'automate .
Q14. On veut construire l'automate de Glushkov de décrit par .
Décrire , le linéarisé de .
Déterminer les préfixes de de longueur 1 , les suffixes de de longueur 1 et les facteurs de de longueur 2.
En déduire l'automate de Glushkov de .
Q15. Déterminiser l'automate .
Propriétés de la racine carrée d'un langage rationnel
Ici, on fixe un langage rationnel sur un alphabet et un automate fini reconnaissant celui-ci.
Q16. Soit un mot de . Montrer que est un élément de si et seulement s'il existe un tel que et .
Q17. En déduire que est un langage rationnel.
Q18. Montrer que l'on a .
Partie III - Algorithmique des mots sans facteur carré
L'objectif de cette partie est de construire différents algorithmes pour vérifier si un mot comporte des facteurs carrés ou non.
Dans toute la suite, désigne un alphabet totalement ordonné comportant lettres, représente le mot vide et est l'ensemble des mots finis obtenus à partir de . Pour tout réel , on note la partie entière de .
III. 1 - Définitions
Définition 9 (Longueur d'un mot). Soit un mot de . La longueur de est notée , pour tout désigne le mot . Par convention, si désigne .
Définition 10 (Mot carré). Soit un mot de . On dit que est un carré s'il existe un mot tel que .
Définition 11 (Facteur d'un mot). Soient et deux mots de . On dit que est un facteur de s'il existe et deux mots (éventuellement vides) tels que .
Définition 12 (Répétition). On dit qu'un mot contient une répétition s'il contient un facteur carré différent de .
Dans la suite, un mot sera représenté en Caml par la liste de ses lettres. Par exemple, le mot baba est représenté par la liste [ ; ; ] et le mot vide est représenté par la liste [ ].
III. 2 - Fonctions utiles sur les listes
Q19. Écrire une fonction récursive Caml de signature longueur : 'a list -> int qui renvoie la longueur de la liste.
Q20. Écrire une fonction Caml de signature sous_liste : 'a list->int->int->'a list où sous_liste L k long renvoie une liste S qui est la sous-liste de L commençant à l'indice k et de longueur long. On suppose que l'indexation des listes commence à 0 .
On pourra dans la suite de l'énoncé utiliser les fonctions longueur et sous_liste.
III. 3 - Un algorithme naïf
Q21. Préciser si les mots suivants contiennent ou non une répétition.
abfdanq
ababa
.
Q22. Soit un mot contenant au plus deux lettres différentes. Montrer que si alors contient au moins une répétition.
Q23. Écrire une fonction Caml de signature estCarre : 'a list -> bool prenant en argument une liste et retournant true si est un carré et false sinon.
Q24. Déterminer la complexité en nombre de comparaisons de lettres de la fonction estCarre.
Q25. Écrire une fonction Caml de signature contientRepetitionAux : 'a list->int->bool prenant en argument une liste et un entier et retournant true si contient une répétition de la forme avec de longueur et false sinon.
Q26. Montrer que toute répétition d'un mot de longueur est de la forme avec .
Q27. En déduire une fonction Caml de signature contientRepetition : 'a list -> bool prenant en argument une liste retournant true si contient une répétition et false sinon.
Q28. Quelle est la complexité en nombre de comparaisons de caractères de la fonction contientRepetition?
III. 4 - Algorithme de Main-Lorentz
L'algorithme de Main-Lorentz permet de détecter de manière plus efficace des répétitions d'un mot . Il comporte essentiellement deux parties :
la première consiste à voir si étant donné deux mots et , le mot contient un carré non nul issu de la concaténation ;
la deuxième s'appuie sur le principe de "diviser pour régner".
Remarquons qu'un mot contient une répétition si et seulement si ou contiennent une répétition ou contient des répétitions provenant de la concaténation. Pour déterminer si un mot contient de nouvelles répétitions, on commence par effectuer des prétraitements consistant à calculer des tables de valeurs de et de qui sont généralement appelées tables de préfixes (ou suffixes). Avant de présenter des algorithmes permettant de générer ces tables, on commence par justifier leur application dans la détection de répétitions.
Définition 13 (Carré centré). Soient et deux mots. On dit que contient un carré centré sur (respectivement sur ) s'il existe un mot non vide et des mots tels que , (respectivement ).
Définition 14 (Plus long préfixe commun, plus long suffixe commun). Soient et deux mots de . Le plus long préfixe (respectivement suffixe) commun de et est le plus long mot tel qu'il existe deux mots et tels que et (respectivement et ). On le note (respectivement lcs( )).
À propos des carrés centrés
Q29. Dans cette question, . Soient abababaa et . Déterminer le plus grand préfixe commun de et .
Q30. Soient et deux mots de . Montrer que contient un carré centré sur si et seulement s'il existe tel que .
De la même manière, on peut montrer que contient un carré centré sur si et seulement s'il existe tel que .
Ainsi, pour pouvoir déterminer s'il existe un carré centré sur ou , on peut utiliser les valeurs :
Dans la suite, étant donné deux mots et , on note et suff les tableaux vérifiant :
Calcul de table de préfixes
On présente un algorithme permettant le calcul de la table pref ainsi que sa complexité en nombre de comparaisons de caractères en page 8. En adaptant cet algorithme, il est également possible de calculer la table pref en de comparaisons de caractères.
Q31. On pose et . Déterminer les tableaux pref et pref sans justification.
Q32. En déroulant l'algorithme 2 de la page suivante appliqué au mot aaabaaabaaab, compléter le tableau
0
-
0
12
1
1
3
2
2
11
4
12
0
de la façon suivante : pour une valeur donnée, on indique les valeurs de à l'issue des instructions internes de la boucle.
Par exemple, à l'initialisation, n'est pas définie, vaut 0 et . Pour , à l'issue des instructions internes à la boucle, on a , pref .
Q33. Déduire de l'algorithme 2 une procédure calculant .
Dans la suite, on suppose que l'algorithme tabpref(u,v) qui prend en argument deux chaînes de caractères et et qui renvoie la table pref nous est donné. On admet que la complexité de cet algorithme est de en nombre de comparaisons de caractères.
Q34. Déduire des questions précédentes un algorithme qui, étant donnés deux mots et , renvoie VRAI s'il existe un carré centré sur et FAUX sinon.
Q35. Quelle est la complexité de cet algorithme en nombre de comparaisons de caractères ?
Application des tables
Q36. Déduire des questions précédentes un algorithme récursif qui prend en argument une chaîne de caractères et qui renvoie VRAI si la chaîne contient une répétition et FAUX sinon.
Q37. Déterminer la complexité de cet algorithme en nombre de comparaisons de caractères.
Algorithme 2 - Calcul de la table $\operatorname{pref}_{u}$
Entrées : une chaîne de caractères $u$
Sorties : un tableau $\operatorname{pref}_{u}$
$i \leftarrow 0$, pref $\leftarrow$ tableau de taille $|u|$ initialisé à 0 , pref $[i] \leftarrow|u|, g \leftarrow 0$
pour $i$ allant de 1 à $|u|-1$ faire
si $i<g$ et $\operatorname{pref}[i-f]<g-i$ alors
$\operatorname{pref}[i] \leftarrow \operatorname{pref}[i-f]$
fin
sinon si $i<g$ et $\operatorname{pref}[i-f]>g-i$ alors
$\operatorname{pref}[i] \leftarrow g-i$
fin
sinon
$(f, g) \leftarrow(i, \max (g, i))$
tant que $g<|u|$ et $u[g]==u[g-f]$ faire
$g \leftarrow g+1$
fin
$\operatorname{pref}[i] \leftarrow g-f$
fin
fin
On admet que la complexité est de en nombre de comparaisons de caractères.
FIN
CCINP Option Informatique MP 2019 - Version Web LaTeX | WikiPrépa | WikiPrépa
