Les calculatrices sont interdites.
N.B. : Le candidat attachera la plus grande importance à la clarté, à la précision et à la concision de la rédaction.
Si un candidat est amené à repérer ce qui peut lui sembler être une erreur d'énoncé, il le signalera sur sa copie et devra poursuivre sa composition en expliquant les raisons des initiatives qu'il a été amené à prendre.
PrÉAMBULE: Les deux parties qui composent ce sujet sont indépendantes et peuvent être traitées par les candidats dans un ordre quelconque.
Partie I: Automates et langages
Le but de cet exercice est l'étude des propriétés des opérations de dérivation à gauche et à droite d'un automate fini selon un mot .
1 Automate fini
Pour simplifier les preuves, nous nous limiterons au cas des automates finis semi-indéterministes, c'est-à-dire les automates finis non déterministes qui ne contiennent pas de transitions instantanées (ou -transitions). Les résultats étudiés s'étendent au cadre des automates finis quelconques.
1.1 Représentation d'un automate fini
Déf. I. 1 (Automate fini semi-indéterministe) Soit l'alphabet (un ensemble de symboles), soit le symbole représentant le mot vide ( ), soit l'ensemble contenant et les mots composés de symboles de (donc ), un automate fini semi-indéterministe sur est un quintuplet composé de:
Un ensemble fini d'états : ;
Un ensemble d'états initiaux: ;
Un ensemble d'états terminaux: ;
Une relation de transition confondue avec son graphe : .
Pour une transition ( ) donnée, nous appelons o l'origine de la transition, e l'étiquette de la transition et la destination de la transition.
Remarquons que est le graphe d'une application de transition dont les valeurs sont définies par:
La notation est plus adaptée que à la formalisation et la construction des preuves dans le cadre des automates indéterministes.
1.2 Représentation graphique d'un automate
Les automates peuvent être représentés par un schéma suivant les conventions:
les valeurs de la relation de transition sont représentées par un graphe orienté dont les nœuds sont les états et les arêtes sont les transitions;
un état initial est entouré d'un cercle ;
un état terminal est entouré d'un double cercle (t);
un état qui est à la fois initial et terminal est entouré d'un triple cercle (it);
une arête étiquetée par le symbole va de l'état à l'état si et seulement si .
Exemple I. 1 L'automate avec :
est représenté par le graphe suivant:
1.3 Langage reconnu par un automate fini
Soit l'extension de à définie par :
Le langage sur reconnu par un automate fini est:
Question I. 1 Donner sans la justifier une expression régulière ou ensembliste représentant le langage reconnu par l'automate de l'exemple I.1.
2 Opérations de dérivation
2.1 Définitions
Soient les opérations internes sur les automates finis semi-indéterministes définies par:
Déf. I. 2 (Dérivées selon un mot) Soient un automate fini semi-indéterministe et , les automates (dérivation à gauche selon ) et (dérivation à droite selon ) sont définis par:
Question I. 2 En considérant l'exemple I.1, construire les automates et (seuls les états et les transitions utiles, c'est-à-dire accessibles depuis les états initiaux, devront être construits).
Question I. 3 Caractériser les langages reconnus par , par une expression régulière ou ensembliste.
2.2 Propriétés
Question I. 4 Montrer que : si est un automate fini semi-indéterministe et un mot, alors . A et A. sont des automates finis semi-indéterministes.
Question I. 5 Montrer que:
Question I. 6 Soit un automate fini semi-indéterministe, montrer que:
Partie II : Algorithmique et programmation en CaML
Cette partie doit être traitée par les étudiants qui ont utilisé le langage CaML dans le cadre des enseignements d'informatique. Les fonctions écrites devront être récursives ou faire appel à des fonctions auxiliaires récursives. Elles ne devront pas utiliser d'instructions itératives (for, while, ...) ni de références.
Format de desciption d'une fonction : La description d'une fonction, lorsque celle-ci est demandée, c'est-à-dire aux questions II. 23 et II.29, doit au moins contenir:
L’objectif général;
Le rôle des paramètres de la fonction;
Les contraintes sur les valeurs des paramètres;
Les caractéristiques du résultat renvoyé par la fonction;
Le rôle des variables locales à la fonction;
Le principe de l'algorithme;
Des arguments de terminaison du calcul pour toutes les valeurs des paramètres qui vérifient les contraintes présentées au point 3.
L'objectif de ce problème est l'étude d'une stratégie complète et cohérente d'interrogation d'une base de connaissances. Une base de connaissances est une représentation de relations logiques existant entre des faits. Cette stratégie repose sur un algorithme de construction d'une base complète, cohérente et minimale. Cet algorithme qui préserve le contenu logique de la base est généralement appelé << complétion >> de la base.
1 Préliminaire: Calcul des propositions
La représentation d'une base de connaissances repose sur le calcul des propositions.
Déf. II. 1 (Propositions) Soit un ensemble dénombrable de symboles, appelés faits (ou variables propositionnelles), soient les constantes vrai et faux notées , soit l'opérateur unaire (négation), soient les opérateurs binaires (disjonction), (conjonction), (implication); l'ensemble des propositions est le plus petit ensemble tel que: ;
si alors ;
si et op alors op ;
les propositions de sont finies, c'est-à-dire obtenues par application d'un nombre fini de fois des règles précédentes.
Nous noterons les faits en utilisant les minuscules de l'alphabet romain. Nous noterons les propositions et les ensembles de faits en utilisant les majuscules de l'alphabet romain.
Déf. II. 2 (Valuation) Soit les valeurs de vérité, une valuation est une application . Cette application est étendue en une application unique par les égalités :
Déf. II. 3 (Équivalence) Soient deux propositions éléments de est équivalente à (notée ) si et seulement si pour toute valuation .
Question II. 1 Montrer que .
Déf. II. 4 (Tautologie) Soit une proposition est une tautologie si et seulement si .
Déf. II. 5 (Proposition absurde) Soit une proposition est absurde si et seulement si .
Déf. II. 6 (Littéral) Un littéral est une proposition qui prend l'une des formes suivantes :
un fait (littéral positif);
la négation d'un fait (littéral négatif).
Déf. II. 7 (Clause, clause duale) Une clause est une disjonction de littéraux deux à deux distincts. Une clause duale est une conjonction de littéraux deux à deux distincts.
Exemple II. a est une clause. est une clause duale.
Déf. II. 8 (Forme conjonctive, disjonctive) Une forme conjonctive est une conjonction de clauses. Une forme disjonctive est une disjonction de clauses duales.
Exemple II. est une forme conjonctive. est une forme disjonctive.
Question II. 2 Soit la proposition , transformer en une forme conjonctive , puis en une forme disjonctive telles que . Vous utiliserez pour cela les formules de De Morgan.
2 Représentation et codage d'un ensemble de faits
La représentation et les opérations de manipulation des bases de connaissances reposent sur la structure d'ensemble. Nous allons dans une première étape étudier un codage de cette structure qui contiendra des faits. Cette structure sera ensuite adaptée aux connaissances.
2.1 Codage d'un fait
Un fait est représenté par le type de base string.
type fait == string;;
2.2 Codage d'un ensemble de faits
Nous allons utiliser un codage extrêmement simple : un ensemble est une liste contenant exactement un exemplaire de chaque élément contenu dans l'ensemble. Les opérations de manipulation d'un ensemble devront préserver cette propriété.
Un ensemble de faits est représenté par le type faits équivalent à une liste de fait.
type faits == fait list;;
Le parcours d'un ensemble sera donc effectué de la même manière que celui d'une liste.
Nous allons maintenant définir plusieurs opérations sur les ensembles de faits qui pourront être utilisées dans la suite du sujet. Ces opérations seront ensuite étendues aux ensembles de connaissances.
Nous supposons que toutes les listes représentant des ensembles, qui sont passées comme paramètres des fonctions, ne contiennent au plus qu'une fois chaque élément.
2.3 Opération sur la structure d'ensemble
Pour les calculs de complexité, nous noterons la taille de l'ensemble , c'est-à-dire le nombre de faits qu'il contient.
2.3.1 Appartenance à un ensemble
Une première opération consiste à tester l'appartenance d'un fait à un ensemble.
Question II. 3 Écrire en CaML une fonction appartenance de type fait -> faits -> bool telle que l'appel (appartenance ) renvoie la valeur true si l'ensemble contient le fait et la valeur false sinon. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Question II. 4 Donner un exemple de valeurs des paramètres et de la fonction appartenance qui correspond au pire cas en nombre d'appels récursifs effectués.
Calculer une estimation de la complexité dans le pire cas de la fonction appartenance en fonction de la taille de l'ensemble E. Cette estimation ne prendra en compte que le nombre d'appels récursifs effectués.
2.3.2 Ajout dans un ensemble
La deuxième opération est l'ajout d'un fait à un ensemble.
Question II. 5 Écrire en CaML une fonction ajout de type fait -> faits -> faits telle que l'appel (ajout ) renvoie un ensemble contenant les mêmes faits que l'ensemble ainsi que le fait s'il ne figurait pas déjà dans E. L'ensemble renvoyé contiendra exactement une fois le fait . Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
2.3.3 Inclusion entre deux ensembles
La troisième opération est le test d'inclusion du contenu de deux ensembles.
Question II. 6 Écrire en CaML une fonction inclusion de type faits -> faits -> bool telle que l'appel (inclusion E1 E2) renvoie la valeur true si l'ensemble E2 contient au moins les mêmes faits que l'ensemble E1 et la valeur false sinon. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Question II. 7 Donner un exemple de valeurs des paramètres E1 et E2 de la fonction inclusion qui correspond au pire cas en nombre d'appels récursifs effectués.
Calculer une estimation de la complexité dans le pire cas de la fonction inclusion en fonction des tailles des ensembles E1 et E2. Cette estimation ne prendra en compte que le nombre d'appels récursifs effectués.
2.3.4 Égalité entre deux ensembles
La quatrième opération est le test d'égalité du contenu de deux ensembles.
Question II. 8 Écrire en CaML une fonction egalite de type faits -> faits -> bool telle que l'appel (egalite E1 E2) renvoie la valeur true si les deux ensembles E1 et E2 contiennent exactement les mêmes faits et la valeur false sinon. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
2.3.5 Soustraction de deux ensembles
La dernière opération étudiée est la construction d'un ensemble résultant de la soustraction d'un ensemble depuis un autre ensemble.
Question II. 9 Écrire en CaML une fonction soustraction de type faits -> faits -> faits telle que l'appel (soustraction E1 E2) renvoie un ensemble contenant les faits qui sont contenus dans E1 et ne sont pas contenus dans E2. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
2.3.6 Autres opérations prédéfinies
Nous supposons prédéfinies les fonctions suivantes pour les ensembles, dont le calcul se termine quelles que soient les valeurs de leurs paramètres. Elles pourront éventuellement être utilisées dans les réponses aux questions:
union : faits -> faits -> faits telle que l'appel (union E1 E2) renvoie un ensemble contenant les faits contenus dans E1 ainsi que les faits contenus dans E2 ;
intersection : faits -> faits -> faits telle que l'appel (intersection E1 E2) renvoie un ensemble contenant les faits contenus à la fois dans E1 et dans E2.
3 Représentation et codage d'une connaissance
3.1 Représentation d'une connaissance
Déf. II. 9 (Connaissance) Une connaissance notée est composée de deux ensembles finis de faits (ou variables propositionnelles): les hypothèses et les conclusions .
Nous noterons les connaissances en utilisant les minuscules de l'alphabet grec.
Déf. II. 10 (Interprétation logique) L'interprétation logique, notée , d'une connaissance est:
Intuitivement, elle signifie que sous les hypothèses de , nous pouvons déduire une des conclusions de . permet de traiter le cas . permet de traiter le cas . Notons que:
Exemple II. 3 Les formules logiques suivantes sont des connaissances:
Question II. 10 Soit une connaissance quelconque, donner une clause telle que .
Déf. II. 11 (Connaissance absurde) Une connaissance est absurde si et seulement si son interprétation est absurde.
Question II. 11 Montrer que la seule connaissance absurde est .
3.2 Codage d'une connaissance
Pour les variables ou les constantes dont le nom est pris dans l'alphabet grec ( ), l'identifiant en CaML sera leur nom en toute lettre (gamma, ...).
Une connaissance est représentée par le type connaissance équivalent à un couple composé de deux ensembles de faits.
type connaissance == faits * faits ;;
Question II. 12 Écrire en CaML une fonction comparaison de type connaissance -> connaissance -> bool telle que l'appel (comparaison gamma1 gamma2) renvoie la valeur true si les deux connaissances gamma1 et gamma2 contiennent exactement les mêmes hypothèses et conclusions et la valeur false sinon. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
4 Représentation et codage d'une base de connaissances
4.1 Représentation d'une base de connaissances
Déf. II. 12 (Base de connaissances) Une base de connaissances est un ensemble fini de connaissances .
Nous noterons les bases de connaissances en utilisant les majuscules de l'alphabet grec.
Déf. II. 13 (Interprétation logique) L'interprétation logique, notée , d'une base est définie par:
Elle correspond à la conjonction des interprétations logiques de chaque connaissance.
Notons que: .
Question II. 13 Soit avec une base de connaissances quelconque, donner une forme conjonctive telle que .
Déf. II. 14 (Équivalence) Soient deux bases et est équivalente à (notée ) si et seulement si .
4.2 Codage d'une base de connaissances
Une base de connaissances est représentée par le type base équivalent à une liste de connaissances.
type base == connaissance list;;
Exemple II. 4 La base composée des connaissances de l'exemple II. 3 sera représentée par la valeur :
[
( [ "a" ] , [ "b" ] ) ;
( [ "a" ; "c" ] , [] ) ;
( [ ] , [ "b" ; "d" ] )
]
Une base est un ensemble de connaissances. Il est donc nécessaire d'adapter les opérations définies dans la sous-section 2.2 sur les ensembles de faits.
Nous supposons prédéfinies les fonctions suivantes pour les bases, dont le calcul se termine quelles que soient les valeurs de leurs paramètres. Elles pourront éventuellement être utilisées dans les réponses aux questions:
appartenanceB : connaissance -> base -> bool
ajoutB : connaissance -> base -> base
inclusionB : base -> base -> bool
egaliteB : base -> base -> bool
unionB : base -> base -> base
intersectionB : base -> base -> base
soustractionB : base -> base -> base
5 Élimination des tautologies
Une base de connaissances peut contenir des connaissances inutiles, c'est-à-dire qui n'apportent aucune information pertinente lors d'une interrogation, par exemple les tautologies. Pour réduire la taille de la base et les coûts de l'opération d'interrogation, nous nous intéressons à l'élimination des tautologies.
Déf. II. 15 (Tautologie) Une connaissance est une tautologie si et seulement si son interprétation est une tautologie.
Question II. 14 Quelles sont les tautologies parmi les connaissances suivantes (justifier vos réponses) :
Question II. 15 Donner une relation entre les hypothèses et les conclusions d'une connaissance qui soit une condition nécessaire et suffisante pour que cette connaissance soit une tautologie. Donner une preuve de cette condition.
Nous supposons prédéfinie la fonction tautologie de type connaissance -> bool telle que l'appel (tautologie gamma) renvoie la valeur true si la connaissance gamma est une tautologie et la valeur false sinon. Son calcul se termine quelles que soient les valeurs de son paramètre. Elle pourra éventuellement être utilisée dans les réponses aux questions.
Question II. 16 Soit une base et une tautologie, montrer que .
Déf. II. 16 Soit une base, nous noterons ] [ la base privée de ses tautologies, c'est-à-dire:
Nous pouvons déduire de la question II. 16 que .
Question II. 17 Écrire en CaML une fonction elimination de type base -> base telle que l'appel (elimination Omega) renvoie une base de connaissances contenant les mêmes connaissances que [. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
6 Minimisation d'une base de connaissances
Une base de connaissances peut contenir des connaissances redondantes, en particulier, elle peut contenir des connaissances plus générales que d'autres. Pour réduire la taille de la base et les coûts de l'opération d'interrogation, nous nous intéressons à la minimisation de la base, c'est-à-dire à ne conserver que les connaissances les plus générales.
Déf. II. 17 Une connaissance est dite plus générale qu'une connaissance si et seulement si et . Cette relation sera notée .
Question II. 18 Donner les relations entre les connaissances suivantes:
Question II. 19 Soient deux connaissances et , montrer que les bases et sont équivalentes si et seulement si . Pour cela, vous pouvez considérer une valuation et envisager les différents cas possibles.
Déf. II. 18 (Base minimale) Soit une base de connaissance, la base minimale associée à est définie par:
Nous pouvons déduire de la question II. 19 que .
Question II. 20 Écrire en CaML une fonction absorbable de type connaissance -> base -> bool telle que l'appel (absorbable gamma Omega) renvoie la valeur true si la base Omega contient une connaissance plus générale que gamma et la valeur false sinon. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Nous supposons prédéfinie la fonction minimisation de type base -> base telle que l'appel (minimisation Omega) renvoie . Son calcul se termine quelles que soient les valeurs de son paramètre. Elle pourra éventuellement être utilisée dans les réponses aux questions.
7 Complétion d'une base de connaissances
La complétion d'une base de connaissances consiste à construire l'ensemble de toutes les connaissances qui peuvent être déduites d'une base donnée. Cette opération permet ensuite de réduire les coûts d'interrogation de la base.
Déf. II. 19 (Déduction de connaissances) Soient les connaissances et , l'opérateur de déduction de connaissances construit une base notée et définie par:
Notons que si .
L'ensemble des connaissances qui peuvent être déduites d'une base est l'ensemble des connaissances construites par application d'un nombre quelconque de fois de l'opérateur à partir des connaissances de .
Question II. 21 Appliquer l'opérateur sur les connaissances suivantes (ne donner que les résultats différents de ) :
Question II. 22 Soient les connaissances et , montrer que si alors ne contient que des tautologies. Que peut-on en conclure?
La composition d'une connaissance et d'une base consiste à appliquer l'opérateur de déduction sur et sur chaque connaissance de .
Nous souhaitons écrire une fonction composition qui prend en paramètre une connaissance et une base et qui construit une nouvelle base contenant les connaissances résultant de la composition de gamma avec chaque connaissance de la base Omega. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Question II. 23 Décrire cette fonction composition et expliquer son algorithme selon le format présenté en page 4.
Question II. 24 Écrire en CaML cette fonction composition de type connaissance -> base -> base telle que l'appel (composition gamma Omega) renvoie une base contenant les connaissances résultant de la composition de gamma avec les connaissances de la base Omega. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Nous supposons prédéfinie la fonction deduction de type base -> base telle que l'appel (deduction Omega) renvoie une base de connaissances qui contient les connaissances de la base Omega ainsi que le résultat des compositions deux à deux des connaissances de Omega. Son calcul se termine quelles que soient les valeurs de son paramètre. Elle pourra éventuellement être utilisée dans les réponses aux questions.
Question II. 25 Soient deux connaissances et telles que , montrer que les bases et sont équivalentes.
Question II. 26 Soit une base de connaissances quelconque , soit la suite définie par:
Nous admettrons que le résultat de la question II. 25 peut être étendu à: .
Montrer que la suite est croissante;
Montrer que: (soit , nous noterons alors et nous appelerons la complétion de la base );
Montrer que .
Question II. 27 Calculer la complétion de la base contenant les connaissances suivantes : .
L'élimination des tautologies et la minimisation de la base obtenue permettent ensuite de réduire la taille de la base et les coûts d'interrogation.
Question II. 28 Éliminer les tautologies et minimiser la réponse que vous avez proposée pour la question précédente.
Nous souhaitons écrire une fonction completion qui prend en paramètre une base et qui construit une nouvelle base contenant les mêmes connaissances que . Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Question II. 29 Décrire cette fonction completion et expliquer son algorithme selon le format présenté en page 4.
Question II. 30 Écrire en CaML cette fonction completion de type base -> base telle que l'appel (completion Omega) renvoie une base de connaissances contenant les mêmes connaissances que . Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
8 Interrogation d'une base
Les connaissances contenues dans la base établissent un lien entre des faits << hypothèses >> et des faits << conclusions >>. Intuitivement, l'interrogation de la base consiste à:
compléter la base (voir section 7), minimiser la base complétée (voir section 6) et en éliminer les tautologies (voir section 5);
fournir une liste de faits vrais et une liste de faits faux ;
intégrer ces faits dans la base complétée;
rendre la base obtenue minimale (voir section 6) pour obtenir la réponse à la requête.
Définissons ceci formellement:
Déf. II. 20 (Interrogation d'une base) Soit une base , la réponse à la requête composée des faits vrais et des faits faux est la base définie par:
Question II. 31 Soit la base de connaissances proposée à la question II.27, construire la réponse à la requête .
Question II. 32 Montrer que .
Question II. 33 Montrer que .
Question II. 34 Écrire en CaML une fonction interrogation de type faits -> faits -> base -> base telle que l'appel (interrogation V F Omega) renvoie une base de connaissances contenant les mêmes connaissances que . Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Partie II : Algorithmique et programmation en PASCAL
Cette partie doit être traitée par les étudiants qui ont utilisé le langage PASCAL dans le cadre des enseignements d'informatique. Les fonctions écrites devront être récursives ou faire appel à des fonctions auxiliaires récursives. Elles ne devront pas utiliser d'instructions itératives (for, while, repeat,...).
Format de desciption d'une fonction: La description d'une fonction, lorsque celle-ci est demandée, c'est-à-dire aux questions II. 23 et II.29, doit au moins contenir:
L'objectif général;
Le rôle des paramètres de la fonction;
Les contraintes sur les valeurs des paramètres;
Les caractéristiques du résultat renvoyé par la fonction;
Le rôle des variables locales à la fonction;
Le principe de l'algorithme;
Des arguments de terminaison du calcul pour toutes les valeurs des paramètres qui vérifient les contraintes présentées au point 3.
L'objectif de ce problème est l'étude d'une stratégie complète et cohérente d'interrogation d'une base de connaissances. Une base de connaissances est une représentation de relations logiques existant entre des faits. Cette stratégie repose sur un algorithme de construction d'une base complète, cohérente et minimale. Cet algorithme qui préserve le contenu logique de la base est généralement appelé complétion de la base.
1 Préliminaire: Calcul des propositions
La représentation d'une base de connaissances repose sur le calcul des propositions.
Déf. II. 1 (Propositions) Soit un ensemble dénombrable de symboles, appelés faits (ou variables propositionnelles), soient les constantes vrai et faux notées , soit l'opérateur unaire (négation), soient les opérateurs binaires (disjonction), (conjonction), (implication); l'ensemble des propositions est le plus petit ensemble tel que: ;
si alors ;
si et op alors op ;
les propositions de sont finies, c'est-à-dire obtenues par application d'un nombre fini de fois des règles précédentes.
Nous noterons les faits en utilisant les minuscules de l'alphabet romain. Nous noterons les propositions et les ensembles de faits en utilisant les majuscules de l'alphabet romain.
Déf. II. 2 (Valuation) Soit les valeurs de vérité, une valuation est une application . Cette application est étendue en une application unique par les égalités :
Déf. II. 3 (Équivalence) Soient deux propositions éléments de est équivalente à (notée ) si et seulement si pour toute valuation .
Question II. 1 Montrer que .
Déf. II. 4 (Tautologie) Soit une proposition est une tautologie si et seulement si .
Déf. II. 5 (Proposition absurde) Soit une proposition est absurde si et seulement si .
Déf. II. 6 (Littéral) Un littéral est une proposition qui prend l'une des formes suivantes :
un fait (littéral positif);
la négation d'un fait (littéral négatif).
Déf. II. 7 (Clause, clause duale) Une clause est une disjonction de littéraux deux à deux distincts. Une clause duale est une conjonction de littéraux deux à deux distincts.
Exemple II. a est une clause. est une clause duale.
Déf. II. 8 (Forme conjonctive, disjonctive) Une forme conjonctive est une conjonction de clauses. Une forme disjonctive est une disjonction de clauses duales.
Exemple II. est une forme conjonctive. est une forme disjonctive.
Question II. 2 Soit la proposition , transformer en une forme conjonctive , puis en une forme disjonctive telles que . Vous utiliserez pour cela les formules de De Morgan.
2 Représentation et codage d'un ensemble de faits
La représentation et les opérations de manipulation des bases de connaissances reposent sur la structure d'ensemble. Nous allons dans une première étape étudier un codage de cette structure qui contiendra des faits. Cette structure sera ensuite adaptée aux connaissances.
2.1 Codage d'un fait
Un fait est représenté par le type de base STRING.
2.2 Codage d'un ensemble de faits
Nous allons utiliser un codage extrêmement simple: un ensemble est une liste contenant exactement un exemplaire de chaque élément contenu dans l'ensemble. Les opérations de manipulation d'un ensemble devront préserver cette propriété.
Un ensemble de faits est représenté par le type de base FAITS correspondant à une liste de faits.
Le parcours d'un ensemble sera donc effectué de la même manière que celui d'une liste.
Nous supposons prédéfinies les constantes et les fonctions suivantes dont le calcul se termine quelles que soient les valeurs de leurs paramètres. Elles pourront éventuellement être utilisées dans les réponses aux questions:
NIL représente la liste vide de faits;
FUNCTION LF_Ajout(f:FAIT;E:FAITS):FAITS; renvoie une liste de faits composée d'un premier fait et du reste de la liste contenu dans ;
FUNCTION LF_Premier (E:FAITS) : FAIT; renvoie le premier fait de la liste E. Cette liste ne doit pas être vide;
FUNCTION LF_Reste(E:FAITS) : FAITS; renvoie le reste de la liste E privée de son premier fait. Cette liste ne doit pas être vide;
FUNCTION LF_Juxtaposition(E1:FAITS;E2:FAITS):FAITS; renvoie la liste composée de la liste E1 suivie de la liste E2.
Nous allons maintenant définir plusieurs opérations sur les ensembles de faits qui pourront être utilisées dans la suite du sujet. Ces opérations seront ensuite étendues aux ensembles de connaissances.
Nous supposons que toutes les listes représentant des ensembles, qui sont passées comme paramètres des fonctions, ne contiennent au plus qu'une fois chaque élément.
2.3 Opération sur la structure d'ensemble
Pour les calculs de complexité, nous noterons la taille de l'ensemble , c'est-à-dire le nombre de faits qu'il contient.
2.3.1 Appartenance à un ensemble
Une première opération consiste à tester l'appartenance d'un fait à un ensemble.
Question II. 3 Écrire en PASCAL une fonction
appartenance( :FAIT;E:FAITS) :BOOLEAN; telle que l'appel appartenance( ) renvoie la valeur TRUE si l'ensemble contient le fait et la valeur FALSE sinon. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Question II. 4 Donner un exemple de valeurs des paramètres et de la fonction appartenance qui correspond au pire cas en nombre d'appels récursifs effectués.
Calculer une estimation de la complexité dans le pire cas de la fonction appartenance en fonction de la taille de l'ensemble E. Cette estimation ne prendra en compte que le nombre d'appels récursifs effectués.
2.3.2 Ajout dans un ensemble
La deuxième opération est l'ajout d'un fait à un ensemble.
Question II. 5 Écrire en PASCAL une fonction ajout(f:FAIT;E:FAITS) : FAITS; telle que l'appel ajout ( ) renvoie un ensemble contenant les mêmes faits que l'ensemble ainsi que le fait s'il ne figurait pas déjà dans . L'ensemble renvoyé contiendra exactement une fois le fait . Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
2.3.3 Inclusion entre deux ensembles
La troisième opération est le test d'inclusion du contenu de deux ensembles.
Question II. 6 Écrire en PASCAL une fonction
inclusion(E1:FAITS;E2:FAITS) :BOOLEAN; telle que l'appel
inclusion(E1,E2) renvoie la valeur TRUE si l'ensemble E2 contient au moins les mêmes faits que l'ensemble E1 et la valeur FALSE sinon. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Question II. 7 Donner un exemple de valeurs des paramètres E1 et E2 de la fonction inclusion qui correspond au pire cas en nombre d'appels récursifs effectués.
Calculer une estimation de la complexité dans le pire cas de la fonction inclusion en fonction des tailles des ensembles E1 et E2. Cette estimation ne prendra en compte que le nombre d'appels récursifs effectués.
2.3.4 Égalité entre deux ensembles
La quatrième opération est le test d'égalité du contenu de deux ensembles.
Question II. 8 Écrire en PASCAL une fonction
egalite(E1:FAITS;E2:FAITS) :BOOLEAN; telle que l'appel egalite(E1,E2) renvoie la valeur TRUE si les deux ensembles E1 et E2 contiennent exactement les mêmes faits et la valeur FALSE sinon. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
2.3.5 Soustraction de deux ensembles
La dernière opération étudiée est la construction d'un ensemble résultant de la soustraction d'un ensemble depuis un autre ensemble.
Question II. 9 Écrire en PASCAL une fonction
soustraction(E1:FAITS;E2:FAITS) :FAITS; telle que l'appel
soustraction(E1,E2) renvoie un ensemble contenant les faits qui sont contenus dans E1 et
ne sont pas contenus dans E2. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
2.3.6 Autres opérations prédéfinies
Nous supposons prédéfinies les fonctions suivantes pour les ensembles, dont le calcul se termine quelles que soient les valeurs de leurs paramètres. Elles pourront éventuellement être utilisées dans les réponses aux questions:
union(E1:FAITS;E2:FAITS) :FAITS; renvoie un ensemble contenant les faits contenus dans E1 ainsi que les faits contenus dans E2;
intersection(E1:FAITS;E2:FAITS) :FAITS; renvoie un ensemble contenant les faits contenus à la fois dans E1 et dans E2.
3 Représentation et codage d'une connaissance
3.1 Représentation d'une connaissance
Déf. II. 9 (Connaissance) Une connaissance notée est composée de deux ensembles finis de faits (ou variables propositionnelles): les hypothèses et les conclusions .
Nous noterons les connaissances en utilisant les minuscules de l'alphabet grec.
Déf. II. 10 (Interprétation logique) L'interprétation logique, notée , d'une connaissance est:
Intuitivement, elle signifie que sous les hypothèses de , nous pouvons déduire une des conclusions de . permet de traiter le cas . permet de traiter le cas . Notons que:
Exemple II. 3 Les formules logiques suivantes sont des connaissances:
Question II. 10 Soit une connaissance quelconque, donner une clause telle que .
Déf. II. 11 (Connaissance absurde) Une connaissance est absurde si et seulement si son interprétation
est absurde.
Question II. 11 Montrer que la seule connaissance absurde est .
3.2 Codage d'une connaissance
Pour les variables ou les constantes dont le nom est pris dans l'alphabet grec ( ), l'identifiant en PASCAL sera leur nom en toute lettre (gamma, ...).
Une connaissance est représentée par le type de base CONNAISSANCE correspondant à un couple composé de deux ensembles de faits.
Nous supposons prédéfinies les constantes et les fonctions suivantes dont le calcul se termine quelles que soient les valeurs de leurs paramètres. Elles pourront éventuellement être utilisées dans les réponses aux questions:
FUNCTION C_Creer(H:FAITS;C:FAITS):CONNAISSANCE; renvoie une connaissance dont les hypothèses sont les faits de l'ensemble H et les conclusions sont les faits de l'ensemble C;
FUNCTION C_Hypotheses(gamma:CONNAISSANCE):FAITS; renvoie les hypothèses de la connaissance gamma,
FUNCTION C_Conclusions(gamma:CONNAISSANCE):FAITS; renvoie les conclusions de la connaissance gamma.
Question II. 12 Écrire en PASCAL une fonction
comparaison(gamma1:CONNAISSANCE;gamma2:CONNAISSANCE) : BOOLEAN; telle que l'appel comparaison(gamma1, gamma2) renvoie la valeur TRUE si les deux connaissances gamma1 et gamma2 contiennent exactement les mêmes hypothèses et conclusions et la valeur FALSE sinon. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
4 Représentation et codage d'une base de connaissances
4.1 Représentation d'une base de connaissances
Déf. II. 12 (Base de connaissances) Une base de connaissances est un ensemble fini de connaissances .
Nous noterons les bases de connaissances en utilisant les majuscules de l'alphabet grec.
Déf. II. 13 (Interprétation logique) L'interprétation logique, notée , d'une base est définie par :
Elle correspond à la conjonction des interprétations logiques de chaque connaissance. Notons que: .
Question II. 13 Soit avec une base de connaissances quelconque, donner une forme conjonctive telle que .
Déf. II. 14 (Équivalence) Soient deux bases et est équivalente à (notée ) si et seulement si .
4.2 Codage d'une base de connaissances
Une base de connaissances est représentée par le type de base BASE correspondant à une liste de connaissances.
Nous supposons prédéfinies les constantes et les fonctions suivantes dont le calcul se termine quelles que soient les valeurs de leurs paramètres. Elles pourront éventuellement être utilisées dans les réponses aux questions:
NIL représente la liste vide de connaissances;
FUNCTION B_Ajout(gamma:CONNAISSANCE;Omega:BASE):BASE; renvoie une liste de connaissances composée d'une première connaissance gamma et du reste de la liste contenu dans Omega;
FUNCTION B_Premier(Omega:BASE):CONNAISSANCE; renvoie la première connaissance de la liste Omega. Cette liste ne doit pas être vide;
FUNCTION B_Reste(Omega:BASE):BASE; renvoie le reste de la liste Omega privée de sa première connaissance. Cette liste ne doit pas être vide;
FUNCTION B_Juxtaposition(Omega1:BASE;Omega2:BASE):BASE; renvoie la liste composée de la liste Omega1 suivie de la suite Omega2.
Exemple II. 4 La base composée des connaissances de l'exemple II. 3 sera représentée par la valeur: B_Ajout (
C_Creer( LF_Ajout( "a", NIL), LF_Ajout( "b", NIL ) ),
B_Ajout (
C_Creer( LF_Ajout( "a", LF_Ajout( "c", NIL)), NIL),
B_Ajout (
C_Creer( NIL, LF_Ajout( "b", LF_Ajout( "d", NIL))),
NIL)))
Une base est un ensemble de connaissances. Il est donc nécessaire d'adapter les opérations définies dans la sous-section 2.2 sur les ensembles de faits.
Nous supposons prédéfinies les fonctions suivantes pour les bases, dont le calcul se termine quelles que soient les valeurs de leurs paramètres. Elles pourront éventuellement être utilisées dans les réponses aux questions:
Une base de connaissances peut contenir des connaissances inutiles, c'est-à-dire qui n'apportent aucune information pertinente lors d'une interrogation, par exemple les tautologies. Pour réduire la taille de la base et les coûts de l'opération d'interrogation, nous nous intéressons à l'élimination des tautologies.
Déf. II. 15 (Tautologie) Une connaissance est une tautologie si et seulement si son interprétation est une tautologie.
Question II. 14 Quelles sont les tautologies parmi les connaissances suivantes (justifier vos réponses):
Question II. 15 Donner une relation entre les hypothèses et les conclusions d'une connaissance qui soit une condition nécessaire et suffisante pour que cette connaissance soit une tautologie. Donner une preuve de cette condition.
Nous supposons prédéfinie la fonction tautologie(gamma: CONNAISSANCE) : BOOLEAN; telle que l'appel tautologie(gamma) renvoie la valeur TRUE si la connaissance gamma est une tautologie et la valeur FALSE sinon. Son calcul se termine quelles que soient les valeurs de son paramètre. Elle pourra éventuellement être utilisée dans les réponses aux questions.
Question II. 16 Soit une base et une tautologie, montrer que .
Déf. II. 16 Soit une base, nous noterons ] [ la base privée de ses tautologies, c'est-à-dire :
Nous pouvons déduire de la question II. 16 que .
Question II. 17 Écrire en PASCAL une fonction elimination(Omega : BASE ) : BASE; telle que l'appel elimination( Omega ) renvoie une base de connaissances contenant les mêmes connaissances que [. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
6 Minimisation d'une base de connaissances
Une base de connaissances peut contenir des connaissances redondantes, en particulier, elle peut contenir des connaissances plus générales que d'autres. Pour réduire la taille de la base et les coûts de l'opération d'interrogation, nous nous intéressons à la minimisation de la base, c'est-à-dire à ne conserver que les connaissances les plus générales.
Déf. II. 17 Une connaissance est dite plus générale qu'une connaissance si et seulement si et . Cette relation sera notée .
Question II. 18 Donner les relations entre les connaissances suivantes :
Question II. 19 Soient deux connaissances et , montrer que les bases et sont équivalentes si et seulement si . Pour cela, vous pouvez considérer une valuation et envisager les différents cas possibles.
Déf. II. 18 (Base minimale) Soit une base de connaissance, la base minimale associée à est définie par:
Nous pouvons déduire de la question II. 19 que .
Question II. 20 Écrire en PASCAL une fonction
absorbable(gamma: CONNAISSANCE;Omega:BASE) :BOOLEAN; telle que
l'appel absorbable(gamma, Omega) renvoie la valeur TRUE si la base Omega contient une connaissance plus générale que gamma et la valeur FALSE sinon. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Nous supposons prédéfinie la fonction minimisation(Omega:BASE) : BASE ; telle que l'appel minimisation(Omega) renvoie une base de connaissances contenant les mêmes connaissances que . Son calcul se termine quelles que soient les valeurs de son paramètre. Elle pourra éventuellement être utilisée dans les réponses aux questions.
7 Complétion d'une base de connaissances
La complétion d'une base de connaissances consiste à construire l'ensemble de toutes les connaissances qui peuvent être déduites d'une base donnée. Cette opération permet ensuite de réduire les coûts d'interrogation de la base.
Déf. II. 19 (Déduction de connaissances) Soient les connaissances et , l'opérateur de déduction de connaissances construit une base notée et définie par:
Notons que si .
L'ensemble des connaissances qui peuvent être déduites d'une base est l'ensemble des connaissances construites par application d'un nombre quelconque de fois de l'opérateur à partir des connaissances de .
Question II. 21 Appliquer l'opérateur sur les connaissances suivantes (ne donner que les résultats différents de ) :
Question II. 22 Soient les connaissances et , montrer que si alors ne contient que des tautologies. Que peut-on en conclure?
La composition d'une connaissance et d'une base consiste à appliquer l'opérateur de déduction sur et sur chaque connaissance de .
Nous souhaitons écrire une fonction composition qui prend en paramètre une connaissance et une base et qui construit une nouvelle base contenant les connaissances résultant de la composition de gamma avec chaque connaissance de la base Omega. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Question II. 23 Décrire cette fonction composition et expliquer son algorithme selon le format présenté en page 15.
Question II. 24 Écrire en PASCAL cette fonction composition(gamma: CONNAISSANCE; Omega: BASE ) : BASE; telle que l'appel composition(gamma, Omega) renvoie une base contenant les connaissances résultant de la composition de gamma avec les connaissances de la base Omega. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Nous supposons prédéfinie la fonction deduction(Omega:BASE) : BASE; telle que l'appel deduction(Omega) renvoie une base de connaissances qui contient les connaissances de la base Omega ainsi que le résultat des compositions deux à deux des connaissances de Omega. Son calcul se termine quelles que soient les valeurs de son paramètre. Elle pourra éventuellement être utilisée dans les réponses aux questions.
Question II. 25 Soient deux connaissances et telles que , montrer que les bases et sont équivalentes.
Question II. 26 Soit une base de connaissances quelconque , soit la suite définie par:
Nous admettrons que le résultat de la question II. 25 peut être étendu à: .
Montrer que la suite est croissante;
Montrer que: (soit , nous noterons alors et nous appelerons la complétion de la base );
Montrer que .
Question II. 27 Calculer la complétion de la base contenant les connaissances suivantes : .
L'élimination des tautologies et la minimisation de la base obtenue permettent ensuite de réduire la taille de la base et les coûts d'interrogation.
Question II. 28 Éliminer les tautologies et minimiser la réponse que vous avez proposée pour la question précédente.
Nous souhaitons écrire une fonction completion qui prend en paramètre une base et qui construit une nouvelle base contenant les mêmes connaissances que . Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Question II. 29 Décrire cette fonction completion et expliquer son algorithme selon le format présenté en page 15.
Question II. 30 Écrire en PASCAL cette fonction completion(Omega : BASE ) : BASE; telle que l'appel completion(Omega) renvoie une base de connaissances contenant les mêmes connaissances que . Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
8 Interrogation d'une base
Les connaissances contenues dans la base établissent un lien entre des faits << hypothèses >> et des faits << conclusions >>. Intuitivement, l'interrogation de la base consiste à:
compléter la base (voir section 7), minimiser la base complétée (voir section 6) et en éliminer les tautologies (voir section 5);
fournir une liste de faits vrais et une liste de faits faux ;
intégrer ces faits dans la base complétée ;
rendre la base obtenue minimale (voir section 6) pour obtenir la réponse à la requête.
Définissons ceci formellement:
Déf. II. 20 (Interrogation d'une base) Soit une base , la réponse à la requête composée des faits vrais et des faits faux est la base définie par:
Question II. 31 Soit la base de connaissances proposée à la question II.27, construire la réponse à la requête .
Question II. 32 Montrer que .
Question II. 33 Montrer que .
Question II. 34 Écrire en PASCAL une fonction
interrogation(V:FAITS;F:FAITS;Omega:BASE) :BASE; telle que l'appel
interrogation( , Omega ) renvoie une base de connaissances contenant les mêmes connaissances que . Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Fin de l'énoncé
CCINP Option Informatique MP 2004 - Version Web LaTeX | WikiPrépa | WikiPrépa
