SESSION 2019 MPIN007 ÉPREUVE SPÉCIFIQUE - FILIÈRE MP ____________________ INFORMATIQUE 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. 1/8 -- 1 of 8 -- Partie I - Inversions de permutations (Informatique pour tous) Pour tout n ∈ N\{0}, une permutation de taille n est une bijection de l’ensemble {0, 1, · · · , n − 1} dans lui-même. Dans la suite, l’ensemble des permutations de taille n est noté Sn. Étant donné une permutation σ de taille n, on la représente sous la forme σ0σ1 · · · σn−1 où : ∀i ∈ {0, · · · , n − 1}, σi = σ(i). Par exemple, σ = 1032 représente la permutation envoyant 0 sur 1, 1 sur 0, 2 sur 3 et 3 sur 2. Soit σ = σ0 · · · σn−1 une permutation de taille n. On dit que (i, j) ∈ {0, 1, · · · , n − 1}2 est une inversion de σ si σi > σj et i < j. On note inv(σ) 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 n est représentée en Python par une liste sans répétition conte- nant tous les entiers compris entre 0 et n−1. Par exemple, la liste [1, 0, 3, 2] représente la permutation σ = 1032. Si A est un ensemble fini, Card(A) désigne le cardinal de l’ensemble A. Pour tout entier n ≥ 1, on pose E n = Πn k=1{0, 1, · · · , n − k}. Par exemple, on a E3 = {0, 1, 2} × {0, 1} × {0}. I.1 - Tri et inversions Q1. Déterminer l’ensemble des inversions de la permutation σ = 140253. 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] 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. 1. aabfa 2. abfdanq 3. ababa 4. avba. Q22. Soit w un mot contenant au plus deux lettres différentes. Montrer que si |w| ≥ 4 alors w contient au moins une répétition. Q23. Écrire une fonction Caml de signature estCarre : ’a list -> bool prenant en argument une liste w et retournant true si w 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 w et un entier m et retournant true si w contient une répétition de la forme xx avec x de longueur m et false sinon. Q26. Montrer que toute répétition d’un mot w de longueur n est de la forme xx avec |x| ≤ n 2. Q27. En déduire une fonction Caml de signature contientRepetition : ’a list -> bool prenant en argument une liste w retournant true si w 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 w. Il comporte essentiellement deux parties : — la première consiste à voir si étant donné deux mots u et v, le mot uv 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 uv contient une répétition si et seulement si u ou v contiennent une répétition ou uv contient des répétitions provenant de la concaténation. Pour déterminer si un mot uv contient de nouvelles répétitions, on commence par effectuer des prétraitements consistant à calculer des tables de valeurs de u et de v 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 u et v deux mots. On dit que uv contient un carré centré sur u (respectivement sur v) s’il existe un mot w non vide et des mots u′, v′′, w′, w′′ tels que u = u′ww′, v = w′′v′′, w = w′w′′ (respectivement u = u′w′, v = w′′wv′′, w = w′w′′). 6/8 -- 6 of 8 -- Définition 14 (Plus long préfixe commun, plus long suffixe commun). Soient u et v deux mots de Σ. Le plus long préfixe (respectivement suffixe) commun de u et v est le plus long mot w tel qu’il existe deux mots r et s tels que u = wr et v = ws (respectivement u = rw et v = sw). On le note lcp(u, v) (respectivement lcs(u, v)). À propos des carrés centrés Q29. Dans cette question, Σ = {a, b}. Soient u = abababaa et v = ababaaa. Déterminer le plus grand préfixe commun de u et v. Q30. Soient u et v deux mots de Σ. Montrer que uv contient un carré centré sur u si et seulement s’il existe i ∈ {0, · · · , |u| − 1} tel que ∣∣∣lcs(u[0, i − 1], u)∣∣∣ + ∣∣∣lcp(u[i, |u| − 1], v)∣∣∣ ≥ |u| − i. De la même manière, on peut montrer que uv contient un carré centré sur v si et seulement s’il existe j ∈ {1, · · · , |v| − 1} tel que ∣∣∣lcs(v[0, j − 1], u)∣∣∣ + ∣∣∣lcp(v, v[ j, |v| − 1])∣∣∣ ≥ |v| − j. Ainsi, pour pouvoir déterminer s’il existe un carré centré sur u ou v, on peut utiliser les valeurs : ∣∣∣lcs (u [0, i − 1] , u) ∣∣∣, ∣∣∣lcp(u[i, |u| − 1], v)∣∣∣ , ∣∣∣lcs (v[0, j − 1], u) ∣∣∣, ∣∣∣lcp(v, v[ j, |v| − 1])∣∣∣ . Dans la suite, étant donné deux mots u et v, on note prefu, prefu,v, suffu et suffu,v les tableaux vérifiant : ∀i ∈ {0, · · · , |u| − 1}, prefu[i] = ∣∣∣lcp(u[i, |u| − 1], u)∣∣∣, prefu,v[i] = ∣∣∣lcp(u[i, |u| − 1], v)∣∣∣ suffu[i] = ∣∣∣lcs(u[0, i], u)∣∣∣, suffu,v[i] = ∣∣∣lcs(u[0, i], v)∣∣∣. Calcul de table de préfixes On présente un algorithme permettant le calcul de la table prefu 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 prefu,v en O(|u|) de comparaisons de caractères. Q31. On pose u = aabbba et v = abbaab. Déterminer les tableaux prefu et prefu,v sans justification. Q32. En déroulant l’algorithme 2 de la page suivante appliqué au mot u = aaabaaabaaab, complé- ter le tableau i = f g pref[i] 0 _ 0 12 1 1 3 2 2 · · · ... ... ... ... 11 4 12 0 de la façon suivante : pour une valeur i donnée, on indique les valeurs de f, g, pref[i] à l’issue des instructions internes de la boucle. Par exemple, à l’initialisation, i = 0, f n’est pas définie, g vaut 0 et pref[0] = 12. Pour i = 1, à l’issue des instructions internes à la boucle, on a f = 1, g = 3, pref[1] = 2. 7/8 -- 7 of 8 -- Q33. Déduire de l’algorithme 2 une procédure calculant suffu. Dans la suite, on suppose que l’algorithme tabpref(u,v) qui prend en argument deux chaînes de caractères u et v et qui renvoie la table prefu,v nous est donné. On admet que la complexité de cet algorithme est de O(|u|) en nombre de comparaisons de caractères. Q34. Déduire des questions précédentes un algorithme qui, étant donnés deux mots u et v, renvoie VRAI s’il existe un carré centré sur u 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 prefu Entrées : une chaîne de caractères u Sorties : un tableau prefu i ← 0, pref ← tableau de taille |u| initialisé à 0, pref[i] ← |u|, g ← 0 pour i allant de 1 à |u| − 1 faire si i < g et pref[i − f ] < g − i alors pref[i] ← pref[i − f ] fin sinon si i < g et pref[i − f ] > g − i alors pref[i] ← g − i fin sinon ( f, g) ← (i, max(g, i)) tant que g < |u| et u[g] == u[g − f ] faire g ← g + 1 fin pref[i] ← g − f fin fin On admet que la complexité est de O(|u|) en nombre de comparaisons de caractères. FIN 8/8 I M P R I M E R I E N A T I O N A L E – 19 1149 – D’après documents fournis -- 8 of 8 --