Préliminaires
L’épreuve est formée d’un problème unique, constitué de 25 questions, qui porte sur l’algorithmique de quelques résultats mathématiques reliés à la notion de relation d’ordre.
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 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 des extraits du manuel de documentation de OCaml sont reproduits en annexe. Ces derniers portent sur le module Array.
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.
Quand l’énoncé demande de coder une fonction, sauf demande explicite, 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é et de la concision des programmes : il est attendu que l’on choisisse des noms de variables intelligibles ou encore que l’on structure de longs codes par des blocs ou par des fonctions auxiliaires dont on décrit le rôle.
1.
Relation d’ordre et tri topologique
Nous fixons un ensemble fini V et appelons n son cardinal. Nous notons systématiquement {v_0,v_1,\ldots,v_{n-1}} les éléments distincts de {V}.
Définition : Nous appelons relation d’ordre sur V toute relation binaire E qui est 1. réflexive, c’est-à-dire telle que, pour tout indice i compris entre 0 et {n-1}, nous avons la relation {v_i\mathrel{\mathcal E}v_i} , 2. antisymétrique, c’est-à-dire telle que, pour tous indices i et j compris entre 0 et {n-1}, si les relations {v_i\mathrel{\mathcal E}v_j} et {v_j\mathrel{\mathcal E}v_i} sont vérifiées, alors nous avons l’égalité {v_i=v_j} 3. transitive, c’est-à-dire que, pour tous indices i, j et k compris entre 0 et {n-1}, si les relations {v_i\mathrel{\mathcal E}v_j} et {v_j\mathrel{\mathcal E}v_k} sont vérifiées, alors nous avons encore la relation {v_i\mathrel{\mathcal E}v_k} .
Un ensemble fini muni d’une relation d’ordre s’appelle un ensemble ordonné et se note {(V,\mathcal E)}. Nous réservons le symbole {\le} pour désigner l’ordre usuel sur les entiers.
Indication OCaml : Nous représentons tout ordre sur un ensemble de cardinal n par une matrice carrée r de dimension {n\times n}, de type
|
1 |
type order = bool array array |
où le coefficient r.(i).(j) vaut true si et seulement si la relation {v_i\mathrel{\mathcal E}v_j} est vérifiée.
Dans le reste du sujet, le choix du paradigme de programmation est libre.
Définition : Nous appelons graphe d’un ensemble ordonné {(V,\mathcal E)}, ou simplement graphe de la relation d’ordre E, le graphe orienté G = {(V,\mathcal E)} dont l’ensemble des arcs est {E=\{(v_i,v_j):(i,j)\in\{0,\ldots,n-1\}^2\text{ et }v_i\mathrel{\mathcal E}v_j\}.} Nous rappelons que le degré sortant d’un sommet v désigne le nombre d’arcs dont l’extrémité initiale vaut v.
Autrement dit, pour tout indice i compris entre 0 et {n-1}, l’entier d[i] est le degré sortant du sommet {v_i}.
Définition : Étant donné un ensemble ordonné {(V,\mathcal E)} de cardinal {n}, nous appelons tri topologique de {V} toute permutation {\tau} des entiers de l’intervalle {\{0,\ldots,n-1\}} telle que, pour tous indices {i} et {j} compris entre {0} et {n-1}, si l’on a la relation {v_i\mathrel{\mathcal E}v_j}, alors on a l’inégalité {\tau(i)\le\tau(j)}.
Pour tous indices {i} compris entre {0} et {n-1}, nous disons dans ce cas que le sommet {v_i} est le sommet de numéro {\tau(i)}.
Il est attendu que la fonction attribue les numéros par ordre décroissant et que, en cours d’exécution, elle s’appuie sur la question 8 pour identifier le prochain sommet à numéroter.
Il pourra s’agir d’invariants de boucle dans le cas d’un programme itératif ou de postconditions dans le cas d’un programme récursif.
Dire comment on qualifie une telle complexité en fonction de l’espace en mémoire utilisé pour représenter l’argument d’entrée r.
2. Chaînes et antichaînes
Définition : Étant donné un ensemble ordonné {(V,\mathcal E)}, nous appelons chaîne toute partie C de {V} totalement ordonnée, c’est-à-dire, telle que pour tous éléments {c} et {c^{\prime}\in C}, nous avons la relation {c\mathrel{\mathcal E}c^{\prime}} ou la relation {c^{\prime}\mathrel{\mathcal E}c}. Indication OCaml : Nous représentons une chaîne par le type int list.
Nous donnons le code suivant
|
1 2 3 4 5 |
let rec is_chain (r:order) (c:int list) : bool = match c with | [] -> true | v::cc -> List.for_all (fun x -> x > v || x < v) cc && is_chain r cc |
où nous avons recouru à la fonction for_all du module List ainsi décrite dans la documentation de OCaml : val for_all : (’a -> bool) -> ’a list -> bool for_all f [a1; …; an] checks if all elements of the list satisfy the predicate f.
That is, it returns (f a1) && (f a2) && … && (f an) for a non-empty list and true if the list is empty.
Dans le premier cas, on fournira une démonstration ; dans le second cas, on modifiera la fonction is_chain afin qu’elle soit correcte.
Nous nous proposons d’écrire une fonction is_chain_bis r c obéissant à la spécification de la question 12 et de complexité en temps {O(\gamma\log\gamma)} où {\gamma} est la longueur de la liste c.
À cette fin, nous nous préparons à introduire une structure de donnée mutable à capacité bornée permettant de stocker une collection d’éléments de {(V,\mathcal E)} à travers l’interface suivante :
|
1 2 3 4 5 |
type hp val init : order -> int -> hp val is_empty : hp -> bool val push : hp -> int -> bool val pop : hp -> bool |
L’appel init r gamma doit permet d’initialiser une collection vide, informée de la relation d’ordre r, et de capacité {\gamma}.
L’appel is_empty q doit indiquer si la collection q est vide. L’appel push q i doit insérer l’élément {v_i\in V} à la collection q ; l’appel pop q doit retirer un élément de la collection q.
Nous envisageons que les appels à push et de pop puissent échouer, ce qui est signalé par la valeur de retour de ces fonctions.
Nous écrivons la fonction is_chain_bis r c sous la forme suivante :
|
1 2 3 4 5 6 7 8 9 10 11 12 |
let is_chain_bis (r:order) (c:int list) : bool = let q = init r (List.length c) in let rec insert c : bool = match c with | [] -> true | hd::tl -> (push q hd) && insert tl in let rec extract_all () : bool = if is_empty q then true else (pop q) && (extract_all ()) in (insert c) && (extract_all ()) |
Cette fonction insère les éléments de la liste c à une collection initialement vide q, de type hp, puis les retire de cette collection q.
Justifier la réponse.
Définition : Étant donné un ensemble ordonné {(V,\mathcal E)}, nous appelons antichaîne toute collection de sommets {A\subseteq V} dont les éléments sont deux à deux incomparables, c’est-à-dire, telle que pour tous éléments distincts {a} et {a^{\prime}\in A}, aucune des relations {a\mathrel{\mathcal E}a^{\prime}} ou {a^{\prime}\mathrel{\mathcal E}a} n’est vérifiée.
Indication OCaml : Nous représentons une antichaîne par le type int list.
En déduire que la fonction is_antichain admet pour complexité en temps la même complexité que celle obtenue à la question 13.
3. Couverture par des chaînes
Définition : Nous disons qu’une famille finie {(C_\ell)_{1\le\ell\le\lambda}} de chaînes de l’ensemble ordonné {(V,\mathcal E)} est une couverture si la réunion {\bigcup_{1\le\ell\le\lambda}C_\ell} est égale à l’ensemble {V}.
Démontrer l’inégalité {\alpha\le\lambda.}
Définition : Étant donné un ensemble ordonné {(V,\mathcal E)}, nous appelons graphe des poursuites d’un ensemble ordonné {(V,\mathcal E)} le graphe biparti non orienté {P=(W_0\uplus W_1,F)} où les ensembles de sommets {W_0} et {W_1} sont deux copies distinctes de {V}, dont on note les éléments {\begin{array}{l}W_0=\{w_i:i\in\{0,\ldots,n-1\}\},\\[8pt]W_1=\{w_{n+i}:i\in\{0,\ldots,n-1\}\},\end{array}}et dont l’ensemble des arêtes est {\begin{array}{rl}F=\{(w_i,w_{n+j}):&(i,j)\in\{0,\ldots,n-1\}^2,\\[4pt]&i\ne j,\ v_i\mathrel{\mathcal E}v_j\}\end{array}} Indication OCaml : Nous représentons un graphe biparti à 2n sommets par un tableau de longueur 2n contenant des listes de voisins
|
1 |
type bipartite = int list array |
Chaque arrête est notée deux fois en mémoire.
Définition : Nous appelons couplage tout ensemble d’arêtes dont les extrémités sont distinctes.
1. pour tous indices {i} et {j} compris entre {0} et {n-1}, si le couple {(w_i,w_{n+j})\in W_0\times W_1} est une arête de {M}, alors les deux éléments {v_i} et {v_j} appartiennent à une même part {C_\ell},
2. le cardinal {\lambda} est aussi grand que possible.
Montrer que pour tout indice {\ell} compris entre {1} et {\lambda}, l’ensemble {C_\ell} est une chaîne de {(V,\mathcal E)}.
Indication OCaml : Nous représentons un couplage dans le graphe des poursuites {P=(W_0\uplus W_1,F)} par un tableau m de longueur {n}, de type int array, tel que m[j] = i si le couple {(w_i,w_{n+j})\in W_0\times W_1} est une arête du couplage et m[j] = -1 si le sommet {w_{n+j}\in W_1} n’est pas l’extrémité d’une arrête du couplage.
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.
All 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 a two-dimensional array (an array of arrays) with first dimension dimx and second dimension dimy.
All 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 i 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 a copy of a, that is, a fresh array containing the same elements as a. — mem : ’a -> ’a array -> bool mem a l is true if and only if a is structurally equal to an element of l (i.e. there is an x in l such that compare a x = 0). — for_all : (’a -> bool) -> ’a array -> bool Array.for_all f [|a1; …; an|] checks if all elements of the array satisfy the predicate f .
That is, it returns (f a1) && (f a2) && … && (f an). — exists : (’a -> bool) -> ’a array -> bool Array.exists f [|a1; …; an|] checks if at least one element of the array satisfies the predicate f .
That is, it returns (f a1) || (f a2) || … || (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 : [| f a.(0); f a.(1); …; f a.(length a – 1) |]. — mapi : (int -> ’a -> ’b) -> ’a array -> ’b array Same as Array.map, but the function is applied to the index of the element as first argument, and the element itself as second argument. — iter : (’a -> unit) -> ’a array -> 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); (). — iteri : (int -> ’a -> unit) -> ’a array -> unit Same as Array.iter, but the function is applied to the index of the element as first argument, and the element itself as second argument. D’après https://v2.ocaml.org/api/Array.html