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.