Mines Informatique MP 2002

Thème de l'épreuve Formules de Horn, problème du sac-à-dos et langages conjugués
Principaux outils utilisés algorithmes et complexité, récursion, logique, automates et langages

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


J . 2062

A 2002 -- INF -- MP

É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ÉCOMMUNÏCATIONS DE BRETAGNE
ÉCOLE POLYTECHNIQUE
(Filière T.S.I.)

CONCOURS D'ADMISSION 2002

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

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 les demande pas explicitement.

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

COMPOSITION DE L'ÉPREUVE

L'épreuve comprend trois parties indépendantes :

0 un exercice de logique des propositions, n° 1 page 2, à résoudre en 30 mn 
environ ;
0 un problème d'algofithmique, n° 2 page 3, à résoudre en 120 mn environ ;
- un exercice sur les automates, n° 3 page 7, à résoudre en 30 mn environ.

page I/8
Tournez la page S.V.P.

Épreuve d'Informatique

1 Exercice de logique des propositions ---- 30 mn environ

Définitions et notations

On considère un ensemble fini de n variables propositionnelles V : {p1, . . . 
,pn}, et l'ensemble 3"v des
formules construites à partir des variables propositionnelles de V, des 
connecteurs usuels de conjonction

(noté A) et de disjonction (noté V), et de la négation (--.), On considère que 
la formule sans aucune variable

propositionnelle (formule vide), notée T, est un élément de S'y.
Toutes les formules considérées dans cet exercice sont des formules de 3'v.
Pour toute formule F, VF désigne l'ensemble des variables propositionnelles qui 
apparaissent dans F.
On appelle littéral une variable propositionnelle ou bien la négation d'une 
variable propositionnelle. Le

littéral est dit positif dans le premier cas, et négatif dans le second cas.
On appelle clause toute formule de la forme 11 V . . . V lq, où q ; 1 et 11, . 
. . ,lq sont des littéraux deux

à deux distincts.
On dit qu'une formule est sous forme normale conjonctive si elle est sous la 
forme C1 /\ . . . A C..., où

m > 0 et C1, . . . ,C... sont des clauses (pour m = 0, on obtient T).
Une formule de Ham est une formule sous forme normale conjonctive telle que 
chacune de ses clauses

comporte au plus un littéral positif.
Enfin, rappelons qu'une formule est satisfiable s'il existe une valuation à 
valeurs dans {vrai, faux}

de ses variables propositionnelles qui rende la formule vraie. La formule T est 
considérée comme étant
satisfiable.

Énoncé de l'exercice

1 -- Dans les exemples suivants, préciser si les formules sont satisfiables ou 
non. Quand cela est possible,
donner un exemple de valuation des variables propositionnelles qui rende la 
formule vraie.
i) ("Pi VP2) A(P1 V "1292 V "P3)
ii) (P2) /\ ("'P1 V "'P3) /\ ("'P2) A (P1 V "'P3 V "'P4)
iii) (P2) A ("1171 V "';02) A (Pi V "*P2) /\ (P1 V '"P2 V "*P3)

2 -- Soit H une formule sous forme normale conjonctive telle que chacune de ses 
clauses contienne au
moins un littéral négatif. Montrer que H est satisfiable en exhibant une 
valuation de V.

3 -- Soit H une formule de Horn telle qu'une de ses clauses soit restreinte à 
un littéral positif Pk (où le est
dans {l, . . . , n}), et qu'aucune autre de ses clauses ne soit restreinte à 
fipk. Montrer que l'on peut
construire à partir de H une formule de Horn H' telle que:

-- VH' Ç VH\{Pk},
-- H est satisfiable si et seulement si H ' est satisfiable.

4 -- Déduire des deux questions précédentes un algorithme permettant de 
déterminer si une formule de
Horn H est satisfiable ; la complexité dans le pire des cas de cet algorithme 
doit être majorée par un
polynôme en n et m (où n et m désignent respectivement le nombre de variables 
propositionnelles et
le nombre de clauses de H), propriété que l'on justifiera. Cet algorithme sera 
explicité sans utiliser un

langage de programmation.
5 -- Appliquer l'algorithme de la question 4 à l'exemple iii) de la question ].

FIN DE L'EXERCICE DE LOGIQUE DES PROPOSITIONS

page 2/8

Épreuve commune 2002

2 Problème d'algorithmique -- 120 mn environ

Préüminaire. Il faudra écrire des programmes à l'aide d'un langage de 
programmation qui pourra être
soit Pascal, soit Caml, tout autre langage étant exclu. Indiquer le langage de 
programmation choisi.

Attention! Il est interdit de modifier ce choix au cours de l'épreuve.

Le problème du sac à dos

On considère le problème suivant : Madame X doit partir en voyage ; elle 
emporte un sac à dos qui peut
supporter au maximum un poids Q, poids qui est un entier strictement positif. 
Par ailleurs, elle dispose de
n objets numérotés par 0, l, , n -- 1. Pour tout z' appartenant à O, 1, , n -- 
l, l'objet de numéro
z' possède deux caractéristiques : son utilité notée u,-- et son poids noté 
p,-- qui sont des entiers strictement
positifs. Madame X désire emporter certains de ces objets dans son sac à dos; 
le poids total des objets
emportés ne doit pas dépasser Q ; elle cherche à maximiser la somme des 
utilités des objets qu'elle emporte

parmi les contenus possibles ne dépassant pas au total le poids Q.

Attention: pour la programmation que vous aurez à faire ultérieurement:

-- le nombre n est mémorisé dans une variable entière nommée aussi n;

-- les quantités u,-- et p,-- sont mémorisées dans des tableaux d'entiers 
nommés respectivement u et p et
indicés de 0 à n -- 1 ;

-- la quantité Q est mémorisée dans une variable entière nommée aussi Q.

Quand on écrira une fonction (ou une procédure) dans le langage de 
programmation choisi, les tableaux u
et p ainsi que les variables Q et n seront supposés déjà définis comme 
variables globales et initialisés avec

les données du problème. Après l'initialisation, à l'indice i du tableau u 
(resp. p) se trouve la valeur u,--
(fEURSP- Pi)-

Notaüon. Si a: est un nombre réel, Læj désigne la partie entière par défaut de 
a: (c'est--à--dire le plus grand
entier inférieur ou égal à a:) tandis que [a:] désigne sa partie entière par 
excès (c'est--à--dire le plus petit
entier supérieur ou égal à a:).

PREMIÈRE PARTIE
Sac à dos fractionnaîre

Dans cette partie, les objets sont fractionnables. On note a:,-- la quantité de 
l'objet de numéro z' emportée par
Madame X. Le problème s'écrit:

n---1
Maximiser z = z u,--æ,--
i=0
avec les contraintes :
n--1
ZPi--"OE < Q
i=0
et pouri EUR {0,1, . .. ,n ---1}, an, EUR [0,1]

page 3/8
Tournez la page S.V.P.

Épreuve d'Informatique

l -- On suppose que, pour tout i appartenant à {l, . . . , n -- 1} :
Ui--l Ui

Pi-1 Pi
On définit un entier z'* compris entre 0 et n par:

n--1
si Zp,- < Q, alors z'* :
i=0
sip0, > Q, alors lz'*- -- 0
i ----1

sipo ,

i=0 i=0

a -- Montrer qu'une solution maximale pour le problème est donnée par:

pourivérifiant0 --3 sont
Pi--1 Pi

vérifiées, écrire, dans le langage de programmation choisi, une fonction qui 
calcule z' *.

2 -- Remarque: le reste du problème ne dépend pas de cette question 2.

a -- On cherche à déterminer la solution du problème du sac à dos fractionnaire 
sans faire l'hypothèse

que, pour tout z' appartenant à {l, . .. , n -- l} :
U'_1 'U.'
3 > _1 .
Pi--1 Pi

En revanche, on suppose que l'on a Z?____1_0 p,--> , Q.

page 4/8

Épreuve commune 2002

On cherche à déterminer i* appartenant à {0,1, . .. ,n -- 1} et une partition 
de l'ensemble
{0,1, . . . ,n -- l} \ {i*} en deux sous--ensembles I ' et I " de façon à avoir 
simultanément:
pourtoutz EUR I', --3 2 '
Pi Pi*
pour tout] EUR I", ' ; --l
Pi* PJ"
21%" < Q
ieI'
Fr + 21%" 2 Q
ieI'

On dit qu'un algorithme est linéaire en une variable 11 liée aux données 
traitées s'il existe une
fonction linéaire de v majorant le nombre d'opérations élémentaires (opérations 
arithmétiques,
comparaisons...) effectuées par cet algorithme pour traiter ces données.

On admet qu'on dispose d'un algorithme A qui, étant donné un ensemble E de m 
éléments ayant
chacun une valeur, partitionne cet ensemble en deux sous--ensembles E' et E" de 
cardinaux res-
pectifs L%_| et [%'-l de telle sorte que toutes les valeurs des éléments de E' 
soient supérieures ou
égales à toutes les valeurs des éléments de E" ; on suppose de plus que A est 
linéaire en m.
Expliciter, sans utiliser de langage de programmation, un algorithme récursif 
(qu'il ne sera pas
nécessaire de prouver) utilisant l'algorithme A qui détermine z'*, I ' et I " ; 
cet algorithme devra
être linéaire en n.

b -- Prouver la linéarité en n de l'algorithme proposé ci--dessus. Pour 
simplifier cette preuve, on pourra
se restreindre aux valeurs de n qui sont des puissances de 2; on admettra alors 
que l'algorithme

est aussi linéaire lorsque n est quelconque.

c -- Déduire des questions 1 - a, 2 -- a et 2 - b qu'on peut résoudre le 
problème du sac à dos fractionnaire

portant sur n objets en un temps majoré par une fonction linéaire de n même si 
les objets ne sont
u- . . , .

pas au préalable classés pour que les rapports ---'-- (2 EUR {0,1, . . . ,n 
---- 1}) sownt decrmssants.
Pi

SECONDE PARTIE
Sac à dos en 0--1

Dans cette partie, les objets ne sont plus fractionnables : chaque objet est 
pris ou laissé. Le problème s'écrit :

n--1
Maximiser z = 2 u,-æ,--

i=0
avec les contraintes :

n----l
z Pi$i < Q

i=0
et pourz' EUR {0,1, . .. ,n -- 1}, a:,-- E {0,1}

On dit que EE : (î5, :::--1, . . . , a:n__1) EUR {0,1}" est réalisable si on a 
Z?_Çâ p,--îä,'- { Q. On appelle valeur
d'une telle solution la valeur correspondante de la fonction 2 ou, autrement 
dit, la quantité ZÎQJ u,--àÎ,--. Le

page 5/8
Tournez la page S.V.P.

Épreuve d'Informatique

problème consiste donc à déterminer la meilleure solution réalisable, 
c'est--à--dire celle qui a la plus grande
valeur.

3 -- Montrer que le maximum du problème du sac à dos en 0--1 est inférieur ou 
égal au maximum du

4..

problème de sac à dos fractionnaire ayant les mêmes données numériques.

Méthode par séparation
Écrire, dans le langage de programmation choisi, un algorithme fondé sur la 
stratégie diviser pour

régner qui exhibe tour à tour toutes les solutions réalisables et mémorise la 
meilleure.

Cet algorithme utilisera le principe esquissé ci-après : la meilleure solution 
réalisable peut être cherchée
successivement parmi les solutions réalisables avec 500 = 1 (s'il en existe) 
puis parmi celles avec
a:0 : 0. La meilleure solution réalisable pour laquelle m0 = 1 peut être 
cherchée successivement parmi
les solutions réalisables avec :r1 : 1 (s'il en existe) puis parmi celles avec 
oe1 : 0, etc.

Avant d'écrire l'algorithme en langage de programmation :
- on donnera la signification des différentes variables utilisées (autres que 
celles introduites par
l'énoncé) ;
-- on précisera le rôle des fonctions ou procédures utilisées.

Indiquer la complexité dans le pire des cas de la méthode par séparation.

Méthode par séparation et évaluation
Remarque : cette question peut être traitée sans avoir résolu les deux 
questions précédentes.

La méthode par séparation et évaluation améliore la méthode par séparation en 
utilisant la résolution

du problème de sac à dos fractionnaire ; elle se place dans l'hypothèse où, 
pour tout z' appartenant à
u -_ u--

{1,... ,n--1},onaz ' 1) --'-

_ pi--l Pi

On ne fera qu'esqursser cette méthode à travers un exemple.

On associe au problème de sac à dos en 0--1 un arbre binaire décrit ci-dessous.

La racine de l'arbre représente l'ensemble de toutes les solutions réalisables.

À un sommet (noeud ou feuille) quelconque de l'arbre correspondent un indice 
z'0 (0 < z'0 < n) et un
io-uplet (îîÿ,îzîî, . . . , cc,--0-1) EUR {0,1}io ; ce sommet représente 
l'ensemble, qui doit être non vide, des
solutions réalisables (550,331, . . . ,xn_1) pour lesquelles on a: 550 : EEE, 
xl : "ff, . . . , æ,0_1 : æ,--0_1 ;
ces solutions réalisables seront dites contenues par ce sommet. Si io # n, un 
tel sommet possède 1 ou
2 fils: un fils correspondant à l'indice du + 1 et à (î'5,âî, . . . ,:r,--0_1, 
O) et, si p,-O + ZÊ°=BI p,-î{ < Q,
un second fils correspondant à l'indice io + 1 et à (55, îî, . . . , su,-0-1, 
1).

On appelle évaluation d'un sommet un majorant commun aux valeurs de toutes les 
solutions réalisables
contenues par ce sommet.

On considère dans toute la fin du problème l'exemple suivant, qui sera appelé 
le problème ("P) :

Maximiser z = 16550 + 21351 + 19332 + 15563 + 13504 + 7335
avec les contraintes :

15OE0 + 22m1 + 20332 + 1733 + 15124 + 9325 < 51

et pourz' E {O, 1,2,3,4,5}, a:,-- E {0,1}

(79)

page 6/8

Épreuve commune 2002

Une partie de l'arbre associé est dessinée ci--dessous :

a -- Déterminer directement la meilleure solution réalisable contenue par le 
sommet C (obtenu en
fixant 1130 = 121 = 1).

b -- Déterminer directement la meilleure solution réalisable contenue par le 
sommet E (obtenu en
fixant a:0 : 1, 551 = 0, mg =1).

c -- Résoudre le problème de sac à dos fractionnaire ci--dessous :

Maximiser 15553 + 13354 + 7335
avec les contraintes :

175133 + 15274 + 9235 < 36

et pouri EUR {3,4, 5}, a:,-- E [0,1]

En déduire une évaluation du sommet F (obtenu en fixant 1120 = 1, 931 : æ2 : 
0). La solution
réalisable optimale du problème (P) peut--elle être contenue dans F ?

d -- Montrer, en utilisant la même démarche que dans la question précédente, 
que la solution réalisable
optimale du problème (P) n'est pas contenue dans le sommet G (obtenu en fixant 
m0 = 0).

e -- Déduire des questions précédentes la solution optimale du problème (P).

FIN DU PROBLÈME D'ALGORITHMIQUË

3 Exercice sur les automates finis -- 30 mn environ

Rappels pour fixer les notations

Un alphabet A est un ensemble fini d'éléments, appelés lettres. L'ensemble des 
suites finies de lettres

de A, appelées mots, est noté A'". Le mot vide est noté 1A*. Un langage est une 
partie de A'".

Un automate fini A est un graphe orienté et étiqueté, noté par un quintuplet < 
Q,A,E,I,T > : A est

un alphabet; Q est l'ensemble (fini) des états de A: ce sont les sommets du 
graphe; I et T, deux sous-
ensembles de Q, sont respectivement l'ensemble des états initiaux et des états 
terminaux de A. Enfin, E,
sous--ensemble de Q >< A >< Q, est appelé ensemble des transitions de A. Une 
transition (p,a,q) est un arc du
graphe, allant de l'état p à l'état q et étiqueté par a ; on la note également 
p --°> q.

Un calcul de A est un chemin c dans le graphe: (: : pg --cÏï--> p1 --a2--> pg - 
-- &) p... où, pour tout i,

0 < z' { n -- 1, p,-- & p,--+1 appartient à E. L'état pg est l'origine du 
calcul c, pn l'extrémité de c. La

page 7/8
Tournez la page S.V.P.

Épreuve d'Informatique

longueur du calcul est donnée par le nombre n d'arcs de c. L'étiquette de c est 
le mot f formé par la
suite des étiquettes des transitions successives du calcul c: f : a1a2 . . . 
an. Le calcul 0 peut aussi être

noté pg --î--> p,, ; il est réussi si pg est initial et p,, terminal.

Un mot de A* est reconnu ar l'automate A si c'est l'éti nette d'(au moins) un 
calcul réussi de A. Le
P q

langage reconnu par A, noté L(A), est l'ensemble des mots reconnus par A. Un 
langage est reconnaissable
s'il est reconnu par un automate fini.

On dira qu'un automate A = < Q,A,E,I,T > est normalisé si:
i) 1 est un singleton, I = {2}, qui n'est l'extrémité d'aucune transition de A;
ii) T est un singleton, T = {t}, qui n'est l'origine d'aucune transition de A.

Un automate normalisé est donc naturellement représenté par le schéma 
ci-dessous (noter que certaines
transitions peuvent aussi aller de i à t, même si elles n'apparaissent pas sur 
le schéma).

Énoncé de l'exercice

Si un mot f de A* se factorise en f : uv, avec u et U dans A'", le mot 9 = ou 
est un conjugué de f.
Soit Con j: A* --> P(A*) l'application qui à un mot f fait correspondre 
l'ensemble de ses conjugués :

Conj(f) : {ou | (u,v) EUR (A')2 avec uv : f}.
En particulier, pour tout f, f E Conj(f) puisque f = 1,4- f : f1A- et, pour 
tout f E A U {1A.},
Conj( f ) = {f}. L'application s'étend par additivité : si L est un langage, 
Conj(L) : U fe L Conj( f ).

Dans tout l'exercice, L est un langage reconnu par un automate fini. L'objet de 
l'exercice est de
montrer que Conj (L) est reconnaissable.

l -- Montrer que L \ {l A--} est reconnu par un automate (fini) normalisé.
2 -- Soient A = < Q,A,E,{i},{t} > un automate normalisé qui reconnaît le 
langage L \ { 1 A--} et q un
état de A distinct de z' et t. A chaque calcul réussi de A qui passe par q (et 
donc de longueur au moins

égale à 2) d'étiquette f : f1f2: z' --Ê--> q --â--> t, on associe le conjugué g 
: f2f1 de f et on note G'q

l'ensemble des mots obtenus de cette façon:

GQ = {g : f2f1 | i --Î--l--> q --Ë> test un calcul réussi de A}.

Construire un automate qui reconnaît le langage G.,.
3 -- Montrer que Conj(L) est reconnaissable.

FIN DE L'EXERCICE SUR LES AUTOMATES

FIN DE L'ÉPREUVE

page 8/8

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



Mines Informatique MP 2002 -- Corrigé
Ce corrigé est proposé par Mathieu Giraud (ENS Lyon) ; il a été relu par Xavier
Goaoc (ENS Cachan) et Sébastien Desreux (ENS Ulm).

L'épreuve se compose de trois parties (deux exercices et un problème) 
indépendantes et de longueurs largement inégales. Beaucoup de points du 
programme sont
concernés, notamment la description d'algorithmes, leur compréhension et 
l'évaluation de leur complexité. Quelques preuves sont aussi demandées.
· Le premier exercice traite de logique des propositions en résolvant le 
problème de la satisfiabilité des formules de Horn. Il demande de résoudre de
petits exemples, d'effectuer quelques preuves et de concevoir un algorithme
polynomial.
· Le problème est plutôt long (l'énoncé recommande d'y consacrer les deux tiers
du temps imparti). Il étudie divers aspects du problème dit du « sac à dos »
dans ses variantes fractionnaire (première partie) et entière (seconde partie).
Il met en jeu diverses techniques algorithmiques (dont la récursion) et comporte
aussi quelques questions concrètes (exemples) et un peu de programmation.
· Enfin, l'exercice sur les automates vise à prouver que le langage des 
conjugués
d'un langage régulier est lui aussi régulier. Il utilise pour cela des 
techniques
usuelles sur les automates et les langages réguliers.
Chaque partie s'ouvre par une certaine quantité de notations qu'il est 
préférable de
bien assimiler avant de se lancer dans la résolution, pourquoi pas en 
commençant par
examiner un exemple. De plus, beaucoup de questions sont largement indépendantes
et, comme le rappelle l'énoncé, « tout résultat fourni dans l'énoncé peut être 
utilisé,
même s'il n'a pas été démontré ».
Remarquons enfin que la part de la programmation est assez faible (seulement
trois questions dans le problème) ; ce corrigé propose à chaque fois des 
solutions en
Caml et en Pascal.

Indications
Partie I
1.2 Utiliser les littéraux négatifs.
1.3 Simplifier une à une les clauses de H en distinguant différents cas selon la
présence de pk et de ¬pk .
1.4 Réduire le nombre de clauses de H jusqu'à pouvoir décider de la 
satisfiabilité.
Partie II
2.1.a Vérifier tout d'abord que la solution proposée (x) est effectivement 
solution.
La preuve de la maximalité est plus délicate ; prendre une solution quelconque 
et
considérer les objets d'indices a = min{i  [[ 0 ; n - 1 ]] | yi < 1} et
b = max{i  [[ 0 ; n - 1 ]] | yi > 0}.
2.1.b Appliquer la méthode de la question 2.1.a en n'oubliant pas de vérifier 
que les
données proposées respectent les conditions sur les ui /pi . On pourra commencer
par déterminer i .
2.1.d Vérifier avec soin les cas où i vaut 0 ou n.
2.2.a La récursion de l'algorithme pourra porter sur l'ensemble à partitionner.
À chaque étape, l'appel récursif concerne seulement une des deux moitiés de
cet ensemble.
2.2.c Il n'est pas demandé dans cette question de détailler un nouvel 
algorithme mais
simplement d'indiquer comment utiliser les résultats précédents.
2.3 Une solution au problème en 0­1 est aussi une solution du problème 
fractionnaire.
2.5 Le pire des cas de la méthode par séparation est atteint lorsque l'arbre de
recherche est complet.
2.6.c Procéder de la même manière qu'à la question 2.6.b ; utiliser la question 
2.3.
2.6.e Déterminer une évaluation de A à partir de celles des feuilles C, E, F et 
G
calculées dans les quatre questions précédentes.
Partie III
3.1 À partir d'un automate reconnaissant L, construire un nouvel automate en
ajoutant des nouveaux états i et t répondant aux conditions de normalisation
et simulant le comportement de certaines transitions des états de I et de T.
3.2 Construire deux automates reconnaissant respectivement les mots f1 et les
mots f2 , puis les fusionner.
3.3 Exprimer Conj(L r {1A }) en fonction des langages Gq puis utiliser le 
résultat
de la question 3.2. Ne pas oublier de traiter le cas du mot 1A .

1.

Exercice de logique des propositions

Lorsque nous donnons des valuations, nous écrivons directement l'égalité
pk = vrai (alors que l'on peut aussi écrire v(pk ) = vrai).
1.1
i) (¬p1  p2 )  (p1  ¬p2  ¬p3 ) est satisfiable par la valuation p1 = p2 = p3 = 
vrai ;
ii) (p2 )  (¬p1  ¬p3 )  (¬p2 )  (p1  ¬p2  ¬p4 ) n'est pas satisfiable car les 
clauses
(p2 ) et (¬p2 ) ne peuvent être satisfaites simultanément ;
iii) (p2 )(¬p1 ¬p2 )(p1 ¬p2 )(p1 ¬p2 ¬p3 ) n'est pas satisfiable. Supposons en
effet que les deux premières clauses soient satisfaites. Alors la première 
clause
implique p2 = vrai, puis la deuxième clause nécessite p1 = vrai, ce qui a pour
conséquence que la troisième clause ne peut pas être satisfaite.
1.2 Supposons que H soit une formule sous forme normale conjonctive telle que
chacune de ses clauses contienne au moins un littéral négatif. On considère 
alors
la valuation qui associe à chaque variable propositionnelle la valeur faux. 
Puisque
chaque clause contient au moins un littéral négatif, elle est satisfaite. Il 
s'ensuit :
Une telle formule H est satisfiable.
1.3 Écrivons la formule sous la forme H = C1  C2  · · ·  Cm et supposons que
la clause Cr est restreinte au littéral pk . On construit à partir de H une 
nouvelle
formule H en omettant la clause Cr et en transformant chaque clause C ,  6= r ,
de la manière suivante :
1. si le littéral pk y apparaît, alors on enlève C ;
2. si le littéral ¬pk y apparaît, alors on garde C , mais en y supprimant ¬pk ;
3. dans les autres cas, on conserve C .
Les clauses contenant à la fois pk et ¬pk sont traitées par le cas 1. Après 
cette
transformation, la formule H :
· est une formule de Horn (car on n'a ajouté aucun littéral positif) ;
· ne fait apparaître ni pk ni ¬pk donc VH  VH r {pk }.
Il n'y a pas égalité entre VH et VH r {pk } car d'autres variables ont pu
disparaître lors de l'élimination de certaines clauses.
Il ne reste plus qu'à montrer que H est satisfiable si et seulement si H l'est.
· Supposons H satisfaite par une valuation v. La clause Cr de H, réduite à {pk 
},
impose que pk soit évalué à vrai dans v. Soit v  la restriction de v à VH .
Cette valuation satisfait les clauses de H produites par le cas 3 (clauses 
inchangées) et celles produites par le cas 2 (puisque pk = vrai). Ainsi la 
formule
H est satisfaite par v  .

· Réciproquement, supposons H satisfaite par une certaine valuation v  . On 
étend
alors la valuation v  en fixant pk = vrai, ce qui satisfait les clauses 
traitées par
le cas 1. Finalement H est aussi satisfaite.
On a réduit H en une autre formule de Horn équivalente H .
1.4 Utilisons le résultat de la question 1.3 pour diminuer le nombre de clauses 
de H ;
il faut d'abord en vérifier les conditions :
· une de ses clauses doit être réduite à un littéral positif pk (sinon, on sait 
d'après
la question 1.2 que la formule est satisfiable) ;
· aucune autre clause ne doit être réduite à ¬pk (sinon la formule n'est pas
satisfiable).
Ces deux conditions fournissent les deux cas d'arrêt de l'algorithme.
Algorithme S : Satisfiabilité d'une formule de Horn
Entrée : une formule de Horn H.
Sortie : vrai si H est satisfiable, faux sinon.
Répéter
1. Parcourir les clauses de H jusqu'à trouver une clause Cr réduite à un seul 
littéral
positif (pk ).
Si une telle clause n'existe pas, renvoyer vrai.
2. Parcourir de nouveau les clauses de H en cherchant s'il existe une clause 
réduite
au seul littéral négatif (¬pk ).
Si c'est le cas, renvoyer faux.
3. Réduire la formule H en suivant la méthode exposée à la question 1.3.
Fin Répéter
L'étape 1 permet aussi de reconnaître comme vraie la formule vide T.
Évaluons maintenant la complexité de cet algorithme. Les étapes 1 et 2 
nécessitent d'examiner chaque clause, ce qui se fait pour chacune de ces étapes 
en O (m)
opérations élémentaires. L'étape 3 demande, dans le pire des cas, d'observer 
chaque
littéral de chaque clause. Il y a n variables propositionnelles distinctes et m 
clauses,
donc au plus O (mn) clauses. L'étape 3 se fait donc en au plus O (mn) opérations
élémentaires.
Enfin, la boucle générale s'exécute au plus m+1 fois puisqu'au moins une clause 
est
supprimée à chaque itération. L'algorithme total exige au plus O ((m + 1)(m + 
mn))
opérations.
Cet algorithme polynomial
a une complexité

en temps de O m2 n dans le pire des cas.
Ce résultat montre la particularité des formules de Horn. Le problème général 
de la satisfiabilité des formules logiques est en effet NP-complet : on ne
connaît aucun algorithme polynomial pour le résoudre et on conjecture même
qu'un tel algorithme n'existe pas.