CCP 2004 concours informatique

Description

CCP 2004 concours informatique

Informations

• Publié par: aramis
• Nombre de lectures: 216
• Langue: Français

Extrait

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