Centrale Informatique MP 2008

Thème de l'épreuve Mots de Lukasiewicz, recherche de motifs
Principaux outils utilisés programmation récursive et itérative, dénombrement
Mots clefs Mots de Lukasiewicz, recherche de motifs, alphabet, algorithme de Rabin-Karp

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
              

Rapport du jury

(télécharger le PDF)
     

Énoncé obtenu par reconnaissance optique des caractères


- version du 7 mars 2008 12h26 INFORMATIQUE i=1 Filière MP Soit u = (u1 , . . . , un ) un mot tel que i=1 n X ui = -1. Demontrer qu'il existe i=1 un unique entier i, 1 6 i 6 n, tel que (ui , ui+1 , . . . , un , u1 , . . . , ui-1 ) soit un mot de Lukasiewicz. Ce mot est appele conjugue de u. I.B.2) Ecrire une fonction conjugue qui calcule le conjugue d'un mot u = (u1 , . . . un ) n X verifiant ui = -1. I.B.1) I.B - Denombrement Cette derniere fonction adjonction realise l'adjonction d'une nouvelle cellule en tete de liste (et retournant un pointeur sur ladite cellule). On ne demande pas de l'ecrire. I.A.3) Montrer que si u et v sont des mots de Lukasiewicz, alors (+1) · u · v est un mot de Lukasiewicz. I.A.4) Reciproquement, montrer que tout mot de Lukasiewicz de longueur superieure ou egale a 3 admet une decomposition unique de la forme (+1) · u · v, ou u et v sont des mots de Lukasiewicz. I.A.5) Ecrire une fonction decompose qui associe ce couple (u, v) a un mot de Lukasiewicz de longueur superieure ou egale a 3. En Pascal, on pourra ecrire une procedure qui modifie deux de ses parametres u et v passes par reference. On ne demande pas de traiter les cas ou le mot fourni en entree ne serait pas de Lukasiewicz. I.A.6) On souhaite calculer tous les mots de Lukasiewicz d'une longueur donnee. Comparer les avantages d'une solution recursive appliquant le principe de la decomposition suggere par la question A.4), et celle d'une solution appliquant le meme principe, mais pour laquelle on tabulerait les resultats intermediaires. I.A.7) Ecrire une fonction obtenirLukasiewicz qui calcule la liste des mots de Lukasiewicz de taille inferieure ou egale a un entier donne. En Pascal, on dispose des types et fonction : type ptliste=^liste; liste=record valeur : string; suivant:ptliste end; function adjonction(x:string; pt:ptliste):ptliste; Page 1/3 I.A - Quelques proprietes I.A.1) Donner tous les mots de Lukasiewicz de longueur 1, 2 et 3, puis tous ceux de longueur paire. I.A.2) Ecrire une fonction qui indique si un mot est de Lukasiewicz. Cette fonction renverra une valeur booleenne. La fonction proposee devra imperativement avoir une complexite (en termes d'operations elementaires) en O(n), avec n la longueur du mot d'entree. On note avec un point · la concatenation de deux mots, par exemple a · b. - En Caml, un mot de Lukasiewicz sera represente par une liste d'entiers (int list). - En Pascal, un mot de Lukasiewicz sera represente par une chaine de caracteres (string) composee de symboles '+' (pour +1) et '-' (pour -1). On rappelle les operations suivantes : · acceder au caractere numero i de la chaine c : c[i] (la numerotation commence a 1) ; · obtenir la longueur d'une chaine c : length(c) ; · extraire une chaine d'une sous-chaine : copy(cha^ ine, position, longueur). Par exemple, copy('abcdef', 2, 3) retourne 'bcd' ; · concatener deux chaines ou caracteres c1 et c2 pour obtenir une nouvelle chaine : c1 + c2. On demande d'indiquer le type de toutes les fonctions ecrites, que ce soit en Caml ou en Pascal. i=1 On appelle mots de Lukasiewicz les mots u = (u1 , u2 , . . . , un ) sur cet alphabet qui verifient les deux proprietes suivantes : n k X X ui = -1 et ui > 0 pour 1 6 k 6 n - 1. Dans cette partie, les mots consideres sont pris sur l'alphabet {-1, +1}. Partie I - Mots de Lukasiewicz Les deux parties sont independantes. Le candidat indiquera en tete de sa copie le langage choisi : Caml ou Pascal. Épreuve : Concours Centrale - Supélec 2008 - version du 7 mars 2008 12h26 INFORMATIQUE i=1 Filière MP Soit u = (u1 , . . . , un ) un mot tel que i=1 n X ui = -1. Demontrer qu'il existe i=1 un unique entier i, 1 6 i 6 n, tel que (ui , ui+1 , . . . , un , u1 , . . . , ui-1 ) soit un mot de Lukasiewicz. Ce mot est appele conjugue de u. I.B.2) Ecrire une fonction conjugue qui calcule le conjugue d'un mot u = (u1 , . . . un ) n X verifiant ui = -1. I.B.1) I.B - Denombrement Cette derniere fonction adjonction realise l'adjonction d'une nouvelle cellule en tete de liste (et retournant un pointeur sur ladite cellule). On ne demande pas de l'ecrire. I.A.3) Montrer que si u et v sont des mots de Lukasiewicz, alors (+1) · u · v est un mot de Lukasiewicz. I.A.4) Reciproquement, montrer que tout mot de Lukasiewicz de longueur superieure ou egale a 3 admet une decomposition unique de la forme (+1) · u · v, ou u et v sont des mots de Lukasiewicz. I.A.5) Ecrire une fonction decompose qui associe ce couple (u, v) a un mot de Lukasiewicz de longueur superieure ou egale a 3. En Pascal, on pourra ecrire une procedure qui modifie deux de ses parametres u et v passes par reference. On ne demande pas de traiter les cas ou le mot fourni en entree ne serait pas de Lukasiewicz. I.A.6) On souhaite calculer tous les mots de Lukasiewicz d'une longueur donnee. Comparer les avantages d'une solution recursive appliquant le principe de la decomposition suggere par la question A.4), et celle d'une solution appliquant le meme principe, mais pour laquelle on tabulerait les resultats intermediaires. I.A.7) Ecrire une fonction obtenirLukasiewicz qui calcule la liste des mots de Lukasiewicz de taille inferieure ou egale a un entier donne. En Pascal, on dispose des types et fonction : type ptliste=^liste; liste=record valeur : string; suivant:ptliste end; function adjonction(x:string; pt:ptliste):ptliste; Page 1/3 I.A - Quelques proprietes I.A.1) Donner tous les mots de Lukasiewicz de longueur 1, 2 et 3, puis tous ceux de longueur paire. I.A.2) Ecrire une fonction qui indique si un mot est de Lukasiewicz. Cette fonction renverra une valeur booleenne. La fonction proposee devra imperativement avoir une complexite (en termes d'operations elementaires) en O(n), avec n la longueur du mot d'entree. On note avec un point · la concatenation de deux mots, par exemple a · b. - En Caml, un mot de Lukasiewicz sera represente par une liste d'entiers (int list). - En Pascal, un mot de Lukasiewicz sera represente par une chaine de caracteres (string) composee de symboles '+' (pour +1) et '-' (pour -1). On rappelle les operations suivantes : · acceder au caractere numero i de la chaine c : c[i] (la numerotation commence a 1) ; · obtenir la longueur d'une chaine c : length(c) ; · extraire une chaine d'une sous-chaine : copy(cha^ ine, position, longueur). Par exemple, copy('abcdef', 2, 3) retourne 'bcd' ; · concatener deux chaines ou caracteres c1 et c2 pour obtenir une nouvelle chaine : c1 + c2. On demande d'indiquer le type de toutes les fonctions ecrites, que ce soit en Caml ou en Pascal. i=1 On appelle mots de Lukasiewicz les mots u = (u1 , u2 , . . . , un ) sur cet alphabet qui verifient les deux proprietes suivantes : n k X X ui = -1 et ui > 0 pour 1 6 k 6 n - 1. Dans cette partie, les mots consideres sont pris sur l'alphabet {-1, +1}. Partie I - Mots de Lukasiewicz Les deux parties sont independantes. Le candidat indiquera en tete de sa copie le langage choisi : Caml ou Pascal. Épreuve : Concours Centrale - Supélec 2008 - version du 7 mars 2008 12h26 INFORMATIQUE i=1 Filière MP Soit u = (u1 , . . . , un ) un mot tel que i=1 n X ui = -1. Demontrer qu'il existe i=1 un unique entier i, 1 6 i 6 n, tel que (ui , ui+1 , . . . , un , u1 , . . . , ui-1 ) soit un mot de Lukasiewicz. Ce mot est appele conjugue de u. I.B.2) Ecrire une fonction conjugue qui calcule le conjugue d'un mot u = (u1 , . . . un ) n X verifiant ui = -1. I.B.1) I.B - Denombrement Cette derniere fonction adjonction realise l'adjonction d'une nouvelle cellule en tete de liste (et retournant un pointeur sur ladite cellule). On ne demande pas de l'ecrire. I.A.3) Montrer que si u et v sont des mots de Lukasiewicz, alors (+1) · u · v est un mot de Lukasiewicz. I.A.4) Reciproquement, montrer que tout mot de Lukasiewicz de longueur superieure ou egale a 3 admet une decomposition unique de la forme (+1) · u · v, ou u et v sont des mots de Lukasiewicz. I.A.5) Ecrire une fonction decompose qui associe ce couple (u, v) a un mot de Lukasiewicz de longueur superieure ou egale a 3. En Pascal, on pourra ecrire une procedure qui modifie deux de ses parametres u et v passes par reference. On ne demande pas de traiter les cas ou le mot fourni en entree ne serait pas de Lukasiewicz. I.A.6) On souhaite calculer tous les mots de Lukasiewicz d'une longueur donnee. Comparer les avantages d'une solution recursive appliquant le principe de la decomposition suggere par la question A.4), et celle d'une solution appliquant le meme principe, mais pour laquelle on tabulerait les resultats intermediaires. I.A.7) Ecrire une fonction obtenirLukasiewicz qui calcule la liste des mots de Lukasiewicz de taille inferieure ou egale a un entier donne. En Pascal, on dispose des types et fonction : type ptliste=^liste; liste=record valeur : string; suivant:ptliste end; function adjonction(x:string; pt:ptliste):ptliste; Page 1/3 I.A - Quelques proprietes I.A.1) Donner tous les mots de Lukasiewicz de longueur 1, 2 et 3, puis tous ceux de longueur paire. I.A.2) Ecrire une fonction qui indique si un mot est de Lukasiewicz. Cette fonction renverra une valeur booleenne. La fonction proposee devra imperativement avoir une complexite (en termes d'operations elementaires) en O(n), avec n la longueur du mot d'entree. On note avec un point · la concatenation de deux mots, par exemple a · b. - En Caml, un mot de Lukasiewicz sera represente par une liste d'entiers (int list). - En Pascal, un mot de Lukasiewicz sera represente par une chaine de caracteres (string) composee de symboles '+' (pour +1) et '-' (pour -1). On rappelle les operations suivantes : · acceder au caractere numero i de la chaine c : c[i] (la numerotation commence a 1) ; · obtenir la longueur d'une chaine c : length(c) ; · extraire une chaine d'une sous-chaine : copy(cha^ ine, position, longueur). Par exemple, copy('abcdef', 2, 3) retourne 'bcd' ; · concatener deux chaines ou caracteres c1 et c2 pour obtenir une nouvelle chaine : c1 + c2. On demande d'indiquer le type de toutes les fonctions ecrites, que ce soit en Caml ou en Pascal. i=1 On appelle mots de Lukasiewicz les mots u = (u1 , u2 , . . . , un ) sur cet alphabet qui verifient les deux proprietes suivantes : n k X X ui = -1 et ui > 0 pour 1 6 k 6 n - 1. Dans cette partie, les mots consideres sont pris sur l'alphabet {-1, +1}. Partie I - Mots de Lukasiewicz Les deux parties sont independantes. Le candidat indiquera en tete de sa copie le langage choisi : Caml ou Pascal. Épreuve : Concours Centrale - Supélec 2008 Demontrer que u est un mot de Lukasiewicz si et seulement si (u) = (-1). I.D.4) Filière MP II.B - Algorithme de Rabin-Karp La presentation de l'algorithme de Rabin-Karp est faite dans le cas de l'alphabet A0 = {0, 1, ..., 9}. Un mot m A0 peut etre vu naturellement comme un entier (m = 366 est dans A0 ... mais aussi dans N). II.B.1) La premiere idee de l'algorithme de Rabin-Karp est que si on cherche p = 366 dans m = 97463667305, on va regarder les lettres de m par groupes de 3, en initialisant un compteur a c = 974, et en « avancant » dans m en ajoutant a chaque fois une nouvelle lettre, et en effacant la premiere de c. Dans notre exemple, c passe d'abord a 746 puis 463. Plus formellement, lire la lettre = mi+|p| dans m en effacant mi change c en 10c + - 10|p| mi . Si c = p, cela signifie que le motif p est present en position i dans m. On suppose dans cette premiere version de l'algorithme de Rabin-Karp que p est de tres petite longueur, de sorte que le compteur c ne depassera jamais la valeur du plus grand entier autorise par Caml ou Pascal. On considere definie une fonction appelee numeral prenant comme entree un caractere de l'alphabet A0 et retournant la valeur entiere correspondante (par exemple on associe l'entier 0 au caractere '0') : · En Caml, numeral : char -> int =  · En Pascal, function numeral(a : char) : integer ; II.A - Algorithme naif II.A.1) Ecrire une fonction coincide prenant en entree deux chaines de caracteres p et m, une position pos, et retournant true si p apparait en position pos dans m (et false sinon). Cette fonction devra uniquement utiliser des comparaisons de caracteres, sans utiliser sub_string (Caml) ou copy (Pascal). De plus, en cas de reponse false, elle devra arreter les tests des que possible. II.A.2) Ecrire une fonction recherche prenant en entree deux chaines de caracteres p et m, et retournant la liste (dans n'importe quel ordre, et eventuellement vide) des positions de p dans m. En Pascal, on dispose comme dans la premiere partie des types ptliste,liste et de la fonction adjonction, avec cette fois le champ valeur de type integer. II.A.3) Evaluer la complexite (en termes de comparaisons de caracteres, et en fonction de |p| et |m|) de la fonction precedente dans le pire des cas. On exhibera un cas defavorable (en terme de complexite), avec p et m arbitrairement grands. m = m1 ...mn , on dit que p apparait en position i dans m lorsque p = mi ...mi+|p|-1 , avec |p| la longueur de p. Dans ce probleme, nous allons etudier deux algorithmes de recherche de motif (en general note p) dans un mot (en general note m). Par exemple, le motif p0=bra apparait deux fois dans le mot m0=abracadabra. Les programmes de recherche de motif devront retourner la liste (eventuellement vide) des positions (au sens de Caml/Pascal) du motif dans le mot. Dans l'exemple precedent, les programmes devront retourner une liste contenant les positions 1 et 8 en Caml ; 2 et 9 en Pascal. C'est la position de la premiere lettre qui est prise en compte. Plus formellement, si Page 2/3 Partie II - Recherche de motif Ecrire une fonction rho qui calcule (u). Ecrire une fonction rhoLim qui calcule (u). I.D.2) I.D.3) I.D.1) Justifier le fait que la suite (n (u))nN est constante au dela d'un certain rang. La valeur limite de la suite (n (u))nN est notee (u). (u) = u, si u ne contient pas de capsule (u) = (u1 , . . . , ui-1 , ui+2 , . . . un ), si (ui , ui+1 , ui+2 ) = (+1, -1, -1) est la premiere capsule de u I.D - Capsules On appelle capsule d'un mot u tout facteur de u de la forme (+1, -1, -1). On definit sur {-1, 1} une fonction dite de decapsulage : I.C - Regularite I.C.1) Montrer que le langage L = (+1)n (-1)n+1 , n N n'est pas reconnaissable (implicitement dans la suite : « par un automate fini »). I.C.2) Montrer que l'intersection de deux langages reconnaissables est un langage reconnaissable. I.C.3) Prouver le caractere reconnaissable ou non du langage constitue des mots de Lukasiewicz. I.B.3) En utilisant les resultats precedents, determiner le nombre de mots de Lukasiewicz de longueur 2n + 1. On pourra utiliser ce resultat admis : « Si u et v sont deux mots non vides, les deux propositions suivantes sont equivalentes : · uv = vu · il existe un mot w non vide et deux entiers k, > 1 tels que u = wk et v = w » INFORMATIQUE Demontrer que u est un mot de Lukasiewicz si et seulement si (u) = (-1). I.D.4) Filière MP II.B - Algorithme de Rabin-Karp La presentation de l'algorithme de Rabin-Karp est faite dans le cas de l'alphabet A0 = {0, 1, ..., 9}. Un mot m A0 peut etre vu naturellement comme un entier (m = 366 est dans A0 ... mais aussi dans N). II.B.1) La premiere idee de l'algorithme de Rabin-Karp est que si on cherche p = 366 dans m = 97463667305, on va regarder les lettres de m par groupes de 3, en initialisant un compteur a c = 974, et en « avancant » dans m en ajoutant a chaque fois une nouvelle lettre, et en effacant la premiere de c. Dans notre exemple, c passe d'abord a 746 puis 463. Plus formellement, lire la lettre = mi+|p| dans m en effacant mi change c en 10c + - 10|p| mi . Si c = p, cela signifie que le motif p est present en position i dans m. On suppose dans cette premiere version de l'algorithme de Rabin-Karp que p est de tres petite longueur, de sorte que le compteur c ne depassera jamais la valeur du plus grand entier autorise par Caml ou Pascal. On considere definie une fonction appelee numeral prenant comme entree un caractere de l'alphabet A0 et retournant la valeur entiere correspondante (par exemple on associe l'entier 0 au caractere '0') : · En Caml, numeral : char -> int =  · En Pascal, function numeral(a : char) : integer ; II.A - Algorithme naif II.A.1) Ecrire une fonction coincide prenant en entree deux chaines de caracteres p et m, une position pos, et retournant true si p apparait en position pos dans m (et false sinon). Cette fonction devra uniquement utiliser des comparaisons de caracteres, sans utiliser sub_string (Caml) ou copy (Pascal). De plus, en cas de reponse false, elle devra arreter les tests des que possible. II.A.2) Ecrire une fonction recherche prenant en entree deux chaines de caracteres p et m, et retournant la liste (dans n'importe quel ordre, et eventuellement vide) des positions de p dans m. En Pascal, on dispose comme dans la premiere partie des types ptliste,liste et de la fonction adjonction, avec cette fois le champ valeur de type integer. II.A.3) Evaluer la complexite (en termes de comparaisons de caracteres, et en fonction de |p| et |m|) de la fonction precedente dans le pire des cas. On exhibera un cas defavorable (en terme de complexite), avec p et m arbitrairement grands. m = m1 ...mn , on dit que p apparait en position i dans m lorsque p = mi ...mi+|p|-1 , avec |p| la longueur de p. Dans ce probleme, nous allons etudier deux algorithmes de recherche de motif (en general note p) dans un mot (en general note m). Par exemple, le motif p0=bra apparait deux fois dans le mot m0=abracadabra. Les programmes de recherche de motif devront retourner la liste (eventuellement vide) des positions (au sens de Caml/Pascal) du motif dans le mot. Dans l'exemple precedent, les programmes devront retourner une liste contenant les positions 1 et 8 en Caml ; 2 et 9 en Pascal. C'est la position de la premiere lettre qui est prise en compte. Plus formellement, si Page 2/3 Partie II - Recherche de motif Ecrire une fonction rho qui calcule (u). Ecrire une fonction rhoLim qui calcule (u). I.D.2) I.D.3) I.D.1) Justifier le fait que la suite (n (u))nN est constante au dela d'un certain rang. La valeur limite de la suite (n (u))nN est notee (u). (u) = u, si u ne contient pas de capsule (u) = (u1 , . . . , ui-1 , ui+2 , . . . un ), si (ui , ui+1 , ui+2 ) = (+1, -1, -1) est la premiere capsule de u I.D - Capsules On appelle capsule d'un mot u tout facteur de u de la forme (+1, -1, -1). On definit sur {-1, 1} une fonction dite de decapsulage : I.C - Regularite I.C.1) Montrer que le langage L = (+1)n (-1)n+1 , n N n'est pas reconnaissable (implicitement dans la suite : « par un automate fini »). I.C.2) Montrer que l'intersection de deux langages reconnaissables est un langage reconnaissable. I.C.3) Prouver le caractere reconnaissable ou non du langage constitue des mots de Lukasiewicz. I.B.3) En utilisant les resultats precedents, determiner le nombre de mots de Lukasiewicz de longueur 2n + 1. On pourra utiliser ce resultat admis : « Si u et v sont deux mots non vides, les deux propositions suivantes sont equivalentes : · uv = vu · il existe un mot w non vide et deux entiers k, > 1 tels que u = wk et v = w » INFORMATIQUE · · · FIN · · · Page 3/3 e) Comparer les complexites dans le pire des cas de l'algorithme de Rabin-Karp et de l'algorithme naif. f) En pratique, aura-t-on interet a prendre q plutot petit ou plutot grand ? Que peut-on alors esperer pour le temps de calcul de la recherche des occurrences de p dans m ? On demande une justification informelle, le choix de l'entier q et l'evaluation de temps moyen de calcul etant deux choses tres delicates . . . q est suppose tel que les calculs arithmetiques modulo q sont d'un cout constant. Le temps de calcul pendra donc en compte ces operations arithmetiques, et les comparaisons de caracteres, du type mi = pj . Lorsque c = p, on a c p [q]. Mais reciproquement, lorsque c p [q], on n'est pas assure d'avoir c = p. On regarde alors (avec l'algorithme naif) si le facteur de m correspondant au compteur c calcule est egal a p. Si c p [q] mais c 6= p, on parle de « fausse-position ». a) Donner les valeurs successives de c lors de la recherche de p = 366 dans m = 97463667305, avec q = 9. b) Ecrire une fonction recherchant les positions d'un motif dans un mot, en appliquant l'algorithme de Rabin-Karp, avec un entier q donne en parametre. c) Lors de la recherche de p = 0001000 dans m = 000000000 avec q = 1000, combien de cas de fausse-position va-t-on rencontrer ? d) Majorer le temps de calcul de la liste des positions de p dans m, en fonction de |p| et |m| avec l'algorithme de Rabin-Karp. a) Ecrire une fonction prenant en entree un mot m, une longueur , et retournant la valeur initiale du compteur, calculee en lisant les = |p| premieres lettres de m. Dans l'exemple donne plus haut, sur l'entree (m, 3), la fonction doit retourner 974. b) Ecrire enfin une fonction prenant en entree un motif, un mot (suppose de taille superieure au motif), et calculant la liste des positions dans m ou le motif p est present. II.B.2) L'hypothese quant a la longueur « faible » de p etant tres restrictive, on modifie l'algorithme precedent en choisissant un entier q modulo lequel on calculera c. En lisant la lettre = mi+| p| et en effacant mi , le nouveau compteur devient donc c 10c + - 10|p| mi [q]. INFORMATIQUE Filière MP

Extrait du corrigé obtenu par reconnaissance optique des caractères


 Centrale Informatique MP 2008 -- Corrigé Ce corrigé est proposé par Benjamin Monmege (ENS Cachan) ; il a été relu par Vincent Danjean (Enseignant-chercheur en école d'ingénieur) et Vincent Puyhaubert (Professeur en CPGE). Ce sujet comporte deux problèmes indépendants. · Le premier problème, assez long, introduit la notion de mots de Lukasiewicz. Il s'agit de mots u sur l'alphabet {-1, +1} dont la somme des caractères vaut -1 et dont la somme partielle des k premiers caractères est positive ou nulle pour tout k de 1 à |u|-1. Ces mots servent entre autres à représenter le comportement d'une pile, dans laquelle on peut empiler et dépiler un caractère. Les sommes partielles représentent alors la hauteur de pile à un moment donné. Le fait que celles-ci doivent rester positives ou nulles signifie qu'on ne peut retirer un élément à une pile vide. Une somme totale égale à -1 indique que l'on a dépilé le « fond de pile » et que le calcul est terminé. Dans ce problème, on s'intéresse à des propriétés internes des mots de Lukasiewicz, à leur dénombrement, à la reconnaissabilité de l'ensemble des mots de Lukasiewicz ainsi qu'à une caractérisation fonctionnelle de ces mots. C'est un problème assez technique avec de nombreux programmes, essentiellement des fonctions récursives qui utilisent des listes d'entiers. Des questions délicates se concentrent dans la partie B. Les preuves nécessitent alors de l'habileté dans les manipulations de mots sur un alphabet, telles que le découpage ou la concaténation. Les parties B, C et D sont indépendantes et seule la partie C donne l'occasion de travailler avec des automates. · Le deuxième problème, plus court, s'intéresse au thème classique de la recherche de motif dans un mot. Après l'écriture de l'algorithme naïf, le sujet étudie l'algorithme de Rabin-Karp, qui utilise des opérations arithmétiques sur les lettres. C'est une partie facile demandant des programmes simples en style impératif. Quelques questions qualitatives, sans doute discriminantes, permettaient de détecter les candidats comprenant bien les idées du problème. Pour conclure, il s'agit d'un sujet qui permet de bien réviser l'intégralité des notions du programme, même si pour la plupart elles ne font l'objet que de quelques questions. Les conseils du jury Le rapport du jury souligne que « le niveau moyen des candidats a semblé en baisse ». Il cite deux raisons principales récurrentes. La première concerne la programmation : ils rappellent ainsi quelques conseils à suivre dont « indenter correctement ; ne pas commencer un programme en bas de page ; donner des noms expressifs aux variables et fonctions annexes ». La deuxième est relative aux automates, dont ils relèvent « une très forte incompréhension pour la grande majorité des candidats » : le jury attend par exemple que « les futurs candidats comprennent qu'un automate fini est autre chose qu'un quintuplet » et relève la mauvaise connaissance du lemme de l'étoile. Indications I.A.2 Utiliser une fonction récursive et un filtrage afin de parcourir la liste tout en calculant la somme de ses termes. I.A.3 Noter u = (u1 , . . . , un ) et v = (v1 , . . . , vm ) les deux mots de Lukasiewicz et déterminer la somme des lettres de chaque sous-mot de w = (+1) · u · v en distinguant trois cas. I.A.4 Démontrer ce résultat en deux temps : d'abord l'existence, ensuite l'unicité. Il faut avant tout trouver où réaliser la coupure entre le sous-mot u et le sousmot v tels que x = (+1) · u · v : une idée pourrait être d'utiliser l'indice i i P minimal vérifiant xk = 0. k=1 I.A.5 Utiliser une fonction récursive parcourant la liste en mémorisant dans une autre liste les premiers termes déjà lus. I.A.6 Réfléchir aux appels récursifs nécessaires dans une méthode récursive. I.A.7 C'est évidemment la méthode itérative qu'il faut choisir, comme vous avez dû le constater dans la question précédente. Construire progressivement un tableau contenant tous les mots de Lukasiewicz de taille inférieure à n : il suffira de fusionner certaines cases du tableau pour en remplir d'autres... I.B.1 Il s'agit du même type de preuve qu'à la question I.A.4. I.B.3 Il faut dans un premier temps bien comprendre le lien qui existe entre les mots de Lukasiewicz et l'ensemble des mots dont la somme des lettres vaut -1. Par l'opération de conjugaison, on a un lien très précis que l'on peut exploiter ici. I.C.1 Il s'agit d'une application directe du lemme de l'étoile (également appelé lemme de pompage). I.C.2 À l'aide d'un automate reconnaissant un langage L1 et d'un automate reconnaissant un langage L2 , il faut construire un automate reconnaissant L1 L2 . I.C.3 Appliquer les deux questions précédentes en essayant d'écrire le langage L comme intersection du langage contenant les mots de Lukasiewicz et d'un langage reconnaissable à déterminer. I.D.1 Considérer la suite des longueurs de n (u). I.D.2 Il s'agit d'une recherche de motifs : une fonction récursive fait ici l'affaire si on l'écrit convenablement. I.D.4 Commencer par démontrer les deux lemmes suivants · u est un mot de Lukasiewicz (u) est un mot de Lukasiewicz · le seul mot de Lukasiewicz sans capsule est (-1) et conclure. II.A.1 On dispose en Caml de la fonction string_length pour obtenir la longueur d'une chaîne de caractères. Il suffit de vérifier caractère par caractère s'il y a égalité des chaînes. II.A.3 Calculer d'abord la complexité de la fonction coincide. II.B.2.d Attention ! Les opérations élémentaires à considérer ici sont les comparaisons de caractères et les calculs modulo q. I. Mots de Lukasiewicz I.A Quelques propriétés I.A.1 Le seul mot de Lukasiewicz de longueur 1 est évidemment (-1). Si (u1 , u2 ) est un mot de Lukasiewicz alors nécessairement u1 > 0 donc u1 = 1 et ainsi u2 = -1 - u1 = -2, ce qui est impossible. Donc il n'y a pas de mot de Lukasiewicz de longueur 2. De même, si (u1 , u2 , u3 ) est un mot de Lukasiewicz, u1 = 1 ; u2 = 1 impliquerait u3 = -3 ce qui est impossible donc u2 = -1 et alors u3 = -1. Par conséquent le seul mot de Lukasiewicz de longueur 3 est (1, -1, -1). n P Si (u1 , . . . , un ) est un mot de Lukasiewicz avec n pair, alors ui est une somme i=1 d'un nombre pair d'entiers impairs : elle est donc paire et ne peut être égale à -1. Il n'y a aucun mot de Lukasiewicz de longueur paire. Pour mieux comprendre la notion de mot de Lukasiewicz, on peut essayer de lui donner une interprétation graphique. À tout mot u = (u1 , . . . , un ), on associe une ligne polygonale dans le demi-plan des abscisses positives. Cette ligne polygonale démarre en l'origine : à chaque caractère lu, la ligne passe à l'unité suivante en abscisse et elle le fait en montant d'une unité s'il s'agit du caractère (+1), en descendant sinon. Comme un bon dessin vaut mieux qu'un long discours, voilà cette représentation graphique pour le mot (1, -1, 1, 1, -1, 1, -1, -1, -1). On voit alors qu'être un mot de Lukasiewicz est équivalent à avoir une ligne polygonale allant de l'origine à un point d'ordonnée -1, en restant constamment au-dessus de la droite des abscisses, sauf au dernier caractère. Dans la littérature liée à la combinatoire, on parle souvent de chemins à pas (1, 1) et (1, -1). I.A.2 Appliquons directement la définition pour créer cette fonction de test de type int list -> bool. L'idée est de parcourir le mot en entrée avec une fonction récursive auxiliaire qui stocke le reste du mot encore à lire et la somme des premiers éléments déjà lus. Si à un moment, cette somme devient négative, le programme renvoie faux. À la fin, on teste simplement si la somme totale vaut -1. Cette fonction est bien de complexité linéaire en la longueur du mot d'entrée. let test_Lukasiewicz u = let rec test_positif v somme = match v with [] -> (somme = -1); |v1::v' -> if (somme >= 0) then test_positif v' (somme+v1) else false in test_positif u 0 ;; I.A.3 Soient u = (u1 , . . . , un ) et v = (v1 , . . . , vm ) deux mots de Lukasiewicz. Notons w = (+1) · u · v. Pour simplifier, notons w = (w1 , . . . , wn+m+1 ) avec w1 = +1, puis (w2 , . . . , wn+1 ) = u, (wn+2 , . . . , wn+m+1 ) = v. On vérifie, en suivant la définition, que w est un mot de Lukasiewicz. · · n+m+1 P n P i=1 i=1 wi = w1 + ui + m P vi = +1 - 1 - 1 = -1 i=1 w1 = +1 > 0 pour tout k compris entre 2 et n, k P wi = +1 + i=1 n+1 P n P i=1 i=1 wi = +1 + k-1 P ui > 0 i=1 ui = +1 - 1 = 0 > 0 pour tout k compris entre n + 2 et n + m, k P wi = +1 - 1 + i=1 k-n-1 P vi > 0 i=1 Si u et v sont deux mots de Lukasiewicz, (+1) · u · v est un mot de Lukasiewicz. La propriété établie se vérifie aisément graphiquement. Considérons par exemple les deux mots u = (1, -1, 1, -1, -1) et v = (1, 1, -1, -1, -1) représentés par les chemins suivants u v Alors (+1) · u · v se représente par u v k P On voit que le mot v commence lorsque la somme partielle wi s'annule pour la deuxième fois, la première fois se trouvant à l'origine. i=1