Mines Informatique MP 2003

Thème de l'épreuve Logique propositionnelle trivaluée. Coloration de graphes.
Principaux outils utilisés graphes généraux, tables de vérité, logique propositionnelle, itérateurs sur les listes, récurrences, algorithmes récursifs
Mots clefs lois de De Morgan, nombre chromatique, méthode de HÖrner

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                       

Rapport du jury

(télécharger le PDF)
     

Énoncé obtenu par reconnaissance optique des caractères


ÉCOLE NATIONALE DES PONTS ET CHAUSSÉES,
ÉCOLES NATIONALES SUPÉRIEURES DE L'AÊRONAUTIQUE ET DE L'ESPACE,
DES TECHNIQUES AVANCÉES, DES TELECOMMUNICATIONS,
DES MINES DE PARIS, DES MINES DE SAINT--ÊTOENNE, DES MINES DE NANCY
DES TÉLÉCDMMUNIÇATIONS DE BRETAGNE,
ÉCOLE POLYTECHNIQUE
(Filière T.S.I.)

CONCOURS D'ADMISSION 2003

ÉPREUVE D'INFORMATIQUE

Filière MP
(Durée de l'épreuve : 3 heures)

Sujet mis àla disposition des concours Cycle International, ENSTIM et TPE--EIVP.

Les candidats et les candidates sont priés de mentionner de façon

apparente sur la première page de la copie :
« INFORMATIQUE -- Filière MP »

RECOMMANDATIONS AUX CANDIDATS ET CANDIDATES

. L'énoncé de cette épreuve, y compris cette page de garde, comporte 8 pages.

0 Si, au cours de l'épreuve, un candidat ou une candidate repère ce qui lui 
semble être une erreur
d'énoncé, il ou elle le signale sur sa copie et poursuit sa composition en 
expliquant les raisons des
initiatives qu'il ou elle a décidé de prendre.

- Tout résultat fourni dans l'énoncé peut être utilisé pour les questions 
ultérieures même s'il n'a pas
été démontré.

- Il ne faut pas hésiter à formuler les commentaires qui semblent pertinents 
même lorsque l'énoncé
ne le demande pas explicitement.

. L'utilisation d'une calculatrice ou d'un ordinateur est interdite.

COMPOSITION DE L'ÉPREUVE
L'épreuve comporte deux parties indépendantes :

0 un exercice de logique des propositions, page 2, à résoudre en 45 mn environ ;
- un problème d'algorithmique, pages 3 à 8, à résoudre en 135 mn environ.

1. Exercice de logique -- 45 mn environ
Logique propositionnefie tri--valuée

On désire étendre la logique propositionnelle bivaluée classique (notée par la 
suite 45) de sorte à

prendre en compte, en plus de V (vrai) et F (faux), une troisième valeur de 
vérité, notée [ (pour indéterminé).
?

La logique de Lukasiewicz, notée 15, est une telle logique tri-valuée dans 
laquelle le connecteur de

négation ( --' ), le connecteur de conjonction ( A ), le connecteur de 
disjonction ( v ) et le connecteur
d'implication ( => ) sont définis par les tables de vérités suivantes :

On dit que deux propositions sont équivalentes dans une logique donnée ..[' si 
elles ont même table de
vérité dans cette logique.

D 1 -Indiquer une proposition P1 équivalente dans 45 à la proposition «x v y » 
et n'utilisant pas d'autres
connecteurs que --1 et A. Les propositions P1 et « x v y » sont-elles 
équivalentes dans ..[3 '?

E] 2 -- Indiquer une proposition P2 équivalente dans ..[ê à la proposition « x 
=> y » et n'utilisant pas d'autres
connecteurs que -1 et v. Les propositions P2 et « x =: y » sont-elles 
équivalentes dans 4% ?

Cl 3 -- Établir (en détaillant son obtention) la table de vérité dans J3 de la 
proposition P3 suivante :

((x=>y) A ((--x)=>y)) =>y--
Cette proposition est--elle une tautologie dans ..[5 (la définition d'une 
tautologie dans la logique °['3 reste la même
que dans la logique J£) ?

D 4 -- On appelle littéral une variable pr0positionnelle ou sa négation. Dans 
45, toute proposition logique admet
une forme normale disjonctive (c'est--à--dire une disjonction de conjonctions 
de littéraux) qui lui est équivalente.
Établir une proposition P4 sous forme normale disjonctive équivalente dans .,[5 
àla proposition « (x v y) => 1 ».

Les propositions P.; et « (x v y) => z » sont-elles équivalentes dans ..[â ?
D 5 -- Peut--on faire un raisonnement par contraposition dans 45 (on justifiera 
la réponse) '?

Cl 6 - On définit un ordre sur les valeurs F, I et V par : F < 1 < V. On 
considère une logique Jtri--valuée pour

laquelle simultanément :
. J'est une extension de ..[5 pour les quatre connecteurs usuels (--1, A, v, =) 
; autrement dit, les restrictions

aux valeurs V et F des tables de vérité de J donnent les tables de vérité de 
..[ê ;

le connecteur A est commutatif ;

la proposition « x v y » est équivalente à P1 ;

la proposition << x => y » est équivalente à P; ;

pour toute valeur de y, la fonction x t----> x A y croît au sens large avec x ;

- les propositions << --. (----. x) » et « x » sont équivalentes.
Combien y a--t--il de telles logiques (on justifiera la réponse) '?

2. Problème d'algorithmique -- 135 mn environ

Coloration d'un graphe

Préliminaire concernant la programmation : il faudra écrire des fonctions ou 
des procédures à l'aide d'un
langage de programmation qui pourra être soit Caml, soit Pascal, tout autre 
langage étant exclu. Indiquer en
début de problème le langage de programmation choisi ; il est interdit de 
modifier ce choix au cours de
l'épreuve. Certaines questions du problème sont formulées différemment selon le 
langage de programmation ;
cela est indiqué chaque fois que c'est nécessaire. Par ailleurs, lorsqu'un 
candidat ou une candidate écrira une
fonction ou une procédure en langage de programmation, il ou elle précisera si 
nécessaire le rôle des variables
locales et pourra définir des fonctions ou procédures auxiliaires qu'il ou elle 
explicitera. Enfin, lorsque le
candidat ou la candidate écrira une fonction ou une procédure, il ou elle 
pourra faire appel à une autre fonction ou
procédure définie dans les questions précédentes.

Définitions et notations
On utilisera dans tout le problème les notations et définitions suivantes :

- une paire est un ensemble composé de deux éléments a et b distincts et est 
notée {a, 17} (ce qui est égal à
{b, al) ;

0 un graphe G est composé d'un ensemble S(G) d'éléments appelés sommets et 
d'une liste A(G) de paires de
sommets ; les éléments de A(G) sont appelés arêtes et ne sont pas 
nécessairement tous distincts ;

o le cardinal de S(G) est noté n(G) et on a toujours: S(G) : {O, 1, ..., n(G) 
-- 1} ; un graphe est donc
entièrement décrit par le couple (n(G), A(G)) ;

0 deux sommets s et t de G sont dits voisins si {s, t} est une arête de G ;

0 un même identificateur écrit dans deux polices de caractères différentes 
désignera la même entité mais du
point de vue mathématique pour une police (en italique) et du point de vue 
informatique pour "l'autre (en
romain) ; par exemple, G sera la représentation informatique du graphe G.

Une représentation graphique d'un graphe G consiste à associer à chaque sommet 
de G un cercle
contenant le numéro du sommet et à tracer une ligne entre deux cercles 
représentant des sommets si les sommets

correspondants forment une arête de G.
Exemple introductif : un graphe (nommé Gex]) et une représentation de Gex]

On considère le graphe Gex] dessiné à droite et dont les
caractéristiques sont :

n(Gex] ) = 5

A(Gex1) : {{O, 4}, {4, 3}, {O, 3},{1, 3}, {O, 3}, {3, 0}}.

Il y a trois arêtes entre le sommet O et le sommet 3.
Le sommet 0 a pour voisins les sommets 3 et 4.

Le sommet 1 a pour voisin le sommet 3.

Le sommet 2 n'a pas de voisin.

Le sommet 3 a pour voisins les sommets O, 1 et 4.
Le sommet 4 a pour voisins les sommets O et 3.

Le graphe Gex]
Indications pour la programmation
Caml : On définit les types Arete et Graphe par :
type Arete : {a : int; b : int};;
type Graphe : {n : int; A: Arete list};;
Ainsi, le graphe Gex] de l'exemple introductif est défini par :
letGexl= {n=5; A= [{a=0;b=4}; {a=4; b=3}; {a=0; b=3};
{a=l;b=3}; {a=0;b=3l; {a= ;b=0}l};;

Les variables de type Arete ou de type Graphe sont des enregistrements; un 
enregistrement

contient des champs ; par exemple, une variable de type Arete contient les 
champs a et b. On peut
accéder à un champ d'une variable de type enregistrement en faisant suivre le 
nom de cette variable
d'un point puis du nom du champ considéré ; par exemple, on accède au champ n 
du graphe Gexl par
Gexl . n (qui vaut 5). '

Pascal : Dans tout le problème, on supposera qu'on écrit les différentes 
fonctions dans un fichier contenant les
' définitions suivantes : ' ' '

COHSt
MAX_SOMMETS = 100;
MAX_ARETES = 1000;

type Arete : RECORD
a : integer;
b : integer;
end;

type Graphe : RECORD

n : integer;
nb_aretes : integer;
A : array[0..MAX_ARETES -- 1] of Arete;

end;

type Table : RECORD
nb_donnees : integer;
cases : array[0..MAX_SQMMETS -- 1] of integer;

end;

Les types Arete, Graphe et Table sont des types pour des enregistrements 
(RECORD). Un
enregistrement contient des champs (quelquefois aussi appelés des membres); par 
exemple, une
variable de type Arete contient les champs a et b ; on peut accéder à un champ 
d'une variable de type
enregistrement en faisant suivre le nom de cette variable d'un point puis du 
nom du champ considéré,
comme on le voit dans la définition de Gexl ci-dessous. Les variables de type 
enregistrement se

manipulent comme toute autre variable : on peut définir des variables de type 
enregistrement, on peut
affecter à une variable de type enregistrement la valeur d'une autre variable 
du même type, les variables
de type enregistrement peuvent servir de paramètres à des fonctions ou 
procédures et peuvent être
renvoyées par des fonctions ; en revanche, il est interdit de les comparer 
directement.

Ainsi, le graphe Gex] de l'exemple introductif est défini par :

Gexl.n := 5;
Gexl.nb_aretes := 6;

Gexl.A[0].a := O; Gexl.A[0].b : 4;
Gexl.A[l].a := 4; Gexl.A[l].b = 3;
Gexl.A[2].a ': O; Gexl.A[2].b = 3;
Gexl.A[3].a .: l; Gex1.A[3].b ': 3;
Gexl.A[4].a := O; Gexl.A[4].b : 3;
Gexl.A[5].a :: 3; Gexl.A[5].b : 0;

On supposera que les graphes traités n'ont jamais plus de MAX_SOMMETS sommets 
ou plus de
MAX_ARETES arêtes.

Remarques importantes (langage Pascal) : lorsqu'on aura affaire à une variable 
T de type Table, le
tableau T . cases servira à contenir un ensemble de données entières et on 
convient que le champ
T . nb_donnees devra toujours indiquer le nombre de données de cet ensemble (et 
non la longueur
totale MAX__SOMOETS du tableau T. cases) ; les données contenues dans T. cases 
se trouveront
donc toujours dans les cases indicées de 0 à T . nb_donnees -- 1. Par ailleurs, 
pour une variable G
de type Graphe correspondant à un graphe G, G.n contiendra le nombre n(G) de 
sommets de G,
G . nb_aretes contiendra le nombre d'arêtes de G et le tableau G . A contiendra 
les arêtes de G entre

les indices 0 et G. nb_aretes --- l.

I-- Détermination des voisins des sommets
Cl 7-- Il s'agit dans cette question de programmer une fonction qui insère une 
donnée entière dans une suite triée

d' entiers distincts a condition que cette nouvelle donnée ne figure pas déjà 
dans la suite.
Caml . Écrire une fonction insere telle que, si L est une liste d'entiers 
distincts triée par ordre croissant et s

un entier quelconque, insere L s renvoie
- la liste d'entiers obtenue en insérant s dans L selon l'ordre croissant si la 
valeur s ne figurait

pas dans L,
-- la liste L si s figurait déjà dans L.

Pascal : Écrire une fonction insere telle que, lorsque
-- T est une variable de type Table telle que T . cases contient T . nb_donnees 
entiers triés

par ordre croissant et
-- s est un entier,
insere (T, s) renvoie
- un résultat de type Table obtenu en insérant s dans T. cases selon l'ordre 
croissant si la
valeur s ne figurait pas dans T . cases (on n'oubliera pas d'actualiser T . 
nb_donnees),

_ -- T si s figurait déjà dans T . cases.

E] 8-- On s'intéresse àla complexité de la fonction insere.

Caml: Indiquer, en fonction de la longueur de L, la complexité dans le pire des 
cas de l'algorithme utilisé pour
la fonction insere de la question Cl 7.

Pascal . Indiquer, en fonction de T . nb_donnees, la complexité dans le pire 
des cas de l'algorithme utilisé
pour la fonction insere de la question [| 7.

Cl 9 -- Il s'agit dans cette question d'écrire une fonction qui donne la liste 
triée des voisins d'un sommet donné

dans un graphe donné.
Caml : Ecrire en Caml une fonction voisins telle que voisins G s renvoie la 
liste triée par ordre

croissant des voisins du sommets dans le graphe G. On utilisera pour cela la 
fonction insere.
Pascal : Écrire en Pascal une fonction voisins telle que voisins (G, s) renvoie 
un résultat de type
Table dont :
-- le champ cases contient les voisins du sommets dans le graphe G triés par 
ordre croissant,
-- le champ nb_donnees contient le nombre de ces voisins.
On utilisera pour cela la fonction insere.

II -- Un algorithme de bonne coloration d'un graphe

On appelle coloration d'un graphe G toute application c de l'ensemble S des 
sommets de G dans
l'ensemble des entiers naturels non nuls. Pour tout sommet s, l'entier c(s) 
s'appelle couleur des pour la
coloration c.

Une coloration c est une bonne coloration de G si pour toute arête {s, t} de G, 
on a c(s) # c(t) ;
autrement dit, une coloration est une bonne coloration si les extrémités de 
toute arête sont de couleurs

différentes.
On considère l'algorithme de bonne coloration suivant. Les couleurs disponibles 
sont les entiers

naturels non nuls ; la plus petite couleur est ainsi la couleur 1. On colorie 
les sommets les uns après les autres,

dans l'ordre 0, 1, 2 n(G) ---- 1 ; lorsqu'on considère un sommet s, on lui 
attribue la plus petite couleur
disponible, c'est-à--dire la plus petite couleur qui n'est pas déjà la couleur 
d'un voisin de s.

D 10 -- Que donne cet algorithme pour le graphe ° °

Gex2 ci--contre ? Y a--t--il une autre bonnecoloration \

de G utilisant moins de couleurs ?
Le graphe Gex2

D 11 -- Il s'agit d'écrire en langage de programmation l'algorithme de bonne 
coloration décrit plus haut. Pour
déterminer cette bonne coloration, on utilisera n( G) cases à valeurs entières 
d'un tableau dont les indices
O, 1, ..., n(G) -- 1 correspondront aux sommets de G; la case d'indice : 
contiendra après le déroulement de
l'algorithme la.couleur du sommets.

Caml : Écrire en Caml une fonction coloration telle que coloration G renvoie le 
tableau des couleurs

attribuées aux sommets du graphe G par l'algorithme décrit ci-dessus.

Pascal : On définit pour cette question un nouveau type par :
type Couleurs : array[0..MAX_SOMMETS -- 1] of integer;

Ecrire en Pascal une fonction coloration telle que coloration (G) renvoie le 
tableau des
couleurs attribuées aux sommets du graphe G par l'algorithme décrit ci-dessus ; 
le résultat retourné par
la fonction coloration sera de type Couleurs.

III --- Définition du nombre chromatique de G
Soit G un graphe et p un entier strictement positif. On appelle bonne 
p-coloration de G une bonne

coloration n'utilisant que des couleurs appartenant à l'ensemble { l, p}. On 
introduit les notations suivantes :
. BC(G, p) est l'ensemble des bonnes p-colorations de G ;
. fc(G, p) est le cardinal de BC(G, p) ;

- EC(G) = {p e N" tel que fc(G, p) == 0}.

D 12 ---- Montrer l'existence d'un unique entier nbc(G) tel que :

EC(G) : {p e N" tel que p 2 nbc(G)}.
On dit que nbc(G) est le nombre chromatique du graphe G : c'est le nombre 
minimum de couleurs permettant
de colorier les sommets de G de sorte que deux sommets voisins n'aient pas la 
même couleur.

D 13 -- Soit G un graphe n'ayant aucune arête. Déterminer nbc(G) en fonction de 
n(G) et, pour tout p e IN",
déterminer fc(G, p) en fonction de n(G) et p. '

D 14 -- Soit G un graphe tel que toute paire de sommets soit une arête. 
Déterminer nbc(G) en fonction de n(G) et,
pour tout p e N', déterminer fc(G, p) en fonction de n(G) et p.

13 15 ---'On considère le graphe Gex] de l'exemple introductif. Déterminer 
nbc(Gexl ) et, pour tout p e N",
déterminer fc(Gexl, p) en fonction de p.

IV -- Les applications H et K
On dit qu'un sommet d'un graphe est isolé s'il n'a aucun voisin. Par exemple, 
le sommet 2 est isolé

dans le graphe Gex] .

D 16 -- Étant donnés un graphe G et un sommet de G non isolé s, on note 
prem_voisin(G, s) le plus petit voisin
de s dans G, c'est--à--dire le voisin de s qui a le plus petit numéro. Par 
exemple, prem_voisin(Gexl , O) est le

sommet 3.
Caml: Ecrire en Caml une fonction prem_voisin telle que prem_voisin G 5 renvoie

prem_voisin(G, s). Cette fonction ne prévoira pas le cas où s est un sommet 
isolé de G.
Pascal : Ecrire en Pascal une fonction prem_voisin telle que prem_voisin (G , 
s) renvoie
prem_voisin(G, s). Cette fonction ne prévoira pas le cas où s est un sommet 
isolé de G.

D 17 -- On considère un graphe G possédant au moins une arête. On note 
prem_ni(G) le plus petit sommet non
isolé du graphe G, c'est--à--dire le sommet non isolé qui a le plus petit 
numéro. Par exemple, prem_ni(Gexl ) est le

sommet O.
Caml : Écrire une fonction prem_ni telle que prem_ni G renvoie prem_ni(G). 
Cette fonction ne prévoira

pas le cas où G ne possède aucune arête.
Pascal : Ecrire une fonction prem_ni telle que prem_ni (G) renvoie prem_ni(G). 
Cette fonction ne
prévoira pas le cas où G ne possède aucune arête.

Cl 18 -- Rappelons d'abord que dans la liste A(G) des arêtes d'un graphe G, il 
est possible qu'une même arête soit
répétée. ,
Etant donné un graphe G possédant au moins une arête, on pose :

sl : prem_ni(G)
sz : prem_vaisin(G, prem_ni(G)).
Par exemple, pour le graphe Gex] , s1 = 0 et s2 =" 3.
On note H(G) le graphe obtenu à partir de G en supprimant toutes les arêtes 
entre 81 et 512.

Par exemple, le graphe H(Gexl ),
représenté ci--contre, est caractérisé par :
n(H(Gexl )) = 5,
A(H(Gexl)) : {{O, 4}, {4, 3}, {l, 3}}.

Le graphe H(Gexl )

Caml : Écrire en Caml une fonction H telle que H G renvoie H(G) (qui sera de 
type Graphe). Cette fonction
ne prévoira pas le cas où G ne possède aucune arête.

Pascal : Écrire en Pascal une fonction H telle que H (G) renvoie H(G) (qui sera 
de type Graphe). Cette
fonction ne prévoira pas le cas où G ne possède aucune arête.

CI 19 -- On considère un graphe G possédant au moins une arête. On définit SI 
et sz comme dans la question
précédente ; on peut remarquer la relation : sz > 51- On construit alors un 
graphe noté K(G) de la façon décrite ci--
dessous.
0 On construit H(G) ;
0 dans H(G), on superpose sl et s; ; plus précisément,
-- on considère successivement chaque arête de la liste des arêtes de H(G) ; 
pour chacune d'entre
elles, on renumérote ses extrémités :
-- une extrémité de valeur strictement inférieure à s2 est inchangée ;
-- une extrémité de valeur 52 prend la valeur sl ;
- une extrémité de valeur strictement supérieure à s2 est décrémentée de 1 ;

--- on diminue de 1 le nombre de sommets du graphe.

Par exemple, K(Gexl ), représenté ci- °
contre, est décrit par :
n(K(Gexl )) = 4,
A(K(Gexl)) : {{O, 3}, {3, 0},{1, 0}}. ' @

Le graphe K(Gex1 )

' Caml : Écrire en Caml une fonction K telle que K G renvoie K(G) (le résultat 
sera de type Graphe). Cette
fonction ne prévoira pas le cas où G ne possède aucune arête.

Pascal : Écrire en Pascal une fonction K telle que K (G) renvoie K(G) (le 
résultat sera de type Graphe). Cette

fonction ne préVoira pas le cas où G ne possède aucune arête.

V ---- Fonction fc(G, p) et polynôme chromatique
Soit G un graphe possédant au moins une arête et soit p un entier non nul.

D 20 -- Montrer l'inclusion : BC(G, p) c: BC(H(G), p).

E] 21 -- Comparer les cardinaux de BC(K(G), p) et de BC(H(G), p) \ BC(G, p).

D 22 -- Montrer l'égalité : fc(G, p) =fc(H(G), p) --fc(K(G), p).

E] 23 -- En utilisant la formule obtenue dans la question D 22, décrire en 
termes simples un algorithme récursif
_ de calcul de fc(G, p) ; ici, on ne demande pas d'utiliser un langage de 
programmation.

D 24 -- Prouver que l'algorithme de la question [3 23 se termine.

[] 25 -- Le graphe G étant fixé, montrer que la fonction qui associe à p la 
quantité fc(G, p) est la restriction à N'
d'un polynôme en p de degré n(G). On appelle polynôme chromatique de G et on 
note Pc(G) ce polynôme.

VI ---- Calcul du polynôme Pc(G, p) et de nbc(G)

On ne considérera dans cette partie que des polynômes à une variable et à 
coefficients entiers.

Caml : Un polynôme de degré d est représenté par un tableau à (d + 1) cases, la 
case d'indice i contenant le
coefficient du monôme de degré 1". On pourra, pour connaître le degré d'un 
polynôme, utiliser la
fonction de Caml vect_length qui, lorsqu'on invoque vect_length T, où T est un 
tableau,
retourne le nombre de cases de ce tableau.

Pascal : On définit pour cette dernière partie un nouveau type par :
type Polynome : RECORD

degre : integer;

coeff : array[0..MAX_SOMMETS] of integer;
end;
On utilisera ce type pour représenter un polynôme dont le degré ne dépasse pas 
MAX_SOMMETS Le
champ degre contiendra le degré du polynôme et, pour i S degre, coeff [i] 
contiendra le

coefficient du monôme de degré i.

E] 26 -- Dans cette question, on va s'intéresser à la différence de deux 
polynômes. On ne traitera pas le cas où
simultanément les deux polynômes auraient même degré et même coefficient du 
monôme de plus haut degré.

Caml : Écrire en Caml une fonction difference telle que, lorsque P et Q sont 
deux variables représentant
des polynômes P et Q, difference P Q renvoie le polynôme P ---- Q représenté 
par un tableau
d'entiers comme indiqué dans l'introduction de cette partie.

Pascal : Écrire en Pascal une fonction difference telle que, lorsque P et Q 
sont deux variables de type
Po lynome représentant des polynômes P et Q, di f ference (P , Q) renvoie le 
polynôme P --- Q,
qui sera de type Po lynome.

Cl 27 -- Cette question consiste à calculer le polynôme chromatique Pc(G).

Caml : Écrire en Caml une fonction Pc telle que Pc G renvoie le polynôme Pc(G) 
représenté par le tableau
de ses coefficients comme indiqué au début de cette partie.

Pascal : Écrire en Pascal une fonction Pc telle que Pc (G) renvoie le polynôme 
Pc(G) sous la forme d'une

variable de type Polynome.

D 28 -- Dans cette question, il s'agit de calculer la valeur P(x) d'un polynôme 
P en une valeur entière x. On
n'utilisera pas de fonction prédéfinie du langage qui calculerait les 
puissances d'un entier. Les calculs seront
faits avec les quatre opérations arithmétiques ordinaires. De plus, la 
complexité de l'algorithme utilisé sera
nécessairement du même ordre de grandeur que le degré du polynôme considéré.

Caml : Écrire en Caml une fonction eval telle que eval P x renvoie P(x).
Pascal : Ecrire en Pascal une fonction eval telle que eval (P , x) , où P est 
de type Po lynome et x de type

integer, renvoie P(x).

D 29 -- Écrire dans le langage de programmation choisi une fonction qui calcule 
le nombre chromatique nbc(G)
d'un graphe G.

Extrait du corrigé obtenu par reconnaissance optique des caractères



Mines Informatique MP 2003 -- Corrigé
Ce corrigé est proposé par Samuel Mimram (ENS Lyon) ; il a été relu par 
JeanBaptiste Rouquier (ENS Lyon) et Vincent Puyhaubert (ENS Cachan).

Le sujet est constitué de deux problèmes indépendants.
Le premier problème traite de la logique booléenne et d'une extension tri-valuée
de cette logique. Il est relativement facile et ne requiert que des 
connaissances de
première année : il est principalement fondé sur l'utilisation de tables de 
vérité et
sur la notion d'équivalence entre propositions (deux propositions sont 
équivalentes si
elles ont la même table de vérité).
Le second problème aborde plusieurs aspects de la coloration des graphes, qui 
est
un problème classique d'algorithmique. Il comporte un certain nombre de 
questions
de programmation et des questions théoriques visant à faire manipuler les 
graphes.
En plus de la définition d'un graphe, les notions de nombre chromatique (le 
plus petit
nombre de couleurs nécessaires pour colorier un graphe) et de polynôme 
chromatique
d'un graphe sont introduites. Un algorithme naïf de coloration est proposé ainsi
que des transformations sur les graphes, qui permettent de trouver des 
algorithmes
calculant le polynôme et le nombre chromatique d'un graphe quelconque.
Ce sujet permet de réviser la logique booléene et constitue un bon exercice 
d'algorithmique permettant de voir (ou de revoir) et d'utiliser des fonctions 
avancées de
Caml Light.

Indications
1.

Logique propositionnelle tri-valuée

1 Utiliser l'identité : ¬(x  y)  ¬x  ¬y.
5 Formuler le raisonnement par contraposition en termes de propositions 
logiques.
6 Raisonner sur les tables de vérité et montrer que le problème se ramène à ne
trouver les valeurs que de quelques cases de la table de vérité du connecteur .
2.

Coloration d'un graphe

9 Parcourir pour tout sommet s la liste des arêtes. Pour toute arête de la
forme (s, b) rajouter l'élément b dans une liste initialement vide.
10 Remarquer que deux sommets de même parité ne sont pas voisins pour trouver
une meilleure coloration que celle donnée par l'algorithme.
11 Colorier au fur et à mesure les sommets, de 0 jusqu'à n - 1. À chaque étape,
calculer dans une variable auxiliaire la liste triée des couleurs déja 
utilisées par
les voisins du sommet à colorier.
12 Montrer que EC(G) est non vide, puis que :
p  EC(G) q  N

q > p = q  EC(G)

14 Montrer qu'une coloration du graphe est bonne si et seulement si les 
couleurs des
sommets sont deux à deux distinctes.
15 Considérer le triangle formé par les sommets 0, 3 et 4, puis le sommet 1, 
puis le
sommet 2.
17 prem_ni(G) est le minimum des sommets qui sont extrémité d'une arête.
18 Écrire une fonction qui, à une liste d'arêtes l et deux sommets s1 et s2 , 
enlève
toutes les arêtes de l reliant les sommets s1 et s2 .
19 Utiliser la fonction map de Caml pour renommer les sommets de la liste 
d'arêtes
de H(G).
20 Montrer que deux sommets voisins dans H(G) le sont aussi dans G.
21 Montrer que les colorations c de BC(H(G), p) r BC(G, p) sont les bonnes 
colorations de H(G) vérifiant c(s1 ) = c(s2 ).
22 Utiliser les deux questions précédentes.
24 Raisonner par récurrence sur le nombre d'arêtes des graphes.
25 Raisonner de même qu'à la question 24.
27 S'inspirer de l'algorithme de la question 23.
28 Utiliser la relation de récurrence xi+1 = xi × x (avec x0 = 1).
29 Écrire un programme qui trouve le plus petit entier i tel que Pc(G)(i) 6= 0.

1.

Logique propositionnelle tri-valuée

1 On sait d'après les lois de De Morgan que ¬(x  y)  ¬x  ¬y et que ¬¬x  x
(on note  l'équivalence entre propositions). On en déduit :
¬(¬x  ¬y)  (¬¬x)  (¬¬y)  x  y
La proposition P1 = ¬(¬x  ¬y) convient.
Montrons que les propositions « ¬(¬x¬y) » et « xy » sont équivalentes dans L3 .
On constate sur les tables de vérité que L3 est une extension de L2 (les 
restrictions des tables de vérité de L3 aux valeurs V et F donnent les tables 
de vérité de L2 ). En outre, le connecteur  est commutatif dans L3 car sa table 
de
vérité est symétrique. Pour montrer que les propositions « ¬(¬x  ¬y) » et « x  
y »
sont équivalentes, il suffit donc de montrer qu'elles ont les mêmes valeurs pour
(x, y)  {(V, I); (F, I); (I, I)}. Et en effet, on a bien :
¬(¬V  ¬I) = ¬(F  I) = ¬F = V = V  I
¬(¬F  ¬I) = ¬(V  I) = ¬I = I = F  I
¬(¬I  ¬I) = ¬(I  I) = ¬I = I = I  I

Les propositions « x  y » et P1 = ¬(¬x  ¬y) sont équivalentes dans L3 .

On pouvait aussi se contenter de calculer entièrement la table de vérité de
« ¬(¬x  ¬y) » dans L3 et constater qu'elle est identique à celle de « x  y ».
Cependant, il vaut souvent mieux ­ surtout dans une épreuve de trois heures ­
s'arrêter pour réfléchir quelques minutes que se lancer dans des calculs longs,
fastidieux et sources d'erreurs.

2 En comparant les tables de vérité, on vérifie aisément qu'en logique 
propositionnelle classique, on a : x  y  ¬x  y.
La proposition P2 = ¬x  y convient.
Dans la logique L3 , avec x = y = I, on a :
(¬I  I) = I 6= V = (I  I)
Ces propositions ne sont plus équivalentes dans L3 .

3 Notons P la proposition « x  y » et Q la propostition « (¬x)  y ».
La proposition P3 = « ((x  y)  ((¬x)  y))  y » s'écrit alors « (P  Q)  y ».
Calculons sa table de vérité dans L3 :
x
V
V
V
F
F
F
I
I
I

y
V
F
I
V
F
I
V
F
I

P
V
F
I
V
V
V
V
I
V

Q
V
V
V
V
F
I
V
I
V

(P  Q)
V
F
I
V
F
I
V
I
V

P3
V
V
V
V
V
V
V
I
I

Cette proposition n'est pas une tautologie dans la logique L3 car il existe des
valuations de x et y pour lesquelles elle ne s'évalue pas à « vrai ».
4 Établissons une forme normale disjonctive de la proposition « (x  y)  z »
dans L2 . D'après les questions 1 et 2, on a :
(x  y)  z  ¬(¬x  ¬y)  z
 ¬¬(¬x  ¬y)  z
(x  y)  z  (¬x  ¬y)  z
La proposition P4 = « (¬x  ¬y)  z » convient.
Les propositions P4 et « (x  y)  z » ne sont pas équivalentes dans L3 car on a
par exemple, avec x = F, y = I et z = I :
((¬F  ¬I)  I) = ((V  I)  I) = (I  I) = I
et

((F  I)  I) = (I  I) = V

5 La justification de la validité du raisonnement par contraposition en logique 
classique est l'équivalence des propositions « ¬y  ¬x » et « x  y ». Si l'on 
construit
la table de vérité dans L3 de la proposition « ¬y  ¬x », on constate qu'elle est
identique à celle de l'implication. Le raisonnement par contraposition est donc 
encore
valide dans L3 .
6 Déterminons le nombre de logiques L possibles vérifiant :
1. L est une extension de L2 pour ¬, ,  et  ;
2.  est commutatif ;
3. x  y  P1 ;
4. x  y  P2 ;
5. pour toute valeur de y, la fonction x 7 x  y croît au sens large ;
6. ¬(¬x)  x.
Il n'y a pas unicité des propositions P1 et P2 , solutions des questions 1 et 2
(la proposition P2 = « ¬x  ¬¬y » convenait aussi, par exemple). Cependant,
la démonstration qui suit est indépendante des propositions choisies.