Graphes d'intervalles : représentation, coloration et ordre d'élimination parfait
Afficher ou masquer la section
Le sujet traite des graphes d'intervalles : leur représentation, leur coloration et l'ordre d'élimination associé. Il propose une démarche progressive en Caml, en programmant successivement les fonctions nécessaires à la construction, à la coloration gloutonne, puis à l'exploitation de l'ordre d'élimination parfait, avant d'étudier une condition suffisante pour qu'un graphe cordal admette un tel ordre.
1I. Graphes d'intervallesReprésentation du problème, graphe simple non orienté, graphe d'intervalles, coloration et cliques.
2II. Algorithme glouton pour la colorationÉtude sur un exemple, implantation, preuve et complexité d'un algorithme glouton de coloration.
3III. Graphes munis d'un ordre d'élimination parfaitUn exemple, vérification, ordre d'élimination parfait pour un graphe d'intervalles et coloration associée.
4IV. Ordre d'élimination parfait pour un graphe cordalCycles de longueur 4, cordalité des graphes d'intervalles, existence d'un ordre d'élimination parfait et coupures minimales dans un graphe cordal.
Difficulté moyenne. Le rapport indique que le sujet a été globalement compris, avec une fraction faible de très mauvaises copies, même si les candidats n'ont pas toujours eu le temps de traiter l'ensemble du problème.
Ce qu'a observé le jury
6 erreurs relevées
Calculs de complexité mal justifiés · Fonctions précédentes non réutilisées · Gestion des références absente
Afficher ou masquer la section
Le jury constate que le sujet a été globalement compris et que le niveau global des candidats est satisfaisant, certaines copies étant excellentes. Les principales difficultés portent sur la justification des calculs de complexité, la gestion des références et le respect des structures de données indiquées par l'énoncé.
Les erreurs les plus sanctionnées
1
Calculs de complexité mal justifiésII.D
Même quand le résultat est correct, les calculs de complexité sont rarement justifiés avec précision, notamment lorsque des ajouts en fin de liste ne sont pas pris en compte.
2
Fonctions précédentes non réutilisées
Certains candidats n'utilisent pas les fonctions préalablement écrites ou changent les structures de données indiquées, ce qui conduit toujours à de mauvaises solutions.
3
Gestion des références absente
L'absence de gestion des références dans les cas où elles sont indispensables reste une difficulté courante.
4
Comparaison nombre de couleurs et taille de la plus grande clique impréciseI.E
La fin de la partie I, qui compare le nombre de couleurs nécessaires et la taille de la plus grande clique, a été très souvent imprécise ou fausse.
5
Preuves insuffisamment justifiéesIII
Même quand un résultat semble évident, il convient de le justifier en quelques mots ; ce minimum de justification a souvent manqué en partie III.
6
Utilisation de Python au lieu de Caml Light
Le jury rappelle que l'unique langage retenu pour l'option informatique est Caml Light, alors qu'il a souvent observé des programmations en Python.
Ce qui a été bien réussi
Les meilleurs candidats ont traité correctement le problème, avec une bonne rédaction.
La signature des fonctions Caml était le plus souvent imposée et les candidats l'ont respectée dans l'ensemble.
La deuxième partie, sur l'algorithme glouton, est sans difficulté spécifique pour la majorité des candidats.
Les dernières questions sur les sommets simpliciaux dans un graphe cordal ont été moins souvent traitées, mais globalement correctement.
Conseils du jury
Bien lire exactement les indications du texte sur les différentes structures de données utilisées.
Utiliser les fonctions précédemment programmées plutôt que d'en réécrire de nouvelles, moins lisibles.
Justifier systématiquement les calculs de complexité, y compris les coûts supplémentaires liés aux ajouts dans les listes.
Parcourir les listes avec des fonctions récursives et un filtrage clair plutôt que de multiplier les hd et tl.
Écrire des codes clairs et commentés sans paraphraser le code, en expliquant les choix non optimaux le cas échéant.
Synthèse rédigée par WikiPrépa à partir du rapport officiel du jury (à télécharger en PDF). Les citations sont extraites du rapport.
Les candidats devront répondre aux questions de programmation en utilisant le langage Caml. Ils devront donner le type, ou la signature, de chaque fonction écrite, sauf lorsqu'il est indiqué par le sujet : dans ce cas la réponse doit être d'un type compatible avec la signature proposée. Par exemple, la fonction cons définie par
let cons xl = x : l
est du type 'a -> 'a list -> 'a list qui est compatible avec la signature int -> int list -> int list. L'énoncé indique la signature attendue, toute réponse de type compatible est acceptée.
I Graphes d'intervalles
On considère le problème concret suivant : des cours doivent avoir lieu dans un intervalle de temps précis (de 8 h à 9 h55, … ) et on cherche à attribuer une salle à chaque cours. On souhaite qu'à tout moment une salle ne puisse être attribuée à deux cours différents et on aimerait utiliser le plus petit nombre de salles possibles.
Ce problème d'allocation de ressources (ici les salles) en fonction de besoins fixes (ici les horaires des cours) intervient dans de nombreuses situations très diverses (allocation de pistes d'atterrissage aux avions, répartition de la charge de travail sur plusieurs machines, ...).
I.A - Représentation du problème
On modélise le problème ainsi :
chaque besoin est représenté par un segment [a, b] où a, b ∈ ℕ et a ⩽ b;
deux besoins I et J sont en conflit quand I ∩ J ≠ ∅.
La donnée du problème est une suite finie ( I_0, ⋯, I_(n − 1) ) de n segments où n ∈ ℕ^∗.
Figure 1 Deux exemples de problèmes
On représente un segment en Caml par un couple d'entiers, la donnée du problème est une valeur du type (int*int) vect. Le problème a de la figure 1 est représenté par le tableau
[I (0, 3); (1, 3); (2, 5); (4, 7); (6, 10); (8, 9); (11, 12) I]
I.A.1) Écrire une fonction ayant pour signature
conflit : int * int -> int * int -> bool
telle que conflit I J renvoie true si et seulement si I et J sont en conflit.
I.B - Graphe simple non orienté
On appelle graphe simple non orienté un couple G = (S, A) où
S est un ensemble fini dont les éléments sont appelés les sommets du graphe ;
A est un ensemble de paires d'éléments distincts de S. Lorsque {x, y} ∈ A on dit que x et y sont reliés dans G et {x, y} est appelée une arête de G. Les sommets reliés à un sommet x sont appelés les voisins de x.
Étant donnée une énumération de S sous la forme d'une suite finie ( x_0, ⋯, x_(n − 1) ) on représente A en Caml par un élément du type int list vect ainsi : pour i ∈ {0, ⋯, n − 1}, la liste A. (i) contient les j tels que x_i soit relié à x_j dans G.
On représente graphiquement le graphe G par un diagramme où les arêtes sont représentées par des traits entre les sommets.
Les arêtes du graphe dont une représentation graphique est donnée figure 2 sont représentées en Caml par le tableau:
[| [1;2;3]; [0;2;3]; [0;1;3;4]; [0;1;2]; [2] |]
Figure 2
Une telle liste d'arêtes suffit pour déterminer un graphe lorsque l'énumération des sommets est connue car on peut alors identifier un sommet à son indice. Dans la suite de ce problème on identifiera ainsi un graphe à sa liste d'arêtes.
I.C - Graphe d'intervalles
Soit I¯ = (I_0, …, I_(n − 1)) une suite finie de segments, on appelle graphe d'intervalles associé à I¯ le graphe G(I¯)
dont les sommets sont les segments I_0, …, I_(n − 1)
et où, pour i, j ∈ {0, …, n − 1}, avec i ≠ j, les sommets I_i et I_j sont reliés si et seulement si ils sont en conflit.
Le graphe d'intervalles qui correspond au problème a de la figure 1 admet la représentation graphique de la figure 3.
Figure 3
I.C.1) Donner une représentation graphique du graphe d'intervalles associé au problème b de la figure 1 .
I.C.2) Écrire une fonction ayant pour signature
construit_graphe : (int * int) vect -> int list vect
qui étant donné le tableau des segments I¯ = (I_0, …, I_(n − 1)), énumérés dans cet ordre, renvoie la représentation des arêtes de G(I¯).
I.D - Coloration
Soit G = (S, A) un graphe simple non orienté dont les sommets sont x_0, …, x_(n − 1). On appelle coloration de G une suite finie d'entiers naturels ( c_0, …, c_(n − 1) ) telle que
∀(i, j) ∈ {0, …, n − 1}^2, {x_i, x_j} ∈ A ⟹ c_i ≠ c_j
L'entier c_i est appelé la couleur du sommet x_i et la condition se traduit ainsi: deux sommets reliés ont des couleurs distinctes. Dorénavant, le terme couleur sera synonyme d'entier naturel.
La suite finie ( 0, 1, 2, 3, 0 ) est une coloration du graphe de la figure 2.
Lorsqu'une coloration utilise le plus petit nombre de couleurs distinctes possibles, on dit qu'elle est optimale. On note alors χ(G) ce nombre minimum de couleurs, appelé le nombre chromatique de G.
En associant une salle à chaque couleur, on peut répondre au problème initial à l'aide d'une coloration de son graphe d'intervalles associé.
I.D.1) Déterminer des colorations optimales pour les graphes d'intervalles associés aux deux problèmes de la figure 1. On attribuera à chaque fois la couleur 0 à l'intervalle I_0.
I.D.2) Couleur disponible
a) Écrire une fonction de signature
appartient : int list -> int -> bool
telle que l'appel à appartient l × envoie true si et seulement si l'entier x est présent dans la liste l.
b) Écrire une fonction de signature
plus_petit_absent : int list -> int
telle que l'appel à plus_petit_absent 1 renvoie le plus petit entier naturel non présent dans 1 .
c) On considère ici une coloration progressive des sommets d'un graphe. Pour cela, une coloration partielle est un tableau couleurs: int vect tel que couleurs. (i) contient la couleur de i s'il est coloré et -1 sinon, ce qui ne pose pas de problème car les couleurs sont toujours positives.
Écrire une fonction de signature
couleurs_voisins : int list vect -> int vect -> int -> int list
telle que l'appel à couleurs_voisins aretes couleurs i renvoie la liste des couleurs des voisins colorés du sommet d'indice i dans le graphe décrit par aretes où le tableau couleurs décrit une coloration partielle.
d) En déduire, une fonction de signature
couleur_disponible : int list vect -> int vect -> int -> int
telle que l'appel à couleur_disponible aretes couleurs i renvoie la plus petite couleur pouvant être attribuée au sommet i afin qu'il n'ait la couleur d'aucun de ses voisins dans le graphe décrit par aretes.
I.E - Cliques
Soit G = (S, A) un graphe.
Un sous-ensemble C ⊂ S est appelé une clique de G lorsqu'il vérifie
∀x, y ∈ C, x ≠ y ⟹ {x, y} ∈ A
Le nombre d'éléments de C est appelé sa taille. La taille de la plus grande (celle qui possède le plus grand nombre d'éléments) clique de G est notée ω(G).
I.E.1) Déterminer χ(G) et ω(G) lorsque
a) G ne possède pas d'arête (c'est à dire A = ∅ ).
b) G est un graphe complet à n sommets, c'est à dire |S| = n et pour tous u, v ∈ S distincts, {u, v} ∈ A.
I.E.2) Comparer χ(G) et ω(G) pour un graphe G quelconque.
I.E.3) Écrire une fonction de signature
est_clique : int list vect -> int list -> bool
telle que est_clique aretes xs renvoie true si et seulement si la liste xs est une liste d'indices de sommets formant une clique dans le graphe décrit par aretes.
II Algorithme glouton pour la coloration
Étant donnée une liste de segments I¯ = (I_0, I_1, …, I_(n − 1)) de longueur n ⩾ 1, on se propose de déterminer une coloration optimale de son graphe d'intervalles associé. On appelle coloration de I¯ une suite finie d'entiers naturels ( c_0, …, c_(n − 1) ) telle que
∀(i, j) ∈ {0, …, n}^2, I_i ∩ I_j ≠ ∅ ⟹ c_i ≠ c_j
On suppose dans cette partie que les segments I_k = [a_k, b_k], pour k ∈ {0, …, n − 1}, sont énumérés dans l'ordre croissant de leur extrémités gauches, c'est-à-dire que
a_0 ⩽ a_1 ⩽ … ⩽ a_(n − 1)
On propose l'algorithme suivant:
Pour k variant de 0 à n − 1, colorer l'intervalle I_k avec la plus petite couleur non encore utilisée dans la coloration des intervalles I_j, avec 0 ⩽ j < k, qui ont une intersection non vide avec I_k.
Ainsi, l'intervalle I_0 est toujours coloré avec la couleur 0 , l'intervalle I_1 reçoit la couleur 0 si I_0 ∩ I_1 = ∅, et la couleur 1 sinon, etc.
II.A - L'algorithme sur un exemple
Déterminer la coloration renvoyée par l'algorithme pour le problème b décrit sur la figure 1 .
II.B - Coloration
Écrire une fonction de signature
coloration : (int * int) vect -> int list vect -> int vect
telle que l'appel coloration segments aretes, où segments est un tableau contenant des segments triés par ordre croissant de leurs extrémités gauches et où aretes représente les arêtes du graphe d'intervalles associé à ces segments, renvoie la coloration obtenue avec l'algorithme ci-dessus.
II.C - Preuve de l'algorithme
On se propose maintenant de démontrer que l'algorithme ci-dessus fournit une coloration optimale de l'ensemble de segments. Soit k un entier entre 0 et n − 1. On suppose qu'à la k-ième étape de l'algorithme, le segment I_k reçoit la couleur c.
II.C.1) L'extrémité gauche du segment I_k appartient à un certain nombre de segments parmi I_0, I_1, …, I_(k − 1). Combien au moins?
II.C.2) Prouver que l'ensemble constitué de I_k et de ses voisins d'indice inférieur à k constitue une clique de taille au moins c + 1 dans le graphe d'intervalles associé.
II.C.3) En déduire que le nombre de couleurs nécessaires à une coloration de l'ensemble des segments est au moins égal à c + 1.
II.C.4) Conclure.
II.D - Complexité
Déterminer la complexité de la fonction coloration en fonction du nombre m d'arêtes du graphe d'intervalles associé à la liste I¯.
III Graphes munis d'un ordre d'élimination parfait
On introduit ici la notion d'ordre d'élimination parfait, dont on montre qu'il existe toujours pour un graphe d'intervalles, et qui permet de proposer un algorithme glouton pour le problème de la coloration d'un graphe. Soient G = (S, A) un graphe et (x_0, …, x_(n − 1)) une énumération des sommets de G. Pour tout i ∈ {0, …, n − 1} on note G_i = (S_i, A_i) où S_i = {x_0, …, x_i} et
∀k, l ∈ {0, …, n − 1}, {x_k, x_l} ∈ A_i ⟺ k ⩽ i et l ⩽ i et {x_k, x_l} ∈ A
G_i est ainsi le graphe déduit de G en se restreignant aux sommets de x_0 à x_i.
Une énumération (x_0, …, x_(n − 1)) des sommets de G est appelée un ordre d'élimination parfait si pour tout i ∈ {0, …, n − 1} les voisins de x_i d'indices inférieurs à i forment une clique.
III.A - Un exemple
Déterminer un ordre d'élimination parfait pour le graphe G donné par la représentation de la figure 4 .
Figure 4
III.B - Vérification
III.B.1) Écrire une fonction de signature
voisins_inferieurs : int list vect -> int -> int list
telle que voisins_inferieurs aretes x renvoie la liste des voisins du sommet d'indice x dont l'indice est strictement inférieur à x.
III.B.2) Écrire une fonction de signature
est_ordre_parfait : int list vect -> bool
telle que est_ordre_parfait aretes renvoie true si et seulement si l'énumération associée au graphe représenté par aretes est un ordre d'élimination parfait.
III.C - Ordre d'élimination parfait pour un graphe d'intervalles
Montrer que l'énumération des segments ( I_0, …, I_(n − 1) ) obtenue en les triant par leurs extrémités gauches en ordre croissant est un ordre d'élimination parfait de leur graphe d'intervalles.
III.D - Coloration
On considère un graphe dont (x_0, …, x_(n − 1)) est une énumération des sommets.
On colore ce graphe à l'aide l'algorithme suivant :
pour i allant de 0 à n − 1, on colore x_i avec la plus petite couleur qui ne soit pas utilisée par un de ses voisins déjà colorés.
III.D.1) Appliquer cet algorithme de coloration au graphe G de la figure 4 muni
a) de l'ordre (x_0, …, x_7);
b) d'un ordre d'élimination parfait.
III.D.2) Écrire une fonction de signature
colore : int list vect -> int vect
telle que l'appel à colore aretes renvoie selon cet algorithme un tableau c représentant une coloration valide du graphe décrit par aretes où la couleur du i-ème sommet est donnée par c.(i).
III.D.3) Soit (c_0, …, c_(n − 1)) la coloration obtenue par cet algorithme pour un graphe G dont l'énumération des sommets est un ordre d'élimination parfait.
a) Montrer que pour tout i ∈ {0, …, n − 1} on a χ(G) ⩾ 1 + c_i.
b) En déduire que l'algorithme de coloration renvoie une coloration optimale.
IV Ordre d'élimination parfait pour un graphe cordal
On s'intéresse ici à une nouvelle condition suffisante pour qu'un graphe admette un ordre d'élimination parfait, qui s'exprime en considérant les cycles de longueur au moins égale à 4 du graphe considéré.
Un graphe G est dit cordal lorsque pour tout cycle C = (v_0, v_1, …, v_(n − 1), v_0) de G de longueur n ⩾ 4, il existe i, j distincts entre 0 et n − 1 tels que les sommets v_i et v_j soient reliés dans le graphe G mais non successifs dans le cycle. Une telle arête {v_i, v_j} est appelée une corde du cycle C. Autrement dit, le graphe G est cordal lorsque tout cycle de G de longueur supérieure ou égale à 4 possède une corde.
IV.A - Cycles de longueur 4 dans un graphe d'intervalles
Soit G un graphe d'intervalles. Dans cette question, on se propose de démontrer par l'absurde que tout cycle de longueur 4 de G possède une corde. On suppose à cet effet que G contient un 4-cycle sans corde.
On dispose donc de 4 segments I_0, I_1, I_2, I_3 tels que I_0 ∩ I_1 ≠ ∅, I_1 ∩ I_2 ≠ ∅, I_2 ∩ I_3 ≠ ∅, I_3 ∩ I_0 ≠ ∅, et I_0 ∩ I_2 = ∅, I_1 ∩ I_3 = ∅. On supposera pour simplifier que les extrémités des segments sont toutes distinctes.
IV.A.1) Montrer qu'aucun des segments I_k, k = 0, 1, 2, 3 n'est inclus dans un autre de ces segments.
IV.A.2) On a donc par exemple min I_0 < minI_1 < maxI_0 < maxI_1. Montrer que min I_1 < minI_2 < maxI_1 < maxI_2 et de même pour I_2 et I_3.
IV.A.3) Conclure à une contradiction.
IV.B - Cordalité des graphes d'intervalles
Montrer plus généralement que tout graphe d'intervalles est cordal.
IV.C - Une enquête policière
Six personnes sont entrées dans la bibliothèque le jour où un livre rare y a été volé. Chacune d'entre elles est entrée une seule fois dans la bibliothèque, y est restée un certain temps, puis elle en est sortie. Si deux personnes étaient ensemble dans la bibliothèque à un instant donné, alors au moins l'une des deux a vu l'autre. À l'issue de l'enquête, les témoignages recueillis sont les suivants : Albert dit qu'il a vu Bernard et Édouard dans la bibliothèque. Bernard a vu Albert et Isabelle. Charlotte affirme avoir vu Didier et Isabelle. Didier dit qu'il a vu Albert et Isabelle. Édouard certifie avoir vu Bernard et Charlotte. Isabelle dit avoir vu Charlotte et Édouard. Seul le coupable a menti. Qui est-il ?
IV.D - Ordre d'élimination parfait
Un sommet v d'un graphe G est dit simplicial lorsque l'ensemble des voisins de v dans G est une clique.
Étant donnés un graphe G = (S, A) et S^′ ⊂ S un ensemble de sommets de G le sous-graphe de G induit par S^′ est le graphe H = (S^′, A^′) où A^′ ⊂ A est l'ensemble des arêtes de G dont les extrémités appartiennent à S^′. On représente en Caml un sous-graphe induit d'un graphe G possédant n sommets par le couple (aretes, sg) de type int list vect * bool vect où aretes est une description du graphe G et sg est un tableau de taille n tel que sg. (i) vaut true si le sommet d'indice i est un sommet du sous-graphe induit et false sinon.
IV.D.1) Écrire une fonction de signature
simplicial : (int list vect * bool vect) -> int -> bool
telle que l'appel à simplicial (aretes, sg) k , où le sommet d'indice k est supposé appartenir au sous-graphe induit H décrit par (aretes, sg), renvoie true si le sommet d'indice k est simplicial dans H et false sinon. Déterminer la complexité de la fonction simplicial.
IV.D.2) Écrire une fonction de signature
trouver_simplicial : (int list vect * bool vect) -> int
telle que l'appel à trouver_simplicial (aretes, sg) renvoie, s'il en existe, un sommet simplicial du sous-graphe induit décrit par (aretes, sg). Déterminer la complexité de la fonction trouver_simplicial.
IV.D.3) Écrire une fonction de signature
ordre_parfait : int list vect -> int list
telle que l'appel à ordre_parfait aretes renvoie un ordre d'élimination parfait du graphe décrit par aretes, s'il en existe un. Déterminer la complexité de la fonction ordre_parfait.
IV.E - Coupures minimales dans un graphe cordal
Étant donné un graphe G on appelle coupure de G tout ensemble C ⊆ S de sommets de G, de cardinal au moins égal à 2 , tel que certains sommets reliés par un chemin dans le graphe G ne le sont plus dans le sous-graphe H de G induit par S∖C.
On se donne dans cette question un graphe cordal G = (S, A). Soit C une coupure de G de cardinal minimal (supérieur ou égal à 2). Soit H le sous-graphe de G induit par S∖C. Soient a et b deux sommets de G déconnectés par la coupure, et soient G_1 et G_2 les composantes connexes de a et b dans le graphe H. Soient enfin x et y deux sommets distincts de la coupure C.
IV.E.1) Montrer que x est voisin dans le graphe G d'un sommet de G_1 et d'un sommet de G_2, et de même pour y.
IV.E.2) Montrer qu'il existe un chemin P_1 = (x, a_1, …, a_p, y) dont tous les sommets hormis x et y sont des sommets de G_1 et un chemin P_2 = (y, b_1, …, b_q, x) dont tous les sommets hormis x et y sont des sommets de G_2.
IV.E.3) On prend deux tels chemins P_1 et P_2 de longueur minimale. En considérant un cycle formé à partir des chemins P_1 et P_2, montrer que x et y sont reliés dans le graphe G.
IV.E.4) Montrer que C est une clique du graphe G.
IV.F - Sommets simpliciaux dans un graphe cordal
On se propose de montrer que tout graphe cordal G possède la propriété suivante, que l'on appellera la propriété P(G) : G possède un sommet simplicial, et même deux sommets simpliciaux non voisins si G n'est pas complet. On se donne dans toute la question un graphe cordal G.
IV.F.1) Montrer que si G est complet alors tous ses sommets sont simpliciaux.
IV.F.2) Montrer que la propriété P(G) est vérifiée si G possède 1,2 ou 3 sommets.
IV.F.3) On suppose dans cette question que G n'est pas complet, possède au moins trois sommets et que la propriété P(G^′) est vérifiée pour tous les graphes cordaux G^′ ayant strictement moins de sommets que G. Soit C une coupure de G de cardinal minimal. Soient a et b deux sommets de G déconnectés par la coupure C, et G_1 et G_2 les composantes connexes de a et b dans le sous-graphe de G induit par S∖C. Soit S_1 (resp : S_2 ) l'ensemble des sommets de G_1 (resp : G_2 ). Soit enfin H_1 (resp : H_2 ) le sous-graphe de G induit par S_1 ∪ C (resp S_2 ∪ C).
a) Justifier que le graphe H_1 est cordal.
b) On suppose que H_1 est complet. Montrer que S_1 contient un sommet simplicial du graphe H_1. Prouver que ce sommet est en fait un sommet simplicial de G.
c) On suppose que H_1 n'est pas complet. Montrer que S_1 ∪ C contient deux sommets simpliciaux non voisins du graphe H_1. Montrer que au moins l'un de ces deux sommets est dans S_1 et que ce sommet est un sommet simplicial de G.
d) Montrer que la propriété P(G) est vérifiée.
IV.G - Ordre d'élimination parfait dans un graphe cordal
Montrer que tout graphe cordal possède un ordre d'élimination parfait.
Questions fréquentes
4 questions
Sur quels chapitres porte le sujet d'option informatique Centrale MP 2015 ?
Afficher ou masquer la section
Sur quels chapitres porte le sujet d'option informatique Centrale MP 2015 ?
+
Le sujet porte sur la théorie des graphes appliquée aux graphes d'intervalles : coloration, cliques, algorithme glouton et ordre d'élimination parfait, avec une programmation complète en Caml.
Quelles erreurs le jury a-t-il le plus relevées sur ce sujet d'option informatique Centrale MP 2015 ?
+
Le jury relève surtout des calculs de complexité mal justifiés, une gestion des références défaillante et une réutilisation insuffisante des fonctions précédemment programmées.
Ce sujet d'option informatique Centrale MP 2015 est-il difficile ?
+
Le rapport le décrit comme globalement bien compris, avec un niveau satisfaisant des candidats et peu de très mauvaises copies, ce qui correspond à une difficulté moyenne.
Le langage Python est-il accepté pour ce sujet d'option informatique Centrale MP 2015 ?
+
Non, le rapport rappelle explicitement que l'unique langage retenu pour l'option informatique est Caml Light, même si le jury a observé des programmations en Python.
Pas de description pour le moment
Commentaires• Centrale Option Informatique MP 2015
Connectez-vous pour participer aux discussions
Partagez vos avis, posez des questions et échangez avec la communauté
Même chapitre : Théorie des graphes (coloration… (+2)X ENS Option Informatique MP 2018X-ENS · 2018Corrigé
Même chapitre : Complexité algorithmique (+1)Mines Option Informatique MP 2013Mines · 2013Corrigé
Même année, CCINPCCINP Option Informatique MP 2015CCINP · 2015Corrigé
.jpg)
