Mines Informatique optionnelle MP 2023

A2023 -- INFO MP

Cm

Concours commun

Mines-Ponts

ÉCOLE DES PONTS PARISTECH,
ISAE-SUPAERO, ENSTA PARIS,
TÉLÉCOM PARIS, MINES PARIS,
MINES SAINT-ÉTIENNE, MINES NANCY,
IMT ATLANTIQUE, ENSAE PARIS,
CHIMIE PARISTECH - PSL.

Concours Mines-Télécom,
Concours Centrale-Supélec (Cycle International).

CONCOURS 2023
ÉPREUVE D'INFORMATIQUE MP

Durée de l'épreuve : 3 heures

L'usage de la calculatrice ou de tout dispositif électronique est interdit.

Cette épreuve concerne uniquement les candidats de la filière MP.
Les candidats sont priés de mentionner de façon apparente
sur la première page de la copie :
INFORMATIQUE - MP

L'énoncé de cette épreuve comporte 11 pages de texte.

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 CCMEP. 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.

Épreuve d'informatique d'option MP 2023

Préliminaires

L'épreuve est composée d'un problème unique, comportant 27 questions. Après 
cette section
de préliminaires, qui présente le jeu du hanjie, le problème est divisé en 
trois sections qui
peuvent être traitées séparément, à condition d'avoir lu les définitions 
introduites jusqu'à la
question traitée. Dans la première section (page 2), nous résolvons le jeu par 
des raisonnements
logiques. Dans la deuxième section (page 3), nous modélisons le jeu et le 
résolvons par une
stratégie algorithmique de retour sur trace. Dans la troisième section (page 
6), nous appliquons
une méthode de parcours de graphe en théorie des automates pour accélérer la 
résolution du
Jeu.

Dans tout l'énoncé, un même identificateur écrit dans deux polices de 
caractères différentes
désigne la même entité, mais du point de vue mathématique pour la police en 
italique (par
exemple n) et du point de vue informatique pour celle en romain avec espacement 
fixe (par
exemple n).

Des rappels de logique et des extraits du manuel de documentation de OCaml sont
reproduits en annexe. Ces derniers portent sur le module Array et le module 
Hashtbl1.

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, en 
reprenant
l'en-tête de fonction fourni par le sujet, sans s'obliger à recopier la 
déclaration des types.
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 vérifier 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.

Description du jeu du hanjie

Le hanjie est un jeu de réflexion à l'intersection de l'art des pixels et de la 
tomographie
discrète, technique d'imagerie courante en médecine, en géophysique ou en 
science des
matériaux entre autres domaines.

Il consiste à retrouver une image par le noircissement de certaines cases d'une 
grille
rectangulaire sur la base d'indications laissées sur les côtés de la grille. 
Pour chaque rangée,
qu'elle soit horizontale ou verticale, le joueur dispose d'une suite d'entiers 
non nuls #1, to, t3,
etc. qui indiquent que la rangée contient une série de t, cases noires 
consécutives, suivie plus
loin d'une série de {> cases noires consécutives, et ainsi de suite. Un nombre 
quelconque de
cases blanches peut se trouver en tête ou en queue de rangée ; au moins une 
case blanche
sépare deux séries de cases noires.

Page 1 sur 11
Épreuve d'informatique d'option MP 2023

Voici un exemple, que nous résolvons à la main. Une
grille vide est fournie ci-contre. Elle est de dimension
5 x 7. Nous marquons les cases par des symboles « ? »
tant que nous ignorons leur couleur.

Nous comptons les rangées à partir de 0, de gauche à
droite pour les colonnes et du haut vers le bas pour les
lignes.

La colonne 0 et la colonne 5 sont de longueur 5. Or
l'indication est [5] dans les deux cas. Elles doivent
donc chacune contenir 5 blocs noirs consécutifs. Nous
les noircissons en totalité.

Dans la ligne 0, il n'y a qu'une seule manière de placer un
bloc de 4 cases noires puis 2 cases noires. De même, dans
la ligne 2, il n y à qu une seule manière de positionner
le bloc de longueur 2 : il doit se trouver au milieu entre
les deux blocs déjà isolés. Dans la ligne 3, nous avons
déjà placé deux cases noires : les autres sont donc toutes
blanches. Enfin, dans la ligne 4, il n'y a plus qu'une
seule manière de placer un bloc de 6 cases noires.

Enfin, en reprenant les indications des colonnes, nous
voyons que dans les colonnes 1, 2 et 4, la dernière case
inconnue est blanche. Dans la colonne 3 et 6 en revanche,
nous devons noircir la dernière case inconnue. Nous avons
obtenu une solution de notre hanjie. Elle est unique.

1. Hanjie et calcul de vérité

[4,2]
[1,1,2]
[1,2,1]

[1,1]

[6]

[4,2]
[1,1,2]
[1,2,1]

[1,1]

[6]

[4,2]
[1,1,2]
[1,2,1]

[1,1]

[6]

[4,2]
[1,1,2]
[1,2,1]

[1,1]

[6]

[T'T]

Tr
O1
Lu

[T'T'1]

[TE]

[T]
[S]
[c]

[S]

[S]

[T'1T°7]
[T'EUR]

CT]
[S]
[T]

CT]
[S]
[c]

Dans cette section, nous raisonnons avec la logique propositionnelle pour 
déterminer la
couleur de certaines cases. Nous nous concentrons sur le hanjie ho défini par

= Hs
JL

[c]

[2]
[1,1]

et dont une solution est la suivante :

[2]
[1,1]

[T]

T7
=
LL

T7
=
LL

C] 1 -- Établir, par raisonnement en langue française, que la solution du 
hanjie ho est unique.

Nous introduisons six variables booléennes, nommées %o.
T1, ..., 5 et Correspondant aux cases ci-contre. Nous
associons la valeur de vérité V (vrai) à la couleur noire
et F (faux) à la couleur blanche.

Page 2 sur 11

TO

l1

T9

L3

T4

T5

Épreuve d'informatique d'option MP 2023

Soit Lo le prédicat : « l'indication de la ligne zéro du hanjie ho est 
satisfaite ».

C[] 2 -- Dresser la table de vérité du prédicat Lo portant sur les variables 
%0, æ1. %2. En
déduire une formule de logique & sous forme normale conjonctive qui décrit le 
prédicat L,.

Soit C le prédicat : « l'indication de la colonne du milieu du hanjie À, est 
satisfaite ».

CT 3 -- Dresser la table de vérité du prédicat C; portant sur les variables x,, 
41. En déduire
une formule de logique 1 sous forme normale conjonctive qui décrit le prédicat 
C.

Les règles d'inférence de la déduction naturelle sont rappelées dans l'annexe B.
[T 4 --- Construire un arbre de preuve qui démontre le séquent 4 + x1 à partir 
des règles

d'inférence de la déduction naturelle.

[] 5 -- Construire de même un arbre de preuve qui démontre le séquent #, 21 F 
24.

Nous notons #Y' la formule de logique obtenue à partir de # en remplaçant la 
variable x;
par æ2 et la variable x4 par %s.

CT 6 --- Démontrer qu'il n'existe pas d'arbre de preuve qui démontre la formule 
& A #" -- -%0.

2. Cadre de résolution systématique du hanijie

2.1. Le hanjie

Nous fixons un alphabet © = {N,B} et notons EUR l'alphabet complété EUR = 
{N,B,1}. Les
symboles N, B et | désignent respectivement les couleurs Noir, Blanc et 
Inconnu. Nous déclarons
en OCamil :

type couleur = N | B |TI

[] 7 - Écrire une fonction OCaml est connu (c:couleur) : bool dont la valeur de 
retour
est le booléen V (vrai) si c EUR EUR = {N,B} et le booléen F (faux) si c égale 
la couleur |.

Pour l'ensemble du sujet, nous fixons deux entiers naturels non nuls m et n qui 
désignent
respectivement un nombre de lignes et un nombre de colonnes.

Définition : Une présolution d'un hanjie est un tableau de dimension m x n à 
valeurs dans
l'ensemble EUR.
Les figures de l'introduction (en page 2) sont des exemples de présolutions.

Page 3 sur 11
Épreuve d'informatique d'option MP 2023

Indication OCami : Nous déclarons des constantes globales, le type et le 
constructeur
Suivants :

let m=5

let n = 7

type presolution = couleur array array

let presolution init () : presolution = (* cree une presolution *)
Array.make matrix mn I (* toute egale a I *)

Lorsqu'un tableau p est de dimension m X n, nous numérotons ses cases ligne 
après ligne
avec les entiers compris entre 0 et m -n -- I. La case en ligne x et colonne y 
a pour numéro
z =y+x.n. Nous notons alors p|z] la valeur de p en position z.

Dans notre exemple, nous aurions les numéros :

na

ligne x --|7|8/|9|10/11|12|13 p. GG) & plel

1411511617 11811920 m Z=y+xn
21 122123 |24|25 | 26 | 27 x = 2/n
28 | 20 | 30 | 31132 |33 | 34 y--=2 mod n.

colonne y

CT 8 -- Écrire en langage OCaml un accesseur get (p:presolution) (z:int) : 
couleur dont
la valeur de retour est la couleur p|z|.

[19 - Écrire en langage OCaml un transformateur set (p:presolution)
(z:int) (c:couleur) : presolution dont la valeur de retour p' est une copie pro-
fonde de p avec p'{z] -- c, c'est-à-dire une copie n'ayant aucun lien avec la 
présolution
initiale.

Dans tout le sujet, on s'astreint à manipuler le type presolution exclusivement 
en employant
les fonctions presolution_init, set et get. De la sorte, on pourra considérer 
que le type
presolution est immuable.

CT] 10 -- Définir le terme immuable et citer un avantage à utiliser des 
variables immuables.

La ligne x d'un tableau, avec 0 < x < m, désigne l'ensemble des positions de numéro x - n, xen+1,...,(x+1)-.n--1 (lire n numéros au total). La colonne y, avec 0 < y < n, désigne l'ensemble des positions de numéro y, y+n,...,y+(m--1):n (lire m numéros au total). Nous utilisons le terme rangée pour parler indifféremment d'une ligne ou d'une colonne. Définition : Nous disons qu'une rangée d'une présolution est complète si elle est à valeurs dans EUR. CT 11 -- Écrire une fonction OCaml est_complete _lig (p:presolution) (x:int) : bool qui teste si la ligne x de la présolution p est complète. Nous supposons écrite de même une fonction est complete col (p:presolution) (y:int) : bool, qui teste si la colonne y de la présolution p est complète. Page 4 sur 11 Épreuve d'informatique d'option MP 2023 Définition : Si une rangée est complète, nous appelons {race la suite des longueurs des sous-suites maximales de termes consécutifs égaux à Noir. Par exemple, la trace de la rangée B,N,N,B, N, B.N.N,N,B,N us NO Lu est [2;1;3;1|. CT 12 -- Écrire une fonction OCaml trace lig (p:presolution) (x:int) : int list dont la valeur de retour est la trace de la ligne x de la présolution p. Nous supposons écrite de la même manière une fonction trace col (p:presolution) (y:int) : int list, dont la valeur de retour est la trace de la colonne y de la présolution p. Définition : Le terme indication désigne toute suite finie d'entiers naturels non nuls. Nous appelons hanjie de dimension mxn la donnée d'un tableau d'indications 2nd;,, de longueur m, et d'un tableau d'indications 2nd,,4, de longueur n. Indication OCamil : Nous déclarons : type hanjie = { ind lig : int list array; ind col : int list array } Définition : Une solution d'un hanjie h = (ind;;,, ind.) de dimension m x n est un tableau p de même dimension m x n et à valeurs dans l'ensemble EUR tel que le tableau des traces des lignes de p égale 2nd;, et le tableau des traces des colonnes de p égale 2nd.4. Par exemple, le hanjie étudié en introduction et déclaré par : [II4;2]; [1;:1;2]; [1;2;1]; [1;1]; [6] |]; CIES]; (1:11; (1;1;1]; [(3;1]; [1] ; [5] ; let h escargot = {ind lig ind col [2] |] } admet comme solution la valeur OCamil : let p_escargot = [IT[IN; N; N; N; B; N; Nil; CLIN; B; B; N; B; N; Nl]; CLIN; B; N; N; B; N; Bl]l; LIN; B; B; B; B; N; Bl]; CIN; N; N; N, N; N; BI] 1] [] 13 -- Écrire une fonction OCaml est _ admissible (h:hanjie) (p:presolution) : bool dont la valeur de retour est le booléen V (vrai) si et seulement si, pour toute rangée complète de p, la trace égale l'indication du hanjie. Il n'est pas nécessaire de contrôler que la présolution et le hanjie ont même dimension. 2.2. Recherche de solutions Définition : Nous disons qu'une présolution p" étend une présolution p, si pour tout numéro z avec p{[z| EUR EUR, les couleurs p'{[z] et p|z] sont égales. Par exemple, la présolution p° -- | B | N | | | N | B | étend p -- | B | | | | | N | | | puisque deux cases sont passées de la couleur | à une couleur connue N ou B et les autres sont restées inchangées. Page 5 sur 11 Épreuve d'informatique d'option MP 2023 Indication OCaml : Le type paramétré 'a option permet de distinguer l'absence d'une valeur définie, avec le constructeur None, de la présence d'une valeur v de type 'a, avec la construction Some v. Il est défini par la déclaration : type 'a option = None | Some of 'a [] 14 -- Écrire une fonction OCaml etend_ trivial (h:hanjie) (p:presolution) (z:int) (c:couleur) : presolution option qui, si la copie p' de p avec p'[z] = c est une extension de p et est admissible au sens de la question 13, renvoie Some p' et sinon renvoie None. Plus généralement, nous appelons extenseur toute fonction OCamil etend (h:hanjie) (p:presolution) (z:int) (c:couleur) : presolution option ainsi spécifiée : Précondition : Le numéro z est valide (0 < z  presolution --->
int -> couleur -> presolution option

Nous souhaitons implémenter une recherche de solutions par une stratégie de 
retour sur trace
dans laquelle les cases d'une présolution sont considérées par numéro croissant.

CT 15 -- Compléter le code suivant afin que, si p est une présolution dont au 
moins les z -- 1
premières cases appartiennent à EUR, alors explore p z renvoie si possible une 
solution qui
étend p à partir du numéro z à l'aide d'itérations sur l'extenseur ext et sinon 
renvoie la
valeur None :
let resout (h:hanjie) (ext:extenseur) : presolution option =
let p0 = presolution init () in
let rec explore (p:presolution) (z:int) : presolution option =
(x A COMPLETER *)
in
explore p0 0

3. Résolution autonome de lignes et extenseur

La stratégie d'extension de la question 14 est très naïve. Elle ignore les 
déductions in-
termédaires qui pourraient être faites grâce à une seule indication à partir 
d'une rangée
partiellement complétée.

Soit w EUR © le mot formé des inscriptions dans une rangée dont l'indication 
est T7 --
Hi5t2:...:t,] avec s > 1. Nous notons [w|,; l'ensemble des mots de EUR" de 
trace 7 qui
étendent w. Lorsque l'ensemble [w], n'est pas vide, nous posons, pour tout 
indice à compris
entre 0 et n -- 1, l'ensemble des couleurs

FE, = {2, EUR CZ = 20.2» 1 E [w|,}.

Page 6 sur 11
Épreuve d'informatique d'option MP 2023

Enfin nous posons, pour tout indice à compris entre 0 et n -- 1,

| si Æ, = {B,N}

Définition : Nous appelons plus grande extension commune du mot w par rapport à 
l'indi-
cation T le mot &æ = 20---25_1 E ©, lorsqu'il est défini.

Par exemple, si nous rencontrons la ligne | N | | | | | | | | | | | N | | | 
avec l'indication [1,2,1].
il y à deux extensions complètes possibles : INIBININB BIN Bou NB BININB NB!
La plus grande extension commune est dans ce cas IN | B | | | N | | | B | N | B 
|

CT 16 -- Dans cette question uniquement, nous supposons que n est de la forme n 
= 3s -- 1,
où 5 est un entier naturel non nul, que l'indication 7 est égale à [1; 1;...;1] 
avec s occurrences
de 1 et que w vaut |". Compter le nombre de mots du langage [w|..

Nous notons L. le langage des mots de EUR* de trace 7 = [t1;t2;...:t,] 
quelconque. Nous
supposons toujours que l'on à s > 1.

[] 17 -- Proposer une expression régulière e qui dénote le langage L,. Aucune 
justification
n'est attendue.

S

CT 18 -- Dessiner un automate fini déterministe incomplet à s + > t; états qui 
reconnaît le
i=1
langage L,. Aucune justification n'est attendue.

[] 19 -- Dire combien d'états l'automate de Glushkov qui dérive de l'expression 
régulière e
de la question 17 possède et si cet automate coïncide avec celui dessiné à la 
question 18.

Dans ce qui suit, nous nous intéressons à des automates finis déterministes 
incomplets
qui ne possèdent qu'un seul état final et dont l'alphabet est toujours EUR. 
Nous numérotons
systématiquement les états de sorte que l'état initial soit 0 et l'unique état 
final soit r -- 1,
où r est le nombre total d'états. Le terme transition désigne un triplet (q, c, 
q') où q et q' sont
des états (avec 0 < q,q° < r) et c est une couleur (avec c EUR EUR). Nous représentons la fonction de transition par un tableau de longueur r ; la case q du tableau contient un dictionnaire qui, quand il existe une transition (q, c, q'), associe la couleur c à l'état q'. Nous déclarons : type automate = { r : int; transitions : (couleur, int) Hashtbl.t array} Définition : Le déploiement d'un automate À ayant r états par un mot w = wow: ::: Wh_1 EUR C° de longueur n est un nouvel automate, noté À © w, qui possède r -+ (n + 1) états. Pour toute transition (q,c,q') dans l'automate À et pour tout indice 4 compris entre 0 et n -- 1, Page 7 sur 11 Épreuve d'informatique d'option MP 2023 pour w, E Cet c = w; ou encore pour w; = |, il y a dans l'automate À © w une transition G-r+ac(i+l)-r +4). [TT 20 -- Dans cette question uniquement, on considère l'exemple avec n = 4, wo = INBI EUR ©" et où À, est l'automate défini par rod Dessiner le déploiement A5 © wo. Marquer les états accessibles. Marquer les états co- accessibles, c'est-à-dire les états à partir desquels il existe un chemin vers l'état final. [] 21 - Soient À un automate et w EUR C* un mot. Écrire une fonction OCaml accessible (a:automate) (w:couleur array) : bool array dont la valeur de retour b est un tableau de booléens tels que b{q| est vrai si et seulement si l'état q de À © w est accessible. [] 22 -- Calculer la complexité en temps de la fonction accessible définie à la question 21. [] 23 -- Soient À un automate à r états et w EUR C* un mot de longueur n. Écrire une fonction coaccessible (a:automate) (w:couleur array) : bool array dont la valeur de retour b est un tableau de booléens tels que blq] est vrai si et seulement si l'état q de À © w est co-accessible. Définition : Soient À un automate à r états et w EUR ©" un mot de longueur n. Nous supposons qu'il existe un mot de longueur n reconnu par l'automate À © w. Nous rappelons que l'automate émondé de À © w est la copie de l'automate duquel ont été retirées toutes les transitions depuis ou vers des états qui ne sont pas à la fois accessibles et co-accessibles (nous ne chassons pas les états inutiles et conservons la numérotation des états). Nous notons À l'ensemble des transitions restantes dans l'automate émondé. Nous notons, pour tout indice ? compris entre 0 et n -- 1, l'ensemble des étiquettes H, -- {ce C: (g,c,g)e ANnli-r,(i+1):r---1]xe x [G+1)-r, (+2) --1]}. Nous posons, pour tout entier ? compris entre O0 et n--l. | si A = {B.N}. Nous appelons mot projeté du déploiement À ba w le mot y = YoY1...Yn-1 EUR C". [] 24 -- Avec les notations du paragraphe qui précède et lorsque l'automate À est l'automate dessiné à la question 18, vérifier que le mot projeté y EUR ©" est la plus grande extension commune du mot w EUR ©" par rapport à l'indication 7 (cf. définition p. 7). Page 8 sur 11 Épreuve d'informatique d'option MP 2023 [] 25 -- Écrire une fonction projete (a:automate) (w:couleur array) : couleur array dont la valeur de retour est le mot projeté du déploiement À © w. Nous rappelons la formule de Stirling : nl Van (©). EUR CT 26 -- Comparer la complexité en temps de la fonction projete (question 25) avec un calcul direct de la plus grande extension commune par énumération de l'ensemble [w|,. Argumenter en s'appuyant sur la question 16. Nous nous donnons une fonction OCaml pgec lig (h:hanjie) (p:presolution) (x:int) presolution option, et respectivement pgec col (h:hanjie) (p:presolution) (y:int) presolution option, qui étend la ligne x, respectivement la colonne y, par la plus grande extension commune à l'image de la question 25 ou bien renvoie None si la plus grande extension commune n'est pas définie. [1 27 - Écrire un extenseur etend nontrivial (h:'hanjie) (p:presolution) (z:int) (c:couleur) : presolution option qui modifie la couleur de p au numéro z et applique les fonctions pgec_lig et pgec_col aussi longtemps que cela permet de faire progresser la présolution. Il est demandé de détailler la stratégie de l'extenseur avant d'en fournir le code. Page 9 sur 11 Épreuve d'informatique d'option MP 2023 A. Annexe : aide à la programmation en OCaml Opérations sur les tableaux : Le module Array offre les fonctions suivantes : length : ?'a array -> int

Return the length (number of elements) of the given array.

make : int -> 'a -> ?'a array

Array.make n x returns a fresh array of length n, initialized with x. AI the 
elements of this new array
are initially physically equal to x (in the sense of the == predicate). 
Consequently, if x is mutable, it is
shared among all elements of the array, and modifying x through one of the 
array entries will modify
all other entries at the same time.

make matrix : int -> int -> 'a -> ?'a array array

Array.make matrix dimx dimy e returns à two-dimensional array (an array of 
arrays) with first
dimension dimx and second dimension dimy. AI the elements of this new matrix 
are initially physically
equal to e. The element (x,y) of a matrix m is accessed with the notation m. 
(x) .(y).

init : int -> (int -> ?'a) -> ?'a array

Array.init n f returns a fresh array of length n, with element number à 
initialized to the result
Of f(i). In other terms, init n f tabulates the results of f applied to the 
integers 0 to n -- 1.

Copy : 'a array -> 'a array

Array.copy a returns à copy of à, that is, a fresh array containing the same 
elements as a.

mem : a -> 'a array -> bool

mem a Lis true if and only if a is structurally equal to an element of { (i.e. 
there is an x in { such that
compare à x = 0).

for_all : ('a -> bool) -> ?'a array -> bool

Array.for all f [lai; ...; an] checks if all elements of the array satisfy the 
predicate f. That
is, it returns (f ai) && (Cf a2) && ... && (f an).

exists : ('a -> bool) -> ?'a array -> bool

Array.exists f [lal; ...; an] checks if at least one element of the array 
satisfies the predicate f.
That is, it returns (£ a1) || (Cf a2) || ... || (C£f an).

map : ('a -> 'b) -> ?'a array -> 'b array

Array.map f a applies function f to all the elements of a, and builds an array 
with the results returned
by f:[1 f a.(0); f a.(1); ...; f a.(length a - 1) |].

iter : ('a -> unit) -> ?'a arraÿ -> unit

Array.iter f a applies function f in turn to all the elements of a. It is 
equivalent to f a.(0); f
a.(1); ...; f a.(length a - 1); ().

D'après https://v2.ocaml.org/api/Array.html

Opérations sur les tables de hachage : Le module Hashtb1 offre les fonctions 
suivantes :

('a, 'b) Hashtbl.t

The type of hash tables from type 'a to type 'b.

create : int -> ('a, 'b) t

Hashtbl.create n creates a new, empty hash table, with initial size n. For best 
results, n should be
on the order of the expected number of elements that will be in the table. The 
table grows as needed,
so n is just an initial guess.

add : ('a, 'b) t -> 'a -> 'b -> unit

Hashtbl.add tbl key data adds a binding of key to data in table tbl.

remove : ('a, 'b) t -> 'a -> unit

Hashtbl.remove tbl x removes the current binding of x in tbl, restoring the 
previous binding if it
exists. It does nothing if x is not bound in tbl.

mem : ('a, 'b) t -> 'a -> bool

Hashtbl.mem tb1l x checks if x is bound in tbl.

iter : ('a -> 'b -> unit) -> ('a, 'b) t -> unit

Hashtbl.iter f tbl applies f to all bindings in table tbl. f receives the key 
as first argument, and
the associated value as second argument. Each binding is presented exactly once 
to f.

find opt : ('a, 'b) t -> ?'a -> ?'b option

Hashtbl.find opt tbl x returns the current binding of x in {bl, or None if no 
such binding exists.

D'après https://v2.ocaml.org/api/Hashtbl.html

Page 10 sur 11
Épreuve d'informatique d'option MP 2023

B. Annexe : règles de la déduction naturelle

Dans les tableaux suivants, la lettre À désigne un ensemble de formules de 
logique; les

lettres À, B et C désignent des formules de logique.

Axiome
A)
A AFA
Introduction Élimination
AA+B ... AA AFASB,,
| AFASB AFB 9
AFAAB
x AFA A+B,, AA
AFAAB AFAAB à,
AFB
AFA 4
AFAVBE AFAVB AAC  ABEC
Y AFGQ vo
NE
AFAVB
| AAËB  AAE-B AFA  A+-A,,
A =A _ AFB

Lt,
[1,1,
[1,1,
[1,1,

Lt,

2

2

2

2

CO EH FH EH Ha
ms

2

FIN DE L'ÉPREUVE

Page 11 sur 11