CCP 2004 informatique

Publié par

1 2Les calculatrices sont interdites. 1.2 Representation´ graphique d’un automateLes automates peuvent etreˆ represent´ es´ par un schema´ suivant les conventions :N.B. : Le candidat attachera la plus grande importance a` la clarte,´ a` la precision´ et a` la concisionde la redaction.´Si un candidat est amene´ a` reperer´ ce qui peut lui sembler etreˆ une erreur d’enonc´ e,´ il le signalera sur– les valeurs de la relation de transition sont represent´ ees´ par un graphe oriente´ dont les nœudssa copie et devra poursuivre sa composition en expliquant les raisons des initiatives qu’il a et´ e´ amene´ sont les etats´ et les aretesˆ sont les transitions ;a` prendre.– un etat´ initial est entoure´ d’un cercle i ;´ – un etat´ terminal est entoure´ d’un double cercle t ;PREAMBULE : Les deux parties qui composent ce sujet sont independantes´ et peuvent etreˆ traitees´ parles candidats dans un ordre quelconque.– un etat´ qui est a` la fois initial et terminal est entoure´ d’un triple cercle it ;– une areteˆ etiquet´ ee´ par le symbole e2 X va de l’etat´ o a` l’etat´ d si et seulement si (o;e;d)2 .Partie I : Automates et langagesExemple I.1 L’automateE = (Q;X;I;T; ) avec :1Le but de cet exercice est l’etude´ des propriet´ es´ des operations´ de deri´ vation a` gauche m :A et a`1droiteA:m d’un automate finiA selon un mot m. Q =fA;B;C;D;EgX =fa;bgI =fA;BgT =fD;Eg1 Automate fini =f(A;a;C);(A;b;D);(B;a;D);(B;b;B);(C;b;E);(D;a;C);(E;a;C)gPour simplifier les ...
Publié le : jeudi 21 juillet 2011
Lecture(s) : 107
Nombre de pages : 13
Voir plus Voir moins
1 2 Les calculatrices sont interdites. 1.2 Representation´ graphique d’un automate Les automates peuvent etreˆ represent´ es´ par un schema´ suivant les conventions : N.B. : Le candidat attachera la plus grande importance a` la clarte,´ a` la precision´ et a` la concision de la redaction.´ Si un candidat est amene´ a` reperer´ ce qui peut lui sembler etreˆ une erreur d’enonc´ e,´ il le signalera sur – les valeurs de la relation de transition sont represent´ ees´ par un graphe oriente´ dont les nœuds sa copie et devra poursuivre sa composition en expliquant les raisons des initiatives qu’il a et´ e´ amene´ sont les etats´ et les aretesˆ sont les transitions ; a` prendre. – un etat´ initial est entoure´ d’un cercle i ; ´ – un etat´ terminal est entoure´ d’un double cercle t ; PREAMBULE : Les deux parties qui composent ce sujet sont independantes´ et peuvent etreˆ traitees´ par les candidats dans un ordre quelconque. – un etat´ qui est a` la fois initial et terminal est entoure´ d’un triple cercle it ; – une areteˆ etiquet´ ee´ par le symbole e2 X va de l’etat´ o a` l’etat´ d si et seulement si (o;e;d)2 . Partie I : Automates et langages Exemple I.1 L’automateE = (Q;X;I;T; ) avec : 1 Le but de cet exercice est l’etude´ des propriet´ es´ des operations´ de deri´ vation a` gauche m :A et a` 1 droiteA:m d’un automate finiA selon un mot m. Q =fA;B;C;D;Eg X =fa;bg I =fA;Bg T =fD;Eg 1 Automate fini =f(A;a;C);(A;b;D);(B;a;D);(B;b;B);(C;b;E);(D;a;C);(E;a;C)g Pour simplifier les preuves, nous nous limiterons au cas des automates finis semi-indeterministes,´ c’est-a-dire` les automates finis non deterministes´ qui ne contiennent pas de transitions instantanees´ est represent´ e´ par le graphe suivant : (ou -transitions). Les resultats´ etudi´ es´ s’etendent´ au cadre des automates finis quelconques. a a A C E b 1.1 Representation´ d’un automate fini b a a Def´ . I.1 (Automate fini semi-indeterministe)´ Soit l’alphabet X (un ensemble de symboles), soit  B D ? le symbole representant´ le mot vide ( 62 X), soit X l’ensemble contenant  et les mots composes´ ? b de symboles de X (donc  2 X ), un automate fini semi-indeterministe´ sur X est un quintuplet A = (Q;X;I;T; ) compose´ de : – Un ensemble fini d’etats´ : Q ; 1.3 Langage reconnu par un automate fini – Un ensemble d’etats´ initiaux : I  Q ; ? ? Soit l’extension de a` Q X  Q definie´ par : – Un ensemble d’etats´ terminaux : T  Q ; – Une relation de transition confondue avec son graphe :  Q X Q.  ? 8q2 Q; (q;;q)2 ? ? ? 8e2 X;8m2 X ;8o2 Q;8d2 Q; (o;e:m;d)2 ,9q2 Q; ((o;e;q)2 )^ ((q;m;d)2 ) Pour une transition (o;e;d) donnee,´ nous appelons o l’origine de la transition, e l’etiquette´ de la transition et d la destination de la transition. ? Le langage sur X reconnu par un automate fini est : Remarquons que est le graphe d’une application de transition  : Q X ! P(Q) dont les valeurs sont definies´ par : ? ? L(A) =fm2 X j9o2 I;9d2 T; (o;m;d)2 g 8o2 Q;8e2 X; (o;e) =fd2 Qj (o;e;d)2 g Question I.1 Donner sans la justifier une expression reguli´ er` e ou ensembliste representant´ le lan- La notation est plus adaptee´ que  a` la formalisation et la construction des preuves dans le cadre gage reconnu par l’automateE de l’exemple I.1. des automates indeterministes.´ 3 4 ´ ´ 2 Operations de derivation Partie II : Algorithmique et programmation en CaML 2.1 Definitions´ Cette partie doit etreˆ traitee´ par les etudiants´ qui ont utilise´ le langage CaML dans le cadre des ensei- Soient les operations´ internes sur les automates finis semi-indeterministes´ definies´ par : gnements d’informatique. Les fonctions ecrites´ devront etreˆ recursi´ ves ou faire appel a` des fonctions auxiliaires recursi´ ves. Elles ne devront pas utiliser d’instructions iterati´ ves (for,while, . . . ) ni de ´ ´ ´ Def. I.2 (Derivees selon un mot) SoientA = (Q;X;I;T; ) un automate fini semi-indeterministe´ et ref´ erences.´ ? 1 1 m 2 X , les automates m :A (derivation´ a` gauche selon m) etA:m (derivation´ a` droite selon Format de desciption d’une fonction : La description d’une fonction, lorsque celle-ci est demandee,´ m) sont definis´ par : c’est-a-dire` aux questions II.23 et II.29, doit au moins contenir : 1 ? m :A = (Q;X;fq2 Qj9i2 I;(i;m;q)2 g;T; ) 1. L’objectif gen´ eral´ ; 1 ? A:m = (Q;X;I;fq2 Qj9t2 T;(q;m;t)2 g; ) 2. Le roleˆ des parametres` de la fonction ; 1 1 1 1 3. Les contraintes sur les valeurs des parametres` ; Question I.2 En consider´ ant l’exemple I.1, construire les automates a :E, b :E, E:a et E:b (seuls les etats´ et les transitions utiles, c’est-a-dir` e accessibles depuis les etats´ initiaux, devront etrˆ e 4. Les caracteristiques´ du resultat´ renvoye´ par la fonction ; construits). 5. Le roleˆ des variables locales a` la fonction ; 6. Le principe de l’algorithme ; 1 1 1 1 Question I.3 Caracteriser´ les langages reconnus par a :E, b :E,E:a E:b , par une expression 7. Des arguments de terminaison du calcul pour toutes les valeurs des parametres` qui verifient´ les reguli´ er` e ou ensembliste. contraintes present´ ees´ au point 3. 2.2 Propriet´ es´ L’objectif de ce probleme` est l’etude´ d’une strategie´ complete` et coherente´ d’interrogation d’une ? base de connaissances. Une base de connaissances est une representation´ de relations logiques exis- Question I.4 Montrer que : siA est un automate fini semi-indeterministe´ et m 2 X un mot, alors 1 1 tant entre des faits. Cette strategie´ repose sur un algorithme de construction d’une base complete,` m :A etA:m sont des automates finis semi-indeterministes.´ coherente´ et minimale. Cet algorithme qui preserv´ e le contenu logique de la base est gen´ eralement´   appele´ completion´ de la base. Question I.5 Montrer que : ? ? ? ? ? 1 Preliminair´ e : Calcul des propositions 8m2 X ;8n2 X ;8o2 Q;8q2 Q;8d2 Q; (o;m;q)2 ^ (q;n;d)2 , (o;m:n;d)2 La representation´ d’une base de connaissances repose sur le calcul des propositions. Question I.6 SoitA un automate fini semi-indeterministe´ , montrer que :  ? ? 1 8m2 X ;8n2 X ; n2 L(m :A), m:n2 L(A) Def´ . II.1 (Propositions) SoitF =ff ;f ; : : :g un ensemble denombr´ able de symboles, appeles´ faits 0 1 ? ? 1 8m2 X ;8n2 X ; n2 L(A:m ), n:m2 L(A) (ou variables propositionnelles), soient les constantes vrai et faux notees´ >;?, soit l’oper´ ateur unaire : (negation),´ soient les oper´ ateurs binaires_ (disjonction),^ (conjonction),) (implication); l’en- sembleP(F) des propositions est le plus petit ensemble tel que : – F P(F) ; – f>;?gP(F) ; – si P 2P(F) alors:P 2P(F) ; 2 – si P ;P 2P (F) et op2f_;^ ;)g alors P opP 2P(F) ; 1 2 1 2 – les propositions deP(F) sont finies, c’est-a-dir` e obtenues par application d’un nombre fini de fois des regles precedentes. ` ´ ´ Nous noterons les faits en utilisant les minuscules de l’alphabet romain. Nous noterons les proposi- tions et les ensembles de faits en utilisant les majuscules de l’alphabet romain. 5 6 Def´ . II.2 (Valuation) Soit B =f0;1g les valeurs de verit´ e,´ une valuation est une application 2.1 Codage d’un fait  :F ! B. Cette application est etendue en une application unique ^ :P(F)! B par les egalites : ´ ´ ´ Un fait est represent´ e´ par le type de basestring. ^(>) = 1 ^(?) = 0 type fait == string;; ^(f ) = (f ) i i ^(:P) = 1 ^(P) ^(P _ P ) = 1 (1 ^(P )) (1 ^(P )) 1 2 1 2 2.2 Codage d’un ensemble de faits ^(P ^ P ) = ^(P ) ^(P ) 1 2 1 2 ^(P ) P ) = 1 ^(P ) (1 ^(P )) 1 2 1 2 Nous allons utiliser un codage extremementˆ simple : un ensemble est une liste contenant exac- tement un exemplaire de chaque el´ ement´ contenu dans l’ensemble. Les operations´ de manipulation ´ Def´ . II.3 (Equivalence) Soient deux propositions P ;P el´ ements´ deP(F), P est equivalente´ a` P 1 2 1 2 d’un ensemble devront preserv´ er cette propriet´ e.´ (notee´ P  P ) si et seulement si pour toute valuation , ^(P ) = ^(P ). 1 2 1 2 Un ensemble de faits est represent´ e´ par le typefaits equi´ valent a` une liste defait. Question II.1 Montrer que a) b:a_ b. type faits == fait list;; Def´ . II.4 (Tautologie) Soit une proposition P 2P(F), P est une tautologie si et seulement si P >. Le parcours d’un ensemble sera donc effectue´ de la memeˆ maniere` que celui d’une liste. Nous allons maintenant definir´ plusieurs operations´ sur les ensembles de faits qui pourront etreˆ Def´ . II.5 (Proposition absurde) Soit une proposition P 2 P(F), P est absurde si et seulement si utilisees´ dans la suite du sujet. Ces operations´ seront ensuite etendues´ aux ensembles de connais- P ?. sances. Nous supposons que toutes les listes representant´ des ensembles, qui sont passees´ comme parametres` Def´ . II.6 (Litteral)´ Un litter´ al est une proposition qui prend l’une des formes suivantes : des fonctions, ne contiennent au plus qu’une fois chaque el´ ement.´ – un fait (litter´ al positif) ; – la negation´ d’un fait (litter´ al negatif).´ 2.3 Operation´ sur la structure d’ensemble Def´ . II.7 (Clause, clause duale) Une clause est une disjonction de litter´ aux deux a` deux distincts. Une clause duale est une conjonction de litteraux deux a deux distincts. ´ ` Pour les calculs de complexite,´ nous noterons j E j la taille de l’ensemble E, c’est-a-dire` le nombre de faits qu’il contient. Exemple II.1 c_:b_ a est une clause. b^ c^:a est une clause duale. Def´ . II.8 (Forme conjonctive, disjonctive) Une forme conjonctive est une conjonction de clauses. 2.3.1 Appartenance a` un ensemble Une forme disjonctive est une disjonction de clauses duales. Une premiere` operation´ consiste a` tester l’appartenance d’un fait a` un ensemble. Exemple II.2 (a_:c)^:b est une forme conjonctive. c_ (:a^ b) est une forme disjonctive. ´ Question II.3 Ecrire en CaML une fonctionappartenance de typefait -> faits -> bool Question II.2 Soit la proposition P = (a^ c)?)^ (a) b)^ (>) b_ d), transformer P en une telle que l’appel(appartenance f E) renvoie la valeurtrue si l’ensembleE contient le faitf forme conjonctive C, puis en une forme disjonctive D telles que P  C  D. Vous utiliserez pour et la valeurfalse sinon. Cette fonction devra etrˆ e recur´ sive ou faire appel a` des fonctions auxiliaires cela les formules de De Morgan. recur´ sives. Question II.4 Donner un exemple de valeurs des parametresf etE de la fonctionappartenance ` 2 Representation´ et codage d’un ensemble de faits qui correspond au pire cas en nombre d’appels recur´ sifs effectues.´ Calculer une estimation de la complexite´ dans le pire cas de la fonction en La repr´ et les operations´ de manipulation des bases de connaissances reposent sur la fonction de la taille de l’ensembleE. Cette estimation ne prendra en compte que le nombre d’appels structure d’ensemble. Nous allons dans une premiere` etape´ etudier´ un codage de cette structure qui recur´ sifs effectues.´ contiendra des faits. Cette structure sera ensuite adaptee´ aux connaissances. 7 8 2.3.2 Ajout dans un ensemble 2.3.6 Autres operations´ pred´ efinies´ Nous supposons pred´ efinies´ les fonctions suivantes pour les ensembles, dont le calcul se termine La deuxieme` operation´ est l’ajout d’un fait a` un ensemble. quelles que soient les valeurs de leurs parametres.` Elles pourront ev´ entuellement etreˆ utilisees´ dans les reponses´ aux questions : ´ Question II.5 Ecrire en CaML une fonction ajout de type fait -> faits -> faits telle – union : faits -> faits -> faits telle que l’appel(union E1 E2) renvoie un que l’appel (ajout f E) renvoie un ensemble contenant les memesˆ que l’ensemble E ainsi ensemble contenant les faits contenus dansE1 ainsi que les faits contenus dansE2 ; que le faitf s’il ne figurait pas dej´ a` dans E. L’ensemble renvoye´ contiendra exactement une fois le faitf. Cette fonction devra etrˆ e recur´ sive ou faire appel a` des fonctions auxiliaires recur´ sives. – intersection : faits -> faits -> faits telle que l’appel (intersection E1 E2) renvoie un ensemble contenant les faits contenus a` la fois dans E1 et dansE2. 2.3.3 Inclusion entre deux ensembles La troisieme` operation´ est le test d’inclusion du contenu de deux ensembles. 3 Representation´ et codage d’une connaissance 3.1 Repr´ d’une connaissance ´ Question II.6 Ecrire en CaML une fonctioninclusion de typefaits -> faits -> bool telle que l’appel(inclusion E1 E2) renvoie la valeurtrue si l’ensembleE2 contient au moins Def´ . II.9 (Connaissance) Une connaissance notee´ = H ‘ C est composee´ de deux ensembles les memesˆ faits que l’ensembleE1 et la valeurfalse sinon. Cette fonction devra etrˆ e recur´ sive ou finis de faits (ou variables propositionnelles) : les hypotheses` H = fhg et les conclusions C = i i2I faire appel a` des fonctions auxiliaires recur´ sives. fc g . j j2J Nous noterons les connaissances en utilisant les minuscules de l’alphabet grec. Question II.7 Donner un exemple de valeurs des parametr` esE1 etE2 de la fonctioninclusion qui correspond au pire cas en nombre d’appels recur´ sifs effectues.´ Def´ . II.10 (Interpretation´ logique) L’interpretation´ logique, notee´ I( ), d’une connaissance Calculer une estimation de la complexite dans le pire cas de la fonctioninclusion en fonction ´ =fhg ‘fc g est : i i2I j j2J des tailles des ensembles E1 et E2. Cette estimation ne prendra en compte que le nombre d’appels recur´ sifs effectues.´ ^ _ I( ) = (>^ h )) (?_ c ) i j i2I j2J ´ 2.3.4 Egalite´ entre deux ensembles Intuitivement, elle signifie que sous les hypotheses` de fhg , nous pouvons deduir´ e une des i i2I conclusions defc g .> permet de traiter le cas I = ;.? permet de traiter le cas J = ;. Notons j j2J La quatrieme` operation´ est le test d’egalit´ e´ du contenu de deux ensembles. que : W – I(;‘fc g ) =>) (?_ c ) ; j j2J j j2J ´ V Question II.8 Ecrire en CaML une fonctionegalite de typefaits -> faits -> bool telle – I(fhg ‘;) = (>^ h ))? ; i i2I i i2I que l’appel(egalite E1 E2) renvoie la valeurtrue si les deux ensemblesE1 etE2 contiennent – I(;‘;) =>)?. exactement les memesˆ faits et la valeur false sinon. Cette fonction devra etrˆ e recur´ sive ou faire appel a des fonctions auxiliaires recursives. ` ´ Exemple II.3 Les formules logiques suivantes sont des connaissances : – f ag‘f bg ; 2.3.5 Soustraction de deux ensembles – f a, cg‘; ; – ;‘f b, dg. La derniere` operation´ etudi´ ee´ est la construction d’un ensemble resultant´ de la soustraction d’un ensemble depuis un autre ensemble. Question II.10 Soit =fhg ‘fc g une connaissance quelconque, donner une clause P telle i i2I j j2J queI( ) P . ´ Question II.9 Ecrire en CaML une fonction soustraction de type faits -> faits -> ´ Def. II.11 (Connaissance absurde) Une connaissance est absurde si et seulement si son interpretation´ faits telle que l’appel (soustraction E1 E2) renvoie un ensemble contenant les faits qui I( ) est absurde. sont contenus dansE1 et ne sont pas contenus dansE2. Cette fonction devra etrˆ e recur´ sive ou faire appel a` des fonctions auxiliaires recur´ sives. Question II.11 Montrer que la seule connaissance absurde est;‘;. 9 10 3.2 Codage d’une connaissance Exemple II.4 La base composee´ des connaissances de l’exemple II.3 sera represent´ ee´ par la valeur : [ Pour les variables ou les constantes dont le nom est pris dans l’alphabet grec ( , . . . ), l’identifiant en ( [ "a" ] , [ "b" ] ) ; CaML sera leur nom en toute lettre (gamma, . . . ). ( [ "a" ; "c" ] , [] ) ; ( [ ] , [ "b" ; "d" ] ) Une connaissance est represent´ ee´ par le type connaissance equi´ valent a` un couple compose´ ] de deux ensembles de faits. Une base est un ensemble de connaissances. Il est donc necessaire´ d’adapter les operations´ definies´ type connaissance == faits * faits ;; dans la sous-section 2.2 sur les ensembles de faits. Nous supposons pred´ efinies´ les fonctions suivantes pour les bases, dont le calcul se termine ´ Question II.12 Ecrire en CaML une fonctioncomparaison de typeconnaissance -> quelles que soient les valeurs de leurs parametres.` Elles pourront ev´ entuellement etreˆ utilisees´ dans connaissance -> bool telle que l’appel (comparaison gamma1 gamma2) renvoie la les reponses´ aux questions : valeurtrue si les deux connaissancesgamma1 etgamma2 contiennent exactement les memesˆ hy- potheses` et conclusions et la valeurfalse sinon. Cette fonction devra etrˆ e recur´ sive ou faire appel – appartenanceB : connaissance -> base -> bool a` des fonctions auxiliaires recur´ sives. – ajoutB : connaissance -> base -> base – inclusionB : base -> base -> bool 4 Representation´ et codage d’une base de connaissances – egaliteB : base -> base -> bool – unionB : base -> base -> base 4.1 Repr´ d’une base de connaissances – intersectionB : base -> base -> base ´ Def. II.12 (Base de connaissances) Une base de est un ensemble fini de connais- – soustractionB : base -> base -> base sances =f g . k k2K ´ Nous noterons les bases de connaissances en utilisant les majuscules de l’alphabet grec. 5 Elimination des tautologies Une base de connaissances peut contenir des connaissances inutiles, c’est-a-dire` qui n’apportent Def´ . II.13 (Interpretation´ logique) L’interpretation´ logique, notee´ I( ) , d’une base =f g k k2K aucune information pertinente lors d’une interrogation, par exemple les tautologies. Pour reduire´ la est definie´ par : taille de la base et les coutsˆ de l’operation´ d’interrogation, nous nous interessons´ a` l’elimination´ des ^ tautologies. I( ) =>^ I( ) k k2K Def´ . II.15 (Tautologie) Une connaissance est une tautologie si et seulement si son interpretation´ Elle correspond a` la conjonction des interpretations´ logiques de chaque connaissance. I( ) est une tautologie. Notons que :I(;) =>. Question II.14 Quelles sont les tautologies parmi les connaissances suivantes (justifier vos reponses)´ : Question II.13 Soit = f g avec = fhg ‘ fc g une base de connaissances quel- k k2K k i i2I j j2J k k conque, donner une forme conjonctive C telle queI( )  C. – =fa;bg‘fcg ; 1 – =fag‘fag ; 2 ´ Def´ . II.14 (Equivalence) Soient deux bases et , est equivalente´ a` (notee´  ) si et 1 2 1 2 1 2 – =fbg‘fb;cg ; 3 seulement siI( )I( ). 1 2 – =fa;cg‘fcg ; 4 – =fbg‘; ; 5 4.2 Codage d’une base de connaissances – =;‘fcg. 6 Une base de connaissances est represent´ ee´ par le type base equi´ valent a` une liste de connais- sances. Question II.15 Donner une relation entre les hypotheses` et les conclusions d’une connaissance qui soit une condition necessair´ e et suffisante pour que cette connaissance soit une tautologie. Donner type base == connaissance list;; une preuve de cette condition.   6   11 12 ´ Nous supposons pred´ efinie´ la fonctiontautologie de typeconnaissance -> bool telle Question II.20 Ecrire en CaML une fonctionabsorbable de type connaissance -> base que l’appel (tautologie gamma) renvoie la valeur true si la gamma est une -> bool telle que l’appel (absorbable gamma Omega) renvoie la valeur true si la base tautologie et la valeur false sinon. Son calcul se termine quelles que soient les valeurs de son Omega contient une connaissance plus gen´ er´ ale quegamma et la valeurfalse sinon. Cette fonction parametre.` Elle pourra ev´ entuellement etreˆ utilisee´ dans les reponses´ aux questions. devra etrˆ e recur´ sive ou faire appel a` des fonctions auxiliaires recur´ sives. Nous supposons pred´ efinie´ la fonctionminimisation de typebase -> base telle que l’ap- Question II.16 Soit une base et une tautologie, montrer que [f g . pel(minimisation Omega) renvoie . Son calcul se termine quelles que soient les valeurs de son parametre.` Elle pourra ev´ entuellement etreˆ utilisee´ dans les reponses´ aux questions. Def´ . II.16 Soit une base, nous noterons ] [ la base privee de ses tautologies, c’est-a-dire : ´ ` ] [ =f 2 j 6 >g ´ 7 Completion d’une base de connaissances Nous pouvons deduir´ e de la question II.16 que ] [ . La completion´ d’une base de connaissances consiste a` construire l’ensemble de toutes les connais- ´ sances qui peuvent etreˆ deduites´ d’une base donnee.´ Cette operation´ permet ensuite de reduire´ les Question II.17 Ecrire en CaML une fonction elimination de type base -> base telle que coutsˆ d’interrogation de la base. l’appel(elimination Omega) renvoie une base de connaissances contenant les memesˆ connais- sances que ] [ . Cette fonction devra etrˆ e recur´ sive ou faire appel a` des fonctions auxiliaires recur´ sives. Def´ . II.19 (Deduction´ de connaissances) Soient les connaissances = H ‘ C et = H ‘ C , 1 1 1 2 2 2 l’oper´ ateurB de deduction´ de connaissances construit une base notee´ B et definie´ par : 1 2 6 Minimisation d’une base de connaissances B =f(H nffg)[ H ‘ C [ (C nffg)j f 2 H \ C g 1 2 1 2 1 2 1 2 Une base de connaissances peut contenir des redondantes, en particulier, elle peut Notons que B =; si H \ C =;. contenir des plus gen´ erales´ que d’autres. Pour reduire´ la taille de la base et les coutsˆ 1 2 1 2 L’ensemble des connaissances qui peuvent etrˆ e deduites´ d’une base est l’ensemble des connais- de l’operation´ d’interrogation, nous nous interessons´ a` la minimisation de la base, c’est-a-dire` a` ne conserver que les connaissances les plus gen´ erales.´ sances construites par application d’un nombre quelconque de fois de l’oper´ ateurB a` partir des connaissances de . Def´ . II.17 Une connaissance = H ‘ C est dite plus gen´ er´ ale qu’une connaissance 1 1 1 = H ‘ C si et seulement si H  H et C  C . Cette relation sera notee´  . Question II.21 Appliquer l’oper´ ateurB sur les connaissances suivantes (ne donner que les resultats´ 2 2 2 1 2 1 2 2 1 differ´ ents de;) : Question II.18 Donner les relations entre les connaissances suivantes : – =fa;bg‘fc;dg ; 1 – =fa;bg‘fc;dg ; 1 – =fb;cg‘feg ; 2 – =fa;cg‘fb;dg ; 2 – =feg‘; ; 3 – =fag‘fdg ; 3 – =;‘fb;cg. 4 – =fcg‘fb;dg ; 4 – =;‘;. Question II.22 Soient les connaissances = H ‘ C et = H ‘ C , montrer que si 1 1 1 2 2 2 5 j H \ C j> 1 alors B ne contient que des tautologies. Que peut-on en conclure? 1 2 1 2 Question II.19 Soient deux connaissances et , montrer que les bases f ; g et f g sont 1 2 1 2 1 La composition d’une connaissance et d’une base consiste a` appliquer l’operateur´ de deduction´ equivalentes si et seulement si  . Pour cela, vous pouvez considerer une valuation  et en- ´ ´ 2 1 B sur et sur chaque de . visager les differ´ ents cas possibles. Nous souhaitons ecrire´ une fonctioncomposition qui prend en parametre` une connaissance et une base et qui construit une nouvelle base contenant les connaissances resultant´ de la compo- Def´ . II.18 (Base minimale) Soit une base de connaissance, la base minimale associee a ´ ` sition degamma avec chaque connaissance de la baseOmega. Cette fonction devra etreˆ recursi´ ve ou est definie´ par : faire appel a` des fonctions auxiliaires recursi´ ves. =f 2 j8 2 ; = )  g Question II.23 Decrir´ e cette fonction composition et expliquer son algorithme selon le format Nous pouvons deduir´ e de la question II.19 que  . present´ e´ en page 4.   13 14 ´ Question II.24 Ecrire en CaML cette fonctioncomposition de typeconnaissance -> base 8 Interrogation d’une base -> base telle que l’appel (composition gamma Omega) renvoie une base contenant les   Les connaissances contenues dans la base etablissent´ un lien entre des faits hypotheses` et des connaissances resultant´ de la composition de avec les connaissances de la base Omega. faits conclusions. Intuitivement, l’interrogation de la base consiste a` : Cette fonction devra etrˆ e recur´ sive ou faire appel a` des fonctions auxiliaires recur´ sives. Nous supposons pred´ efinie´ la fonctiondeduction de type base -> base telle que l’appel – completer´ la base (voir section 7), minimiser la base complet´ ee´ (voir section 6) et en eliminer´ (deduction Omega) renvoie une base de connaissances qui contient les connaissances de la base les tautologies (voir section 5) ; Omega ainsi que le resultat´ des compositions deux a` deux des connaissances deOmega. Son calcul     – fournir une liste de faits vrais et une liste de faits faux ; se termine quelles que soient les valeurs de son parametre.` Elle pourra ev´ entuellement etreˆ utilisee´ – integrer´ ces faits dans la base complet´ ee´ ; dans les reponses´ aux questions. – rendre la base obtenue minimale (voir section 6) pour obtenir la reponse´ a` la requete.ˆ Question II.25 Soient deux connaissances = H ‘ C et = H ‘ C telles que H \C =ffg, 1 1 2 2 2 2 1 2 Definissons´ ceci formellement : montrer que les basesf ; g[ B etf ; g sont equivalentes.´ 1 2 1 2 1 2 Def´ . II.20 (Interrogation d’une base) Soit une base , la reponse´ a` la requeteˆ composee´ des faits Question II.26 Soit une base de connaissances quelconque , soit la suitef g definie´ par : i vrais V et des faits faux F est la base definie´ par : V;F 8 = < 0 [ = f (Hn V )‘ (Cn F) j H ‘ C 2 ] [ g = [ B i+1 i i j V;F : 2 ; 2 i j i Question II.31 Soit la base de connaissances proposee´ a` la question II.27, construire la reponse´ a` Nous admettrons que le resultat´ de la question II.25 peut etrˆ e etendu´ a` :8i2 N;  . i+1 i la requeteˆ V =fbg;F =fdg. 1. Montrer que la suitef g est croissante ; i Question II.32 Montrer que ] ( ) [ . 2. Montrer que :9k 2 N; = (soit l = minfk 2 N j = g, nous noterons alors k+1 k k+1 k V;F V;F = et nous appelerons la completion de la base ) ; ´ l 3. Montrer que  . Question II.33 Montrer que ( ) . V;F V;F Question II.27 Calculer la completion´ de la base contenant les connaissances suivantes : ´ Question II.34 Ecrire en CaML une fonctioninterrogation de type faits -> faits -> – =fa;bg‘fc;dg ; 1 base -> base telle que l’appel(interrogation V F Omega) renvoie une base de connais- – =fb;cg‘feg ; 2 sances contenant les memesˆ connaissances que . Cette fonction devra etrˆ e recur´ sive ou faire – =feg‘;. V;F 3 appel a` des fonctions auxiliaires recur´ sives. L’elimination´ des tautologies et la minimisation de la base obtenue permettent ensuite de reduire´ la taille de la base et les coutsˆ d’interrogation. ´ Question II.28 Eliminer les tautologies et minimiser la reponse´ que vous avez proposee´ pour la question prec´ edente´ . Nous souhaitons ecrire´ une fonction completion qui prend en parametre` une base et qui construit une nouvelle base contenant les memesˆ connaissances que . Cette fonction devra etreˆ recursi´ ve ou faire appel a` des fonctions auxiliaires recursi´ ves. Question II.29 Decrir´ e cette fonction completion et expliquer son algorithme selon le format present´ e´ en page 4. ´ Question II.30 Ecrire en CaML cette fonction completion de type base -> base telle que l’appel(completion Omega) renvoie une base de connaissances contenant les memesˆ connais- sances que . Cette fonction devra etrˆ e recur´ sive ou faire appel a` des fonctions auxiliaires recur´ sives.
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.