Les calculatrices sont interdites. Le sujet est composé de trois parties indépendantes. 1/11 SESSION 2021 MP7IN ÉPREUVE MUTUALISÉE AVEC E3A-POLYTECH ÉPREUVE SPÉCIFIQUE - FILIÈRE MP ____________________ INFORMATIQUE Durée : 4 heures ____________________ 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. RAPPEL DES CONSIGNES x Utiliser uniquement un stylo noir ou bleu foncé non effaçable pour la rédaction de votre composition ; d’autres couleurs, excepté le vert, peuvent être utilisées, mais exclusivement pour les schémas et la mise en évidence des résultats. x Ne pas utiliser de correcteur. x Écrire le mot FIN à la fin de votre composition. ___________________________________________________________________________________ -- 1 of 12 -- Partie I - Étude des partitions non croisées Dans cette partie, on introduit et on étudie de façon élémentaire les partitions non croisées, objets com- binatoires apparaissant dans divers domaines des mathématiques, notamment dans la théorie des proba- bilités libres et des matrices aléatoires. Le langage de programmation utilisé dans cette partie est le langage Python. Dans la suite, pour tout couple (i, n) ∈ N2, les notations !n" et !i, n" désignent respectivement les en- sembles {1, 2, . . . , n} et {i, i + 1, . . . , n}. Par convention, !0" = ∅ et si i > n alors !i, n" = ∅. Définition 1 (Partition) Soit A un sous-ensemble non vide de N. Une partition P de A est un ensemble de parties de A tel que : 1. ∀P ∈ P, P ! ∅ ; 2. ∀(P, Q) ∈ P2, (P ! Q) =⇒ (P ∩ Q = ∅) ; 3. ⋃ P∈P P = A. Par exemple, {{2, 4, 5} , {7, 9} , {8}} est une partition de l’ensemble {2, 4, 5, 7, 8, 9}. Définition 2 (Classe) Soit P une partition d’un sous-ensemble A non vide de N. Soit i un élément de A. La classe de i est l’unique élément P de P tel que i ∈ P. Elle est notée Cl(i). Par exemple, pour P = {{2, 4, 5} , {7, 9} , {8}}, on a Cl(4) = {2, 4, 5}. Définition 3 (Partition non croisée) Soit P une partition d’un sous-ensemble A non vide de N. On dit que P est non croisée si pour tout quadruplet (a, b, c, d) ∈ A4 tel que a < b < c < d on a : (Cl(a) = Cl(c), Cl(b) = Cl(d)) =⇒ (Cl(a) = Cl(b) = Cl(c) = Cl(d)) . Par exemple, P = {{2, 4, 5} , {7, 9} , {8}} est bien une partition non croisée de {2, 4, 5, 7, 8, 9}. En effet, aucun quadruplet (a, b, c, d) ∈ {2, 4, 5, 7, 8, 9}4 tel que a < b < c < d ne vérifie la condition Cl(a) = Cl(c), Cl(b) = Cl(d). De même, Q = {{2, 7, 8, 9}, {4, 5}} en est bien une. En effet, (a, b, c, d) = (2, 7, 8, 9) est l’unique quadru- plet tel que a < b < c < d vérifiant Cl(a) = Cl(c), Cl(b) = Cl(d) et ces quatre éléments sont bien dans la même classe. Par contre, R = {{2, 5} , {4, 7, 9} , {8}} n’en est pas une. En effet, Cl(2) = Cl(5) et Cl(4) = Cl(7) mais Cl(2) ! Cl(4). Le terme « non croisée » découle naturellement des représentations picturales des partitions (figure 1). 2 4 5 7 8 9 2 4 5 7 8 9 2 4 5 7 8 9 Figure 1 - Représentations picturales de P, Q, R 2/11 -- 2 of 12 -- Dans la suite, on s’intéresse uniquement aux partitions d’un sous-ensemble fini de N. On les représente en Python à l’aide de listes de listes croissantes d’entiers triées dans l’ordre lexicographique. Par exemple, les partitions P = {{2, 4, 5}, {7, 9}, {8}} et R = {{2, 5} , {4, 7, 9} , {8}} sont respectivement représentées par les listes P = [[2,4,5],[7,9],[8]] et R = [[2,5],[4,7,9],[8]]. I.1 - Exemples et fonctions élémentaires (Informatique Pour Tous) Q1. Justifier brièvement que P = {{1, 7} , {2} , {3, 4, 5} , {6}} est une partition non croisée de !7" et que Q = {{1, 6} , {2} , {3, 4, 5, 7}} n’en est pas une. Q2. Parmi les ensembles suivants, indiquer sans justification lesquels sont des partitions de !5". Parmi les partitions, préciser sans justification lesquelles sont non croisées. 1. P1 = {{1, 3} , {2, 4, 5}}, 2. P2 = {{1, 3} , {1, 2} , {4, 5}}, 3. P3 = {{1, 3} {2, 4}}, 4. P4 = {{1, 4, 5} , {2, 3}}. Q3. Décrire l’ensemble des partitions non croisées de !4". Pour Q4, Q5 et Q6, on se fixe un ensemble fini A ⊂ N. Cet ensemble est représenté en Python par la liste croissante d’entiers A, définie au préalable. On suppose également que pour ces questions, la variable P désigne une liste de listes croissantes d’entiers triée dans l’ordre lexicographique. On définit la fonction Python mystere(P) par : d e f m y s t e r e ( P ) : L = [ F a l s e f o r _ i n range ( l e n (A ) ) ] f o r i i n range ( l e n ( P ) ) : i f P [ i ] == [ ] : r e t u r n F a l s e e l s e : f o r j i n range ( l e n ( P [ i ] ) ) : i f P [ i ] [ j ] n o t i n A : r e t u r n F a l s e e l s e : # A . i n d e x ( a ) r e n v o i e l ’ i n d i c e de a d a n s A k = A . i n d e x ( P [ i ] [ j ] ) i f L [ k ] : r e t u r n F a l s e e l s e : L [ k ] = T r u e r e t u r n n o t ( F a l s e i n L ) Q4. Uniquement dans cette question, on suppose que A = [1,2,3,4,5]. Expliciter sans justification les valeurs de : 1. mystere([[1,3],[1,5],[2,4]]) 2. mystere([[1,3,4],[2]]) 3. mystere([[1,3,5],[2,4]]) 4. mystere([[],[1,2,3,4,5]]). Q5. Écrire une fonction Python classe(P,i) prenant en arguments une variable P représentant une partition P de A et un entier i ∈ A qui renvoie une liste L représentant Cl(i). 3/11 -- 3 of 12 -- On définit la fonction Python au code incomplet est_nc(P) suivante : d e f e s t _ n c ( P ) : # On r a p p e l l e que A e s t une l i s t e t r i é e d a n s l ’ o r d r e c r o i s s a n t N = l e n (A) f o r i i n range (N) : f o r j i n range ( i +1 ,N) : f o r k i n range ( j +1 ,N) : f o r l i n range ( k +1 ,N) : . . . Q6. Recopier et compléter le code de la fonction est_nc(P), sachant qu’elle prend en argument une variable P représentant une partition P de A et qu’elle renvoie True si P est non croisée et False sinon. I.2 - Nombre de partitions non croisées Pour tout n ≥ 1, on note Cn le nombre de partitions non croisées d’un ensemble A ⊂ N ayant exac- tement n éléments et NC(A) l’ensemble des partitions non croisées de A. Par convention, C0 = 1 et NC(∅) = {∅}. Définition 4 (Partition non croisée emboîtée) Soient A un ensemble fini de N de cardinal n et P une partition non croisée de A. On dit que P est em- boîtée si le minimum m et le maximum M de A sont dans la même classe (Cl(m) = Cl(M)). L’ensemble des partitions non croisées et emboîtées de A et son cardinal sont respectivement notés NCE(A) et Dn. Par exemple, S = {{1, 2, 5, 9}, {3, 4}, {6, 7, 8}} est une partition non croisée et emboîtée de !9". Le terme « emboîtée » découle naturellement des représentations picturales des partitions (figure 2). 1 2 3 4 5 6 7 8 9 Figure 2 - Représentations picturale de S Q7. Montrer que pour tout n ∈ N, on a Cn = Dn+1. Q8. Soit n ∈ N. On définit l’application Φn comme suit : Φn : n+1 ⋃ i=1 NCE(!i") × NC(!i + 1, n + 1") → NC(!n + 1") (Q1, Q2) ' → Q1 ∪ Q2. En admettant que Φn est une application bijective, montrer que Cn+1 = n ∑ k=0 CkCn−k. Q9. (Informatique Pour Tous) Écrire une fonction Python calcul_C(n) qui prend en argument un entier naturel n et qui renvoie la valeur Cn. 4/11 -- 4 of 12 -- Partie II - Logique et étude du problème Horn-Sat Dans cette partie, ∧, ∨, ¬, désignent respectivement les connecteurs de conjonction, de disjonction et de négation. Les symboles V, F désignent respectivement les valeurs de vérité VRAI et FAUX du calcul propositionnel. Dans la suite, on s’intéresse au problème Horn-Sat, qui peut être décrit de la façon suivante : étant donnée une formule de Horn P, existe-t-il une interprétation I telle que [P]I = V ? L’objectif est d’expliciter un algorithme permettant de résoudre ce problème. Définition 5 (Formule propositionnelle) Soit X un ensemble de symboles appelés variables propositionnelles. Les formules propositionnelles sur X sont alors définies de façon inductive comme suit : - V, F sont des formules propositionnelles ; - tout élément x de X est une formule propositionnelle ; - si P et Q sont des formules propositionnelles, alors ¬P, (P ∧ Q) , (P ∨ Q) sont des formules pro- positionnelles. Dans la suite, les variables propositionnelles et formules propositionnelles considérées sont construites à l’aide d’un ensemble X qui ne sera pas explicité. Définition 6 (Littéral) Soit x une variable propositionnelle. Un littéral est la formule x ou la formule ¬x. Le littéral x (respec- tivement ¬x) est un littéral positif (respectivement négatif). Définition 7 (Clause disjonctive) Soient n ∈ N, x1, x2, . . . , xn des littéraux. La formule x1 ∨ x2 ∨ . . . ∨ xn est appelée clause disjonctive à n littéraux (ou de taille n). Par convention, () désigne la clause disjonctive vide, c’est-à-dire la clause sans littéral. Une clause de Horn est une clause disjonctive contenant au plus un littéral positif. Une clause unitaire est une clause composée d’un unique littéral. Définition 8 (Forme normale conjonctive) Soit P une formule propositionnelle. On dit que P est une forme normale conjonctive s’il existe un entier n ∈ N, C1, C2, . . . , Cn des clauses disjonctives vérifiant P = C1 ∧ C2 ∧ . . . ∧ Cn. Par convention, une forme normale conjonctive sans clause est représentée par ∅. Définition 9 (formule de Horn) Soit P une formule propositionnelle. On dit que P est une formule de Horn s’il existe n ∈ N, C1, C2, . . . , Cn des clauses de Horn vérifiant P = C1 ∧ C2 ∧ . . . ∧ Cn. Définition 10 (Interprétation) Soient n ∈ N et x1, x2, . . . xn des variables propositionnelles. Une interprétation est une application I : {x1, x2, . . . , xn} → {V, F}. Définition 11 (Évaluation) Soient P une formule propositionnelle, x1, x2, . . . , xn les variables propositionnelles apparaissant dans P et I une interprétation sur {x1, x2, . . . , xn}. L’évaluation de P suivant l’interprétation I que l’on note [P]I est définie par récurrence de la façon suivante : 5/11 -- 5 of 12 -- - si P ∈ {V, F}, alors [P]I = P ; - si P ∈ {x1, x2, . . . , xn}, alors [P]I = I(P) ; - si P = ¬Q où Q est une formule propositionnelle, alors [P]I = ¬[Q]I ; - si P = A ◦ B où A, B sont des formules propositionnelles et ◦ ∈ {∧, ∨}, alors [P]I = [A]I ◦ [B]I . Par convention, [()]I = F et [∅]I = V. Définition 12 (Satisfiable) Soit P une formule propositionnelle. On dit que P est satisfiable s’il existe une interprétation I telle que [P]I = V. Q10. Pour chacune des formules suivantes, montrer qu’elle est satisfiable ou qu’elle est non satisfiable. 1. P1 = (x ∨ y) ∧ (¬x ∨ ¬y) ∧ (x ∨ ¬y), 2. P2 = (x) ∧ (¬x ∨ ¬y) ∧ (¬y ∨ z) ∧ (z), 3. P3 = (), 4. P4 = (x ∨ ¬y ∨ ¬t) ∧ (z ∨ ¬t ∨ ¬x ∨ ¬y). Q11. Parmi les fomules de la Q10, lesquelles sont des formules de Horn ? On ne justifiera pas la réponse. Définition 13 (Propagation unitaire) Soit P une forme normale conjonctive contenant une clause unitaire (x). On construit une formule P′ à partir de P de la façon suivante : 1. supprimer de P toutes les clauses où x apparaît ; 2. enlever toutes les occurrences du littéral ¬x. Cette procédure de simplification est appelée propagation unitaire. Par exemple, si P = (x ∨ ¬y ∨ z) ∧ (¬x ∨ y ∨ z) ∧ (x), on a alors P′ = (y ∨ z). Si P = (x) ∧ (¬x), on a alors P′ = (). Dans la suite, on note Π(P) une formule sans clause unitaire obtenue en itérant la propagation unitaire sur P. On admet que si Π(P) ne contient pas de clause vide () alors Π(P) est unique et que si Π(P) contient au moins une clause vide alors toute formule sans clause unitaire obtenue par itération de la propagation unitaire sur P contient au moins une clause vide. Q12. On pose : P = (x1) ∧ (x1 ∨ x2 ∨ x3) ∧ (¬x1 ∨ x3 ∨ x4) ∧ (¬x1 ∨ ¬x2) ∧ (¬x2 ∨ ¬x1 ∨ x3) ∧ (x3 ∨ ¬x4 ∨ x5) ∧ (¬x1 ∨ x2 ∨ x5). Calculer Π(P). On pourra donner le résultat directement sans détailler les calculs. Q13. Soit P une formule de Horn. Montrer que Π(P) est une formule de Horn. Q14. Soit P une forme normale conjonctive. Montrer que P est satisfiable si et seulement si Π(P) est satisfiable. Q15. Soit P une forme normale conjonctive. Montrer que si () apparaît dans Π(P), alors P n’est pas satisfiable. Q16. Soit C une clause de Horn. Montrer que si C n’est ni la clause vide ni une clause unitaire positive, alors C est satisfiable. Q17. Soit P une formule de Horn ne contenant ni de clause vide ni de clause unitaire positive. Montrer que P est satisfiable. Q18. Soit P une formule de Horn. Montrer que P n’est pas satisfiable si et seulement si () apparaît dans Π(P). 6/11 -- 6 of 12 -- Partie III - Étude des classes sylvestres Étant donné un arbre binaire de recherche T , sa classe sylvestre est l’ensemble des mots qui donnent l’arbre T après insertion dans l’arbre vide. L’objectif de cette partie est de donner une caractérisation et une description de cet ensemble. On commence par rappeler la structure des arbres binaires de recherche ainsi que leurs propriétés usuelles. Puis, on introduit la notion de S-équivalence sur les mots qui permet de caractériser la classe sylvestre d’un arbre T . Enfin, à l’aide du produit de mélange, on présente un algorithme calculant la classe sylvestre d’un arbre donné. Dans toute la suite, Σ désigne un alphabet fini totalement ordonné. Le symbole ε désigne le mot vide. III.1 - Algorithme d’insertion dans un arbre binaire Définition 14 (Arbre binaire) Un arbre binaire T (étiqueté par les éléments de Σ) est récursivement soit : - l’arbre vide que l’on note ◦ ; - un triplet (Tg, r, Td) où r est un élément de Σ, Tg et Td des arbres binaires. Les éléments r, Tg et Td sont respectivement appelés racine, sous-arbre gauche et sous-arbre droit de T . Définition 15 (Arbre binaire de recherche) Un Arbre Binaire de Recherche (abrégé en ABR) T est récursivement soit : - l’arbre vide ; - un triplet (Tg, r, Td) où r est un élément de Σ, Tg et Td des ABR. De plus, toute valeur apparaissant dans Tg est strictement inférieure à r et toute valeur apparaissant dans Td est supérieure ou égale à r. Définition 16 (Insertion dans un arbre binaire) L’insertion d’un élément a de Σ dans un arbre binaire T est une opération que l’on note T ← a définie récursivement comme suit : - si T = ◦, alors T ← a = (◦, a, ◦) ; - si T = (Tg, r, Td) et r ≤ a, alors T ← a = (Tg, r, Td ← a) ; - si T = (Tg, r, Td) et r > a, alors T ← a = (Tg ← a, r, Td). On définit récursivement alors l’insertion d’un mot w dans un arbre binaire T noté également T ← w comme suit : - si w = ε, alors T ← w = T ; - si w = av avec a ∈ Σ, alors T ← w = (T ← a) ← v. Dans le cas où T est un ABR, on admet que T ← a et T ← w sont également des ABR. Étant donné un mot w sur Σ, l’arbre binaire de recherche associé à w est l’arbre ◦ ← w. Définition 17 (Classe sylvestre) Soit T un arbre binaire de recherche. La classe sylvestre de T que l’on note Syl(T ) est l’ensemble des mots w vérifiant : (◦ ← w) = T . Par exemple, si T = ((◦, a, ◦), b, (◦, c, ◦)), on a Syl(T ) = {bac, bca}. Et si T = ◦, alors Syl(T ) = {ε}. Pour simplifier la représentation des arbres binaires, on peut utiliser des graphes. Par exemple, l’arbre T = ((◦, a, ((◦, b, ◦), a, ◦)), f, (◦, c, ◦)) est représenté dans la figure 3. 7/11 -- 7 of 12 -- f a ◦ a b ◦ ◦ ◦ c ◦ ◦ Figure 3 - Représentation de T Dans la suite, les lettres de Σ sont représentées en Ocaml par des char et les mots sur l’alphabet Σ par des char list. Ainsi, le mot w = "arbre" est représenté par la liste w = [’a’;’r’;’b’;’r’;’e’]. On représente les arbres binaires en Ocaml à l’aide de la structure arbre suivante : type ’a arbre = Vide | Noeud of (’a arbre) * ’a * (’a arbre). Ainsi, l’arbre T = (◦, a, (◦, b, ◦)) est représenté en Ocaml par : Noeud(Vide, ’a’, Noeud(Vide, ’b’, Vide)). Q19. Représenter le graphe de l’ABR associé au mot "fantastique", l’ordre sur les lettres étant l’ordre alphabétique. Q20. Écrire une fonction récursive en Ocaml de signature : insertion_lettre : char -> char arbre -> char arbre et telle que insertion_lettre a t est l’arbre binaire obtenu en insérant la lettre a dans l’arbre binaire t. Q21. Écrire une fonction récursive en Ocaml de signature : insertion_mot : char list -> char arbre -> char arbre et telle que insertion_mot w t est l’arbre binaire obtenu en insérant le mot w dans l’arbre binaire t. Définition 18 (Lecture préfixe) Soit T un arbre binaire. La lecture préfixe de T que l’on note wT est le mot défini récursivement par : - si T = ◦, alors wT = ε ; - si T = (Tg, r, Td), alors wT = rwgwd où wg et wd sont les lectures préfixes respectives de Tg et de Td. 8/11 -- 8 of 12 -- Q22. Expliciter wT pour l’arbre binaire T représenté ci-dessous : s y l ◦ ◦ v ◦ ◦ e s t ◦ ◦ ◦ r ◦ e ◦ ◦ . Figure 4 - Représentation de T de Q22 Q23. Écrire une fonction récursive en Ocaml de signature : prefixe : char arbre -> char list et telle que prefixe t est le mot qui correspond à la lecture préfixe de l’arbre t. Q24. Soit T un ABR, soit wT la lecture préfixe de T . Montrer que T est l’ABR associé à wT . III.2 - Une relation d’équivalence sur les mots Définition 19 (S-adjacence) Soient u et v deux mots sur Σ. On dit que u est S-adjacent à v (ou que u et v sont S-adjacents) s’il existe trois lettres a < b ≤ c de Σ et trois mots f1, f2, f3 sur Σ vérifiant : (u = f1bf2acf3 et v = f1bf2caf3) ou (u = f1bf2caf3 et v = f1bf2acf3). Définition 20 (S-équivalence) Soient u et v deux mots sur Σ. On dit que u est S-équivalent à v (ou que u et v sont S-équivalents) s’il existe n ∈ N, (w0, w1, . . . , wn) ∈ (Σ!)n+1 vérifiant : u = w0, v = wn, ∀i ∈ {0, 1, . . . , n − 1}, wi est S-adjacent à wi+1 . Q25. Montrer que la relation " être S-équivalent à " est bien une relation d’équivalence sur Σ!. Q26. Soient a, b, c trois lettres de Σ vérifiant a < b ≤ c. Montrer que pour tout arbre binaire de recherche T contenant au moins la lettre b, on a : T ← ac = T ← ca. On pourra raisonner par récurrence sur le nombre de nœuds de T . Q27. Montrer que si deux mots u et v sont S-équivalents, alors les ABR (◦ ← u) et (◦ ← v) sont égaux. 9/11 -- 9 of 12 -- Q28. Soit w un mot de longueur n ≥ 1 sur Σ, soit r la première lettre de w. On veut montrer qu’il existe un mot w′ = ruv où u (respectivement v) est un mot dont toutes les lettres sont plus petites strictement (respectivement plus grandes au sens large) que r et tels que w et w′ sont S-équivalents. On note A l’ensemble des mots S-équivalents à w. Pour tout a = a0 a1 . . . an−1 ∈ A, on pose : N(a) = {(i, j) ∈ !1, n − 1"2∣∣∣ i < j, aj < r ≤ ai } . (a) Justifier que l’ensemble A est fini. (b) Justifier que tous les mots de A commencent par r. (c) Soit a ∈ A. Montrer que si N(a) ! ∅, alors il existe k ∈ !1, n − 2" tel que (k, k + 1) ∈ N(a). (d) Soit a ∈ A. Montrer que si N(a) = ∅, alors il existe u (respectivement v) un mot dont toutes les lettres sont plus petites strictes (respectivement plus grandes ou égales) que r et tels que a = ruv. (e) Soit a un élément de A tel que le nombre d’éléments de N(a) soit le plus petit possible. Montrer par l’absurde que N(a) = ∅ et en déduire qu’il existe u, v vérifiant les conditions de la question tels que ruv et w sont S-équivalents. Q29. Montrer que tout mot w est S-équivalent à wT , où wT est la lecture préfixe de T = (◦ ← w). On pourra raisonner par récurrence sur la longueur du mot w et exploiter les résultats de la Q28. Q30. En déduire que deux mots sont S-équivalents si et seulement si ils sont des éléments d’une même classe sylvestre. III.3 - Construction de classes sylvestres Pour construire des classes sylvestres, il est utile d’utiliser le produit de mélange. Définition 21 (Mélange) Soient u et v deux mots sur Σ. Le mélange de u et v, noté u v, est l’ensemble récursivement défini comme suit : - si v = ε, alors u v = {u} ; - si u = ε, alors u v = {v} ; - si u = au′ et v = bv′ où a et b sont des lettres, u′ et v′ des mots, alors : u v = {aw| ∃w ∈ u′ v} ∪ {bw| ∃w ∈ u v′} . Définition 22 (Mélange de langages) Soient L et M deux langages. Le mélange des langages L et M, noté L M, est défini par : L M = ⋃ u∈L,v∈M u v. Si au moins un des deux langages est égal à l’ensemble ∅ (! {ε}), alors on a L M = ∅. Étant donné un ABR T = (Tg, r, Td), on peut montrer que : Syl(T ) = {rw∣∣∣ ∃w ∈ Syl(Tg) Syl(Td)} . On admet ce résultat pour la suite de cette sous-partie. On note que Syl(◦) = {ε}. 10/11 -- 10 of 12 -- Q31. Expliciter sans justification tous les éléments de l’ensemble abba ba. Q32. Écrire une fonction récursive en Ocaml de signature : ajout_lettre : char -> char list list -> char list list et telle que ajout_lettre a liste est la liste de mots de la forme a::w où w est un élément de liste. Q33. Écrire une fonction récursive en Ocaml de signature : shuffle : char list-> char list -> char list list et telle que shuffle u v est une liste contenant exactement tous les mots de u v avec répétitions possibles d’un même mot. On devra utiliser la fonction auxiliaire ajout_lettre et l’opérateur de concaténation @. Q34. Écrire une fonction récursive en Ocaml de signature : shuffle_l : char list list -> char list list -> char list list et telle que shuffle_l l m est une liste contenant exactement tous les mots de L M où la liste l (respectivement m) représente le langage L (respectivement M), avec répétitions possibles d’un même mot. Seules les fonctions définies précédemment peuvent être utilisées en fonctions auxiliaires. Q35. Écrire une fonction récursive en Ocaml de signature : sylvestre_T : char arbre -> char list list et telle que sylvestre_T t est une liste contenant exactement tous les éléments de la classe sylvestre de t. Seules les fonctions définies précédemment peuvent être utilisées en fonctions auxiliaires. FIN 11/11 -- 11 of 12 -- I M P R I M E R I E N A T I O N A L E – 21 1158 – D’après documents fournis -- 12 of 12 --