Durée de l'épreuve : 4 heures
L'usage de la calculatrice et de tout dispositif électronique est interdit.
Les candidats sont priés de mentionner de façon apparente sur la première page de la copie :
INFORMATIQUE II - MPI
L'énoncé de cette épreuve comporte 12 pages de texte.
Cette épreuve concerne uniquement les candidats de la filière MPI.
Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur d'énoncé, il le signale sur sa copie et poursuit sa composition en expliquant les raisons des initiatives qu'il est amené à prendre.
Les sujets sont la propriété du GIP CCMP. Ils sont publiés sous les termes de la licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Pas de Modification 3.0 France. Tout autre usage est soumis à une autorisation préalable du Concours commun Mines Ponts.
Préliminaires
L'épreuve est composée d'un problème unique, comportant 38 questions. Le problème est divisé en quatre sections qui peuvent être traitées séparément, à condition de lire toutes les définitions de la section 1 . Dans la première section (page 1), nous introduisons la complexité de Kolmogoroff et étudions des propriétés de calculabilité. Dans la deuxième section (page 3), nous estimons la complexité de Kolmogoroff à l'aide du codage de Huffman. La troisième section (page 4) contient des prolégomènes pour la section suivante. Dans la quatrième section (page 5), nous nous appuyons sur un modèle de calcul épuré, introduit à travers plusieurs langages formels, afin toujours d'estimer la complexité de Kolmogoroff.
Dans tout l'énoncé, un même identificateur écrit dans deux polices de caractère différentes désigne la même entité, mais du point de vue mathématique pour la police en italique (par exemple ou ) et du point de vue informatique pour celle en romain avec espacement fixe (par exemple n, d ou pi).
Travail attendu
Pour répondre à une question, il est permis de réutiliser le résultat d'une question antérieure, même sans avoir réussi à établir ce résultat.
Il faudra coder des fonctions à l'aide du langage de programmation OCaml exclusivement, en reprenant l'en-tête de fonctions fourni par le sujet, sans s'obliger à recopier la déclaration des types. Il est permis d'utiliser la totalité du langage OCaml mais il est recommandé de s'en tenir aux fonctions les plus courantes afin de rester compréhensible. Des rappels ponctuels de documentation du langage OCaml peuvent être proposés à titre d'aide. Quand l'énoncé demande de coder une fonction, sauf demande explicite de l'énoncé, il n'est pas nécessaire de justifier que celle-ci est correcte ou de tester que des préconditions sont satisfaites.
Le barème tient compte de la clarté des programmes : nous recommandons de choisir des noms de variables intelligibles ou encore de structurer de longs codes par des blocs ou par des fonctions auxiliaires dont on décrit le rôle.
1 Complexité de Kolmogoroff
Nous notons l'ensemble ordonné des 256 caractères ASCII étendus usuels et l'ensemble des chaînes de caractères. Pour toute chaîne de caractères , la longueur de , notée , est le nombre de caractères qui la composent. Par exemple, la longueur de la chaîne "abac" est 4 . Le nombre d'occurrences d'un symbole dans une chaîne de caractères est noté . Par exemple, .
Dans l'ensemble du sujet, nous nous appuyons sur une machine universelle, c'est-à-dire une fonction OCaml eval, de type string -> string, telle que :
si la chaîne , de type string, est le code source d'une expression OCaml de type string et si l'exécution du code se termine sans erreur, alors eval x se termine et a pour valeur de retour la valeur de ;
sinon, eval ne se termine pas.
Les exécutions de eval ont lieu sur une machine idéale dont la mémoire est infinie et qui est capable de gérer des types natifs de taille quelconque.
Définition : Pour toute chaîne de caractères , nous disons que la chaîne de caractères est une description de la chaîne si le calcul eval x se termine et renvoie la chaîne . Nous appelons complexité de Kolmogoroff de et notons la longueur de la plus courte chaîne de caractères qui décrit .
L'objet de ce sujet est d'étudier des propriétés et diverses majorations de la complexité de Kolmogoroff. Dans toutes nos illustrations, nous nous concentrons sur la description de la chaîne de caractères
qui correspond à l'entier écrit en base 10 et que nous fixons une fois pour toutes.
1.1 Un premier exemple
- Proposer une première majoration de la complexité de Kolmogoroff , qui s'appuie sur la chaîne de caractères comme description de .
Indication OCaml : Il est rappelé que la fonction string_of_int convertit un entier en une chaîne de caractères. - Soient un entier naturel et la partie entière de . Exprimer la quantité en fonction de . Compléter le code OCaml suivant en utilisant une stratégie «diviser pour régner » :
let exp10 (* Calcul de a ecrire *)
in string_of_int (exp10 (exp10 10))
afin d'en faire une description de la chaîne de caractères . . En déduire une nouvelle borne grossière (à près) de la complexité de Kolmogoroff , significativement meilleure que celle de la question 1. - Décrire quelle ou quelles difficultés adviendraient si l'on exécutait le code de la question 2 sur une machine réelle.
1.2 Quelques propriétés
Indication OCaml : L'expression String.make (n : int) (sigma : char) : string désigne la chaîne de caractères répétant fois le caractère . Pour tout entier compris entre 0 et 255 , Char.chr ( n : int) : char désigne le caractère dans la numérotation ASCII. - Présenter une bijection entre l'ensemble des entiers naturels et l'ensemble de chaînes de caractères. En écrire le code sous la forme d'une fonction OCaml phi (n : int) : string.
Nous prétendons avoir écrit une fonction OCaml kolmogoroff (y : string) : int qui calcule la complexité de Kolmogoroff .
5 - Écrire une fonction OCaml psi (m : int) : int dont la valeur de retour est l'entier
où est la bijection définie à la question 4 et qui utilise la fonction kolmogoroff.
6 - Établir d'une part que, pour tout entier naturel , on a
et d'autre part que l'on a
Discuter l'existence de la fonction OCaml kolmogoroff.
Définition : Nous appelons décompresseur toute fonction OCaml d : string -> string. Pour toute chaîne de caractères et pour tout décompresseur (noté informatiquement d), nous disons que la chaîne de caractères est une description de la chaîne par rapport à si le calcul eval (d z) se termine sans erreur et a pour valeur de retour . Nous appelons complexité de Kolmogoroff par rapport à de la chaîne , et notons , la longueur de la plus courte chaîne de caractères qui décrit par rapport à .
7 - Dire comment se nomme en informatique un programme qui transforme un code source dans un certain langage de programmation en un code équivalent dans un second langage.
8 - Montrer que pour tout décompresseur , il existe une constante entière telle que, pour toute chaîne de caractères , nous avons :
2 Estimation de la complexité grâce au décompresseur de Huffman
Nous fixons dans cette section la chaîne de caractères suivante
La chaîne contient 71 caractères, l'espace étant un caractère et les guillemets ne faisant pas partie de la chaîne.
9 - Inférer le type OCaml de l'expression dénotée par la chaîne de caractères . - Déterminer la valeur de l'évaluation de x0 en tant que code source OCaml. - Signaler une ou plusieurs caractéristiques du code source qui rend la lecture de ce code impénétrable par un humain.
Indication OCaml : Nous rappelons le détail de quelques fonctions du module OCaml Hashtbl permettant de manipuler des dictionnaires (ou tableaux associatifs) mutables.
Hashtbl.create ( n : int) : ('a, 'b) Hashtbl.t crée un dictionnaire vide de taille initiale .
Hashtbl.add (d : ('a, 'b) Hashtbl.t) (k : 'a) (v : 'b) : unit ajoute une association entre la clé et la valeur au dictionnaire .
Hashtbl.find_opt (d : ('a, 'b) Hashtbl.t) ( ) : ' b option vaut Some v sile dictionnaire d possède une association entre la clé et la valeur et vaut None sinon. - Écrire une fonction OCaml count (x : string) : (char, int) Hashtbl.t dont la valeur de retour est un dictionnaire qui associe chaque caractère présent dans la chaîne à son nombre d'occurrences .
Nous exécutons count x0 et obtenons le dictionnaire suivant :
'n'
't'
'i'
'l'
'l'
'c'
'f'
'h'
'r'
's'
'-'
'*'
'0'
'='
'e'
'
8
8
4
4
4
1
1
1
1
1
1
1
3
4
10
19
Nous appelons la chaîne de bits correspondant à la compression de la chaîne par l'algorithme de Huffman. - Dessiner un arbre de Huffman associé à la chaîne de caractères . Il est recommandé de placer les feuilles de gauche à droite comme dans le tableau ci-dessus.
Nous notons le décompresseur qui utilise l'arbre de Huffman de la question 13 pour transformer une chaîne de bits en un mot et renvoie la chaîne de caractères "string_of_int ( )". - Calculer la longueur de la chaîne obtenue après compression de . En déduire que la complexité de Kolmogoroff de par rapport au décompresseur vérifie
3 Interlude
Nous souhaitons écrire une fonction new_string : unit -> string ainsi spécifiée : à chaque appel, une chaîne de caractères inédite est produite. Nous offrons trois propositions de code.
let inc s = s := "a" ~ (!s); !s (* Commun aux 3 propositions *)
let new_string1 = (* Proposition 1 *)
let seed1 = ref "#" in
fun () -> inc seed1
let new_string2 () = (* Proposition 2 *)
let seed2 = ref "#" in
inc seed2
let seed3 = ref "#" (* Proposition 3 *)
let new_string3 () =
inc seed3
15 - Analyser la portée de la variable seed1, respectivement seed2 et seed3, dans la fonction new_string1, respectivement new_string2 et new_string3.
16 - Déduire de la question 15 laquelle des trois fonctions new_string1, new_string2 et new_string3 ne respecte pas la spécification. Écrire un test qui permet de discriminer la fonction erronée.
17 - Déduire de la question 15 laquelle des deux fonctions correctes restantes est plus propice à des erreurs de manipulation. Expliquer.
4 Estimation de la complexité grâce au décompresseur de De Bruijn
Nous nous avisons que la complexité de Kolmogoroff est influencée par la verbosité et l'expressivité du langage de programmation. Dans cette section, nous tentons de réduire l'encombrement ou la facilité d'écriture dus à la syntaxe du langage OCaml en introduisant un modèle de calcul nouveau et épuré.
4.1 Construction syntaxique d'un langage
Nous présentons systématiquement les grammaires sous la forme d'un quadruplet ( ) où désigne l'alphabet des symboles non terminaux, l'alphabet des symboles terminaux, le symbole initial et l'ensemble des règles de production, de la forme avec et .
Une dérivation immédiate se note , avec , et indique qu'il existe une règle de production de et des décompositions et , avec . Une dérivation se note et indique l'existence d'une suite finie, éventuellement vide, de dérivations immédiates. Enfin, le langage engendré par une grammaire se note et désigne l'ensemble des mots de qui dérivent du symbole initial .
Selon les questions, nous représentons les mots de par le type char list ou le type string.
Soit la grammaire ( ) dont les règles de production sont
18 - Exhiber une expression régulière qui dénote le langage .
19 - Dessiner l'automate de Glushkov associé à l'expression régulière de la question 18.
20 - Écrire une fonction OCaml parseV (w : char list) : string * char list dont la spécification suit :
Pré-condition : Il existe une décomposition du mot en avec et . Valeur de retour : Couple ( ) où le préfixe est représenté par le type string et est le suffixe restant.
Effet : Une exception SyntaxError est levée si la pré-condition n'est pas satisfaite.
Soit la grammaire dont les règles de production sont
21 - Montrer que le langage est sans préfixe, c'est-à-dire qu'il n'existe pas deux mots non vides et dans tels que soit un préfixe strict de . On pourra, par exemple, raisonner par induction structurelle sur le nombre de parenthèses ouvrantes et fermantes qui se trouvent dans un préfixe d'un mot de . - Montrer que la grammaire n'est pas ambiguë, c'est-à-dire que, pour tout mot du langage , il n'existe qu'un seul arbre d'analyse (parfois aussi appelé arbre de dérivation) associé.
Soit la grammaire ( ) dont les règles de production sont
23 - Montrer que la grammaire n'est pas ambiguë.
Soit finalement la grammaire ( ) dont les règles de production sont
Nous admettons que la grammaire n'est pas ambiguë. Nous appelons variable les mots de . Informellement, la grammaire engendre un langage qui permet de parler de variables, d'applications d'une expression à une autre et de fonctions. Il nous reste à en construire une sémantique, ce qui sera fait en section 4.3.
Afin de représenter l'arbre d'analyse d'un mot du langage , nous introduisons le type ada par la déclaration suivante.
type ada = V of string | A of (ada * ada) | F of (string * ada)
Nous notons l'ensemble des arbres d'analyse.
Le constructeur OCaml V représente les dérivations immédiates de règle et introduit les feuilles; le constructeur OCaml A représente les dérivations immédiates de règle et introduit des nœuds internes d'arité 2 ; le constructeur OCaml F représente les dérivations immédiates de règle et introduit des nœuds internes d'arité 1 . Les dérivations à partir du symbole non terminal sont directement représentées par une valeur OCaml de type string.
admet pour arbre d'analyse :
24 - Écrire une fonction OCaml parseT (w : char list) : ada * char list dont la spécification suit :
Pré-condition : Il existe une décomposition du en avec et , dans laquelle le préfixe est de longueur maximale.
Valeur de retour : Couple ( ) où est l'arbre d'analyse de et est le suffixe restant.
Effet : Une exception SyntaxError est levée si la pré-condition n'est pas satisfaite.
Indication OCaml : Nous supposons définie une fonction charlist_of_string : string -> char list qui transforme une chaîne de caractères en une liste de caractères. - Écrire une fonction OCaml parse ( w : string) : ada dont la valeur de retour est l'unique arbre d'analyse de quand et qui lève une exception SyntaxError sinon.
Définition : Pour tout entier naturel , nous définissons le mot
où la variable b# apparaît fois à droite des deux symboles ->. - Indiquer s'il existe un automate fini capable de reconnaître le langage et justifier la réponse.
Définition : Plus généralement, nous disons qu'un mot de incarne un entier naturel s'il existe deux variables distinctes et dans telles que est de la forme
où la variable apparaît fois à droite des deux symboles . - Écrire une fonction OCaml int_of_ada (a : ada) : int dont la valeur de retour est l'entier naturel incarné par . Si un tel entier n'existe pas, une exception SyntaxError est levée.
4.2 Réécriture des variables et sérialisation
- Nommer une structure de donnée concrète efficace qui réalise le type de donnée abstrait «ensemble » lorsqu'il existe une relation d'ordre entre les objets à ranger.
Indication OCaml : Nous supposons définis un module OCaml StringSet permettant de construire des ensembles de chaînes de caractères persistants, de type StringSet.t, et des fonctions :
StringSet.mem : string -> StringSet.t -> bool qui teste l'appartenance d'un élément à un ensemble.
StringSet.remove : string -> StringSet.t -> StringSet.t qui retourne un ensemble privé d'un élément.
StringSet.singleton : string -> StringSet.t qui construit un singleton à partir d'un élément.
StringSet.union : StringSet.t -> StringSet.t -> StringSet.t qui construit l'union de deux ensembles.
Définition : L'ensemble des variables libres d'un arbre d'analyse est défini par induction structurelle avec les règles d'inférence suivantes :
si l'arbre d'analyse est de la forme V v , où , alors est le singleton ;
si l'arbre d'analyse est de la forme A (a1, a2), où et sont deux arbres d'analyse, alors est la réunion ;
si l'arbre d'analyse est de la forme F (v, a1), où et est un arbre d'analyse, alors est l'ensemble . - Écrire une fonction OCaml free_vars (a : ada) : StringSet.t dont la valeur de retour est l'ensemble des variables libres de l'arbre d'analyse .
Définition : Un arbre d'analyse est dit clos s'il ne contient pas de variables libres; de même, un mot de est dit clos si son arbre d'analyse est clos.
Dans un arbre d'analyse clos , pour toute chaîne de caractères , si la construction OCaml v v apparait comme feuille de l'arbre , alors il existe un nœud interne de la forme F (v,_) parmi les ascendants de V v qui coïncide avec l'《 introduction » de la variable .
Afin de ne plus s'encombrer avec des variables nommées par une chaîne de caractères, nous adoptons une nouvelle représentation des mots du langage sous forme d'un arbre, appelé terme de De Bruijn.
Définition : Un terme de De Bruijn s'obtient à partir d'un arbre d'analyse en remplaçant toute feuille de l'arbre , disons V v avec , par une feuille étiquetée par l'entier , où est le nombre de nœuds internes de la forme F (v',) avec , qui existent entre ladite feuille V v et le plus proche nœud interne de la forme F (v,) parmi ses ascendants dans l'arbre d'analyse .
Nous déclarons un nouveau type
type of int | Adb of ( ) | Fdb of tdb
Nous notons l'ensemble des termes de De Bruijn.
Voici un exemple de construction d'un terme de De Bruijn (à droite) à partir d'un arbre d'analyse (à gauche) du mot
(aa#->ab#->ba#->bb#->(ab#((bb#aa#)ab#))bb#->(bb#aa#->(bb#->bb#aa#))):
30 - Dessiner le terme de De Bruijn qui représente le mot .
31 - Écrire une fonction OCaml ada_of_tdb ( t : tdb) : ada dont la valeur de retour est un arbre d'analyse clos associé au terme de De Bruijn .
Définition : Le codage binaire des termes de De Bruijn est l'application définie par induction structurelle avec les règles d'inférence suivantes sur l'ensemble des termes de De Bruijn :
si le terme est de la forme u, avec , alors est la chaîne de caractères (avec le symbole 1 répété fois).
si le terme est de la forme et étant deux termes de De Bruijn, alors est la chaîne de caractères .
si le terme est de la forme Fdb t1, où est un terme de De Bruijn, alors est la chaîne de caractères . - Soient un entier naturel et le terme de De Bruijn associé au mot et obtenu à la question 30. Calculer la longueur de la chaîne de caractères qui encode . - Vérifier que le codage binaire des termes de De Bruijn est une application injective.
Nous utilisons le type string avec les caractères '0' et '1' afin de représenter des codages binaires de termes de De Bruijn.
34 - Écrire une fonction OCaml decode ( string ) : tdb dont la valeur de retour est l'unique terme de De Bruijn tel que si un tel terme existe et qui lève une exception SyntaxError sinon.
Il est possible de s'appuyer sur la fonction charlist_of_string précédemment présentée.
4.3 Interpréteur et décompresseur de De Bruijn
Dans cette sous-section, nous construisons un interpréteur, c'est-à-dire une procédure qui évalue les expressions appartenant au langage et en déduisons une nouvelle description du mot " relative à un décompresseur approprié.
Naïvement, lorsque nous rencontrons un sous-mot de la forme avec et , nous aimerions que soit équivalent à un mot tiré de dont les occurrences de la variable ont été remplacées par . Autrement dit, lorsqu'un arbre d'analyse est de la forme A (F (v, b), a), nous voudrions construire un nouvel arbre à partir de et dans lequel les apparitions de sont devenues des sous-arbres .
Définition : Soient deux arbres d'analyse et une variable. La substitution de la variable par l'arbre a dans l'arbre est l'application définie par induction structurelle avec les règles d'inférence suivantes :
Si l'arbre est de la forme V v1, avec , alors
Si l'arbre est de la forme A (b1, b2), où et sont deux arbres d'analyse, alors
où et .
Si l'arbre est de la forme , avec et , alors
où est une variable inédite qui n'appartient pas à .
Nous supposons déjà programmée une fonction new_string : unit -> string inspirée de la section 3 qui permet, si besoin, d'engendrer une variable de jamais encore utilisée.
35 - Écrire une fonction OCaml substitute (v : string) (by_a : ada) (in_b : ada) : ada qui substitue la variable par l'arbre dans l'arbre .
Définition : La réduction en un pas est l'application définie par induction structuelle avec les règles d'inférence suivantes :
Si l'arbre est de la forme V v , où , alors la valeur n'est pas définie.
Si l'arbre est de la forme A (a1, a2), où et sont deux arbres d'analyse, alors
Si l'arbre est de la forme F (v, a1), où et , alors
36 - Écrire une fonction OCaml reduce_one_step (a : ada) : ada qui implémente la réduction en un pas . Lorsque reduce_one_step rencontre un cas non défini, une exception NoReduction est levée.
37 - Écrire une fonction OCaml interpret (a : ada) : ada qui applique répétitivement la réduction en un pas à l'arbre d'analyse jusqu'à ce que la réduction ne soit plus définie. La valeur de retour est le dernier arbre d'analyse rencontré.
Nous admettons que, pour tout entier naturel non nul , si est le mot de
l'expression interpret (parse pi) produit une incarnation de l'entier . Nous notons le décompresseur défini par
let decompB (z : string) : string =
"string_of_int }\mp@subsup{}{|}{}(int\_of_ada\sqcup(interpret\lrcorner(ada_of_tdb\lrcorner(decodeப" ^ z ^ "))))"
38 - Proposer une méthode pour obtenir une chaîne de caractères , formée uniquement de 0 et de 1 , telle que decompB zo a pour valeur de retour la chaîne de caractères "1000000 ..." et en calculer la longueur. En déduire que la complexité de Kolmogoroff de par rapport au décompresseur vérifie
Fin de l'épreuve
Mines Informatique 2 MPI 2023 - Version Web LaTeX | WikiPrépa | WikiPrépa
