Résumé "Intelligence artificielle" (c) 2003-01-28 Fabian M. Suchanek http://suchanek.name/texts/summaries/ia.txt Ceci est le résumé des cours du module "Intelligence artificielle" donnés par Mme Zara, M Lemaire et M Gensel en hiver 2002 à l'Université Pierre-Mendès-France Grenoble. (Since this text is supposed to be in French, I could not avoid using non-ASCII characters, sorry for that to all foreign readers) Le résumé reprend le méta-langage de programmation des cours, qui est utilisé d'une manière très conséquente dans tous les polycopiés. Le lecteur, en lisant le texte ci-dessous, accepte que l'auteur décline toute responsabilité concernant des informations fausses ou incomplètes. Si quelqu'un trouve une faute, je lui serais reconnaissant de bien vouloir me le dire. C'est le seul moyen de profiter moi-même de la publication de ce résumé. Mon e-mail est f.m.suchanek@zweb.de, mais il faut effacer la lettre 'z' dans l'adresse. ===================================================================== Introduction et Révision ===================================================================== cf aussi ai.txt (en anglais) cf aussi infod.txt (en allemand) cf aussi fol.txt (en allemand) cf aussi maths.txt (en francais) cf aussi gc.txt (en francais) Suite, Tuple: Une collection rangée d'éléments. v = (v[1], v[2], ... v[n]) Vecteur: Un tuple de nombres réels. Un vecteur peut être représenté dans un système de coordonnées par un flèche qui part de l'origine et va jusqu'au point indiqué par les éléments du vecteur. Annotation: Pour une définition plus générale, cf maths.txt Matrice: Un tuple de vecteurs qui ont le même nombre d'éléments -- donc un tableau. Couple: Un tuple de deux éléments. Triplet: Un tuple de trois éléments. Algorithme: Une suite finie d'instructions. Programme: Un algorithme (codé) qui peut être effectué par un ordinateur. Chaîne: Une suite de symboles, d'ordinaire notée sans les parenthèses et les virgules et parfois entourée par des guillemets. Exemple: "Salut" Langage: Un sous ensemble de toutes les chaînes. Intelligence artificielle: La théorie des problèmes pour lesquels il n'y a pas de solution algorithmique. Ensemble: Une collection non rangée d'éléments non identiques. M = {x1, x2, ..., xn} est l'ensemble de x1 x2, ... xn M = {x | f(x) } est l'ensemble de tous les x pour lesquels f(x) est vrai Cardinalité d'un ensemble: Le nombre de ses éléments. card(M) = nombre des éléments de M Sous ensemble d'un ensemble M: Un ensemble T tel que tous les éléments appartenant à T appartiennent à M. On dit que T est inclu dans M. T < M Intervalle des bornes a et b: L'ensemble des nombres réels entre a et b. [a,b] = {x | x réel et x>=a et x= B f(a)=b, où a appartient à A et b appartient à B f(a1,a2)=b a1 f a2 = b Paramètre: Un élément qu'on donne à une fonction. Union: L'application "\/" qui prend deux ensembles X et Y et redonne l'ensemble qui contient les élements qui appartiennent à X ou à Y ou à tous les deux. Intersection: L'application "/\" qui prend deux ensembles X et Y et redonne l'ensemble qui contient exactement les élements qui appartiennent à X et à Y. Arbre: Un élément et une suite d'arbres. La suite peut être vide. Chaque arbre de cette suite est appelé un "enfant", l'élément est appelé "noeud". Exemple: N1 / | \ N2 N3 N4 | \ \ N5 N6 N7 Degré d'un noeud: Le nombre de ses enfants. Exemple: Le degré de N1 dans l'arbre de ci-dessus est 3 Noeud terminal, Feuille: Un noeud sans enfants. Exemple: Dans l'arbre ci-dessus, N2, N5, N6 et N7 sont des feuilles Chemin dans un arbre: Une suite de noeuds, dont chaqu'un est l'enfant de son prédecesseur. Exemple: Dans l'arbre ci-dessus, un chemin est (N1, N4, N7) Longueur d'un chemin: Le nombre de noeuds du chemin moins 1. Racine d'un arbre: Le noeud qui n'est enfant d'aucun autre noeud. Exemple: Dans l'arbre ci-dessus, N1 est la racine. Niveau d'un arbre: Un ensemble des noeuds auxquels le chemin de la racine a la même longueur. Exemple: Dans l'arbre ci-dessus, {N1}, {N2,N3,N4} et {N5,N6,N7} sont des niveaux. Profondeur d'un arbre: Son nombre des niveaux. Exemple: Dans l'arbre ci-dessus, la profondeur est 3. Arbre uniforme: Un arbre dont tous les noeuds (suaf que les feuilles) sont du même degré. Recherche dans un arbre: Une suite de noeuds, qui commence par la racine et termine par un noeud qui remplit une certaine condition. Recherche en longueur: Une recherche qui traverse les noeuds selon leurs niveaux. Exemple: Dans l'arbre ci-dessus, (N1, N2, N3, N4, N5) est une recherche en longueur Recherche en profondeur: Une recherche qui traverse les enfants de la racine par recherche en profondeur. Exemple: Pour l'arbre ci-dessus une recherche en profondeur est N1 + tous les enfants de N1, c'est-à-dire N2 + tous les enfants de N2 (aucun) N3 + tous les enfants de N3, alors N5 + tous les enfants de N5 (aucun) N6 + tous les enfants de N6 (aucun) N4 + tous les enfants de N2, alors N7 + tous les enfants de N7 (aucun) alors (N1, N2, N3, N5, N6, N4, N7) Entité: Quelque chose. Concept: Une idée abstraite qui décrit un ensemble d'entités. Exemple: La notion d'un "arbre" est un concept qui décrit tous les arbres concrets qui existent dans le monde. Annotation: Pour un traitement détaillé cf philo.txt (en anglais) ou funclog.htm (en francais, disponible à partir du février 2003) Relation: Une propriété d'un couple. Exemple: 4 est superieur à 3, alors le couple (4,3) a la propriété que sa première valeur est supérieure à la deuxième. On note: ">(4,3)" ou "(4,3) appartient à >" ou "4 > 3" Annotation: Pour les détails, voir gc.txt (en francais) Graphe: Un couple d'un ensemble et une relation sur cet ensemble. Les éléments de l'ensemble sont appelés "noeuds" (de graphe) et la relation designe quand il y a un "arc" entre deux noeuds. D'ordinaire, on dessine les noeuds comme cercles et les arcs comme flèches entre les noeuds. Un arbre peut être vu comme étant un graphe spécial. Les notions d'un graphe peuvent donc être appliquées à un arbre. Annotation: Pour les détails, voir gc.txt (en francais) Graphe localement fini: Un graphe dont chaque noeud a un nombre fini d'arcs. Coût d'un arc, poids d'un arc: Une valeur associée à cet arc. Addition de vecteurs: L'application "+" qui prend deux vecteurs a et b de n éléments et qui rend le vecteur a + b = (a[1]+b[1], a[2]+b[2], ... a[n]+b[n]) Comme d'habitude, le résultat s'apelle "somme". Produit scalaire: L'application "°" qui prend deux vecteurs a et b de n éléments et qui rend la valeur a°b = a[1]*b[1] + a[2]*b[2] + ... a[n]*b[n] Norme: L'application ||.||, qui prend un vecteur x et rend la racine carrée du produit scalaire de x par lui-même: ||x||=sqrt(x°x) Corrélation, Cosinus: L'application "cos" qui prend deux vecteurs x et y et rend la valeur cor(x,y) = cos(x,y) = x ° y / ||x|| / ||y|| Interprétation: Cette valeur correspond au cosinus de l'angle des deux vecteurs, si on les représente dans un système de coordonnées. Elle peut être utilisée pour mésurer la similarité des deux vecteurs. Dans le sens de la statistique, cette valeur indique la corrélation de deux variables, c'est-à-dire leur "proximité". Les cas extrèmes sont les suivants: * cos(x,y)=1: Les deux vecteurs ont la même orientation, corrélation maximale. * cos(x,y)=0: Les deux vecteurs forment un angle de 90 degrés, pas decorrélation. * cos(x,y)=-1: Les deux vecteurs ont des orientation inversées, corrélation négative maximale. Variable: Une minuscule de la fin de l'alphabet. Une variable peut avoir une valeur associée. Exemple: x, y, z Annotation: Toutes les notions de la logique classique sont maintenant introduites comme étant les mots d'un langage théorique. Constante: Une minuscule du début de l'alphabet. Exemple: a, b, c Prédicat: Une majuscule à laquelle est associé un entier. Parfois, les prédicats sont notés par des noms complets. Opérateur de comparaison: Un des prédicats '<', '>', '=' et '!='. Foncteur: Un symbol auquel est associé un entier. Opérateur arithmétique: Un des symboles suivants: +,-,*,/,^ Arité d'un foncteur, arité d'un prédicat: L'entier associé. Expression, terme: * Une variable OU * une constante OU * un foncteur suivi par "(", n termes et ")", où n est l'arité du foncteur. * un terme suivi par un opérateur arithmétique et un terme Exemple: f(g(a,x+7),c) Littéral: Une chaîne de la forme "P(t[1],t[2],...t[n])" où P est un prédicat, les t[i] sont des termes et n est l'arité de P. Cela signifie: Le tuple des t[i] a la propriété exprimée par P. Les comparaisons peuvent aussi être écrits sous la forme "terme prédicat terme". Formule: * Un littéral OU * Une chaîne de la forme "~X", où X est une formule OU * Une chaîne de la forme "(A et B)" où A et B sont des formules OU * Une chaîne de la forme "(A ou B)" où A et B sont des formules OU * Une chaîne de la forme "(A => B)" où A et B sont des formules OU * Une chaîne de la forme "(A <=> B)" où A et B sont des formules OU * Une chaîne de la forme "All x: A" où x est une variable et A est une formule OU * Une chaîne de la forme "Ex x: A" où x est une variable et A est une formule Annotation: Cette définition nous explique quelles chaînes sont des formules correctes de la logique classique -- sans y associer un "sens". Quantificateur existentiel: La chaîne "Ex x:" où x est une variable. Le quantificateur existentiel est noté par un "E" inversé, suivi par la variable. Quantificateur global: La chaîne "All x:" où x est une variable. Le quantificateur global est noté par un "A" inversé, suivi par la variable. Conjonction: Une formule de la forme "(A et (B et ... ) ... )", d'ordinaire notée par "A et B et ...". Disjonction: Une formule de la forme "(A ou (B ou ... ) ... )", d'ordinaire notée par "A ou B ou ...". Implication: Une formule de la forme "(A => B)", quelques fois notée par "Si A, alors B". Prémisse d'une implication: Sa première formule. Si la prémisse est une conjonction, toutes les formules de la conjonction sont considerées comme prémisses. Conclusion d'une implication: Sa deuxième formule. Langage premier ordre, Logique classique: L'ensemble de toutes les formules. Langage d'ordre zéro, Langage propositionel: L'ensemble de toutes les formules sans variables et sans foncteurs. Le langage propositionel est donc un sous ensemble moins puissant du langage premier ordre. Langage intermédiaire, 0+: L'ensemble de toutes les formules, dont les seuls foncteurs sont ">", "=" et "<". Langage avec coefficients: Le langage de premier ordre ou un sous ensemble dont tous les littéraux et implications possèdent un nombre réel associé (un coefficient). Ces nombres servent à déterminer la confiance. Règles de calcul: Les remplacements suivants: * ~(A et B) <----> ~A ou ~B * ~(A ou B) <----> ~A et ~B * A => B <----> ~ A ou B * A <=> B <----> (A => B) et (B => A) * A et B <----> B et A * A ou B <----> B ou A * A ou (B et C) <----> (A ou B) et (A ou C) * A et (B ou C) <----> (A et B) ou (A et C) * ~ Ex x: A <----> All x: ~A * ~ All x: A <----> Ex x: ~A * ~~A <----> A * A => B <----> ~A ou B * A <=> B <----> (A => B) et (B => A) * (A => B) et A ----> (A => B) et A et B Modus Ponens * (All x:A) ----> (All x:A) et Ac où Ac est la formule obtenue par le remplacement de x par c dans A Interprétation d'un littéral: Une des valeurs "vrai" ou "faux" associée à ce littéral. Exemple: Certaines associeraient peut-être la valeur "vrai" au littéral D(c), si D signifie "déliceux" et c signifie "chocolat" Règles d'interprétation: Les remplacements suivants: * P(...) ----> Interprétation de P(...) * ~vrai ----> faux * ~faux ----> vrai * (A et faux) ----> faux * (A et vrai) ----> A * (A ou faux) ----> A * (A ou vrai) ----> vrai * Ex x: A ----> vrai, ssi il y a un x tel que A * All x: A ----> vrai, ssi A vaut pour tous les x Interprétation d'une formule: Une des valeurs "vrai" ou "faux", obtenue par l'application des règles de calcul et des règles d'interprétation à la formule. Annotation: La notion de l'interprétation nous donne alors finalement le "sens" de la logique classique: On remplace les littéraux par leur interprétation, on fait le calcul et on recoit la valeur de toute la formule. Équivalence de formules: La propriété d'un couple de formules de posseder la même interprétation, quelles que soient les interprétations des littéraux. Example: Les formules P(X) et ~~P(x) vont avoir la même interprétation, quelle que soit l'interprétation de P(x) Fait: Une réalité. Les faits sont d'ordinaire notés par des littéraux. Vérité: La propriété d'une déclaration de décrire un fait. Hypothèse: Une déclaration dont la vérité n'est pas connue. Une hypothèse est d'ordinaire notée par une formule. Déduire une hypothèse, prouver une hypothèse: Trouver que l'hypothèse doit être vraie. Règle: Une déclaration qui permet de prouver des hypothèses. Les règles sont d'ordinaire notées par des implications. Polynôme: Une somme de multiples d'une variable réelle élevée à 0,1,...n: a[n]*x^n + ... a[1]*x^1 + a[0]*x^0 Fonction rationelle: Une fonction qui calcule son résultat comme étant un quotient de deux polynômes. max: La fonction qui prend un ensemble de valeurs réelles et en redonne la plus grande. min: La fonction qui prend un ensemble de valeurs réelles et en redonne la plus petite. Infini: La valeur théorique INF qui est plus grande que toutes les valeurs réelles. Limite: La valeur théorique d'une expression avec une variable ayant une valeur avec laquelle on ne peut pas calculer. On écrit: lim variable->valeur expression = limite Exemple: lim n->INF 1/n = 0 Dérivation d'une fonction f:R^n->R par le i-ème paramètre: L'application df/dx[i] qui prend des paramètres x[1],...x[n] et redonne lim h->0 (f(x[1],x[2],...x[n])-f(x[1],x[2],... x[i]+h, ... x[n]))/h La dérivation mesure alors le changement de f, quand on secoue x[i]. e: La valeur 2.7182818... ===================================================================== Cours de M Lemaire ===================================================================== Le cours de M Lemaire présuppose déjà de bonnes connaissances de la logique. J'espère d'en avoir traité les plus importantes dans l'introduction. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Résolution ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Couple de substitution: Un couple d'une variable et un terme. Ce couple indique que la variable va être remplacée par le terme. Example: [x/a] Substitution: L'application d'un couple de substitution à une formule, c'est-à-dire le remplacement de toutes les occurences de la variable par le terme. Exemple: (a et b ou x) [x/c] = (a et b ou c) Rebaptiser une variable: Appliquer un couple de substitution de forme [x/y], où x est la variable à rebaptiser et y est un nouveau nom pour cette variable. Formule simple: Une formule qui ne contient ni des "=>" ni des "<=>" et dont tous les "~" ne s'appliquent qu'à des littéraux. Chaque formule peut être transformée en une formule simple équivalente par les règles de calcul. Exemple: ~ All x: P(x) et Q(y) ------peut être transformée en-------> Ex x: ~P(x) ou ~Q(x) Formule prénex: Une formule simple, dont tous les quantificateurs se trouvent au début. Chaque formule simple peut être transformée en une formule prénex équivalente par l'algorithme suivant: 1. Rebaptise les variables dans les "All x: A" et "Ex x: A" de sorte que les noms sont uniques. 2. Bouge tous les quantificateurs au début de la formule, en gardant leur ordre Formule skolem: Une formule prénex sans quantificateurs existentiels. Chaque formule prénex peut être transformé en une formule skolem par l'algorithme suivant: 1. Tant qu'il y a encore des quantificateurs existentiels, repète 2. Cherche le premier quantificateur existentiel, sa variable soit notée par x dans la suite 3. Choisis un foncteur f qui n'apparaît pas encore dans la formule 4. Substitue toutes les occurences de la variable x par "f(x1,x2,...xn)", où (x1,x2,...xn) est la suite de toutes les variables qui apparaissent dans les quantificateurs globaux précédents. Si il n'y a pas de "All x:" précédent, cela revient à la substitution de la variable par une constante. 5. Supprime le quantificateur existentiel 6. FinTantQue Le résultat n'est plus équivalent à la formule initiale. Mais si il y a une interpretation vraie de la formule initiale, il y en a aussi une de la formule skolem. L'idée de la substitution 4 est de dire: Si il y a un x pour lequel la sous-formule est vraie, alors je peux bien donner un nom constant à cet x. Dans le cas où x dépend d'autres variables, il faut exprimer x en fonction de ces variables. Formule sous forme normale conjonctive: Une formule de la forme (A1 ou A2 ou... AN) et (B1 ou B2 ou... BM) et ... où tous les symboles sont des littéraux. Chaque formule skolem peut être transformée en une telle formule par l'effacement des quantificateurs globaux et l'application des règles de calcul. Clause: Une disjonction de littéraux, notée par l'ensemble de ces littéraux. Exemple: (a ou b ou c) -----> {a, b, c} Formule clause: Une formule sous forme normale conjonctive, notée par l'ensemble de ses clauses. Exemple: ( a ou b) et (c) ~~~~> { {a,b}, {c} } Unifieur: Un ensemble de couples de substitution tel que l'application de tous les couples à deux littéraux rend les deux littéraux egaux. Exemple: Littéraux: P(x,a), P(b,y), Unifieur: { [x/b], [y/a] }, Résultat: P(b,a) Résolvante: Une clause obtenue de deux clauses par l'algorithme suivant: 1. Rebaptise les variables dans les deux clauses de sorte que les clauses ne possèdent plus de variables du même nom 2. Tant qu'il y a un autre littéral dans une des deux clauses qui apparaît avec un "~" dans l'autre clause, repète 3. Trouve un unifieur pour ces deux littéraux. Si il n'y en a pas, continue à 6 4. Applique cet unifieur aux deux clauses. 5. Efface ces deux littéraux 6. FinTantQue 7. Ce qui reste est la résolvante Contradiction: Une formule de forme "A et ~A". Exemple: La formule suivante contient une contradiction: (A(b) ou C(d)) et (E(f) et ~E(f)) nil: La clause vide. Résolution: L'algorithme suivant pour déterminer si il y a des substitutions telles que une formule clause contient une contradiction: 1. TantQue 1==1, repète 2. Choisis deux clauses de la formule clause 3. Ajoute leur résolvante à la formule 4. Si nil est dans la formule, c'est fini: Il y a des substitutions telles que la formule est contradictoire 5. Si toutes les combinaisons ont déjà été essayées, c'est fini: La formule ne contient pas de contradiction 6. FinTantQue Preuve par résolution: La preuve d'une hypothèse à partir de faits par l'algorithme suivant: 1. Exprime les faits par des formules clauses 2. Exprime l'hypothèse mise en négative par une formule clause 3. Forme l'union de toutes ces formules clauses 4. Applique la résolution à cette union 5. Si il y a une contradiction, l'hypothèse est vraie L'idée est la suivante: On crée un monde, où tout les faits sont vrais et l'hypothèse est fausse. L'union du pas 3 représente ce monde par une grande formule clause. Maintenant, la résolution se met en marche. Si elle trouve des substitutions telles que il y a une contradiction, cela veut dire qu'il y des valeurs pour les variables telles que ce monde serait contradictoire. Si les faits eux-mêmes ne sont pas contradictoires, c'est alors l'hypothèse fausse qui produit la contradiction. Donc il y a des valeurs pour les variables telles que l'hypothèse est vraie. Stratégie de résolution: Un algorithme qui précise le choix des clauses dans la résolution. Résolution par recherche en longueur: Une stratégie de résolution, qui fait une recherche en longueur dans l'arbre engendré par toutes les suites possibles des choix des clauses. C'est-à-dire: La formule orginale est considérée comme premier niveau de l'arbre. On calcule d'abord toutes les résolvantes de la formule, puis on les ajoute toutes d'un seul coup (c'est le deuxième niveau de l'arbre). Puis, on calcule les résolvantes suivantes et on les ajoute toutes à un seul coup (c'est le troisième niveau de l'arbre), etc. Cette stratégie trouve la suite de choix la plus courte, mais a besoin de beaucoup d'espace et temps. Ensemble support: L'ensemble de la formule clause de la négation de l'hypothèse et toutes ses résolvantes dérivées. Résolution par l'ensemble support: Une stratégie de résolution, qui choisit toujours une clause de l'ensemble support pour calculer la résolvante. Le résultat est ajouté à l'ensemble support. L'idée est que pour produire une contradiction, on aura forcément besoin de l'hypothèse -- car les faits eux-mêmes ne doivent pas être contradictoires. Résolution par rapport aux données: Une stratégie de résolution, qui choisit toujours une clause des faits initiaux pour calculer la résolvante. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Logique des défauts ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Compatibilité: La relation de deux formules de posseder des substitutions telles que l'union des deux formules ne contient pas de contradiction. Formule de défaut: Un triplet de formules clauses, noté par A:B/C. Ce triplet signifie: Si A est vrai et B est compatible avec ce qui est connu, alors C est vrai. La formule de défaut permet donc de représenter des connaissances de la forme "Généralement, A implique C.". D'ordinaire, les formules normales sont écrites au lieu des formules clauses. Exemple: Il y avait un crime et on veut savoir si x est suspect. On dit alors: a_mobile(x):coupable(x)/suspect(x), si x a un mobile et si il peut être coupable, alors il est suspect. Prérequis d'une formule de défaut: Sa première formule. Justification d'une formule de défaut: Sa deuxième formule. Conséquent d'une formule de défaut: Sa troisième formule. Théorie de défauts: Un couple d'une formule clause et un ensemble de formules de défauts. Cela signifie: La formule clause décrit un monde et les formules de défauts permettent de construire des mondes possibles, qui pourraient en résulter. Logique des defauts: L'ensemble de toutes les théories de défaut. "Expansion" d'une formule clause A: Une formule clause qui contient A et toutes les formules clauses qui en peuvent être dérivées par les règles de calcul. L'expansion est notée par Th(A). Exemple: A={ {ilpleut()}, {~ilpleut(),jepleure()} }, soit "ilpleut() et (ilpleut() => jepleure())" Th(A) = { {ilpleut()}, {~ilpleut(),jepleure()}, {jepleure()} } soit "ilpleut() et (ilpleut() => jepleure()) et jepleure()" Annotation: "expansion" n'est pas une notion officielle. En parlant de Th(A), il s'agit forcément de formules clauses -- sinon, Th(A) serait infini ("a" ~~> "a ou a" ~~> "a ou a ou a" etc.). Extension d'une théorie de défauts (W,D): Une formule clause E obtenue de (W,D) telle que: * E est l'union de tous les E[i] * E[0] = W * E[i+1] = Th(E[i]) \/ {C | A:B/C appartient à D et A appartient à E[i] et B n'appartient pas à E } Une extension décrit alors un monde possible selon les faits de W et les formules de défaut de D. Il peut y avoir plusieurs extensions pour la même théorie de défauts. La définition ci-dessus ne permet pas de construire directement une extension. Construction des extensions: L'algorithme suivant (assez bête) pour calculer toutes les extensions d'une théorie de défauts: 1. Prends toutes les clauses qui apparaissent dans les formules de la théorie de défauts, fais-en une suite S. 2. Soit E' l'ensemble vide 3. TantQue 1==1, repète 4. Soit i=1 5. TantQue la i-ème clause de S est dans E', repète 6. Efface-la de E' 7. i := i + 1 8. FinTantQue 9. Ajoute la i-ème clause de S à E' 10. Contrôle si E' est une extension selon la définition ci-dessus. Cela veut dire: Calcule les E'[i] jusqu'à ce que E'[i]=E'[i-1]. Si le résultat est égal à E', alors E' est une extension. 11. FinTantQue Cet algorithme essaye toutes les combinaisons possibles des clauses (en comptant en binaire, pour ceux qui s'y intéressent :-). Il va se terminer automatiquement par une ArrayIndexOutOfBoundsException à la ligne 4 :-) Défaut normal: Une formule de défaut de la forme A:B/B. Exemple: oiseau(x):vole(x)/vole(x) c'est-à-dire: Généralement, les oiseaux volent. (Les pies même deux fois :-) Théorie de défauts normale: Une théorie de défauts dont toutes les formules de défaut sont des défauts normaux. Une théorie de défauts normale admet toujours une extension non vide. Défaut semi-normal: Une formule de défaut de la forme A: (B et C...) /B . Théorie de défauts semi-normale: Une théorie de défauts dont toutes les formules de défaut sont des défauts semi-normaux. Une telle théorie n'a pas forcément une extension non vide. Circularité: La propriété d'une théorie de défauts semi-normale d'avoir une formule de défaut qui depend d'une autre formule de défaut qui depend de la première. Si il n'y a pas de circularité, la théorie de défauts semi-normale admet toujours une extension non vide. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Systèmes experts ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Domaine: Une partie du monde. Modélisation d'un domaine: La déscription de ce domaine par un formalisme (par ex. la logique classique). Raisons pour la modélisation: * Simulation du raisonnement humain * Capitalisation de la connaissance * Formation professionelle * Génération d'explications * Apprentissage * Interfaces homme/machine Base de connaissances: Un ensemble de règles. Déclencher une règle: Essayer de prouver les prémisses de cette règle pour prouver la conclusion. Déclaratif: Sous forme d'une déclaration. Un savoir déclaratif est un "savoir quoi". Il est facile à exprimer et ne préjuge pas de son utilisation ultérieure. Procédural: Sous forme d'une instruction. Un savoir procédural inclut un savoir-faire, un "savoir comment". Base de faits: Un ensemble de faits. Les faits sont exprimés d'une manière déclarative. Moteur d'inférence: Un algorithme universel qui prouve une hypothèse à partir d'une base de faits et une base de connaissances. Système à base de règles, Système expert: Un triplet d'une base de connaissances, une base de faits et un moteur d'inférence. L'idée d'un système expert est de séparer les connaissances du domaine et le processus de la preuve. Le langage utilisé pour la base de faits et la base de connaissances (soit le langage propositionel, la logique classique, un langage intermédiaire ou un langage avec coefficients) caractérise la puissance du système expert. Si le moteur d'inférence a prouvé une hypothèse, il peut expliquer les arguments pour l'hypothèse en donnant les règles et faits qu'il a utilisés. Avantages de la séparation des faits du moteur d'inférence: * Possibilité d'énoncer les faits avec un formalisme qui est plus facile à comprendre qu'une langage de programmation * Possibilité de modifier les données sans modifier le moteur d'inférence * Possibilité de réutiliser le moteur d'inférence pour différents domaines Parcours guidé par les données, Chaînage avant: Le procédé d'un moteur d'inférence de partir par les règles et les faits et de trouver toutes les hypothèses vraies. Algorithme: 1. Soit F la base de faits 2. Soit R l'ensemble de toutes les règles dont toutes les prémisses appartiennent à F 3. Ajoute toutes les conclusions de R à F 4. Si F a changé, alors continue à 2 5. F est l'ensemble de toutes les hypothèses vraies Cet algorithme est simple à implémenter. Parcours guidé par le but, Chaînage arrière: Le procédé d'un moteur d'inférence de déterminer la vérité d'une hypothèse donnée. Algorithme: 1. Soit R l'ensemble de toutes les règles qui contiennent l'hypothèse comme conclusion 3. TantQue R != {}, repète 4. Choisis une règle r appartenant à R 5. Efface r de R 6. Soit i=1 7. Tant qu'il y a une i-ème premisse de r, repète 8. Prends la i-ième prémisse de r comme une sous hypothèse s, essaye de prouver s par le même algorithme 9. Si s est fausse, alors continue à 13 10. i := i + 1 11. FinTantQue 12. L'hypothèse est vraie, c'est fini 13. FinTantQue 14. L'hypothèse est fausse, c'est fini Cela revient à une recherche en profondeur dans l'arbre engendré par les règles. L'algorithme est plus efficace pour la vérification d'une hypothèse que le chaînage en avant, mais plus difficile à implémenter. Chaînage mixte: Le procédé d'un moteur d'inférence d'utiliser le chaînage avant et le chaînage arrière. Méta-règle: Une règle qui propose une hypothèse ou une règle à partir de certains faits. Chaînage mixte avec des méta-règles: Le procédé d'un moteur d'inférence de trouver d'abord les hypothèses possibles grâce à des méta-règles. Cela revient à un chaînage avant sur les méta-règles. Puis, le moteur essaye de prouver ces hypothèses. Cela revient à un chaînage arrière. Chaînage mixte en posant des questions: Le procédé d'un moteur d'inférence de poser des questions à l'utilisateur pour les faits n'appartenant pas à la base de faits (chaînage arrière). Puis, le moteur d'inférence effectue un chaînage avant à partir de ces nouveaux faits. Système expert avec coefficients: Un système expert qui utilise un langage avec coefficients. Toutes les littéraux de la base de faits et toutes les règles de la base de connaissances possèdent donc un coefficient. Le nombre 1 signifie "sûrement vrai", 0 signifie "inconnu" et -1 signifie "sûrement faux". Moyens de choisir une règle à déclencher: * Les systèmes experts avec coefficients déclenchent toujours toutes les règles appliquables * Les systèmes qui posent des questions prennent les règles qui contiennent les faits les plus recents. * On peut choisir les règles les plus spécifiques, c'est-à-dire celles, dont la plupart des prémisses est déjà prouvée. * On peut utiliser des méta-règles qui proposent la règle à déclencher Seuil: Une valuer réelle d'un système expert avec coefficients qui détermine la confiance nécessaire pour déclencher une règle. Si cette valeur est grande, on ne déclenche que les règles les plus sûres. Si la valeur est petite, on déclenche presque toutes les règles. 0.8 est un exemple pour un seuil. Coefficient d'une conjonction: Le minimum des coefficients des formules de la conjonction. L'idée est que la conjonction de deux déclarations est aussi sûre que la déclaration la moins sûre parmi elles. c(A et B) = min(c(A), c(B)) Coefficient d'une disjonction: Le maximum des coefficients des formules de la disjonction. L'idée est qu'une seule formule vraie de la disjonction suffit pour rendre toute la formule vraie. c(A ou B) = max(c(A), c(B)) Déclencher une règle dans un système expert avec coefficients: Effectuer l'algorithme suivant: 1. Calcule le coefficient Cp de la prémisse de la règle en utilisant les équations ci-dessus 2. Si Cp est inféreur au seuil, la règle ne se déclenche pas, c'est fini 3. Calcule le coefficient de la conclusion en multipliant Cp par le coefficient Cr de la règle: C = Cr*Cp 4. Si la conclusion n'est pas encore dans la base de faits, alors ajoute-la avec son coefficient, c'est fini 5. Soit C' le coefficient de la conclusion dans la base de faits 6. Si C>0 et C'>0 alors calcule C''=C+C'-C'*C Cela revient à l'"ou" de deux probabilités Si C=<0 et C'=<0 alors calcule C''=C+C'+C'*C Cela est la négation du cas précedent Sinon calcule C''=(C+C')/(1-min(|C|,|C'|)) 7. Donne C'' comme nouveau coefficient à la conclusion dans la base de faits ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Modélisation d'expertise en 4 niveaux ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Problème des règles mixtes: Le désavantage d'un système expert d'avoir besoin de règles en dehors du domaine. Exemple: Considérons la règle suivante Si patient_alcoolique et symptômeX, alors maladieXYZ Un système expert va demander à l'utilisateur la vérité de la prémisse "patient_alcoolique". Bien sûr, ceci n'est pas nécessaire si le patient a moins de k ans (où k est une constante qui dépend du pays :-). Pour éviter la question, on ajoute alors une prémisse: Si âge>k et patient_alcoolique et symptômeX, alors maladieXYZ Mais cette prémisse existe seulement pour une raison informatique et n'a rien à voir avec la maladieXYZ. Réseau sémantique: Un graphe dont les noeuds sont des concepts et les arcs sont des relations. Les relations les plus fréquentes sont d'ordinaire "est-un" et "partie-de". KADS: Knowledge acquisition design system, une modélisation d'expertise en 4 niveaux. Le but est de permettre non seulement à l'informaticien, mais aussi à l'expert du domaine de comprendre la modélisation. Premier niveau de KADS: Un réseau sémantique du domaine. Ce niveau sert à trouver les termes techniques du domaine et d'organiser la terminologie. Inférence: Une activité de base qui produit des objets du domaine à partir d'autres objets du domaine. Une inférence est notée par une boîte avec le nom de l'inférence. On note à gauche les objets initiaux et à droite les objets résultants de l'inférence, connectés par des flèches à la boîte. Deuxième niveau de KADS: L'ensemble d'inférences du domaine. En donnant les inférences du domaine, on donne aussi les éléments et les relations du domaine. Alors le premier et le deuxième niveau de KADS peuvent être décrits ensemble. Troisième niveau de KADS: Un ensemble d'arbres, dont chaque arbre décrit une tâche du domaine. Une telle tâche contient des sous tâches, qui sont notées comme les enfants. Les feuilles de l'arbre sont les inférences. Quatrième niveau de KADS: Le niveau de la stratégie. À ce niveau, on ajoute de petits algorithmes aux arbres du troisième niveau. Ces algorithmes peuvent effectuer des choix entre les tâches ou des boucles en fonction des éléments du domaine. Car le quatrième niveau se sert du troisième, ces deux niveaux peuvent être décrits ensemble. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Analyse de la sémantique latente ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ cf aussi cl.txt (en anglais) Signification d'un mot: Le concept auquel le mot fait référence. Synomymes: Deux mots avec la même signification. Corpus: Une collection de textes. Contexte d'un mot dans un texte: L'ensemble des mots qui apparraissent avant et après ce mot dans le texte. Paragraphe d'un corpus: Une part du corpus, désigniée par un alinéa. Matrice d'occurances: Une matrice dont chaque ligne correspond à un mot et chaque colonne correspond à un paragraphe d'un corpus. On note à la ligne i et la colonne j le nombre d'occurances du mot i dans le paragraphe j. On filtre les mots qu'on met dans la matrice (p.ex. seulement les verbes, adjectifs et noms) et on ne met chaque mot qu'une seule fois. Analyse en composantes principales, ACP: Un algorithme qui transforme une matrice en une nouvelle matrice qui contient presque les mêmes informations, tout en ayant moins de colonnes. Annotation: Pour les détails, cf maths.txt Reconstruction d'une matrice: La détermination de la matrice initiale à partir de la matrice résultant d'une ACP. Comme l'ACP perd quelques informations, la matrice reconstruite n'est pas exactement égale à la matrice initiale. Ce processus élimine le "bruit de fond" de la matrice d'occurances et donne les valeurs théoriques des occurances des mots. Vecteur d'un mot: La ligne d'une matrice d'occurances (ou d'une matrice reconstruite) qui correspond à ce mot. Tous les mots peuvent donc être représentés dans un système de coordonnées. Leur corrélation indique une affinité à propos de leur sens: Si deux vecteurs ont la même direction, cela veut dire que les mots sont utilisés dans les mêmes contextes. Si on accepte le principe que "Meaning is use" ("La signification est l'utilisation"), cela signifie que les deux sens des mots sont proches. Vecteur d'un texte: La somme des vecteurs des mots du texte. Par conséquent, la proximité de deux textes peut être analysée à l'aide du cosinus des deux vecteurs. Proximité sémantique de deux textes: Le cosinus de leurs deux vecteurs. Proximité sémantique de deux mots: Le cosinus de leurs deux vecteurs. Mots associés à un mot m: La suite des mots qui ont une grande proximité sémantique à m. On les classe selon la valeur du cosinus. Analyse de la sémantique latente, Latent Sematics Analysis, LSA: L'établissement de matrices d'occurances, leur ACP et l'interprétation des résultats. D'ordinaire, on possède un grand nombre de mots et paragraphes (1000, 10000, 100000) et on réduit la matrice d'occurances à une matrice d'environ 300 colonnes. Métaphore: Un concept qui est utilisé pour décrire un autre concept. Exemple: "Mon avocat est un requin", le requin est la métaphore pour l'avocat. Tertium comparationis: Le concept commun d'une métaphore et du concept décrit. En trouvant le tertium comparationis, on comprend ce que la métaphore dit du concept décrit. Exemple: Dans "Mon avocat est un requin", le concept commun de "mon avocat" et de "requin" est leur trait d'être avide. Compréhension de métaphores: Selon Kintsch, on essaye de comprendre une métaphore en construisant les mots associés à la métaphore et les mots associés au concept décrit. On continue jusqu'à ce qu'on trouve un concept commun, donc le tertium comparationis. Plus le tertium comparationis est éloigné, plus il est difficile de le trouver et plus la métaphore est dûre à comprendre. Applications de la LSA: * Représentation informatique des significations des mots La LSA extraite les significations de mots automatiquement sans l'aide d'un homme. * Détermination automatique de synonymes Les synonymes peuvent être utilisés pour completer des recherches sur internet * Comparaison de textes La LSA peut comparer la proximité d'un texte d'étudiant à une solution modèle * Simulation de la compréhension de métaphores La LSA ne fait que compter les occurances des mots, elle ne s'occupe pas de la strucure sémantique du texte. Néanmoins, elle arrive à des résultats raisonnables si les textes sont suffisamment grands. ===================================================================== Cours de M Gensel ===================================================================== Le cours de M Gensel avance assez vite, mais le travail sur ce résumé a été soutenu par un polycopié instructif et bien structuré. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Problèmes de Satisfaction de Contraintes ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Solution polynômielle d'un problème: Une solution dont le temps nécessaire peut être décrit par un polynôme en fonction de la taille des données. Annotation: Pour les détails, voir infod.txt Problème polynômiel: Un probleme pour lequel une solution polynômielle est connue. Problème NP: Un problème non polynômiel. Exemple: La recherche dans un arbre est NP par rapport au nombre des niveaux: Si n est le nombre des niveaux et k est le nombre des enfants par noeud, il y a k^n feuilles à parcourir. Problème NP-complet: Un problème NP, dont la solution polynômielle entraînerait la solution polynômielle de tous les problèmes NP. Domaine d'une variable: L'ensemble des valeurs possibles de cette variable. Un domaine peut être fini ou infini. dom(x)={v | x peut avoir la valeur v} Affectation: Le processus de donner une valeur à une variable. On écrit variable := valeur. Type: Un domaine prédéfini. booléen: Le type {true, false}. bit: Le type {0,1}. flottant: Le type avec lequel un langage de programmation représente les nombres réels. Contrairement aux nombres réels, ce domaine est fini. Contrainte: Un littéral. Contrainte unaire: Une contrainte avec une seule variable. Contrainte binaire: Une contrainte avec deux variables. Système de contraintes par intension: Un ensemble de contraintes. Système de contraintes par extension: Un ensemble de tuples. Chaque tuple a une valeur pour toutes les variables. Chaque tuple décrit donc une constellation possible d'affectations. CSP, problème de satisfaction de contraintes, Constraint Satisfaction problem: Un triplet CSP=(X, D, C) de * un ensemble de variables X = {x[1], x[2], x[3], ...} * un ensemble D des domaines des variables D = {d[1], d[2], d[3], ...} où d[i]=dom(x[i]) * un système de contraintes C Annotation: X et D sont plutôt des tuples, comme ils sont ordonnés et ne contiennent pas forcément des objets non-identiques. CSP alphanumérique: Un CSP dont tous les domaines comprennent des valeurs réelles ou des lettres. CSP numérique: Un CSP dont tous les domaines sont réels. CSP symbolique: Un CSP non alphanumérique. CSP binaire: Un CSP dont toutes les contraintes sont binaires. Modélisation graphique d'un CSP, graphe CSP: Une représentation d'un CSP avec un système de contraintes par intension. * Si le CSP est binaire: Le graphe a comme noeuds les variables et comme arcs les contraintes binaires. * Sinon: Le graphe a des noeuds pour les variables et pour les contraintes et dont un arc représente la présence d'une variable dans une contrainte. On a donc deux types de noeuds, qu'on dessine comme des boîtes (contraintes) ou cercles (variables). On note dans les noeuds des variables toutes les valeurs de son domaine. Arbre d'exploitation d'un CSP: L'arbre dont la racine est une variable avec un enfant pour chaque valeur possible de cette variable. Chaque enfant est l'arbre d'exploitation des variables restantes. Un chemin à partir de la racine correspond à des affectations de valeurs aux variables. Instantiation d'un CSP: Un ensemble de couples compredrant une variable et une valeur. Chaque variable n'apparait qu'une fois dans l'ensemble. Solution d'un CSP: Une instantiation complète qui satisfait toutes les contraintes. En général, la tâche de trouver une solution est NP-complète, comme il s'agit d'une recherche dans l'arbre d'exploitation. Consistance locale d'une instantiation: Sa propriété de satisfaire toutes les contraintes. Consistence globale d'une instantiation: Sa propriété d'être un sous ensemble d'une solution possible. Support d'une valeur x d'une variable X dans une variable Y: Une valeur y du domaine de Y telle que les deux valeurs satisfont toutes les contraintes. k-consistance d'un CSP: Sa propriété que les instantiations sont localement constistentes pour tout sous ensemble de k variables. L'établissement de k-consistence est NP-complet par rapport a k. Plus grand est k, plus difficile est son établissement mais plus rapide sera la recherche d'une solution. On utilise donc souvent seulement l'arc-consistence ou la 3-consistence. Arc-consistance d'un CSP: 2-constistence, donc sa propriété que chaque valeur de chaque variable a un support dans toutes les autres variables. Un CSP peut être rendu arc-consistant en effacant les valeurs sans support. L'arc-consistence n'implique pas l'existence d'une solution! Chemin-consistance: 3-consistance. Annotation: Cette définition est différente de celle de ai.txt Propagation de contraintes: Un algorithme pour l'établissement de k-consistence. Il part d'un ensemble vide de contraintes et ajoute les contraintes l'une après l'autre. Chaque fois, il efface les valeurs sans support des variables. Si une valeur a été effacée, il vérfie récursivement si elle était le seul support d'une autre valeur. Pour cela, il maintient une liste des contraintes à propager. Algorithme rétrospectif: Un algorithme qui cherche la solution d'un CSP en construisant des instantiations successives. Si on ne peut pas trouver une instantiation suivante valable, les instantiations sont défaites et d'autres instantiations sont cherchées. Backtrack chronologique, Backtrack: L'algorithme rétrospecif suivant: 1. Soit i=1 // Choix de la variable 2. Si il restent encore des valeurs dans dom(x[i]), alors continue à 6 3. Si i==1, alors il n'existe pas de solution 4. Décrémente i 5. Continue à 2 (backtracking) // Choix de la valeur 6. Choisis une nouvelle valeur v[i] de dom(x[i]) 3. Vérfie si l'instantiation {(x[1],v[1]), ... (x[i],v[i])} satisfait encore toutes les contraintes 5. Si cela n'est pas le cas, alors continue à 2 6. Si i est le nombre total de variables, alors une solution est trouvée 7. i := i + 1 8. Continue à 2 Cela revient à une recherche en profondeur dans l'arbre d'exploitation. Backjumping: Une amélioration du Backtrack. Si tout le domaine d'une variable a été parcouru sans avoir trouvé une valeur, on ne revient pas à la variable précedente, mais plutôt à cette variable, qui a causé l'échec. Le pas 4 mentionné ci-dessus est alors remplacé par 4. Soit i le nombre de la variable figurant dans la contrainte violée Cet algorithme coupe une part inutile de l'arbre d'exploitation. Algorithme prospectif: Un algorithme qui cherche la solution d'un CSP en construisant des instantiations successives. Après chaque nouvelle instantiation, les domaines des variables restantes sont filtrés. Si un domaine a été vidé, les instantiations sont défaites, les domaines sont restaurés et d'autres instantiations sont cherchées. Forward checking: L'algorithme prospectif suivant: 1. Soit v[1]:=0, ... v[n]:=0 pour les n variables 2. forwardcheck(1) 3. Il n'y a pas de solution, c'est fini 4. Procédure forwardcheck(i) 5. PourTout valeur de dom(x[i]) 6. Soit v[i] cette valeur 7. Si l'instantiation {(x[1],v[1]), ... (x[i],v[i])} satisfait encore toutes les contraintes, alors 8. Si i==n, alors la solution a été trouvée, c'est fini 9. Fais une copie locale de tous les domaines des variables 10. PourTout variable k>i, repète 11. Efface les valeurs de dom(k) qui sont en contradiction avec l'instantiation actuelle 11. FinPourTout 12. Si il n'y a aucun domaine vide, alors 13. forwardcheck(i+1) 14. FinSi 15. Restaure les domaines des copies 16. FinSi 17. FinPourTout 18. FinProcédure Cet algorithme coupe des sous arbres inutiles après chaque instantiation. Comparaison des algorithmes prospectifs et rétrospectifs: Le algorithmes prospectifs parcourent moins de noeuds dans l'arbre d'exploitation que les algorithmes rétrospectifs. Cependant ils effectuent un filtrage de domaines qui coute beaucoup de temps. Ordonnancement de variables: Un choix d'un ordre des variables pour un algorithme de CSP. L'ordonnancement influe sur le temps de calcul. First fail principle: Un ordonnancement de variables, qui commence par les variables qui ont les plus de chances de conduire à un échec. Comme cela, on espère d'exclure vite les affectuations impossibles pour minimiser le nombre de retour-arrières. On prend d'abord les variables x dont le rapport card(dom(x)) / card({c | c est une contrainte avec x}) est petit. Ordonnancement statique: Un ordonanncement de variables pris avant que l'algorithme se met en marche. Ordonnancement dynamique: Un ordonnancement de variables qui est raffiné pendant l'algorithme. Ceci est par exemple raisonnable pour le First fail principle en combinaison avec le Forward checking: Comme l'algorithme change les domaines, le critère d'ordonnancement card(dom(x)) / card({c | c est une contrainte avec x}) change aussi après chaque instantiation. L'ordonnancement dynamique en rend compte en mettant à jour l'ordre des variables apres chaque instantiation. Ordonnancement de valeurs: Un choix d'un ordre des valeurs dans les domaines pour un algorithme. Cet ordre influe sur le temps de calcul, mais est difficile à déterminer. Restriction d'un CSP: L'ajout d'une contrainte. Dans ce cas, la nouvelle contrainte doit être propagée. Les affectations non permises par le CSP initiale restent non permises. Relaxation d'un CSP: Le retrait d'une contrainte. Dans ce cas, il faut soit reposer tout le CSP soit utiliser DnAC4 ou ACDC. Une solution du CSP initial est aussi une solution du CSP relaxé. CSP dynamique, DCSP: Un CSP auquelon peut à tout moment appliquer une restriction ou une relaxation. Justification d'une valeur enlevée: La contrainte qui a causé le retrait de cette valeur. DnAC4: Une stratégie pour la résolution d'un DCSP, qui mémorise avec chaque valeur enlevée sa justification. Si une contrainte c est retirée, les valeurs ayant c comme justification peuvent être réintroduites. Puis, il faut vérifier que chaqu'une des nouvelles valeurs ait un support. Une valeur toujours non soutenue est enlevée en mémorisant la nouvelle justification. ACDC: Une stratégie pour la résolution d'un DCSP, qui réexamine les domaines après le retrait d'une contrainte c. Toute valeur n'ayant pas de support par c est considérée réhabitable. Puis, toute valeur soutenue par une valeur réhabitable est de même considérée réhabitable. On applique alors un algorithme pour réétablir l'arc-consistance. Comparaison de DnAC4 et ACDC: ACDC est plus flexible, moins coûteux en place mémoire, mais moins efficace en temps que DnAC4. Satisfaction partielle d'un CSP pour toutes les contraintes: Une instantiation d'un sous ensemble maximal des variables qui satisfait toutes les contraintes. Satisfaction partielle d'un CSP pour toutes les variables: Une instantiation de toutes les variables qui satisfait un maximum de contraintes. CSP à intervalles, ICSP: Un CSP dont les domaines sont des intervalles ou des unions d'intervalles. Ses contraintes sont données en intension. Théorème fondamental des ICSPs: Pour chaque fonction rationelle, on peut calculer l'intervalle de son résultat à partir des domaines de ses paramètres. Règle de calcul d'intervalle: Une fonction qui prend un ou deux intervalles et rend un autre intervalle. Pour chaque opérateur arithmétique o, il y a une règle correspondante. Si on connait les domaines de deux variables X et Y, on peut utiliser la règle pour calculer le domaine de X o Y. "Intervalle unitaire": Un intervalle comprendrant une seule valeur. Au lieu d'un intervalle unitaire, on peut écrire simplement la valeur: [a,a] = a Addition d'intervalles: La fonction '+' qui prend deux intervalles [a,b] et [c,d] et redonne l'intervalle [a+c,b+d]. Il est valable: * 0 + [a,b] = [a,b] Soustraction d'intervalles: La fonction '-' qui prend deux intervalles [a,b] et [c,d] et redonne l'intervalle [a-d,b-c]. Il est valable: * [a,b] - [a,b] = [a-b,b-a] ce qui n'est pas 0 ! Multiplication d'intervalles: La fonction '*' qui prend deux intervalles [a,b] et [c,d] et redonne l'intervalle [min({a*c, a*d, b*c, b*d}), max({a*c, a*d, b*c, b*d})]. Il est valable: * r * [a,b] = [r*a,r*b] pour r > 0 * r * [a,b] = [r*b,r*a] pour r < 0 * 2 * [a,b] = [a,b] + [a,b] * 1 * [a,b] = [a,b] * A * (B + C) != A*B + A*C Division d'intervalles: La fonction '/' qui prend deux intervalles [a,b] et [c,d] et redonne l'intervalle [a,b] * [1/c,1/d]. Si 0 appartient à [c,d], la division n'est pas définie. Variable cachée d'un ICSP: Une variable introduite pour simplifier les contraintes. Contrainte simple principale: Une contrainte de la forme X o Y, où X est une variable, Y est une variable cachée et o est un opérateur de comparaison. Contrainte simple secondaire: Une contrainte de la forme X = o(Y[1], Y[2],...), où X est une variable cachée, les Y[i] sont des variables et o est une fonction. D'ordinaire, o est un opérateur arithmétique. Décomposition d'un ICSP: Le remplacement de chaque contrainte par des contraintes simples équivalentes. Arc-consistance dans un ICSP réel: L'arc-consistence dans un ICSP avec des nombres réels. Ce problème n'a pas de solution, comme il est par exemple impossible d'enlever exactement une valeur réelle d'un domaine: Comme les domaines doivent être des unions d'intervalles et comme les nombres réels sont denses, on ne peut pas trouver un nombre fini d'intervalles dont l'union exclut exactement une seule valeur intermédiaire. Arc-consistance dans un ICSP flottant: L'arc-consistence dans un ICSP avec des flottants. Ce problème est difficile à resoudre. Boîte-consistence d'une contrainte d'un ICSP: La propriété de ses variables d'avoir un domaine qui permet la vérification de la contrainte d'après les règles de calcul d'intervalle. Enveloppe-consistence d'une contrainte d'un ICSP: La propriété de ses variables d'avoir un domaine dont toutes les bornes satisfont la contrainte. Intervalle-consistence: (?) Technique de résolution d'une contrainte d'un ICSP: Une transformation de la contrainte qui a pour but la restriction du domaine d'une variable. La contrainte a la forme variable = expression et le but est de réduire le domaine de la variable à gauche. On transforme l'expression. Puis, on applique les règles de calcul d'intervalle à l'expression tranformée pour déterminer le domaine de la variable à gauche. On espère que cela mène à un domaine plus petit que l'application des règles à l'expression initiale. Il y a plusieures techniques de résolution, mais il n'y pas de meilleure méthode universelle. Schéma d'Horner d'un polynôme: Le polynôme réécrit sous la forme a[0] + x*(a[1] + x*(a[2] + ... ) ...). Cette forme peut être utilisée comme technique de résolution d'une contrainte d'un ICSP. Forme centrée de Moore d'une expression: L'expression réécrite sous la forme f(m) + G(x-m), où x est la variable de l'expression et m est le milieu du domaine de x. Cette forme peut être utilisée comme technique de résolution d'une contrainte d'un ICSP. Propagation d'une contrainte dans un ICSP: La restriction des domaines des variables de la contrainte. On utilise les règles suivantes: * Si la contrainte a la forme X = Y, alors dom(X) := dom(X) /\ dom(Y) * Si la contrainte a la forme X = f(Y[1], Y[2], ...), alors on trouve f[1], f[2], ... tels que Y[1] = f[1](X, Y[2], ...) Y[2] = f[2](Y[1], X, ...) ... (on exprime chaque variable par les autres) On trouve les règles de calcul d'intervalle F, F[1], F[2]... associées à f, f[1], f[2]... . On applique dom(X) := dom(X) /\ F(dom(Y[1]), dom(Y[2]), ...) dom(Y[1]) := dom(Y[1]) /\ F[1](dom(X) , dom(Y[2]), ...) dom(Y[2]) := dom(Y[2]) /\ F[2](dom(Y[1]), dom(X), ...) ... On repète l'application jusqu'à ce que les domaines ne changent plus. La propagation ne trouve pas une solution, mais elle élimine des valeurs impossibles. Cycle d'un CSP: Le phénomène que deux contraintes différentes portent sur deux mêmes variables. Un cycle dans un CSP peut entraîner la propagation multiple de la même contrainte. Variable de cycle d'un CSP, Variable coupe-cycle d'un CSP: Une variable partagée par deux contraintes qui constituent un cycle. Consistence d'un CSP avec un cycle: Le phénomène que les domaines se réduisent assez vite vers une solution. Inconsistence d'un CSP avec un cycle: Le phénomène que les domaines ne se réduisent pas du tout ou très lentement vers une solution. Dans ce cas, l'ordinateur solvant le CSP est dépassé. Il y a l'erreur de la pile plaine ("Stack overflow") ou une dégénérescence due aux grands nombres ("Precision overflow/underflow"). Subdivision des domaines: Une approche à la solution d'un ICSP, qui crée deux sous ICSPs en divisant le domaine d'une variable en deux sous ensembles. Chaque sous ICSP est résolu par la même stratégie. Dans un ICSP cyclique, on divise d'abord le domaine des variables coupe-cycles. Annotation: Peut être que "subdivision" est traduit plutôt par "sous-division". Propagation de la tolérance locale: L'algorithme suivant pour la solution d'un ICSP: 1. Détermine les variables des cycles 2. Exprime-les par les variables hors cycles 3. Élimine les contraintes qui comportent une variable de cycle 4. Ajoute les contraintes obtenues à l'étape 2 Comme l'étape 2 nécessite un résolveur algébrique, l'étape 2 n'est pas toujours possible. Méthode de Newton pour un ICSP: L'algorithme suivant pour la solution d'un ICSP: 1. Choisis une précision e>0 2. Applique les étapes suivantes à toutes les contraintes 3. Soit C := {} 4. Transforme la contrainte en la forme 0 = f(x) 5. Calcule la dérivée f'=df/dx de f 6. Trouve la règle d'intervalle F' associée à f' 7. Soit U := { dom(x) } 8. TantQue |U|!=0, repète 9. Enlève X de U 10. TantQue largeur(X)>e, repète 11. Soit m := milieu(X) 12. Soit N(F, X, m) := [m,m] - ( [f(m),f(m)] / F'(X) ) 13. Si N(F, X, m) /\ X est un intervalle, alors X := N(F, X, m) /\ X 14. Sinon 15. Soient X1 et X2 les sous intervalles de N(F, X, m) /\ X, de sorte que X1 \/ X2 = N(F, X, m) /\ X 16. U := U \/ X1 17. X := X2 18. FinSi 19. FinTantQue 20. C := C \/ X 21. FinTantQue 22. C est l'ensemble des intervalles possibles pour x 23. Fin de l'application La méthode de Newton trouve toujours les intervalles possibles et conclut toujours à la non-existence si ils n'existent pas. Mais le calcul de la dérivée n'est pas trivial et le nombre d'itérations est inconnu à priori. Fonction de coût d'un CSP: Une fonction qui prend une solution du CSP et y associe une valeur réelle. Cette valeur détermine la qualité de la solution (plus elle est petite, plus la solution est bonne). Solution optimale d'un CSP: Une solution pour laquelle la fonction de coût rend une valeur minimale. CSP sous optimisation combinatoire: Un CSP dont le but est de trouver une solution optimale. Théoriquement, on pourrait générer toutes les solutions du CSP et puis y trouver la meilleure. Mais comme cela prendrait beaucoup de temps, on utilise des méthodes approchées. Méthode approchée: Un algorithme qui améliore la qualité d'une solution d'un CSP jusqu'à un temps d'arrêt fixé par l'utilisateur. D'abord, on trouve une fonction qui permet de passer d'une solution trouvée à une solution voisine. Puis, la méthode approchée se met en marche pour passer toujours d'une solution à une autre pour en trouver la meilleure. Recuit: Un algorithme utilisé pour la création de cristalles à partir d'un liquide chaud. On refroidit le liquide, et alors la mobilité des molécules est réduite. Si les molécules arrivent à se structurer sous forme d'un cristalle, c'est bien. Cela est l'état d'énérgie minimale. Sinon, on les rechauffe encore un petit peu pour leur permettre de bouger encore. Puis, on les refroidit en espérant qu'ils trouvent alors son état d'énérgie minimale. Recuit simulé: Une méthode approchée qui fonctionne comme le recuit. Le coût d'une solution correspond à l'énérgie des molécules. L'énérgie la plus basse est donc la solution optimale. L'algorithme est le suivant: 1. Soit E la fonction de coût 2. Soit T0 la température de départ 3. Soit K un facteur de réduction entre 0 et 1 (d'ordinaire entre 0.8 et 0.99) 4. Soit Nc le nombre de solutions à exploiter chaque fois 5. Soit C une solution du CSP 6. T := T0 7. TantQue T != 0 (approximativement), repète 8. Pour i=1...Nc, repète 9. Génère une solution voisine C' de C 10. Soit d := E(C') - E(C) 11. Si d < 0, alors C := C' 12. Sinon 13. Soit m un réel pris au hazard entre 0 et 1 14. Si e^(-d/T) > m, alors C := C' 15. FinSi 16. FinPour 17. T := K*T 18. FinTantQue Cette méthode simule le rechauffement en acceptant une solution sous-optimale dans la ligne 15. Mais la probabilité d'un tel pas est réduite constamment. Transformation de solution d'un CSP: Une fonction qui permet de passer d'une solution du CSP à une autre. Méthode tabou: Une méthode approchée qui utilise une liste de transformations interdites. Elle part d'une solution initiale et applique toutes les transformations pour générer toutes les solutions voisines possibles. Puis, elle en choisit la meilleure. La transformation utilisée pour cette meilleure solution est ajouté à la liste tabou. Puis, elle continue à générer les solutions voisines à partir de cette meilleure solution, tout en ignorant les transformations de la liste tabou. Si la longueur de la liste dépasse une certaine borne, la dernière transformation est relâchée. Si cette borne est trop petite, on risque de retomber sur des solutions déjà examinées. Si la borne est trop grande, elle ne permet pas l'application fréquente des transformations essentielles. 1. Soit E la fonction de coût 2. Soit S une solution du CSP 3. Soit S_optimale := S 4. Soit L := () la liste tabou 5. Soit K une borne pour la longueur de L 6. Soit compteur_maximal une borne d'itération 7. Soit compteur := 0 8. Tant que compteur < compteur_maximal, repète 9. Applique toute transformation non taboue à S, les solutions obtenues soient S[1],.. S[n] 10. Chosis i tel que E(S[i]) = min( { E(S[j]) | j=1..n } ) 11. Si E(S[i]) < E(S_optimale), alors 12. S_optimale = S[i] 13. compteur := 0 14. Sinon 15. compteur := compteur + 1 16. FinSi 17. S := S[i] 18. Ajoute la transformation de S[i] à L 19. Si la longueur de L est plus grande que K, alors supprime la dernière transformation de L 20. FinTantQue Le problème de la méthode tabou est que la liste tabou peut être trop contraignante. Annotation: L'étape 19 manque dans le polycopié (?) Aspiration: Une amélioration de la méthode tabou, qui permet de relâcher une transformation de la liste tabou. Intensification: Une amélioration de la méthode tabou, qui mémorise les propriétés d'une bonne solution et favorise leur choix durant la recherche. Diversification: Une amélioration de la méthode tabou, qui cherche à explorer les transformations qui n'ont pas encore été réalisées. La diversification joue alors un rôle complémentaire à l'intensification. Évolution: Le processus de l'adaption d'un espèce à l'environnement d'une génération à l'autre. Certains savoir-faires d'un individu sont codés dans ses chromosomes. Deux parents passent leurs chromosomes, légèrement modifiés, à leurs sucesseurs. Comme les individus bien adaptés ont de meilleures chances de survivre et se réproduire, la prochaine génération possède des chromosomes même plus avantageux. Algorithme génétique: Une méthode approchée qui simule l'évolution. On trouve une fonction qui redonne une solution du CSP pour chaque constellation de ses paramètres. Ces paramètres sont des bits ou des entiers ou réels. Un paramètre correspond à un gène, une suite complète de paramètres correspond à un chromosome (un individu) et un ensemble de suites de paramètres à une population. L'algorithme génétique est le suivant: 1. Soit f:{0,1}^n -> { s | s solution} cette fonction 2. Soit E la fonction de coût 3. Soit K une borne d'itérations 4. Crée aléatoirement une population de 30 à 100 individus P := { I[1],... } 5. TantQue K != 0, repète 6. Choisis les deux meilleurs individus X tel que E(f(X)) == min( { E(f(I[i])) | I[i] appartient à P} ) Y tel que E(f(Y)) == min( { E(f(I[i])) | I[i] appartient à P et I[i]!=X} ) 7. Choisis un entier p entre 1 et n par hasard 8. Crée un nouvel individu des gènes de X et Y N := (X[1], ... X[p], Y[p+1], ...Y[n]) où X[i] est le i-ème gène de X 9. Change un gène de N par hazard 10. P := P \/ { N } 11. K := K - 1 12. FinTantQue 13. Prends l'individu le plus récent N de P 14. f(N) est la solution trouvée Mutation: L'étape 9 de l'algorithme génétique. Crossover: L'étape 8 de l'algorithme génétique. Point de crossover: Le p de l'étape 7 de l'algorithme génétique. Prolog: Un langage de programmation qui permet la preuve d'une hypothèse à partir de faits. La forme des instructions est très proche à la forme des formules de la logique du premier ordre. Prolog1: La première version de Prolog, basée essentiellement sur l'unification et le backtrack. Prolog2: La deuxième version de Prolog, qui permet de gérer des diséquations de la forme X != Y. Prolog3: La troisième version de Prolog, qui permet de programmer de contraintes sur des listes, sur des booléens et certaines contraintes sur des flottants. Prolog4: La quatrième version de Prolog, qui permet toutes sortes de contraintes. CHIP V5: Un langage de programmation (?) pour la solution de CSPs. CHIP V5 prévoit des interfaces aux langages de programmation C, C++ et Prolog. CHIP V5 permet toutes sortes de contraintes et tous les domaines. Annotation: J'ai l'impression que les exemples pour Prolog4 et CHIP ont été confondus. ILOG Solver: Des bibliothèques (?) pour les langages de programmation C++ et LISP, qui permettent la solution de CSPs. ILOG solver est orienté objet et comprend des algorithmes de solution pour tous les problèmes liés aux CSPs. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Représentation de connaissances par objets ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Annotation: Ce chapitre reprend beaucoup du chapitre "Systèmes experts". Les paragraphes de ce chapitre-là on été mis à jour d'après le cours de M Gensel. Représentation de connaissance: La modélisation d'un domaine. Système à base de connaissances, SBC: Un système expert dont la base de connaissances n'est pas limitée à des règles. Plutôt, elle utilise pour la représentation de connaissances: * la logique classique * des règles de production (donc un système expert) * des réseaux sémantiques * des frames * des objets structurés * des représentation hybrides comprenant des règles et des objets La structure d'un SBC est la suivante: _________________________ | | <-> interaction à l'utilisateur | base de connaissances | | ^ | <-> capteurs | | | | V | <-> modules algorithmiques | moteur d'inférence | externes | explications | |_________________________| <-> acquisition ^-> Système de gestion de base de données Utilisation de la logique pour un SBC: Avantages: * La logique est un formalisme précise et connu * Elle a une grande puissance, notamment grâce aux quantificateurs * Ses formules et symboles sont cohérents * On possède des méthodes pour la solution de problèmes exprimés par la logique (p.ex. la résolution), dont les propriétés et limites sont bien évaluées * On a un langage de programmation associé, Prolog La logique est donc beaucoup utilisée pour la démonstration Désavantages: * La logique manque de structuration de la connaissance * Les connaissannces procédurales sont difficiles à exprimer * On a des difficultés avec l'expression d'incertitude, du contexte d'interprétation, de la révision d'un énoncé ou d'une déduction Par cela, la logique classique a été raffinée à des logiques multivaluées, floues, modales, de défauts etc. Utilisation de règles pour un SBC: Avantages: * Les règles se prêtent bien à l'expression du savoir-faire d'un expert humain * Il y a déjà des systèmes experts qui marchent bien (DENDRAL pour la chimie moléculaire, MYCIN pour la diagnose médicale) * On peut exprimer des stratégies * Le formalisme est fort étudié Désavantages: * Les règles ne structurent pas les connaissances * Les règles peuvent simplifier la réalité * Elles nécessitent souvent d'une représentation d'objets * Il est difficile de prendre en compte les exceptions * Il est difficile de raisonner avec des informations incomplètes * Les règles sont parfois redondantes * Elles ne peuvent pas bien décrire un système complexe Prototype, Frame, Facette: Un couple d'un nom et une valeur. La valeur peut être une valeur simple, un frame ou un ensemble de frames. Un frame est utilisé comme unité de connaissance décrivant une situation ou un objet. Les frames ont été inventés par Minski, mais dans son traité, il se limite aux idées conceptuelles. Attribut: Une propriété qui peut avoir une valeur. Un attribut a un domaine comme une variable. Exemple: La couleur des yeux d'une personne est un attribut qui peut avoir les valeurs "bleu", "vert" et "noir" Attribut multi-valué: Un attribut dont les valeurs sont des ensembles ou des listes. Attribut mono-valué: Un attribut non multi-valué. Procédure: Un algorithme à lequel on peut passer des valeurs (les "paramètres") et qui donne un résultat. Classe: Un couple de * un ensemble de classes * un ensemble d'attributs, chaqu'un d'eux eventuellement avec * un domaine * l'information si l'attribut est mono-valué ou multi-valué * des procédures * des informations supplémentaires Une classe décrit donc un concept. Elle définit un aspect structurel (par les attributs et eventuellement des contraintes) et un aspect inférentiel (par les procédures qui permettent de trouver une valeur pour un attribut). Super-classe d'une classe C: Un élément de l'ensemble des classes stocké dans C. Sous-classe d'une classe C: Une classe qui a C comme super-classe. Instance d'une classe C: Un couple de * le nom de la classe C * un ensemble de couples de * un attribut de C * une valeur pour cet attribut Objet: Une classe ou une instance. Annotation: En Java, un objet est une instance! Méthode: Une procédure qui est attachée à un un attribut. Annotation: En Java, une méthode est attachée à une instance! Extension d'une classe: L'ensemble de ses instances. Intension d'une classe: L'ensemble de ses attributs. Réification: La modélisation d'un domaine par des objets. Relation d'une classe: Un attribut dont les valeurs possibles sont des instances. Composante d'une classe C: Une relation de C avec l'idée que les instances référencées ne peuvent pas exister sans une instance de C. Héritage: Le fait qu'une sous classe a tous les attributs de toutes ses super classes. Un domaine d'un attribut d'une sous classe est * l'intersection des domaines correspondants des super classes OU * un sous ensemble de l'intersection des domaines correspondants des super classes Affinement: Le phénomène qu'une classe réduit un domaine d'un attribut qu'elle a hérité d'une super-classe. Spécialisation: La relation entre une classe et sa super-classe. Mono-spécialisation d'une classe: Sa propriété d'avoir une seule super-classe. Multi-spécialisation d'une classe: Sa propriété d'avoir plusieures super-classes. Inconsistance d'une classe: Sa propriété d'avoir un attribut dont le domaine est réduit à un ensemble vide par l'héritage de plusieures super-classes. Graphe de spécialisation: Un graphe dont les noeuds sont des classes et dont les flèches lient une classe à ses super-classes. RCO, Représentation de Connaissances par Objets: Une modélisation qui distingue les classes et les instances. Contrairement aux langages de programmation orienté objet, la RCO * permet l'héritage dynamique * connait des procédures attachés aux attributs * ne permet pas de cacher des attributs (comme "private" en Java) Avantages: * Factorisation de l'information redondante dans les classes * Représentation très compacte d'une entité * Structuration automatique des données possible ("Classification") Désavantages: * Difficulté à exprimer les relations entre les objets * Impossibilité d'utiliser les quantificateurs existentiels Shirka: Un certain langage pour la RCO. Type Shirka: Un des types suivants: * entier * booléen * réel * symbole * une classe Valeur en Shakira: Une valeur comme d'ordinaire, en plus * "lui-même", qui fait référence à l'instance entourante * des déclarations d'instance * pour le type symbole: une chaîne précédée par "'" Déclaration de classe en Shakira: Une chaîne de la forme suivante: { est-un Classe sorte-de = ; attributs = { { ... } ... contraintes = { ... } }; } Déclaration d'instance en Shakira: Une chaîne de la forme suivante: { est-un = ; ... } Déclaration de procédure en Shakira: Une chaîne de la forme suivante: { sorte-de = Objet; attributs = { { fonction $un symbole $valeur } { ... } ... }; } L'algorithme de la procédure lui-même peut être écrit dans un langage de programmation. Appel d'une procédure en Shakira: Une chaîne de la forme suivante: { ... } Contrainte de classe: Une contrainte qui doit être vérifiée par toutes les instances de la classe. Une telle contrainte peut filtrer les domaines, établir de la cohérence et servir pour déterminer des valeurs inconnues pour une instance. Accès Shirka: Une des chaînes suivantes * "ajout" (signifiant un ajout de valeur) * "modif" (signifiant une modification de valeur) * "retrait"(signifiant un retrait de valeur) * "accès" (signifiant un usage de valeur) Facette Shirka: Une des chaînes suivantes (avec leurs valeurs possibles et leur effet): * "$un" avec un type Shirka Le domaine de l'attribut est fixé comme étant le type * "$ensemble-de" avec un type Shirka Le domaine de l'attribut est fixé comme étant l'ensemble des ensembles de valeurs du type donné * "$liste-de" avec un type Shirka Le domaine de l'attribut est fixé comme étant l'ensemble des listes de valeurs du type donné * "$domaine" avec un ensemble Le domaine de l'attribut est fixé * "$sauf" avec un ensemble Les valeurs données sont retirées du domaine * "$intervalle" avec deux bornes Le domaine de l'attribut est fixé * "$card" avec un entier La cardinalité des ensembles du domaine est fixée * "$valeur" avec une valeur La valeur de l'attribut est fixée * "$unité" avec une chaîne * "$sib-exec" avec l'appel d'une procédure La procédure est effectuée pour calculer la valeur de l'attribut si elle est demandée * "$défaut" avec une valeur Donne une valeur par défaut, qui peut être changée dans une instance * "$à-vérifier" avec une contrainte La contrainte est vérifiée * "$<-" avec un identifieur L'attribut prend par défaut la valeur de l'identifieur. L'identifieur est déclaré par un "$var" * "$var" avec un identifieur Déclare l'identifeur et fixe sa valeur à la valeur de l'attribut entourant * "$après-" avec un appel de procédure Fait que la procédure est appellé si la valeur de l'attribut a été accédée de la manière spécifiée * "$avant-" avec un appel de procédure Fait que la procédure est appellé avant que la valeur de l'attribut est accédée de la manière spécifiée Démon: Une procédure qui est effectuée automatiquement quand un évènement se passe. Exemple: Les procédures appellées par "$après-" Mécanisme d'inférence: Un processus qui trouve une valeur d'un attribut pour une instance. Dans Shakira, il y en a * La valeur par défaut, donnée par "$défaut" * La transmission de valeur, effectuée par "$<-" * L'attachement procédural, effectué par "$sib-exec" Conflit d'héritage: Le phénomène que deux mécanismes d'inférence trouvent deux valeurs différentes pour un attribut. Le conflit peut être résolu en fixant une stratégie de résolution: * On effectue une recherche en largeur d'abord dans le graphe de spécialisation à partir de la classe en question OU * On effectue une recherche en profondeur d'abord dans le graphe de spécialisation à partir de la classe en question La première valeur trouvée est prise. Classe sûre pour une instance i: Une classe, dont tout attribut * apparait dans i avec une valeur ET * a un domaine qui permet la valeur que i a pour cet attribut Classe possible pour une instance i: Une classe non sûre, dont tout attribut * n'apparait pas dans i avec une valeur OU * a un domaine qui permet la valeur que i a pour cet attribut Aucune des sous classes d'une classe possible n'est sûre. Classe impossible pour une instance i: Une classe dont il existe un attribut * qui apparait avec une valeur dans i ET * dont le domaine ne permet pas la valeur que i a Toutes les sous classes d'une classe impossible sont impossibles. Classification d'une instance: La détermination de la classe qui décrit le mieux l'instance. Cela est la classe sûre dont les domaines sont les plus petits. Néanmoins la notion "classification d'une instance" est souvent utilisée pour dire "Détermination des classes sûres, possibles et impossibles pour une instance". Si une instance est classifiée, il est possible de trouver ses valeurs inconnues par les mécanismes d'inférence. Classification d'une classe: La détermination des classes qui peuvent être ses super-classes et ses sous-classes. En général, une classe SOUS peut être une sous classe d'une classe SUPER, si il n'existe aucun attribut de SUPER, pour lequel SOUS ait un domaine plus grand que SUPER. Tropes: Un langage de RCO, qui distingue les * concepts (des ensembles d'entités avec toutes les informations) * classes (des points de vues des concepts) Représentation hybride: Une RCO qui utilise aussi des règles. KAPPA: Un certain programme pour la représentation hybride, dont les caractéristiques sont les suivantes: * La multi-spécialisation n'est pas permise * Il possède le langage de programmation KAL * Il possède une interface graphique * Il permet l'interaction avec l'utilisateur pour changer ou demander des valeurs * Il connait des démons, appellés "monitors" KAL: Le langage de programmation de KAPPA. Type KAL: Un des types suivants: * Number (entier) * Atom (symboe) * String (chaîne) * Boolean (booléen) * Object (objet) * List (liste) Variable KAL: Une chaîne unique, à laquelle est associé une valeur. Expression KAL: Une chaîne d'une des formes suivantes * : Redonne la valeur de l'attribut de l'instance (qui peut de même être une instance) * Self: Redonne la valeur de l'attribut de l'instance entourante * KAL connait toutes les opérations arithmétiques standards * # Redonne la suite des deux chaînes * (,...) KAL connait quelques fonctions qui opèrent sur des chaînes * AreAll?([|, ...], ) Redonne true si toutes les instances de toutes les classes énumérées satisfont la condition * IsThereAny?([|, ...], ) Redonne true si il y a une instance pour toute classe énumérée qui satisfait la condition * (,...) KAL connait quelques fonctions qui opèrent sur des listes Condition KAL: Une expression KAL dont le résultat est du type booléen. Instruction KAL: Une chaîne d'une des formes suivantes: * While { ; ... } Répétition tant que la condition est true * For [ ] {;...} Répétition avec la variable ayant les valeurs de à * EnumList(, , ) Effectue l'instruction avec la variable ayant les valeurs de la liste * ForAll [|] { ; ... } Effectue les instructions avec la variable ayant toute instance de la classe comme valeur * SendMessage(,, ,...) Effectue la procédure de l'instance * MakeInstance(, ) Crée une nouvelle instance de la classe avec le nom donné * MoveInstance(, ) Stocke la classe comme classe de l'instance * AskValue(:) Demande la valeur de lÄattribut de l'utilisateur * PostMessage() Affiche le message sur l'écran * Let [ ] { ; ... } Introduit la variable avec une valeur pour les instructions * SetValue(:, ) Change la valeur de l'attribut pour l'instance ... et d'autres instructions pour modifier les instances ou les fenêtres du programme. Procédure en KAL: Une chaîne de la forme suivante: (,...) { ; ... } Le résultat de la fonction est le résultat de la dernière instruction. Association: Un lien entre des classes. Tuple d'une association: Le lien décrit par l'association entre des instances. Rôle d'une association: Une de ses classes concernées. Multiplicité d'un rôle: Le nombre d'instances de cette classe qui sont concernées par l'association. Annotation: Cette définition est différent de de celle de bd.txt ! Aggrégation: Le lien entre une classe et une de ses composantes. AROM, Allier Relations et Objets pour Modéliser: Un certain programme pour la représentation hybride, qui a été developpé parmi autres par M Gensel :-) AROM est écrit en Java et se base sur Java. Il distingue entre des classes et des "relations". Les dernières peuvent être des spécialisations, des associations ou des aggrégations. AROM modélise des classes et des associations. Il permet des spécialisations entre des classes et entre des associations -- mais une sous-association d'une association doit avoir le même nombre de rôles. Une association peut aussi avoir des attributs. On peut créer des instances des classes et des instances des associations. Les dernières s'appellent "tuples". En général, les valeurs des attributs ne peuvent pas être des objets: Une telle constellation est exprimée par une association. AROM possède un langage algébrique qui permet de calculer des valeurs et d'exprimer des contraintes. La modélisation peut être effectuée par l'interface graphique de AROM ou par son langage de modélisation "AMI". "AMI" permet aussi de trouver les instances qui satisfont une condition donnée (des "requêtes"). Annotation: Pour un traitement détaillé de ce type de modélisation cf bd.txt (en francais) AMI: Le langage de AROM. Déclaration de classe en AMI: Une chaîne de la forme suivante: class: variables: variable: type: documentation: "" domain: unité: "" ... Les lignes en dessous de "variable:" sont facultatives. Déclaration d'une instance en AMI: Une chaîne de la forme suivante: instance: is-a: = ... L'expression est exprimée par le langage algébrique de AROM. Déclaration d'une association en AMI: Une chaîne de la forme suivante: association: roles: role: type: multiplicity: min: max: ... variables: variable: type: documentation: "" domain: unité: "" ... Les lignes en dessous de "variable:" sont facultatives. Déclaration d'un tuple en AMI: Une chaîne de la forme suivante: tuple: = ... = ... Requête AMI: Une des chaînes suivantes * "select( in : )" Donne une instance qui satisfait la condition * "set( in : )" Donne l'ensemble des instances qui satisfont la condition * . Donne la valeur de l'attribut pour l'instance Les conditions sont exprimées par le langage algébrique de AROM. ===================================================================== Cours de Mme Zara ===================================================================== Le cours de Mme Zara ne consiste qu'en recopier le polycopié. Par contre, celui-ci est détaillé et facile à comprendre. Il y avait seulement quelques petits problèmes avec les algorithmes. Le cours traite beaucoup de concepts qui ont déjà été introduits dans les cours de M Gensel et M Lemaire. Ils ne sont donc pas répétés dans ce résumé. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ La recherche ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Problème: Une question à résoudre. Annotation: Pour une définition plus détaillée, voir infod.txt (en allemand) Jeu: Un problème qu'on résoud pour le plaisir. Heuristique: Un critère, un principe ou une méthode qui permet de déterminer parmi plusieures lignes de conduite celle qui promet d'être la plus efficace pour atteindre un but. Fonction heuristique d'évaluation: Une fonction qui prend un état et redonne une valeur réelle, qui juge la qualité de l'état. D'après le choix de la fonction, des grandes valeurs ou des petites valeurs symbolisent une bonne qualité. La notion "heuristique" est utilisée comme synonyme de "fonction heuristique d'évaluation". Graphe d'un problème, Représentation d'un problème par espace d'états: Un graphe dont chaque noeud correspond à un état du problème. Chaque arc correspond à une transformation (opérateur) permis d'un état à un autre. Parmi les états, il y a un état initial et des états qui satisfont une condition de but. Il faut atteindre un état désiré à partir de l'état initial à l'aide des transformations. Arbre d'un problème: Le graphe du problème, dans lequel on redouble un état au lieu de faire un lien à un état déjà présent. La racine de l'arbre est l'état initial et les enfants d'un noeud sont tous les états accessibles par une transformation -- même si ils existent déjà ailleurs dans l'arbre. En effet, on évite quand même de les considérer plusieures fois quand on effectue par exemple une recherche. Algorithme de solution: Un algorithme qui essaye de résoudre un problème en calculant l'arbre du problème. On lui donne l'état initial, les transformations possibles et une condition de but. L'algorithme explore certains noeuds de l'arbre pour trouver un chemin de la racine à un noeud satisfaisant la condition de but. Les exigences de base pour la résolution par ordinateur sont * Une structure de symbole ou code qui peut représenter chaque état possible dans l'espace * Des outiles de calcul qui sont capables de transformer l'encodage d'un état en celui d'un autre. * Une méthode efficace d'organisation de ces transformations pour produire l'état désiré aussi vite que possible. Noeud généré d'un arbre de problème: Un noeud dont la représentation a déjà été calculé par un algorithme de solution. Noeud exploré d'un arbre de problème: Un noeud avec un enfant généré. Noeud developpé d'un arbre de problème, Noeud fermé d'un arbre de problème: Un noeud dont tous les enfants sont générés. Noeud ouvert d'un arbre de problème: Un noeud pas fermé. Recherche aveugle, recherche non informée: Une recherche dans un arbre de problème dont l'ordre des noeuds ne dépend pas du problème. La recherche en profondeur et la recherche en largeur sont des exemples d'une recherche aveugle. Pile: Une suite à laquelle on peut ajouter un élément au début (to push) et enlever l'élément du début (to pop). LIFO, Last In First Out, dernier entré premier sorti: Le fonctionnement d'une pile. File: Une suite à laquelle on peut ajouter un élément à la fin (to enqueue) et enlever un élément au début (to dequeue). FIFO, First In First Out, premier entré premier sorti: Le fonctionnement d'une file. Algorithme de recherche en profondeur: L'algorithme de solution suivant: 1. Soit n0 l'état initial 2. Soit OUVERT := ( n0 ) 3. Soit FERMÉ := () 4. TantQue OUVERT != (), repète 5. Supprime le premier noeud n de OUVERT 6. Si n n'est pas dans FERMÉ, alors 7. Si n est un but, n est la solution, c'est fini 8. Ajoute n à FERMÉ 9. Ajoute tous noeuds liés à n au début de OUVERT, 10. FinSi 11. FinTantQue Dans cet algorithme, OUVERT contient les noeuds ouverts et fonctionne comme une pile. Annotation: L'algorithme du polycopié * ne trouve pas n0 si c'est un but * a une liste FERMÉ qui ne sert à rien * ne va pas se terminer si il y a un cycle * n'effectue pas vraiement une recherche en profondeur ! Algorithme de recherche en largeur: L'algorithme de solution suivant: 1. Soit n0 l'état initial 2. Soit OUVERT := ( n0 ) 3. Soit FERMÉ := () 4. TantQue OUVERT != (), repète 5. Supprime le premier noeud n de OUVERT 6. Si n n'est pas dans FERMÉ, alors 7. Si n est un but, n est la solution, c'est fini 8. Ajoute n à FERMÉ 9. Ajoute tous noeuds liés à n à la fin de OUVERT, 10. FinSi 11. FinTantQue Dans cet algorithme, OUVERT contient les noeuds ouverts et fonctionne comme une file. Annotation: L'algorithme du polycopié * ne trouve pas n0 si c'est un but * a une liste FERMÉ qui ne sert à rien * ne va pas se terminer si il y a un cycle Recherche informée: Une recherche dans un arbre de problème dont l'ordre des noeuds est dépendant du problème. D'ordinaire, ces recherches utilisent une heuristique. Retour-arrière d'une recherche: La propriété de la recherche de contenir un noeud N1 suivi par un noeud N2, où N2 est d'un niveau plus haut que N1. Recherche irrevocable: Une recherche sans retour-arrière. Escalade: Une recherche informée irrevocable. Elle choisit toujours l'enfant qui paraît d'être le meilleur et procède a cet enfant sans jamais retourner. Le meilleur enfant est trouvé à l'aide d'une heuristique. Recherche du meilleur-d'abord: Une recherche informée, qui continue toujours avec les enfants du meilleur des noeuds déjà présents. Une heuristique est utilisé pour déterminer le meilleur noeud. Algorithme de la recherche du meilleur d'abord: L'algorithme de solution suivant 1. Soit n0 l'état initial 2. Soit OUVERT := { n0 } 3. Soit FERMÉ := {} 4. Soit f l'heuristique 5. TantQue OUVERT != {}, repète 6. Supprime le meilleur noeud n de OUVERT en utilisant f 7. Si n est un but, alors n est la solution, c'est fini 8. Ajoute n à FERMÉ 9. PourTous les états s accessibles à partir de n 10. Si s n'est ni dans OUVERT ni dans FERMÉ, alors ajoute s à OUVERT 11. FinPourTous 12. FinTantQue Dans cet algorithme, OUVERT est utilisé comme une liste avec priorité (un ensemble dont on enleve toujours le meilleur). Annotation: L'algorithme du polycopié ne va pas terminer si n0 est le seul but. Coût d'un chemin: La somme des poids associés aux arcs utilisés. Si il n'y a aucun poids associé, le coût d'un chemin est sa longuer. Heuristique A*: Une heuristique h qui estime le coût du chemin du noeud donné à un noeud de but. Une petite valeur correspond donc à un bon noeud. Heuristique A* admissible: Une heuristique A* qui sous estime toujours le vrai coût d'un noeud à un but. Recherche A*: Une recherche informée, qui continue toujours avec les enfants du noeud n dont f(n)=g(n) + h(n) est minimal. g(n) est le coût du chemin de la racine au noeud n. h est une heuristique A* admissible, qui estime le côut du chemin de n à un noeud de but. A* rend donc compte du chemin complet: De la racine au noeud actuel et du noeud actuel au but. Pourque A* marche, on stocke avec chaque noeud n le noeud grâce auquel on est arrivé à n. Cette marque est appelé "pointeur". Comme cela, g(n) peut calculer le coût de la racine au noeud n en tracant les pointeurs de n à la racine. Algorithme A*: L'algorithme de solution suivant, qui effectue une recherche A*: 1. Soit n0 l'état initial 2. Soit g:N->R la fonction qui redonne le coût du chemin de n0 au noeud donné comme paramètre en tracant les pointers 3. Soit h:N->R une heuristique A* admissible 4. Soit OUVERT := { n0 } 5. Soit FERMÉ := {} 6. TantQue OUVERT != {}, repète 7. Supprime de OUVERT le noeud n pour lequel f(n)=g(n)+h(n) est minimal 8. Si n est un but, n est la solution, c'est fini 9. Ajoute n à FERMÉ 10. PourTous les enfants s de n 11. Si s n'est pas dans FERMÉ ou g(s)+h(s) > g(n)+coût(n,s)+h(s), alors 12. Stocke n comme pointer prédécesseur dans s 13. Ajoute s à OUVERT 14. FinSi 15. FinPourTous 16. FinTantQue On peut récupérer le chemin de n0 à la solution n en suivant les pointeurs de n à n0. Annotation: L'algorithme du polycopié va se terminer après avoir vu la racine, parce que la ligne 17 ne va pas s'effectuer. Division-élagage: La stratégie d'identifier plusieurs sous-problèmes d'un problème, qui s'excluent mutuellement (division) et d'en supprimer quelques uns (élagage). Représentation par réduction d'un problème, graphe ET/OU d'un problème: Un arbre dont chaque noeud correspond à un sous-problème à résoudre. Les liens d'un noeud à ses enfants sont * soit tous des liens OU, signifiant qu'il faut résoudre un des enfants pour résoudre le parent. Ces liens correspondent aux liens de la représentation du problème par espace d'état. * soit tous des liens ET, signifiant qu'il faut résoudre tous les enfants pour résoudre le parent. La racine représente le problème original. Graphe solution d'un problème: Un sous-graphe du graphe ET/OU * qui contient la racine * dont tous les feuilles sont des problèmes primitifs résolus * dont tous les noeuds avec des enfants ET ont tous leurs enfants ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ La théorie des jeux ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Jeu à deux joueurs: Un jeu joué par deux joueurs qui effectuent des déplacements (transformations de l'état du jeu) en alterance. On appelle le premier joueur MAX et le deuxième MIN. À chaque état final du jeu est associé la notion du joueur ayant gagné. Jeu à l'information totale: Un jeu dont toute information concernant l'état du jeu est connue à tous les joueurs. Les jeux joués par des informaticiens (pardon: par des programmes informatiques) sont pour la plupart des jeux à deux joueurs et à information totale. C'est eux qu'on va considérer dans toute la suite. Arbre de jeu: L'arbre du problème du jeu. Chaque niveau correspond au choix d'un jouer, la racine étant le premier niveau et donc correspondant à MAX. Un noeud d'un niveau du jouer XXX est appelé un "noeud XXX". Les feuilles sont étiquetées par * GAGNANT ou INF si MAX a gagné * PERDANT ou -INF si MAX a perdu (et donc MIN a gagné) * NUL ou 0 si ni MAX ni MIN n'a gagné Annotation: Cela est peut être mal expliqué dans le polycopié, c'est toujours le point de vue de MAX. Étiquettage d'un arbre de jeu: Le processus d'assigner aux noeuds une des étiquettes GAGNANT, PERDANT, NUL. Ces étiquettes expriment à quel état final le choix du noeud va mener. On présuppose que chaqu'un des joueurs fasse un choix optimal pour sa situation: MAX va choisir un déplacement dont il sait qu'il va mener à un noeud GAGNANT -- si MIN fait toujours des déplacements pour arriver à un noeud PERDANT. Étiquettage simple: L'algorithme suivant pour l'étiquettage complet d'un arbre de jeu: 1. Soit A l'arbre du jeu 2. Soient les feuilles de A déjà étiquettées 3. Soit p la profondeur de A 4. TantQue p != 0, repète 5. p := p - 1 6. PourTout noeud n du niveau p 7. Si n n'est pas une feuille, alors 8. Si p est un niveau MAX alors 9. Si il existe un enfant GAGNANT de n, alors n est GAGNANT 10. Sinon 11. Si tout enfant de n est PERDANT, alors n est PERDANT 12. Sinon n est NUL 13. FinSi 14. Sinon 15. Si il existe un enfant PERDANT de n, alors n est PERDANT 16. Sinon 17. Si tout enfant de n est GAGNANT, alors n est GAGNANT 18. Sinon n est NUL 19. FinSi 20. FinSi 21. FinSi 22. FinPourTout 23. FinTantQue Un tel étiquettage permet donc de prédire si MAX peut gagner le jeux ou pas -- si les joueurs jouent d'une manière optimale. MINIMAX algorithme: Un algorithme d'étiquettage qui n'a pas besoin d'explorer tout l'arbre -- ce qui est bien parce que l'arbre peut être assez grand. Au lieu de cela, on utilise une heuristique qui prend un état du jeu et estime la probabilité que MAX va gagner. L'algorithme est le suivant: 1. Soit A l'arbre du jeu 2. Soit p la profondeur de A jusqu'à laquelle on veut explorer l'arbre 3. Donne à tout noeud du niveau p sa valeur heuristique 4. TantQue p != 0, repète 5. p := p - 1 6. PourTout noeud n du niveau p 7. Si n n'est pas une feuille, alors 8. Si p est un niveau MAX alors n prend le maximum des valeurs de ses enfants 9. Sinon n prend le minimum des valeurs de ses enfants 10. FinSi 11. FinPourTout 12. FinTantQue On peut effectuer cet algorithme aussi récursivement à partir de la racine. Principe alpha-beta: Si tu as une idée qui est certainement mauvaise, ne prends pas le temps pour explorer tous ses désavantages. (If you have an idea that is surely bad, do not take time to see how truely awful it is. (Nilsson) ) Étiquettage alpha-beta: Un algorithme pour l'étiquettage d'un arbre de jeu qui profite du principe alpha-beta. Il effectue une recherche en profondeur et utilise une heuristique pour éviter l'exploration de tout l'arbre -- comme MINIMAX. De plus, il se donne un intervalle [alpha, beta] pour l'exploration de chaque sous-arbre. Cet intervalle stocke les limites des choix de MIN (alpha) et MAX (beta). Si MIN a un choix qui est meilleur (plus petit) qu'alpha, il ne vaut pas explorer ses autres choix: De toute facon, le MAX précédent ne va jamais laisser MIN arriver à un point où MIN a un choix meilleur que sa limite. MAX a calculé cette limite a partir de ses autres choix. L'algorithme est le suivant: 1. Soit f:N->R l'heuristique 2. Soit plim la profondeur maximale à explorer 3. Soit n l'état initial du jeu 4. L'étiquette de n est alphabeta(n, -INF, INF) 5. C'est fini 6. Fonction alphabeta(n, alpha, beta) 7. Si n est une feuille, alors retourne l'étiquette de n 8. Si la profondeur de n est plus grande que plim, alors retourne f(n) 9. Si n est un noeud MAX, alors // On explore a priori tous les enfants de n 10. Pour tous les enfants s de n, repète // On essaye de maximiser le choix // Le meilleur choix est en même temps une limite // inférieure pour un choix suivant quelconque de MIN 11. alpha:=max({alpha,alphabeta(s, alpha, beta)}) // Si nous avons dépassé notre limite beta, il ne vaut // plus continuer 12. Si alpha >= beta, alors retourne beta 13. FinPourTous // Nous avons maximisé alpha dans nos limites 14. retourne alpha 15. Sinon // On explore a priori tous les enfants de n 16. Pour tous les enfants s de n, repète // On essaye de minimiser le choix // Le meilleur choix est en même temps une limite // superieure pour un choix suivant quelconque de MAX 17. beta := min({ beta, alphabeta(s, alpha, beta) }) // Si nous avons dépassé notre limite alpha, il ne vaut // plus continuer 18. Si beta =< alpha, alors retourne alpha 19. FinPourTous // Nous avons minimisé beta dans nos limites 20. retourne beta 21. FinSi 22. FinFonction Annotation: L'algorithme du polycopié complique les choses un petit peu. Étiquettage alpha-beta à la main: L'algorithme suivant, qui effectue un étiquettage alpha-beta d'une maniere plus simple: 1. Soit n la racine de l'arbre de jeu 2. alphabeta2(n) 3. C'est fini 4. Procédure alphabeta2(n) 5. Si n est une feuille, alors retourne 6. Si n est un noeud MAX, alors 7. valeur(n) := -INF 8. PourTout enfant s de n 9. alphabeta2(s) 10. Si valeur(s) > valeur(n), alors valeur(n) := valeur(s) 11. Si valeur(n) > min({valeur(i)| i est un noeud MIN supérieur}), alors retourne // Coupe 12. FinPourTout 13. Sinon 14. valeur(n) := INF 15. PourTout enfant s de n 16. alphabeta2(s) 17. Si valeur(s) < valeur(n), alors valeur(n) := valeur(s) 18. Si valeur(n) < max({valeur(i)| i est un noeud MAX supérieur}), alors retourne // Coupe 19. FinPourTout 20. FinSi 21. FinProcédure ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Les jeux ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Jeu des n reines: Le problème de placer n reines sur un échiquier de telle sorte qu'aucune ne soit en prise. Une reine prend une autre, si elle se trouve sur la même ligne, sur la même colonne ou sur la même diagonale. Algorithme: On place une reine sur la première ligne, puis une deuxième sur la deuxième ligne de sorte qu'elle ne soit pas prise. On continue jusqu'à ce qu'on a mis toutes les reines. Dans chaque étape, on choisit la position sur la ligne, pour laquelle l'heuristique rend la meilleure valeur Heuristiques (à maximiser): * Le nombre de cases inattaquées * Le nombre de cases inattaquées de la ligne ayant le plus petit nombre de cases inattaquées. Ceci afin d'éviter un blocage futur. Jeu du taquin: Le problème de réarranger les pièces d'une grille jusqu'à ce qu'ils sont dans leur ordre. On possède une grille carrée et chaque boîte est prise par une pièce -- sauf une. Les pièces sont numerotées et on essaye de les arranger dans leur ordre. À chaque étape, on bouge une pièce dans une boîte vide. Algorithme: On explore toutes les configurations qu'on peut atteindre par un seul déplacement à partir de l'état courant . On juge leur qualité grâce à une heuristique et on choisit le déplacement qui mène à la meilleure configuration. Heuristiques (à minimiser): * Le nombre des pièces malplacées * La somme des distances (horizontales et verticales) de chaque pièce de sa position idéale ("Manhatten distance") Jeu de la fausse pièce: Le problème d'identifier une pièce fausse parmi 12 pièces de monnaie à l'aide d'une balance. La pièce fausse est soit plus légère, soit plus lourde que les autres, qui ont toutes le même poids. La balance a deux plateaux. Algorithme: On choisit un sous ensemble de pièces d'une taille jugé bonne par une heuristique. On place ces pièces sur les deux plateux et on pèse. On continue avec le sous ensemble qui doit comprendre la fausse pièce. Heuristique (à minimser): * Le maximum des pièces qui restent à examiner si * la balance s'est équilibrée * la balance penche à droite * la balance penche à gauche Jeu du voyageur de commerce, Travelling salesperson problem, TSP: Le problème de trouver le plus court chemin qui lie un ensemble de villes donné. Jeu des flèches: Le problème d'inverser le sens de flèches afin d'obtenir un état ou toutes les flèches sont dans le même sens. On possède une suite de n flèches, qui peuvent avoir un sens vers le haut ou vers le bas. On peut toujours inverser un couple de deux flèches voisines. Algorithme: On représente les flèches par une suite de 0 (vers le bas) et 1 (vers le haut). On explore toutes les états qui peuvent être atteindus par un seul déplacement et on en choisit le meilleur à l'aide d'une heuristique. Heuristiques (à minimiser (?)): * Le nombre des flèches par le haut (ne marche pas avec l'escalade) * La distance maximale entre deux flèches mal placées Jeu de tic-tac-toc: Un jeu où chaqu'un des deux joueurs essaye de placer 3 de ses signes dans une diagonale, une ligne ou une colonne d'une grille de 3*3 boîtes. Les joueurs placent ses signes (X pour MAX, O pour MIN) en alternance dans des boîtes encore libres. Si la grille est remplie sans qu'un des joueurs a mis trois signes en ligne, c'est un match nul. Algorithme: On utilise alpha-beta. Heuristique (à maximiser): * La différence du nombre des lignes, colonnes, diagonales ouvertes pour MAX et du nombre des lignes, colonnes, diagonales ouvertes pour MIN