Centrale Option Informatique MP 2026Sujet

Option Informatique

Coloriages

Généralités

Partie A - Exercice : Coloration syntaxique

type token = | Let | In | Var of string | Int of int | Lpar | Rpar | Add | Equal

• Q1.On travaille sur l'alphabet Σ = {0, 1}. Proposer une expression régulière dénotant les écritures en binaire des entiers ( 0 ou toute suite de 0 et de 1 commençant par 1).
• Q2.Proposer alors un automate fini déterministe qui reconnaît ce langage. Comment pourrait-on le modifier pour qu'il reconnaisse les écritures en base 10 des entiers?

Figure 1 - Automate fini non déterministe A_l

• Q3.Indiquer le langage reconnu par l'automate de la figure 1. Proposer un automate fini déterministe qui reconnaît le même langage.
• Q4.Justifier que l'on peut construire un automate fini déterministe permettant de reconnaître l'ensemble des lexèmes proposés dans le type token.

• -Si le premier caractère est ^′ ', ^′∖n^′ ou ^′∖t^′, on l'ignore et on recommence à partir du caractère suivant.
• -Sinon, on lit la liste de caractères à travers l'automate en partant de son unique état initial pour identifier un lexème : un lexème est reconnu dès que l'automate échoue lors de la lecture d'un caractère à partir d'un état acceptant ou si l'on finit sur un état acceptant (on repère ainsi le plus long lexème possible). Une fois un lexème identifié, on construit un objet de type token associé et on le stocke.
• -On recommence à partir de l'éventuel caractère qui a provoqué l'échec.

['l'; 'e'; 't'; ' '; 'v'; 'a'; 'l'; 'e'; 'u'; 'r'; ' '; '='; ' '; '4'; '2']

• -on reconnaît d'abord le token Let en échouant sur l'espace;
• -on recommence avec la chaîne qui reste ;
• -on oublie le caractère espace, on recommence avec la chaîne qui reste;
• -on reconnaît le token Var "valeur" en échouant sur l'espace;
• -et ainsi de suite.

[Let; Var "valeur"; Equal; Int 42]

Partie B - Problème : Coloration de graphes

Définitions et notations

Figure 2 - Le graphe G_1

type graphe = {nbr : int ; adj : int list array}

let g1 = {nbr = 6 ; adj = [|[3; 2; 4];
    [2; 3];
    [3; 0; 1; 5];
    [0; 4; 2; 1];
    [0; 3];
    [2]|]};;

Problème : k-COLORATION

type col = int array

I - Cas de la 2-COLORATION

Figure 3 - Le graphe G_2 et une bicoloration valide associée

I. 1 - graphes bipartis

I. 2 - Une solution naïve

I. 3 - un détour par les structures de données

type 'a pile = 'a list

type 'a file = { entree : 'a pile ; sortie : 'a pile }

Si la pile "sortie" est vide ALORS
    TANT QUE la pile "entree" est non vide
        dépiler l'élément en tête de pile "entree" et l'empiler sur la pile "sortie".
Dépiler et renvoyer l'élément en tête de pile "sortie"

• Q17.Proposer les fonctions :
  • a.initFile : unit -> 'a file qui renvoie une file vide,
  • b.estVideFile : 'a file -> bool qui dit si la file reçue est vide,
  • c.enfile : 'a * 'a file -> 'a file qui ajoute un élément dans la file et renvoie la nouvelle file,
  • d.defile : 'a file -> 'a * 'a file qui sort un élément de la file et le renvoie avec la nouvelle file.
• Q18.Montrer que l'ordre de sortie des éléments dans une structure de ce type est le même que celui d'entrée.
• Q19.Quelle est la complexité temporelle dans le pire cas d'une opération defile?
• Q20.On considère un élément qui transite par une telle structure de file (c'est-à-dire y rentre puis éventuellement en sort). Encadrer le nombre d'opérations empile et dépile réalisées sur cet élément.
• Q21.En déduire un encadrement du nombre d'opérations empile et dépile réalisées lors de n opérations enfile ou defile réalisées sur une file initialement vide. Que peut-on dire sur la complexité temporelle amortie des fonctions enfile et defile?

I. 4 - Une solution plus efficace

• Q22.Proposer une fonction bicol : graphe -> bool * col qui détermine, par un parcours en largeur du graphe, s'il existe une bicoloration valide et le cas échéant en renvoie une. On supposera sans le vérifier que le graphe passé en argument est connexe.
• Q23.Justifier la terminaison de la fonction bicol.
• Q24.Indiquer, en justifiant, quelle est la complexité temporelle de la fonction bicol.
• Q25.Justifier la correction de cette fonction.
• Q26.Proposer une stratégie afin d'adapter la fonction bicol au cas où le graphe n'est pas connexe.
• Q27.Comment pourrait-on implémenter la fonction bicol de la Q22 en utilisant un parcours en profondeur ?

II - Cas de la 3-COLORATION

• Q28.Proposer une fonction de validation partielle partial : graphe -> col -> int -> bool qui décide si la coloration passée en argument est localement valide entre le sommet (de type int) passé en argument (et supposé vraiment coloré) et ses sommets adjacents.
• Q29.Proposer une fonction backtracking : graphe -> bool * col qui détermine s'il existe une 3-coloration valide et le cas échéant en renvoie une pour le graphe (supposé connexe) passé en argument.
• Q30.Indiquer, en justifiant, la complexité temporelle d'une telle stratégie dans le pire cas.

III - Graphes planaires

III. 1 - Formule d'Euler pour un graphe connexe

• -la frontière de sa face 2 se parcourt par le chemin d − e − f − d donc cette face a un degré de 3,
• -la frontière de sa face 3 (la face non bornée) contient les arêtes ab, ac, bc, cd, de, ef, fd et se parcourt par a − b − c − d − e − f − d − c − a donc la face 3 a un degré de 8.

Figure 4 - Graphe planaire et faces

III. 2 - Cas du problème Planar-2-COL

III. 3 - Cas du problème Planar-3-COL

Figure 5 - De gauche à droite, les graphes G_3, G_4 et G_5

III. 4 - Cas k ⩾ 4

• -du sommet s_1,
• -des voisins de s_1 colorés avec la couleur c,
• -des voisins des voisins de s_1 colorés avec la couleur a,
• -des voisins des voisins des voisins de S_1 colorés avec la couleur c,
• -et ainsi de suite.

ANNEXES

val length : 'a list -> int
List.length l returns the length (number of elements) of the given list l.
val hd : 'a list -> 'a
List.hd l returns the first element of the given list l.
Raises Failure if the list is empty.
val tl : 'a list -> 'a list
List.tl l returns the given list l without its first element.
Raises Failure if the list is empty.
val rev : 'a list -> 'a list
List reversal.
val iter : ('a -> unit) -> 'a list -> unit
List.iter f [a1; ...; an] applies function f in turn to [a1; ...; an].
It is equivalent to f a1; f a2; ...; f an.
val iteri : (int -> 'a -> unit) -> 'a list -> unit
Same as List.iter, but the function is applied to the index of the element
as first argument (counting from 0), and the element itself as second argument.
val map : ('a -> 'b) -> 'a list -> 'b list
List.map f [a1; ...; an] applies function f to a1, ..., an,
and builds the list [f a1; ...; f an] with the results returned by f.
val mapi : (int -> 'a -> 'b) -> 'a list -> 'b list
Same as List.map, but the function is applied to the index of the element
as first argument (counting from 0), and the element itself as second argument.
val fold_left : ('acc -> 'a -> 'acc) -> 'acc -> 'a list -> 'acc
List.fold_left f init [b1; ...; bn] is f (... (f (f init b1) b2) ...) bn.
val mem : 'a -> 'a list -> bool
List.mem a set is true if and only if a is equal to an element of set.
val filter : ('a -> bool) -> 'a list -> 'a list
List.filter f l returns all the elements of the list l that satisfy the predicate f.
The order of the elements in the input list is preserved.

val length : ’a array -> int
Array.length a returns the length (number of elements) of the given array a.
val get : ’a array -> int -> ’a
Array.get a n returns the element number n of array a. The first element has number 0.