Course: Informatique - ProLog (UGA, L3Miage)

Topic outline

Organisation générale

Collapse all Expand all
- Présentation générale Page
- Cours Page
  
  Lien vers un cours associé : Programmations déclaratives (UGA-L3-Miage)
- TD (organisation, préparation) Page
- Forum
- Brouillon libre Prolog Virtual programming lab
- Autres brouillons de programmation (Open Caseine !) URL
- Carte des exercices Page
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é.
- Exercice ProLog 1 : balade (sudEst) Virtual programming lab
  
  Receive a grade
- Exercice ProLog 2 : balade (nord) Virtual programming lab
  
  Receive a grade
- Exercice ProLog 3 : balade (directionSud) Virtual programming lab
  
  Receive a grade
- Exercice ProLog 4 : balade (quartSE) Virtual programming lab
  
  Receive a grade
- Exercice ProLog 10 (=1+...+4) : balades (façon requête bd) Virtual programming lab
  
  Receive a grade
- Exercice ProLog 1 : famille (grandParent) Virtual programming lab
  
  Receive a grade
- Exercice ProLog 2 : famille (enfant) Virtual programming lab
  
  Receive a grade
- Exercice ProLog 3 : famille (ancetre) Virtual programming lab
  
  Receive a grade
- Exercice ProLog 4 : famille (generation) Virtual programming lab
  
  Receive a grade
- Exercice ProLog 10 (=1+...+4) : famille (façon requête bd) Virtual programming lab
  
  Receive a grade
- Eléments de correction (Familles) URL
- Exercice ProLog 1 : arithmétique sur les nombres romains (+2) Virtual programming lab
  
  Receive a grade
- Exercice ProLog 2 : arithmétique sur les nombres romains (-1) Virtual programming lab
  
  Receive a grade
- Exercice ProLog 3 : arithmétique sur les nombres romains (+) [durée moyenne < 15 min] Virtual programming lab
  
  Receive a grade
- (** A FAIRE L3 Miage **) Exercice ProLog&Test 3 : arithmétique sur les nombres romains (+) Virtual programming lab
  
  Receive a grade
- Exercice ProLog 4 : arithmétique sur les nombres romains (*) [temps moyen : 20 min] Virtual programming lab
  
  Receive a grade
- Exercice ProLog 5 : arithmétique sur les nombres romains (estPair) Virtual programming lab
  
  Receive a grade
- Exercice ProLog 6 : arithmétique sur les nombres romains (>) Virtual programming lab
  
  Receive a grade
- Exercice ProLog 7 : arithmétique sur les nombres romains (max) Virtual programming lab
  
  Receive a grade
- Exercice ProLog 8 : arithmétique sur les nombres romains (pgcd) Virtual programming lab
  
  Receive a grade
- Exercices ProLog 36 (=1+...+8) : arithmétique sur les nombres romains (façon requête bd) Virtual programming lab
  
  Receive a grade
- 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 intention 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).
  Exemple, pour la concaténation (spec. : le troisième argument doit être la concaténation des deux premiers dans cet ordre) :
  concatener([ ], L, L).
  concatener([E | F], L, [E | R]) :-
  concatener(F, L, R).
- QCM d'entrainement sur les Listes [E|L] (ProLog, Erlang) hors programmes Quiz
  
  Receive a grade
- QCM d'entrainement sur la complétude et la terminaison de programmes ProLog Quiz
  
  Receive a grade
- Exercice ProLog 0 : coupe en deux avec concat (et memeLongueur) [temps moyen < 20 min] Virtual programming lab
  
  Receive a grade
- Exercice ProLog 1.0 : longueur d'une liste [temps moyen : 10 min] Virtual programming lab
  
  Receive a grade
- Exercice ProLog 1.1 : dériver une liste (liste des différences successives) Virtual programming lab
  
  Receive a grade
- Exercice ProLog 2.0 : inverser une liste [temps moyen < 10 min] Virtual programming lab
  
  Receive a grade
- (** A FAIRE L3Miage **) Exercice ProLog 2.0 : inverser une liste Virtual programming lab
  
  Receive a grade
- Exercice ProLog 2.1 : palindrome Virtual programming lab
  
  Receive a grade
- Exercice ProLog 0 : échanger premier dernier avec concat Virtual programming lab
  
  Receive a grade
- Exercice ProLog 1.0 : somme des entiers d'une liste [temps moyen < 10 min] Virtual programming lab
  
  Receive a grade
- Exercice ProLog 1.1 : supprimer les zéros [temps moyen : 25 min] Virtual programming lab
  
  Receive a grade
- Exercice ProLog 2 : supprimer les doublons (qlcq) [temps moyen : 35 min] Virtual programming lab
  
  Receive a grade
- Exercice ProLog 0 : facteur avec concat Virtual programming lab
  
  Receive a grade
- Exercice ProLog 1.1 : plus long préfixe commun Virtual programming lab
  
  Receive a grade
- Exercice ProLog 1.5 : coupe en deux (sans concat) Virtual programming lab
  
  Receive a grade
- Exercice ProLog 2 : échanger début fin Virtual programming lab
  
  Receive a grade
- 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.
- Exercice ProLog 0 : est-ce trié ? Virtual programming lab
  
  Receive a grade
- Exercice ProLog 1 : recherche du minimum [temps moyen : 15 min] Virtual programming lab
  
  Receive a grade
- Exercice ProLog 2 : tri par rech. du minimum Virtual programming lab
  
  Receive a grade
- (** A FAIRE L3 Miage **) Exercice&Test ProLog 2 : tri par rech. du min. Virtual programming lab
  
  Receive a grade
- Exercice ProLog 3 : tri fusion Virtual programming lab
  
  Receive a grade
- Exercice ProLog 1 : insertion [temps moyen : 15 min] Virtual programming lab
  
  Receive a grade
- Exercice ProLog 2 : tri par insertion. [temps moyen : 20 min] Virtual programming lab
  
  Receive a grade
- Exercice ProLog 3 : tri par pivot Virtual programming lab
  
  Receive a grade
- 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. À noter, l'adéquation entre récursivité et arbres : autant les listes sont facilement gérées avec des boucles en algorithmique classique (les deux "objets" sont "linéaires"), autant les arbres et les boucles peuvent avoir du mal à coexister. Comme les arbres sont essentiels pour pouvoir améliorer l'efficacité de nombreux programmes, la récursivité devient elle aussi essentielle pour l'algorithmique classique.
  Avec la résolution des contraintes on peut obtenir des listes circulaires, arbres infinis rationnels, des graphes, etc ...
- Exercice ProLog 1 : recherche dans une liste d'associations. Virtual programming lab
  
  Receive a grade
- Exercice ProLog 2 : Calculatrice à pile pour expressions postfixées. Virtual programming lab
  
  Receive a grade
- Exercice ProLog 3 : inversion (avec file) Virtual programming lab
  
  Receive a grade
- Exercice ProLog 1 : parcours d'un arbre Virtual programming lab
  
  Receive a grade
- Exercice ProLog 2 : nombre de feuilles d'un arbre Virtual programming lab
  
  Receive a grade
- Exercice ProLog 3 : hauteur d'arbre Virtual programming lab
  
  Receive a grade
- Exercice ProLog 0 : est-ce un arbre binaire de recherche ? Virtual programming lab
  
  Receive a grade
- Exercice ProLog 1 : maximum d'un arbre binaire de recherche Virtual programming lab
  
  Receive a grade
- Exercice ProLog 2 : recherche dans un arbre binaire de recherche Virtual programming lab
  
  Receive a grade
- Exercice ProLog 3 : insertion dans un arbre binaire de recherche [temps moyen : 20 min] Virtual programming lab
  
  Receive a grade
- (** A FAIRE L3 Miage **) Exercice ProLog 3 : insertion dans un arbre binaire de recherche Virtual programming lab
  
  Receive a grade
- Exercice ProLog 4 : suppression dans un arbre binaire de recherche Virtual programming lab
  
  Receive a grade
- 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, ...
- (** A FAIRE L3 Miage **) Exercice ProLog : La course à 100 (le compte est bon additif). [temps moyen : 20 min] Virtual programming lab
  
  Receive a grade
- Espace libre Prolog pour l'exercice, le coloriage, voir sujet Examen session 1, 2018-9. Virtual programming lab
  
  Receive a grade
- Exercice ProLog : Répartition équitable. Virtual programming lab
  
  Receive a grade
- Exercices à préparer pour un TD supplémentaire si le Thème Langages formels a été abordé.
  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.
- Exercice ProLog 1 : lecture de listes imbriquées. Virtual programming lab
  
  Receive a grade
- Exercice ProLog 2 : évaluation de listes imbriquées. Virtual programming lab
  
  Receive a grade
- Exercice ProLog 1 : lecture d'expressions arithmétiques simples. Virtual programming lab
  
  Receive a grade
- Exercice ProLog 2 : évaluation d'expressions arithmétiques simples. Virtual programming lab
  
  Receive a grade
- TD7 : correction du partiel, révision et/ou travail sur le mini-projet
Exercices issus d'épreuve d'évaluation des connaissances
- QCM d'auto-évaluation ProLog Quiz
- Plus d'exercices issus des annales ? Choice
- 2016-2017
- CC 1, 2016-17, Algorithmique File
- Exercice ProLog (d'après CC 2016-17) : nombre d'occurences Virtual programming lab
  
  Receive a grade
- Exercice ProLog (d'après CC 2016-17) : compte et supprime Virtual programming lab
  
  Receive a grade
- Exercice ProLog (d'après CC 2016-17) : histogramme Virtual programming lab
  
  Receive a grade
- 2017-2018
- CC, 2017-18, Partie programmation logique File
- Analyse de programme ProLog abstrait (d'après CC 2017-18) : programme red Quiz
- Exercice ProLog (d'après CC 2017-18) : supprime min et max Virtual programming lab
  
  Receive a grade
- Exercice ProLog (d'après CC 2017-18) : médiane Virtual programming lab
  
  Receive a grade
Divers
- Démonstration Sketchpad (1963), programmation par contraintes. URL
- Exercice ProLog : déplier une liste Virtual programming lab
  
  Receive a grade
- Exercice ProLog : tri2 (min/max) Virtual programming lab
  
  Receive a grade
- Exercice ProLog : plusUn Virtual programming lab
  
  Receive a grade
- Exercice Prolog : à 1 près (par requête à l'interpréteur) Virtual programming lab
  
  Receive a grade
- Exercice ProLog : somme1N Virtual programming lab
  
  Receive a grade
- Exercice ProLog : factoriel Virtual programming lab
  
  Receive a grade
- Exercice ProLog : prochain palindrome Virtual programming lab
  
  Receive a grade
- Exercice ProLog : Jour de Naissance Virtual programming lab
  
  Receive a grade
- Exercice ProLog : codage par répétition. Virtual programming lab
  
  Receive a grade
- Exercice ProLog : séparation lettre/chiffre Virtual programming lab
  
  Receive a grade
- Sujet TP-Mini projet (jan 2019) : Mise en groupe (binomes) File
  
  Objet : Pour faire des binômes, un enseignant a à sa disposition, les notes de ses étudiants (il voudrait mettre ensemble des étudiants par niveau) et les déclarations de ces étudiants sur l'envie qu'ils ont à travailler ensemble ou pas.
  Votre objectif : modéliser la situation, faire un programme qui propose une mise en groupe respectant autant que faire se peut les attentes de chacun ...
- Sujet TP-Mini Projet (janvier 2020) : Calculatrice scientifique Page
  
  On voudrait pouvoir faire : 2kg + 200g et obtenir le résultat [juste] en grammes (ou en kg, à vous de voir), idem quand on divise une distance par une vitesse pour savoir la durée d'un trajet.
  Par rapport à une calculatrice habituelle, il faut donc prendre en compte les unités (g[gramme], h[eure], ... éventuellement b[it], o[octet], ...) et les facteurs multiplicatifs (k[ilo], m[illi], ... éventuellement M[ega], G[iga], ...)
- Exercice ProLog : plusUn Virtual programming lab
  
  Receive a grade
Seconde chance 2020

Not available
Autre, en vrac

Informatique - ProLog (UGA, L3Miage)

Topic outline

Organisation générale

Exercices de préparation des TD

Exercices à préparer pour le TD1. Thème Bases de faits.

Exercices à préparer pour le TD2. Thème premiers algorithmes sur les listes.

Exercices à préparer pour le TD3. Thème Les Tris.

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

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

Exercices à préparer pour un TD supplémentaire si le Thème Langages formels a été abordé.

Exercices issus d'épreuve d'évaluation des connaissances

Divers

Seconde chance 2020

Autre, en vrac