Merci beaucoup pour toutes vos vidéos, on nous a recommandé de les regarder en cours d'algorithmique de L2 et elles permettent vraiment de bien comprendre :D
Si ça peut intéresser quelqu'un, il y a quelque temps pour apprendre Prolog, j'ai fait un code qui trouve les cycles. On crée des nœuds, par exemple : node(1). node(2). Des arcs, par exemple : arc(1,2). Un chemin de longueur 0 est un nœud : chemin(X,X,0) :- node(X). Un chemin de longueur 1 est un arc : chemin(X,Y,1) :- arc(X,Y). Un chemin de longueur > 1 : chemin(X,Y,L) :- L > 1, arc(X,Z), M is L - 1, chemin(Z,Y,M). Trouver les cycles : cycle(X,L) :- chemin(X,X,L). Exemple: trouver les cycles de longueur 2 : cycle(X,2).
@@emiliamazari5180 Ta question était adressée à moi ou bien à "À la découverte des graphes" ? Si c'était pour moi, j'ai peur de ne pas avoir compris ta question: ça fait 20 ans que je ne suis plus étudiant et donc je n'ai plus écrit d'algorithmes (au sens académique du terme) :D d'autant plus qu'avec Prolog tu n'écris pas d'algorithme, mais tu décris ton problème et il le résout pour toi. Prolog est semblable aux bases de données (BDD) SQL mais ici on parle de connaissance (Prolog a été créé pour l'IA pour le langage naturel) : node(1). node(2). arc(1,2). sont des faits: 1 est un noeud. 2 est un noeud (1,2) est un arc (orienté). En Prolog les variables commencent par une majuscule (comme X Toto). Les noms commencent par une minuscule (comme toto). Une règle Prolog s'écrit de cette façon A :- A0, A1. veut dire que A est vraie si A0 et A1 sont vrais. Le "ou bien" est une nouvelle règle, par exemple A :- B0, B1, B2. Prolog va "itérer" sur toutes les solutions possibles dans la BDD de connaissance (parcours de graphe). Ici j'ai dit à Prolog que 1/ un chemin de longueur L 0 est un noeud (connu dans la BDD) 2/ Un chemin de longueur L 1 est un arc (connu dans la BDD) 3/ Un chemin de longueur L > 1 est récursif. chemin(X,Y,L) :- L > 1, arc(X,Z), M is L - 1, chemin(Z,Y,M). veut dire que chemin(X,Y,L) est vrai si la variable L est > 1 et qu'il existe une variable intermédiaire Z tel que arc(X,Z) est un arc connu dans la BDD et que cet arc fait partie du chemin (récursif). Prolog va itérer sur la BBD et donner la liste des noms qui correspondent aux variables. Par exemple si tu tapes: cycle(X,0) il va donner 1 et 2. Si tu veux le "projet" complet github.com/Lecrapouille/BacASable/tree/master/Prolog
Merci beaucoup pour toutes vos vidéos, on nous a recommandé de les regarder en cours d'algorithmique de L2 et elles permettent vraiment de bien comprendre :D
Bien clair merci infiniment 🙏
Si ça peut intéresser quelqu'un, il y a quelque temps pour apprendre Prolog, j'ai fait un code qui trouve les cycles.
On crée des nœuds, par exemple :
node(1).
node(2).
Des arcs, par exemple :
arc(1,2).
Un chemin de longueur 0 est un nœud :
chemin(X,X,0) :- node(X).
Un chemin de longueur 1 est un arc :
chemin(X,Y,1) :- arc(X,Y).
Un chemin de longueur > 1 :
chemin(X,Y,L) :- L > 1, arc(X,Z), M is L - 1, chemin(Z,Y,M).
Trouver les cycles :
cycle(X,L) :- chemin(X,X,L).
Exemple: trouver les cycles de longueur 2 :
cycle(X,2).
je pourrais avoir la version algorithmique svp ?
@@emiliamazari5180 Ta question était adressée à moi ou bien à "À la découverte des graphes" ? Si c'était pour moi, j'ai peur de ne pas avoir compris ta question: ça fait 20 ans que je ne suis plus étudiant et donc je n'ai plus écrit d'algorithmes (au sens académique du terme) :D d'autant plus qu'avec Prolog tu n'écris pas d'algorithme, mais tu décris ton problème et il le résout pour toi.
Prolog est semblable aux bases de données (BDD) SQL mais ici on parle de connaissance (Prolog a été créé pour l'IA pour le langage naturel) : node(1). node(2). arc(1,2). sont des faits: 1 est un noeud. 2 est un noeud (1,2) est un arc (orienté). En Prolog les variables commencent par une majuscule (comme X Toto). Les noms commencent par une minuscule (comme toto). Une règle Prolog s'écrit de cette façon A :- A0, A1. veut dire que A est vraie si A0 et A1 sont vrais. Le "ou bien" est une nouvelle règle, par exemple A :- B0, B1, B2.
Prolog va "itérer" sur toutes les solutions possibles dans la BDD de connaissance (parcours de graphe). Ici j'ai dit à Prolog que 1/ un chemin de longueur L 0 est un noeud (connu dans la BDD) 2/ Un chemin de longueur L 1 est un arc (connu dans la BDD) 3/ Un chemin de longueur L > 1 est récursif. chemin(X,Y,L) :- L > 1, arc(X,Z), M is L - 1, chemin(Z,Y,M). veut dire que chemin(X,Y,L) est vrai si la variable L est > 1 et qu'il existe une variable intermédiaire Z tel que arc(X,Z) est un arc connu dans la BDD et que cet arc fait partie du chemin (récursif). Prolog va itérer sur la BBD et donner la liste des noms qui correspondent aux variables. Par exemple si tu tapes: cycle(X,0) il va donner 1 et 2. Si tu veux le "projet" complet github.com/Lecrapouille/BacASable/tree/master/Prolog
C’est quoi DFS ?