Mines Informatique MP 2005

Thème de l'épreuve Satisfiabilité d'une formule booléenne ; transformations de languages et d'automates
Principaux outils utilisés automates et langages, logique propositionnelle, graphes, complexité d'une fonction

Corrigé

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

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                          

Énoncé obtenu par reconnaissance optique des caractères


Épreuve d'informatique 2005

A 2005 -- INF -- MP

ECOLE NATIONALE DES PONTS ET CHAUSSÉES,
ECOLES 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--ÉTIENNE, DES MINES DE NANCY,
DES TELECOMMUNICATIONS DE BRETAGNE,
ECOLE POLYTECHNIQUE
(Filière TSI.)

CONCOURS D'ADMISSION 2005

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

0 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 problème sur les automates, pages 2 et 3 (60 mn environ) ;
0 un problème d'algorithmique, logique et programmation, pages 3 a 9 (120 mn 
environ).

Page 1 sur 9
Tournez la page S.V.P.

1. Problème sur les automates (60 mn environ)

Notations et terminologie

Un alphabet 2 est un ensemble fini d'éléments appelés lettres. Un mot sur 2 est 
une suite finie, éventuellement
vide, de lettres de 22 On note 2" l'ensemble des mots sur 2. La longueur d'un 
mot est le nombre de lettres qui le

composent. Un langage est une partie de Z*.
Si a appartient à 2 et si n désigne un entier positif, a" est le mot constitué 
de n fois la lettre a ; a0 est le mot vide.

Un automate Zest décrit par une structure <2Î, Q, T, I, F>, où :
0 27 est un alphabet ;
0 Q est un ensemble fini et non vide appelé ensemble des états de 2 ;
0 T ç Q >< 2 x Q est appelé l'ensemble des transitions ; étant donnée une 
transition (p, a, q) EUR T, on dit
qu'elle va de l'état p à l'état q et qu'elle est d'étiquette a ;
0 I g Q est appelé ensemble des états initiaux de fil;
0 F ; Q est appelé ensemble des états finals de flL

Début de l'énoncé du problème

Dans tout ce problème, l'alphabet 27 utilisé n'a que deux lettres notées a et b 
: 2 = {a, b}.
On note OE(Z*) l'ensemble des parties de 27", c'est--à--dire l'ensemble des 
langages sur 27*.

On se propose d'étudier plusieurs « transformations de langage », 
c'est--à--dire plusieurs fonctions de ? (2*) dans
!P (D").
On désigne par L3 le langage des mots sur 23 dont la longueur est multiple de 3.

D 1 -- Indiquer un automate déterministe reconnaissant L3.
D 2 -- Donner une expression rationnelle de L3.

On considère une fonction notée (D de 1P(Z*) dans OE(Z*) définie de la façon 
suivante. Soit L une partie de Z* ; un

mot v appartient à CD(L) si et seulement si v est le plus long préfixe de la 
forme a" d'un mot de L. Autrement dit,
un mot v appartient à (L_--,).

D 4 -- Donner un exemple de langage L sur 2, non rationnel, tel que  un automate 
reconnaissant L. Décrire à partir de _
l'automate % un automate reconnaissant  un automate 
reconnaissant L. Décrire à partir de '

l'automate 54 un automate fl'reconnaissant I' (L). On donnera une description 
précise de l'automate 2'
mais il n'est pas demandé de justifier la réponse. Un automate ÿl' décrit de 
façon trop imprécise sera
considéré comme inexact.

On considère une troisième fonction notée 'P de 1'(2*) dans fP(Z*) définie de 
la façon suivante. Soit L une partie

de 27". Un mot v appartient à 'F(L) si et seulement s'il peut se déduire d'un 
mot u de L contenant au--moins une
fois la lettre b par effacement de la première occurrence dans u de la lettre b 
; cela revient à dire qu'un mot v

appartient à 'P(L) si et seulement s'il existe un entier n 2 0 et un mot x sur 
2 tels que : v = a"x et le mot u = a"bx
est dans L.

D 8 --- Déterminer T(L3).

Cl 9 -- Donner un exemple de langage L sur 2 non rationnel invariant par 'l', 
c'est--à--dire vérifiant
'P(L) = L. On prouvera que le langage L proposé n'est pas rationnel. On 
prouvera la relation 'P(L) = L.

D 10 --- Soit L un langage rationnel et fll= <2, Q, T, ], F> un automate 
reconnaissant L. Décrire, à partir de

l'automate 54, un automate fll' reconnaissant 'P(L). On donnera une description 
précise de l'automate ñ'
mais il n'est pas demandé de justifier la réponse. Un automate fll' décrit de 
façon trop imprécise sera
considéré comme inexact.

FIN DU PROBLÈME SUR LES AU T 0MA T ES

2. Problème d'algorithmique, logique ,et programmation (120 mn environ)

L'objectif de ce problème est l'étude d'un cas particulier, de complexité 
polynomiale, du problème de la
satisfiabilité ; ce sujet ne sera abordé que dans la seconde partie. La 
première partie introduit un algorithme de

graphes qui sera utilisé par la suite.

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.
Dans l'énoncé du problème, 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.

Définitions et notations concernant les graphes

. Un graphe orienté G est composé d'un ensemble fini d'éléments appelés sommets 
et d'une liste de couples
de sommets, chacun de ces couples étant appelé arc ; dans ce problème, en 
notant n le nombre de sommets
de G, l'ensemble des sommets sera toujours {O, 1, ..., n -- l}.

0 Si x et y sont deux sommets d'un graphe G et que (x, y) est un arc de G, on 
dira que y est un fils de x (on dit
aussi que y est un successeur de x).

- Si x et y sont deux sommets d'un graphe G, on appelle chemin de x à y une 
suite de sommets xo, xl, ..., x,,
(p 2 0) avec xo = x, xp = y et, pour tout i vérifiant 1 S i .<. p, (x,--_ ;, 
x,--) est un arc de G ; on dit alors que y est un
descendant de x ; on remarque qu'un sommet est descendant de lui--même.

- Une représentation graphique d'un graphe G consiste à associer à chaque 
sommet de G un cercle contenant --
le numéro du sommet et à tracer des flèches du cercle représentant un sommet 
aux cercles correspondant à

ses fils.

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

On considère le graphe Gex à 7 sommets,

représenté ci--contre, dont l'ensemble des
sommets est donc {O, 1, 2, 3, 4, 5, 6}. °." °

Les arcs de ce graphe sont : (O, 5), (5, O), (4, O),

(4, 1), (5, 1), (1, 0),(1, 2), (2, 6)-

Le sommet 0 a pour fils le sommet 5. @
Le sommet 1 a pour fils les sommets 0 et 2.

Le sommet 2 a pour fils le sommet 6.

Le sommet 3 n'a pas de fils.

Le sommet 4 a pour fils les sommets 0 et 1. ° ° °
Le sommet 5 a pour fils les sommets 0 et l.
Le sommet 6 n'a pas de fils.

Le graphe Gex

Indications pour la programmation

Caml : On définit les types suivants :
type Graphe : {nb_sommets : int; fils : int list vect};;

type Clause : {a : int; b : int};;
type Formule : {nb_var : int; clauses : Clause list};;

Ces trois types sont des types enregistrements (aussi appelés types produits). 
Une valeur de type
enregistrement contient des champs. On peut accéder à un champ d'une valeur de 
type enregistrement

en faisant suivre le nom de cette valeur d'un point puis du nom du champ 
considéré. Par exemple, si G
est de type Graphe, G contient les champs nb_s ommets et fils, auxquels on 
accède par
G . nb_sommets et G . fils. Pour une valeur G de type Graphe, le champ G . 
nb_sommets est égal
au nombre de sommets de G, le champ G . fils est un tableau (aussi appelé 
vecteur) de longueur

G.nb_sommets et, pour un entier 5 vérifiant 0 S s 5 G.nb_sommets -- 1, G.fils. 
(s)
est la liste des fils du sommet s.

Le graphe Gex de l'exemple introductif est défini par :

let Gex = {nb_sonmets = 7: fils = [HS]; [0:2]: [6]; []: [0:1]; [0:l]; [ll]l::
Fin des indications pour Caml

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 : 200;
MAX_CLAUSES = 100:

type Table : RECORD

nb : Integer;
val : array[0 .. MAX -- 1] of Integer;
end;

type Graphe : RECORD

nb_sommets : Integer;
fils : array [O .. MAX -- 1] of Table;
end;

type Clause : RECORD
a, b : Integer;
end;

type Formule = RECORD

nb_var : Integer;
nb_clauses : Integer;
clauses : array[0 .. MAX_CLAUSES -- 1] of Clause;
end;
type Valeurs = array[0 .. MAX -- 1] of Boolean;

On supposera que les graphes traités n'ont jamais plus de MAX sommets.
Les types Table, Graphe, Clause et Formule sont des types pour des 
enregistrements
(RECORD). Un enregistrement contient des champs (quelquefois aussi appelés des 
membres); par

exemple, une variable de type Graphe contient les champs nb_sommets et fils ; 
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 Gex 
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.

Lorsqu'on a affaire à une variable T de type Table, le tableau T . val sert à 
contenir un ensemble

de données entières et on convient que le champ T . nb indique toujours le 
nombre de données de cet
ensemble ; on a toujours T . nb < MAX et les données contenues dans T . val se 
trouvent toujours dans
les cases indicées de 0 à T . nb -- l. Pour une variable G de type Graphe, le 
champ G . nb_sommets

est égal au nombre de sommets de G et, pOur un entier s vérifiant 0 S s 5 G . 
nb_sommets -- 1,
la table G. fils [5] contient les fils du sommet s : leur nombre est dans G. 
fils [5] .nb et leurs

numéros dans le tableau G . fils [5] .val.

Ainsi, le graphe Gex de l'exemple introductif est défini par :
Gex.nb_sommets := 7;
Gex.fils[0].nb := l;
Gex.fils[0].val[0] :
Gex.fils[1].nb := 2;
Gex.fils[l].val[0] :
Gex.fils[l].val[l] .
Gex.fils[2].nb := l;
Gex.fils[2].val[0] :
Gex.fils[3].nb := O;
Gex.fils[4].nb := 2;
Gex.fils[4].val[0] -
Gex.fils[4].val[l] .
Gex.fils[5].nb := 2;
Gex.fils[5].val[0] -
Gex.fils[5].val[l] .
Gex.fils[6].nb := 0;

Fin des indications pour Pascal

Il
U1

Il Il
NO

II || ||
H 0 Ch

II Il
HO

PREMIÈRE PARTIE
Descendants d'un sommet d'un graphe orienté

Il s'agit dans cette partie d'étudier un algorithme, nommé ici 
calcuI_descendants, qui permet de déterminer les
descendants d'un sommet dans un graphe donné. À titre d'exemples, remarquons 
que, dans le graphe Gex de
l'exemple introductif, les descendants du sommet 0 sont les sommets O, 1, 2, 5 
et 6, les descendants du sommet 4
sont tous les sommets sauf le sommet 3, le sommet 2 a pour descendants les 
sommets 2 et 6, les sommets 3 et 6

n'ont pour descendants qu'eux--mêmes.

Considérons un graphe G ayant n sommets et considérons un sommet r (0 5 r 5 n 
-- l) de ce graphe. On suppose
qu'on cherche les descendants du soumet r. Le principe de l'algorithme 
calcul_descendants est de « marquer »

de proche en proche tous les descendants du sommet r, en commençant par le 
sommet r lui--même. Le marquage
des descendants de r utilise un algorithme récursif appelé marquage décrit 
ci--dessous : -

Marquage de G à partir de s
- marquer s ;
0 pour tout fils non marqué t de s, eflectuer « Marquage de G à partir de t ».

Pour effectuer dans G l'algorithme calcul_descendants à partir de r, on part 
d'une situation dans laquelle aucun
sommet n'est marqué puis on effectue « Marquage de G à partir de r ». Après 
l'application de cet algorithme, les

sommets marqués sont les descendants du sommet r.

[I 11 -- Appliquer l'algorithme ci--dessus au graphe Gex à partir du sommet 1 
en détaillant toutes les
opérations de l'algorithme.

Cl 12 ---- Il s'agit de programmer le calcul des descendants d'un sommet r 
donné dans un graphe G donné.
On utilisera pour cela un tableau de variables booléennes nommé marques et 
destiné à contenir les
« marques » des sommets. Plus précisément, après le déroulement de 
l'algorithme, si 3 est un sommet du

graphe, la case d'indice s du tableau marques contiendra la valeur vrai 
(c'est--à--dire true pour le langage
de programmation) si et seulement si le sommet s est descendant de r; sinon, 
cette case contiendra la

valeur faux (c'est--à--dire false pour le langage de programmation).
Pour répondre à la question ci-dessous, on sera amené à écrire aussi, en 
langage de programmation, une
fonction récursive nommée marquage correspondant à l'algorithme décrit plus 
haut.

Caml: Écrire en Caml une fonction calcul_descendants telle que, si G est une 
valeur de type
Graphe et r un entier représentant un sommet du graphe, calcul_descendants G r 
renvoie le
tableau marques contenant les marques des sommets indiquant les descendants de 
r.

Pascal : Écrire en Pascal une fonction calcu1_descendants telle que, si G est 
une variable de type
Graphe et r un entier représentant un sommet du graphe, calcul_descendants (G, 
r) renvoie le
tableau marques, de type Valeurs, contenant les marques des sommets indiquant 
les descendants de r.

E] 13 ---- Prouver l'exactitude de l'algorithme calcul_descendants, 
c'est--à--dire que les sommets marqués
après l'exécution de l'algorithme sont bien exactement les descendants de r.

D 14 --- Indiquer la complexité dans le pire des cas de l'algorithme 
calcul_descendants. Cette complexité
sera exprimée à l'aide du nombre n de sommets et du nombre m d'arcs du graphe 
G. On justifiera

brièvement la réponse.

SECONDE PARTIE
Un problème de satisfiabiüté

On appelle variable booléenne une variable qui ne peut prendre que les valeurs 
vrai ou faux. Si x est une variable
booléenne, on appelle complémenté de x et on note x la négation de x qui vaut 
vrai si x vaut faux et

inversement. On appelle littéral une variable booléenne ou son complémenté. 
Pour un littéral a = 35 , où x est

une variable booléenne, on définit le complémenté & de a comme étant égal à x. 
On a ainsi défini le
complémenté de tout littéral.

On appelle clause une disjonction de littéraux et longueur d 'une clause le 
nombre des littéraux qui composent
cette clause. On appelle formule logique sous forme normale conjonctive une 
conjonction de clauses. Dans ce
problème, on s'intéresse aux formules logiques sous forme normale conjonctive 
pour lesquelles toutes les
clauses sont de longueur 2. On dira qu'une telle formule est sous forme NC2.

Lorsqu'on considérera une formule logique, on supposera que les littéraux d'une 
même clause sont différents et
que toutes les clauses sont différentes.

Une formule logique est dite satisfiable s'il existe une façon d'attribuer des 
valeurs aux variables booléennes
telle que la formule soit évaluée à vrai.

On représente le « ou logique » (disjonction) par le symbole v et le « et 
logique » (conjonction) par le symbole A.

D 15 --- Étant données trois variables booléennes x, y et 2, on considère la 
formule :
F.=(xvy)A(x VZ)A(} VZ)A(ÏVE). « -
F , est--elle satisfiable ? Justifier votre réponse.

13 16 ---- Étant données quatre variables booléennes x, y, z et t, on considère 
la formule :
F2 = (xvy)A(î vz)A(ÿ v E)A(tv E)A(y v ?)A(xv 37).
F 2 est--elle satisfiable '? Justifier votre réponse.

On s'intéresse à l'histoire ci--dessous.
Quatre personnes, nommées X, Y, Z et T, peuvent être chacune soit fiable, soit 
non fiable : une personne fiable dit

toujours la vérité ; une personne non fiable peut dire la vérité ou mentir. 
Chacune de ces personnes sait si les

autres sont fiables ou non.
0 La personne X dit : Z est fiable.
. La personne Y dit : Z est non fiable, T est fiable.

. La personne Z dit : Y est fiable, T est fiable.
. La personne T dit :X est non fiable, Y est fiable.

Par ailleurs, on sait que :
- X est fiable ou Y est fiable ouX et Ysont fiables.

. Z est fiable ou T est fiable ou Z et T sont fiables.
On définit quatre variables booléennes ; la variable booléenne x (resp. y, z, 
t) vaut vrai si X (resp. Y, Z, T) est

fiable et faux si X (resp. Y, Z, T) n'est pas fiable.

D 17 -- Exprimer, à l'aide des variables x, y, z, t et de leurs complémentés, 
sous forme NC2, les
renseignements dont on dispose sur la fiabilité ou la non-fiabilité des quatre 
personnes X, Y, Z et T.

Cl 18 --- Déterminer les personnes fiables et les personnes non fiables. On 
prouvera le résultat.

On va désormais numéroter à partir de 0 les variables booléennes d'une formule. 
Ainsi, si les variables sont x, y
et 2, on associe à x le numéro 0, à y le numéro 1 et à z le numéro 2. Par 
ailleurs, s'il y a p variables booléennes,

on numérote les complémentés des variables à partir de p en respectant l'ordre 
choisi pour numéroter les
variables ; avec l'exemple précédent, comme p vaut 3, on numérote x avec le 
numéro 3, y avec le numéro 4 et

z avec le numéro 5. Pour alléger les explications, on identifie désormais un 
littéral avec son numéro.

D 19 ---- On considère un entier compris entre 0 et 2p ---- 1 identifiant un 
littéral ad'une formule dépendant
de p variables booléennes. Il s'agit d'écrire une fonction, nommée barre, qui 
calcule le numéro du

complémenté de 04 Par exemple, si la formule possède trois variables, barre(0) 
doit valoir 3 et barre(5)
doit valoir 2.

Caml : Écrire en Caml une fonction barre telle que si alpha est le numéro d'un 
littéral d'une formule
dépendant de p variables, barre alpha p donne le numéro du complémenté de ce 
littéral.

Pascal: Écrire en Pascal une fonction barre telle que si alpha est le numéro 
d'un littéral d'une
formule dépendant de p variables, barre (alpha , p) donne le numéro du 
complémenté de ce littéral.

À partir d'une formule logique F sous forme NC2, on construit un graphe orienté 
G(F). Si la formule dépend de
p variables, le graphe possède 2p sommets, les sommets O, 1, 2, ..., 2p -- 1, 
correspondant à ces variables et à

leurs complémentés. À chaque clause av ,5, où aet ,B sont des littéraux, on 
fait correspondre deux ares de G(F) :
unde a versfletunde fl vers a

D 20 -- On considère la formule : © ' © ©
F. = (xvy)A(î VZ)A(} vz)A(î v 2).
Cette formule possède trois variables. On identifie

xà0,yàl,zà2, x à3, yà4, zà5.Dessinerle

graphe G(F,) associé à F . en disposant les
sommets comme ci--contre.

@ @ @

Indications pour Caml
Une formule logique sous forme NC2 sera représentée par une valeur de type 
Formule; ainsi la

formule (x v y) A (; v z) A (; v 2) A (; v ?) sera définie de la façon suivante 
:
{nb_var=3; clauses : [{a=0;b=l}; {a=3;b=2}; {a=4;b=2}; {a=3;b=5}]};;

Le premier champ indique le nombre de variables, le second champ indique la 
liste des clauses.
Fin des indications pour Caml

Indications pour Pascal
Une formule logique sous forme NC2 sera représentée par une variable de type 
Formule; si la

variable utilisée pour coder la formule (x v y) A (3:-- v 2) A (; v 2) A (; v 
?) s'appelle F, la formule

est définie par les instructions suivantes :
F.nb_var := 3;
.nb_clauses := 4;
.clauses[0]. =
.clauses[0].
.clauses[l].
.clauses[l].
.clauses[2].
.clauses[2].
.clauses[3].
.clauses[3].

Le champ nb_var indique le nombre des variables booléennes et le champ 
nb_clauses le nombre

de clauses. Le champ clauses est un tableau de variables de type Clause qui 
décrit les clauses.
On supposera que le nombre de variables booléennes ne dépasse pas la moitié de 
la constante MAX et

que le nombre de clauses ne dépasse pas la constante MAX_CLAUSES.
Fin des indications pour Pascal

.
I

Il"
U"lWNJ>NLül--*O

. \.

l \.

!

mmmmmmmmm
U'fl'U'OEÜWU'W
|]

I

D 21 -- Il s'agit d'écrire une fonction nommée transformer qui reçoit en 
paramètre une formule logique F
sous forme NC2 et qui construit G(F).

Caml : Écrire en Caml une fonction transformer telle que, si F est une valeur 
de type Formule, alors
trans former F renvoie une valeur de type Graphe correspondant au graphe G(F) 
décrit plus haut.

Pascal : Écrire en Pascal une fonction transformer telle que, si F est une 
variable de type Formule, alors
trans former (F) renvoie une valeur de type Graphe correspondant au graphe G(F) 
décrit plus haut.

CI 22 -- Indiquer la complexité de la fonction transformer définie 
précédemment. On exprimera cette
complexité en fonction du nombre p de variables et du nombre q de clauses de la 
formule F à laquelle est

appliquée la fonction transformer.

D 23 -- Par la suite, il sera utile de pouvoir retirer d'une formule logique F 
sous forme NC2 toutes les

clauses contenant un littéral donné a ou son complémenté. Dans la formule F ' 
ainsi obtenue, une ou
plusieurs variables ne figureront plus. Néanmoins, on considère que toutes les 
variables de F sont aussi
variables de F ', n'imposant donc pas que toutes les variables d'une formule 
figurent effectivement. Par

exemple, si de F1 = (x v y) A (; v z) A (; v z) A (; v ? ), formule contenant 
trois variables, on décide
de retirer le littéral ; ou son complémenté, on obtient F '1 = (} v z) et on 
considère encore que F ',

dépend de trois variables, et les entiers correspondant aux variables restantes 
sont inchangés (à ;
correspond toujours le numéro 4 et à z le numéro 2).

Caml: Écrire en Caml une fonction retirer qui, si F est une valeur de type 
Formule ayant

F . nb_var variables et si alpha est un entier compris entre 0 et 2> fl ».

CI 26 -- Étant donnée une formule logique F sous forme NC2, montrer que, s'il 
existe un chemin de aà ,6
dans le graphe G(F), alors il existe aussi un chemin de ? à 5 dans G(F).

D 27 -- Étant donnée une formule logique F sous forme NC2, que peut--on dire de 
la formule F s'il existe
dans le graphe G(F) àla fois un chemin de a à a et un chemin de 5 à a?

D 28 -- Étant donnés une formule logique F sous forme NC2 et deux littéraux a 
et fi de F, montrer que
s'il n'existe pas de chemin de a à 67 dans le graphe G(F), alors ,6 et _,5_ ne 
sont pas tous les deux

descendants de adans G(F).

Cl 29 -- Soit F une formule logique sous forme NC2. On considère un littéral a 
tel qu'il n'existe pas de
chemin de a à ?! dans le graphe G(F). On note F ' la formule obtenue à partir 
de F en retirant toutes les
clauses contenant un littéral descendant de adam G(F) ou bien le complémenté 
d'un de ces descendants;

on retire donc en particulier les clauses contenant aou a. Montrer que F est 
satisfiable si et seulement si

F' l'est. En supposant que F ' est satisfiable, indiquer, à l'aide des valeurs 
des variables figurant dans F '
qui donnent la valeur vrai à F ', des valeurs des variables figurant dans F qui 
donnent la valeur vrai à F.

D 30 -- Soit F une formule logique sous forme NC2. Montrer que, si pour tout 
littéral a de F, il n'existe
pas dans le graphe G(F) àla fois un chemin de a à Eet un chemin de "& à a, 
alors F est satisfiable.

D 31 -- Soit F une formule logique sous forme NC2. Décrire un algorithme 
s'appuyant sur les questions
précédentes permettant de savoir si F est ou non satisfiable et qui, dans le 
cas où F est satisfiable, calcule
des valeurs des variables pour lesquelles F vaut vrai. On utilisera une 
fonction récursive et on indiquera
pourquoi le calcul se termine. On ne justifiera pas ici cet algorithme.

D 32 --- Il s'agit de programmer l'algorithme, nommé satisflable, décrit dans 
la question D 31.

Caml : Écrire en Caml une fonction satisfiable telle que si :
° F est une valeur de type Formule,
0 solution est un tableau pour 2 x F . nb_var variables booléennes,

alors satisfiable F solution
. renvoie une valeur booléenne indiquant si la formule F décrite par F est ou 
non satisfiable,

. si F est satisfiable, remplit le tableau solution pour qu'il contienne, après 
exécution de la
fonction, les valeurs des littéraux pour des valeurs des variables donnant la 
valeur vrai à F.

Pascal : Écrire en Pascal une fonction satisf iable telle que si :
0 F est une valeur de type Formule,

0 solution est un tableau de type Valeurs,
alors satisfiable (F, solution)
. renvoie une valeur booléenne indiquant si la formule F décrite par F est ou 
non satisfiable,

. si F est satisfiable, remplit le tableau solution pour qu'il contienne, après 
exécution de la
fonction, les valeurs des littéraux pour des valeurs des variables donnant la 
valeur vrai à F.

D 33 -- Indiquer la complexité dans le pire des cas de l'algorithme safisfiable 
définie précédemment. On
exprimera cette complexité en fonction du nombre p de variables et du nombre q 
de clauses de la formule .

F à laquelle est appliquée la fonction safisflabIe.

FIN DU PROBLÈME D'ALGOIHTHMIQUE, LOGIQUE ET PROGRAMMA TION

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



Mines Informatique MP 2005 -- Corrigé
Ce corrigé est proposé par Boris Yakobowski (ENS Cachan) ; il a été relu par
Samuel Mimram (ENS Lyon) et Vincent Puyhaubert (Professeur en CPGE).

Le sujet est constitué de deux parties totalement indépendantes.
La première partie traite de langages et d'automates. On étudie la 
transformation
de langages (rationnels ou non) par trois fonctions. Parallèlement, étant donné 
un
automate reconnaissant un langage, on en déduit un automate reconnaissant 
l'image
de ce langage par une des fonctions de transformation. Cette étude permet, entre
autre, de montrer la non rationalité d'un langage sans utiliser directement le 
lemme
de l'étoile.
Une importante fraction du programme consacré aux automates est abordée :
expressions et langages rationnels, automates non déterministes, lemme de 
l'étoile.
Cette partie est constituée de deux questions d'introduction et de trois 
sousparties. Bien que ces dernières paraissent indépendantes, des résultats de 
la première
sous-partie peuvent être utilisés dans la troisième. Les questions les plus 
difficiles sont
les questions 5 et 9.
La seconde partie s'intéresse au problème de la satisfiabilité d'une formule
booléenne mise sous la forme d'une conjonction de disjonctions à 2 littéraux
(appelée forme NC2). Ce problème, bien connu, peut être résolu en temps 
polynomial ; le sujet permet la conception d'un algorithme réalisant une telle 
tâche.
Plus précisément, l'algorithme décide si une formule est satisfiable et, dans 
ce cas,
il exhibe une solution.
Le sujet commence par construire un algorithme sur des graphes généraux, avant
de s'intéresser à la partie logique proprement dite. Les connaissances 
demandées sont
les résultats du cours sur la logique booléenne, ainsi que les notions 
d'algorithmique
standard : algorithmes récursifs, complexité, preuve de la correction d'une 
fonction.
Quelques connaissances sur les graphes sont également utiles.
Cette partie est longue, mais globalement facile si l'on suit scrupuleusement
les indications de l'énoncé. Les questions 15 à 18 proposent des exemples 
simples,
tandis que les questions 19 à 24 introduisent les notations et les fonctions 
auxiliaires.
Ensuite, les questions 25 à 28 préparent le fonctionnement de l'algorithme, qui 
est
explicité dans les questions 29 à 33.

Indications
I.

Problème sur les automates

3 Procéder par double inclusion ; pour le sens non trivial, penser à utiliser 
la division
euclidienne.
4 Se rappeler qu'un automate ne sait pas compter.
5 L'automate modifié doit s'arrêter dès qu'il rencontre un b menant à un état 
final,
et accepter les suites de a non suivies par un b. En particulier, toutes les 
transitions
étiquetées par un b deviennent indésirables.
6 Caractériser (L3 ) en fonction de la longueur des mots qu'il contient et des 
lettres
qui doivent nécessairement être présentes dans ces mots.
7 Encoder le fait que la lettre b ait déjà été ajoutée ou non au mot avec de 
nouveaux
états.
8 À nouveau, caractériser la longueur des mots de (L3 ) puis examiner 
l'inclusion
réciproque.
9 Trouver un langage non rationnel sur l'alphabet  = {a}, puis ajouter des b
à la fin des mots qu'il contient. Pour prouver la non-rationalité, on essaiera 
de
réutiliser des résultats obtenus sur .
10 Procéder comme à la question 7, en se rappelant si b a été supprimé ou non.
Attention, cette fois la suppression ne peut avoir lieu qu'au début.
II.

Problème d'algorithmique, logique et programmation

12 Si vous ne connaissez pas de fonction itérant sur les éléments d'une liste, 
vous
pouvez en écrire une récursive.
13 Montrer successivement que tous les sommets marqués sont des descendants
(en exhibant un chemin entre un sommet marqué et r), puis que tous les 
descendants sont marqués (en trouvant un sommet après lequel un descendant est
marqué).
14 Étudier l'ensemble des arcs accessibles depuis r qui sont visités.
15 Procéder par équivalences logiques successives, ou bien en utilisant une 
table de
vérité.
17 Utiliser la définition de l'implication logique par la disjonction et la 
négation.
19 La fonction barre envoie [0, p - 1] sur [p, 2p - 1], et vice-versa.
21 Itérer une fonction qui ajoute les arcs correspondant à une unique clause.
22 Détailler les opérations effectuées pour chaque clause.
23 Caractériser exactement quand une clause doit être retirée, et itérer cette 
fonction
sur la liste des clauses.
24 Trouver la complexité des opérations effectuées sur chaque clause.
25 Caractériser ce que représente un arc entre  et , et utiliser la 
transitivité de
l'implication.
26 Se rappeler que transformer ajoute 2 arcs pour chaque clause.
27 Utiliser la question 25 pour voir ce qu'impliquent ces deux chemins.

28 Raisonner par contraposition, en construisant un chemin de  à .
29 On peut déduire trivialement une assignation pour F' à partir d'une 
assignation
pour F. Dans l'autre sens il faut assigner tous les littéraux qui ont été 
retirés de F.
Pour tous sauf un, il n'y a qu'une valeur possible.
30 Utiliser une récurrence sur le nombre de littéraux présents dans la formule, 
ainsi
que la question précédente.
31 Distinguer les cas suivants :
· la formule ne comprend plus de littéraux ;
· la formule ne comprend que des littéraux impliquant leur complémentaire ;
· la formule comprend un littéral n'impliquant par son complémentaire.
32 Écrire une fonction auxiliaire retirant récursivement tous les descendants 
d'un littéral d'une formule, et l'utiliser pour implémenter l'algorithme défini 
à la question
précédente.
33 Trouver le nombre maximal d'appels récursifs et la complexité du corps de la
fonction entre deux appels.

I. Problème sur les automates
Soit u un mot de longueur n appartenant à un langage L ; on note u[i] sa ie
lettre (pour 1 6 i 6 n). On s'autorise également l'écriture a pour le langage 
{a} .
La longueur du mot u est notée |u|.
L'énoncé définissant l'étoile sur un ensemble de lettres, la notation a est a
priori impropre. On peut au choix écrire systématiquement {a} ou prévenir
le correcteur de cette petite liberté de notation. Par ailleurs, comme on le
rappellera plus bas, l'étoile s'étend également aux langages.
1 L'automate comprend 3 états, chacun encodant le résultat de la congruence de
la longueur du mot modulo 3. L'état correspondant à un reste nul est acceptant 
(en
plus d'être l'état initial).
a
a

a
0

1

2
b

b
b

Il n'y a pas de convention universellement admise sur les états initiaux et
acceptants : les premiers sont parfois notés par un cercle épais ou par une
flèche entrante, tandis que les états acceptants le sont par un double cercle
ou une flèche sortante.
2 Soit L31 le langage des mots de longueur exactement 3. Une expression 
régulière
de ce langage est
L31 = (a|b)(a|b)(a|b)
L'alternative entre deux langages se note traditionnellement en utilisant les
symboles | ou +. Une autre notation pour L31 est donc
L31 = (a + b)(a + b)(a + b)
Étant donné un entier n, le langage L3k+1 des mots de longueur 3(k + 1) se 
déduit
de L3k grâce à l'expression
L3k+1 = L3k L31
Or L30 , le langage des mots de longueur 0, est exactement {}. Par définition de
l'étoile de Kleene, on obtient donc
L3 = L31  = ((a|b)(a|b)(a|b))
Rappelons que, étant donné un langage X, X0 = {}, Xn+1 = Xn X = XXn ,

[
et l'étoile de Kleene, ou fermeture, de ce langage est X =
Xn .
n=0