CCP 2004 concours informatique
13
pages
Français
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe en t'inscrivant gratuitement
Découvre YouScribe en t'inscrivant gratuitement
13
pages
Français
Ebook
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
CCP 2004 concours informatique
Voir
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
© 2010-2024 YouScribe
