Topic outline

  • Organisation générale

    Collapse all Expand all

  • Exercices de préparation des TD

    En faire le maximum.
    Les exercices avec le même numéro sont équivalents, un peut suffire au départ ; pour réviser, faites les autres.
    • Exercices à préparer pour le TD1. Thème Bases de faits.

      Exemples : les relations familiales, l'organisation d'un repas équilibré, les puzzles logiques de Lewis Caroll, les nombres (symboliques), ... tout système symbolique fini et fermé [clos]

      Dans chaque exercice, les éléments sont des symboles uniques (atome au sens ProLog : i.e. identificateurs commençant par une minuscule) dont les propriétés sont données par des prédicats de type "fait" (pas de partie droite, seulement une partie gauche [ou but, ou conclusion]).
      A partir de ces faits, il s'agit de construire des règles (prédicats ProLog complets avec une partie gauche [le but, ou conclusion] et un ensemble de parties droites [les prémisses, ou corps de la règle]) qui décrivent les objets.
      En général, dans les exercices simples, l'hypothèse de monde clos permet de définir des relations négatives et d'éviter les boucles infinies, mais si l'on avance dans des exercices plus compliqués, il n'y aura pas de garantie que cela soit toujours vérifié.
    • Exercices à préparer pour le TD2. Thème premiers algorithmes sur les listes.

      La liste des exercices simples sur les listes serait trop longue pour tenir sur l'écran. Rappelons simplement que la liste vide s'écrit : [ ], les listes en extension : [1, 2, 3] et les listes en intension sont définies par leur premier élément et leur queue (liste elle-même) : [ E | Q ].

      Généralement, les exercices consistent à définir un algorithme en appliquant une analyse récursive basée sur la structure récursive d'une liste. Le schéma de base du programme est donc :

      • prog(cas_de_base).
      • prog([ E | Q ]) :-
          prog(Q).
    • Exercices à préparer pour le TD3. Thème Les Tris.

      Simplement, à partir d'une analyse récursive systématique de l'un ou l'autre de paramètre d'un prédicat de tri, il est possible de produire, sans beaucoup d'imagination, de nombreux algorithmes de tri classique. Et quand cette analyse est dichotomique, cela peut donner des tris efficaces [en n.log(n)]. Il y a là, entre le moteur d'inférence ProLog et l'analyse récursive, du génie.

    • Exercices à préparer pour le TD4. Thème structures de données.

      L'utilisation de listes dans une analyse récursive [ E | Q ] mène naturellement à la notion de pile, le dernier élément mis dans une liste sera le premier que l'on enlèvera (LIFO).

      Avec 2 listes, on peut retrouver la notion de file (une liste pour la tête, une liste pour la queue ; ex : T=[1, 2, 3 | Q ] et Q). Quand on veut ajouter un élément dans la file, il faut l'ajouter en queue. Par exemple, si on ajoute 4 à la liste précédente, on a Q = [4|Q'], et la nouvelle queue de liste est Q'. Si on veut retirer un éléments de la file, il faut le prendre à la tête. Dans l'exemple, on retire l'élément 1, et la nouvelle tête commence à 2. Avec deux listes, dans la même situation, on parle aussi parfois, de différence de listes : les éléments à considérer sont ceux obtenus par différence T - Q. C'est assez proche de la notion de liste avec pointeur de queue en algorithmique classique.

      En imbriquant les listes, on peut obtenir des listes d'association, des dictionnaires, ou des arbres. Les listes d'association et dictionnaires peuvent être de simples listes de couples [Entrée,Valeur] (liste triée pour les dictionnaires), les arbres peuvent être des arbres binaires constitués d'une valeur et de deux sous-arbres, ex : [racine,[gauche,[],[]],[droite,[],[]] pour un arbre avec 3 noeuds.

      Avec la résolution des contraintes on peut obtenir des listes circulaires, arbres infinis rationnels, des graphes, etc ...

    • Exercices à préparer pour le TD5. Thème recherche combinatoire.

      L'intelligence artificielle symbolique a abordé de nombreux problèmes de recherche combinatoire (branch and bound). Cela peut se traiter particulièrement bien avec ProLog dont le moteur d'inférence est basé sur une approche combinatoire, et encore plus depuis que ProLog est associé à des moteurs de résolutions [ou vérification] de contraintes. Ici, il y aura donc plusieurs règles récursives, pour provoquer de la redondance et des contraintes pour limiter la taille de l'espace de recherche. Parmi les méthodes générant la combinatoire, on peut citer des méthodes génériques, celles qui cherchent des répartitions ou des parties, celles qui cherchent des permutations ou des associations, celle qui regardent tous cas possible (par produit(s) cartésien(s)) en opérant des énumération, ... Pour les contraintes, il y a les contraintes d'ordre, de différence, les contraintes arithmétiques, ...

    • Exercices à préparer pour le TD6. Thème Langages formels.

      A l'origine de ProLog, la logique et les langages formels. Depuis longtemps, la forme des programmes ProLog et la forme des grammaires de langages formels sont associées (forme et sémantique), à tel point que ProLog comporte un sous-langage dédié (pas utilisé ici).

      Les exemples d'applications sont innombrables, les développements possibles peuvent aussi aller très loin.

    • TD7 : correction du partiel

  • Evaluations des connaissances

    nota bene : pour les parties "Programmation Logique" et "Langages formels" voir d'anciennes archives ici.

  • Divers

  • GROUPE 3

    Not available unless: You belong to a group in G3