2023-Inp-OptionInfo-Mp-Corrigé

Partie I – Programmation en OCaml :

sélection du (k + 1)e plus petit élément La sélection du (k + 1)e plus petit élément d’une liste d’entiers L, non nécessairement triée, consiste à trouver le (k + 1)e élément de la liste obtenue en triant L dans l’ordre croissant.

Par exemple, si L = [9; 1; 2; 4; 7; 8] le 3e plus petit élément de L est 4. On pourra remarquer que si la liste L est triée dans l’ordre croissant, le (k + 1) e plus petit élément est l’élément de rang k dans L.

On présente un algorithme permettant de résoudre ce problème de sélection avec une complexité temporelle linéaire dans le pire cas. Celui-ci est basé sur le principe de ”diviser pour régner” et sur le choix d’un bon pivot pour partager la liste en deux sous-listes.

Dans cette partie, les fonctions demandées sont à écrire en OCaml et ne doivent faire intervenir aucun trait impératif du langage (références, tableaux ou autres champs mutables ou exception par exemple). Étant donné un réel a, on note {\lfloor a\rfloor} le plus grand entier inférieur ou égal à a.

I.1 – Fonctions utiles

Dans cette section, on écrit des fonctions auxiliaires qui sont utiles pour la fonction principale.

I.2 – La fonction de sélection et sa complexité

On détaille la fonction de sélection :

On cherche à déterminer la complexité en nombre de comparaisons de la fonction selection. Pour tout {n\in\mathbb N}, on note T (n) le nombre maximum de comparaisons entre éléments lors d’une sélection d’un élément quelconque dans des listes L sans répétition de taille n.

En analysant l’Algorithme 1, il est possible de démontrer que, pour tout {n\ge55} : {T(n)\le T\left(\left\lfloor\frac{n+4}5\right\rfloor\right)+T\left(\left\lfloor\frac{8n}{11}\right\rfloor\right)+4n\;(I)}

Algorithme 1 – Sélection du (k + 1)^e plus petit élément

Partie II – Recherche d’une clique de célébrités

II.1 – Définitions et propriétés

Définition 1 (Graphe). On appelle graphe un couple {G=(S,A)} où S est un ensemble fini appelé ensemble des sommets et A est une partie de {S\times S} , appelée ensemble des arêtes. On pourra remarquer que, dans cette définition de graphe, les éléments de la forme (s, s) où {s\in S} sont des arêtes possibles.

Définition 2 (Clique). Soit {G=(S,A)} un graphe. Soit {S'} une partie de S . On dit que {S'} est une clique si : {\forall(s_1,s_2)\in S^\prime\times S^\prime,\ (s_1,s_2)\in A.} Définition 3 (Clique de célébrités, célébrité). Soient {G=(S,A)} un graphe et C une partie de S .

On dit que C est une clique de célébrités si C est une clique et : {\begin{array}{l}\forall(c,s)\in C\times S,\\[4pt]((s,c)\in A)\land((c,s)\in A\Longrightarrow s\in C)\end{array}} Un élément de l’ensemble C est alors appelé célébrité.

Le terme ”célébrité” provient de l’interprétation suivante : l’ensemble des sommets correspond à un ensemble de personnes et une arête (s, c) représente le fait que s connaît c. Ainsi, une célébrité est connue de tous et elle connaît uniquement les autres célébrités.

Dans la suite, on note {C_G} l’unique clique de célébrités non vide du graphe G. Dans le cas où celle-ci n’existe pas,{C_G} désigne alors l’ensemble vide qui est noté {\varnothing}.

II.2 – Algorithmique et programmation en Python (Informatique Commune)

Dans la suite, l’ensemble des sommets est de la forme {0, 1,…, n − 1} où n est un entier supérieur à 1 et un graphe {G=(S,A)} est représenté en Python par sa liste d’adjacence que l’on note LG et qui est définie par : [[j | j ∈ S et (i, j) ∈ A ] i ∈ S ].

Par exemple, si G = ({0, 1, 2, 3} , {(0, 1) , (3, 2) , (3, 1) , (1, 2)}), alors LG = [[1], [2], [], [1, 2]]. On pourra remarquer que si l’ensemble des sommets d’un graphe G est égal à {0, 1,…, n − 1}, alors la longueur de la liste LG est égale à n.

Algorithme 2 – Construction d’une clique de célébrités possibles

Partie III – Étude d’une famille d’automates

Dans cette partie, l’alphabet {\Sigma} désigne l’ensemble{0, 1}, le symbole {\varepsilon} désigne le mot vide et on rappelle que {\Sigma^\star} désigne l’ensemble des mots sur l’alphabet {\Sigma}. Étant donné un mot w, on rappelle que {|w|} désigne la longueur du mot w et l’indexation des lettres de w commence par 0.

La première lettre de w est donc {w_0}. La notation Card (E) désigne le cardinal d’un ensemble E. Étant donnés un entier n et un entier non nul m, la notation n mod m désigne le reste de la division euclidienne de n par m.

III.1 – Définitions

Définition 4 (Automate déterministe ). Un Automate déterministe est un quintuplet {A=(Q,\Sigma,\delta,q_0,F)} avec :

– Q un ensemble fini non vide appelé ensemble des états,

– {\Sigma} est un ensemble fini appelé alphabet,

– {\delta:Q\times\Sigma\to Q} une application appelée application de transition,

– {q_0} un élément de Q appelé état initial,

– F une partie de Q appelée ensemble des états finaux. Définition 5 (Application de transition étendue aux mots). Soit {A=(Q,\Sigma,\delta,q_0,F)} un automate déterministe. On définit de manière récursive {\delta^\star:Q\times\Sigma^\star\to Q} par : {\forall q\in Q,\ \delta^\star(q,\varepsilon)=q,} {\begin{array}{l}\forall q\in Q,\ \forall a\in\Sigma,\ \forall w\in\Sigma^\star,\\[8pt]\delta^\star(q,aw)=\delta^\star(\delta(q,a),w).\end{array}} Définition 6 (Reconnaissance d’un mot par un automate).

Soient w = {w_0w_1\cdots w_n} un mot sur un alphabet {\Sigma} et {A=(Q,\Sigma,\delta,q_0,F)}. On dit que w est reconnu par l’automate A si {\delta^\star(q_0,w)\in F}. Définition 7 (Automate {A_{k,p}}, fonction indicatrice {L_{k,p}}). Soient p et k deux entiers vérifiant {0\le k\le p-1}. L’automate {A_{k,p}} est défini par :

– {Q=\{0,1,\ldots,p-1\}\times\{0,1\}},

– {\Sigma}= {0, 1},

– {\forall(c,e)\in Q,\ \delta((c,e),0)=((c+1)\bmod p,e)},

– {\forall(c,e,)\in Q},

{\begin{array}{rl}\delta((c,e),1)\\[8pt]\quad\displaystyle=\left\{\begin{array}{ll}((c+1)\bmod p,1-e)&\text{si }c=k\bmod p,\\[8pt]((c+1)\bmod p,e)&\text{sinon}.\end{array}\right.\end{array}}– {q_0=(0,0)} ,

– {F=\{0,1,\ldots,p-1\}\times\{1\}}.

On note {L_{k,p}} la fonction indicatrice de l’ensemble des mots reconnus par {A_{k,p}}. Soit autrement : {\forall u\in\Sigma^\star,\ L_{k,p}(u)=\left\{\begin{array}{ll}1&\text{si }A_{k,p}\text{ reconnaît }u,\\[8pt]0&\text{sinon}.\end{array}\right.}

III.2 – Exemples et propriétés élémentaires des {A_{k,p}}

Dans les questions Q18 à Q22, p et k désignent des entiers tels que {p>2} et {k\in\{0,1,\ldots,p-1\}}.

Un corollaire direct du résultat de la question Q18 est que l’ensemble des mots reconnu par l’automate {A_{k,p}} est égal à : {\!\!\!\!\begin{array}{l}\left\{w\in\Sigma^\star\ \middle|\ \operatorname{Card}\left(\left\{m\ge0\middle|\begin{array}{l}pm\!+\!k\le|w|\!-\!1\\[4pt]\text{et }w_{pm+k}=1\end{array}\!\!\!\!\!\!\right\}\!\right)\!\right\}\\[16pt]\qquad\qquad\text{ est impair}\end{array}} Dans la suite du problème, on admet ce résultat.

Définition 8 (Ou exclusif étendu aux mots binaires) . On rappelle que le Ou exclusif qu’on note {\oplus} est une opération définie sur {0, 1} par : {0\oplus0=1\oplus1=0} et {0\oplus1=1\oplus0=1}. Soient {n\in\mathbb N}, u et v deux éléments de {\{0,1\}^n}. On définit le Ou exclusif de u et v, noté {u\oplus v}, le mot de longueur n défini par : {\forall i\in\{0,1,\ldots,n-1\},\ (u\oplus v)_i=u_i\oplus v_i}.

Remarque. Ces égalités permettent la construction d’une relation d’équivalence sur les mots qui est utilisée pour montrer que deux mots de longueur N peuvent être séparés par un automate de la forme {A_{k,p}} ayant {O(\sqrt N\ln(N))} états.