L'énoncé de cette épreuve, y compris cette page de garde, comporte 8 pages.
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 :

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 propositionnelle tri-valuée

On désire étendre la logique propositionnelle bivaluée classique (notée par la suite

) de sorte à prendre en compte, en plus de

(vrai) et

(faux), une troisième valeur de vérité, notée

(pour indéterminé).

La logique de Lukasiewicz, notée

, est une telle logique tri-valuée dans laquelle le connecteur de négation (

), le connecteur de conjonction (

), le connecteur de disjonction (

) 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.

- Indiquer une proposition

équivalente dans

à la proposition «

» et n'utilisant pas d'autres connecteurs que

. Les propositions

et «

» sont-elles équivalentes dans

- Indiquer une proposition

équivalente dans

à la proposition «

» et n'utilisant pas d'autres connecteurs que

et V . Les propositions

et «

» sont-elles équivalentes dans

- Établir (en détaillant son obtention) la table de vérité dans

de la proposition

Cette proposition est-elle une tautologie dans

(la définition d'une tautologie dans la logique

reste la même que dans la logique

) ?

- On appelle littéral une variable propositionnelle ou sa négation. Dans

, 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

sous forme normale disjonctive équivalente dans

à la proposition «

». Les propositions

et «

» sont-elles équivalentes dans

- Peut-on faire un raisonnement par contraposition dans

(on justifiera la réponse)?

6- On définit un ordre sur les valeurs

par:

. On considère une logique L tri-valuée pour laquelle simultanément :

est une extension de pour les quatre connecteurs usuels ( ); autrement dit, les restrictions aux valeurs et des tables de vérité de donnent les tables de vérité de ;
le connecteur est commutatif ;
la proposition « » est équivalente à ;
la proposition « » est équivalente à ;
pour toute valeur de , la fonction croît au sens large avec ;
les propositions « » et « » 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 et distincts et est notée (ce qui est égal à ;
un graphe est composé d'un ensemble d'éléments appelés sommets et d'une liste de paires de sommets ; les éléments de sont appelés arêtes et ne sont pas nécessairement tous distincts ;
le cardinal de est noté et on a toujours : ; un graphe est donc entièrement décrit par le couple ( ) ;
deux sommets et de sont dits voisins si est une arête de ;
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 .

Une représentation graphique d'un graphe

consiste à associer à chaque sommet de

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

Exemple introductif : un graphe (nommé Gex1) et une représentation de Gex1

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

Gex1

.
Il y a trois arêtes entre le sommet 0 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 0,1 et 4 .
Le sommet 4 a pour voisins les sommets 0 et 3 .

Le graphe Gex1

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 Gex1 de l'exemple introductif est défini par:
let Gex1 = {n = 5; A = [{a = 0; b = 4}; {a = 4; b = 3}; {a = 0; b = 3};

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

du graphe Gex1 par Gex1.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 :

const
    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_SOMMETS - 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

; 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 Gex1 ci-dessous. Les variables de type enregis trement 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 Gex1 de l'exemple introductif est défini par:

Gex1.n := 5;
Gex1.nb_aretes := 6;
Gex1.A[0].a := 0; Gex1.A[0].b := 4;
Gex1.A[1].a := 4; Gex1.A[1].b := 3;
Gex1.A[2].a := 0; Gex1.A[2].b := 3;
Gex1.A[3].a := 1; Gex1.A[3].b := 3;
Gex1.A[4].a := 0; Gex1.A[4].b := 3;
Gex1.A[5].a := 3; Gex1.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_SOMMETS 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

de type Graphe correspondant à un graphe

, G.n contiendra le nombre

de sommets de

, G.nb_aretes contiendra le nombre d'arêtes de

et le tableau G.A contiendra les arêtes de

entre les indices 0 et G.nb_aretes - 1.

I - Détermination des voisins des sommets

- 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 à 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

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
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.
- 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 .
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 .
- 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 : Écrire en Caml une fonction voisins telle que voisins renvoie la liste triée par ordre croissant des voisins du sommet dans le graphe . On utilisera pour cela la fonction insere.
Pascal : Écrire en Pascal une fonction voisins telle que voisins( ) renvoie un résultat de type Table dont:
le champ cases contient les voisins du sommet dans le graphe 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

toute application

de l'ensemble

des sommets de

dans l'ensemble des entiers naturels non nuls. Pour tout sommet

, l'entier

s'appelle couleur de

pour la coloration

Une coloration

est une bonne coloration de

si pour toute arête

, on a

; 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

; lorsqu'on considère un sommet

, 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

- Que donne cet algorithme pour le graphe Gex2 ci-contre ? Y a-t-il une autre bonne coloration de

utilisant moins de couleurs ?

Le graphe Gex2

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

cases à valeurs entières d'un tableau dont les indices

correspondront aux sommets de

; la case d'indice

contiendra après le déroulement de l'algorithme la couleur du sommet s.

Caml : Écrire en Caml une fonction coloration telle que coloration G renvoie le tableau des couleurs attribuées aux sommets du graphe

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;
Écrire en Pascal une fonction coloration telle que coloration(G) renvoie le tableau des couleurs attribuées aux sommets du graphe

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

Soit

un graphe et

un entier strictement positif. On appelle bonne

-coloration de

une bonne coloration n'utilisant que des couleurs appartenant àl'ensemble

. On introduit les notations suivantes :

est l'ensemble des bonnes -colorations de ;
est le cardinal de ;
tel que .
- Montrer l'existence d'un unique entier tel que:

On dit que

est le nombre chromatique du graphe

: c'est le nombre minimum de couleurs permettant de colorier les sommets de

de sorte que deux sommets voisins n'aient pas la même couleur.

- Soit

un graphe n'ayant aucune arête. Déterminer

en fonction de

et, pour tout

, déterminer

en fonction de

- Soit

un graphe tel que toute paire de sommets soit une arête. Déterminer

en fonction de

et, pour tout

, déterminer

en fonction de

- On considère le graphe Gex1 de l'exemple introductif. Déterminer

et, pour tout

, déterminer

en fonction de

IV - Les applications et

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 Gex1.

- Étant donnés un graphe

et un sommet de

non isolé

, on note prem_voisin

le plus petit voisin de

dans

, c'est-àdire le voisin de

qui a le plus petit numéro. Par exemple, prem_voisin(Gex1, 0 ) est le sommet 3.

Caml: Écrire en Caml une fonction prem_voisin telle que prem_voisin

s renvoie prem_voisin

. Cette fonction ne prévoira pas le cas où

est un sommet isolé de

.
Pascal : Écrire en Pascal une fonction prem_voisin telle que prem_voisin(G, s) renvoie prem_voisin

. Cette fonction ne prévoira pas le cas où s est un sommet isolé de

- On considère un graphe

possédant au moins une arête. On note prem_ni

le plus petit sommet non isolé du graphe

, c'est-àdire le sommet non isolé qui a le plus petit numéro. Par exemple, prem_ni(Gex1) est le sommet 0 .
Caml : Écrire une fonction prem_ni telle que prem_ni G renvoie prem_ni

. Cette fonction ne prévoira pas le cas où

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

ne possède aucune arête.

- Rappelons d'abord que dans la liste

des arêtes d'un graphe

, il est possible qu'une même arête soit répétée.

Étant donné un graphe

possédant au moins une arête, on pose :

Par exemple, pour le graphe Gex1,

.
On note

le graphe obtenu à partir de

en supprimant toutes les arêtes entre

Par exemple, le graphe

Gex1

, représenté ci-contre, est caractérisé par:

Le graphe H(Gex1)

Caml : Écrire en Caml une fonction H telle que H G renvoie

(qui sera de type Graphe). Cette fonction ne prévoira pas le cas où

ne possède aucune arête.

Pascal : Écrire en Pascal une fonction H telle que

renvoie

(qui sera de type Graphe). Cette fonction ne prévoira pas le cas où

ne possède aucune arête.

- On considère un graphe

possédant au moins une arête. On définit

comme dans la question précédente ; on peut remarquer la relation :

. On construit alors un graphe noté

de la façon décrite cidessous.

On construit ;
dans , on superpose et ; plus précisément,
on considère successivement chaque arête de la liste des arêtes de ; pour chacune d'entre elles, on renumérote ses extrémités :
une extrémité de valeur strictement inférieure às est inchangée ;
une extrémité de valeur prend la valeur ;
une extrémité de valeur strictement supérieure à est décrémentée de 1 ;
on diminue de 1 le nombre de sommets du graphe.

Par exemple,

, représenté cicontre, est décrit par:

Le graphe

Caml : Écrire en Caml une fonction K telle que K G renvoie

(le résultat sera de type Graphe). Cette fonction ne prévoira pas le cas où

ne possède aucune arête.

Pascal : Écrire en Pascal une fonction K telle que

renvoie

(le résultat sera de type Graphe). Cette fonction ne prévoira pas le cas où

ne possède aucune arête.

V- Fonction et polynôme chromatique

Soit

un graphe possédant au moins une arête et soit

un entier non nul.

- Montrer l'inclusion :

- Comparer les cardinaux de

et de

- Montrer l'égalité :

- En utilisant la formule obtenue dans la question

, décrire en termes simples un algorithme récursif de calcul de

; ici, on ne demande pas d'utiliser un langage de programmation.

- Prouver que l'algorithme de la question

se termine.

- Le graphe

étant fixé, montrer que la fonction qui associe à

la quantité

est la restriction à

d'un polynôme en

de degré

. On appelle polynôme chromatique de

et on note

ce polynôme.

VI - Calcul du polynôme et de

On ne considérera dans cette partie que des polynômes à une variable et à coefficients entiers.
Caml : Un polynôme de degré

est représenté par un tableau à

cases, la case d'indice

contenant le coefficient du monôme de degré

. 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

degre, coeff[i] contiendra le coefficient du monôme de degré

- 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

sont deux variables représentant des polynômes

, difference

renvoie le polynôme

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

sont deux variables de type Polynome représentant des polynômes

, difference

renvoie le polynôme

, qui sera de type Polynome.

- Cette question consiste à calculer le polynôme chromatique

.
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.

- Dans cette question, il s'agit de calculer la valeur

d'un polynôme

en une valeur entière

. 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

renvoie

.
Pascal : Écrire en Pascal une fonction eval telle que eval (

), où

est de type Polynome et

de type integer, renvoie

- Écrire dans le langage de programmation choisi une fonction qui calcule le nombre chromatique

d'un graphe