Le parcours en profondeur (DFS) pour planifier (= tri topologique d'un graphe orienté sans circuit)

No video

Le parcours en profondeur (DFS) pour planifier (= tri topologique d'un graphe orienté sans circuit)

Рет қаралды 36,607

À la découverte des graphes

Күн бұрын

Пікірлер: 22

@DeltaBassFrance 2 жыл бұрын

J'ai appris tellement mieux avec votre vidéo qu'en plusieurs heures à la fac, un grand merci à vous

@abdoulraoufgambo Жыл бұрын

j'avais suivis vos vidéos sur les graphes au premiers semestre ça m'a énormément aider.

@AlmoustaphaDjibrilla 10 ай бұрын

kasko😇

@meryemgazanayi5665 2 жыл бұрын

merci

@zakariaaitali9006 3 жыл бұрын

Merci infiniment pour cette explication très claire

@fabienenigmadumont 5 жыл бұрын

Merci beaucoup pour la vidéo

@chaimasoubai7204 2 жыл бұрын

merci bcp

@meryemgazanayi5665 2 жыл бұрын

siri t9ray

@user-ot6nu6vb7r 2 жыл бұрын

Par rapport au temps d'exécution des algorithmes DFS et IFS qui est le plus rapide?

@aissaelmagharibia228 2 жыл бұрын

زيد دروس يتعلق بالبحث العلمي

@mohamedelmatal6820 Жыл бұрын

pouvez vous m'aider dans le traitement de quelques exercices ? 🙏

@franckc2806 4 жыл бұрын

Bonjour, le tri topologique par DFS se programme récursivement (fonction qui s'appelle elle-même) et aussi sans récursivité si on créé soi-même une pile LIFO qui remplace celle que le programme récursif créé de toute façon sans qu'on le sache ! J'ai fait ce programme non récursif (que j'ai pas trouvé sur internet...) et je suis confronté à un problème: quelle est la taille maximale de la pile LIFO nécessaire ? Au début, je croyais naïvement que c'était n, le nombre de sommets, mais en testant le programme sur pleins de graphes aléatoires sans circuits, je m'aperçois que c'est peut être même entre 2n et n au carré. Je ne pensais pas que la taille de la pile nécessaire serait aussi grande. Existe-t-il une valeur théorique de cette taille ? En effet, connaître la taille maximale de la pile est absolument indispensable pour savoir si l'algorithme est fiable et qu'il ne va pas créer un buffer overflow. Bien cordialement. PS: j'ai aussi un autre algorithme de tri-topologique assez simple que j'ai trouvé moi-même, sans faire de DFS, ni de récursivité, et qui marche à "tous les coups", en détectant de surcroit un graphe qui aurait un circuit (à tous les coups de manière expérimentale, je n'ai pas preuve mathématique).

@a_la_decouverte_des_graphes 4 жыл бұрын

Bonjour. Il y a une autre vidéo sur ma chaine qui décrit une autre méthode qui ne fait pas appel au DFS. Je vous invite à la regarder.

@samiotmani9092 5 жыл бұрын

Bonjour , Étant étudiant en médecine je me posais une question. Est-il possible d’utiliser les graphes afin de modéliser les liens logiques entre différentes propositions de telle sorte qu’on puisse faire ressortir un graphe d’un texte quelconque ? Ainsi pour mémoriser une grande quantité de donnés d’un texte il suffirait de l’associer à son graphe. Mais alors comment faire ? Merci pour vos vidéos et votre réponse,

@a_la_decouverte_des_graphes 5 жыл бұрын

Bonjour. Je ne suis pas sûr de bien comprendre votre question. On peut toujours associer un graphe à un texte, de multiple manière, mais je ne suis pas certain que cela ait de l'intérêt. Si l'objectif est de réduire la taille d'un texte il vaut mieux utiliser un algorithme de compression de données (sans pertes). Si l'objectif est autre alors je n'ai pas compris votre question...

@samiotmani9092 5 жыл бұрын

Alors comment associer un graphe à un texte ?

@a_la_decouverte_des_graphes 5 жыл бұрын

On peut imaginer de faire la chaine des mots du texte. Chaque mot est un sommet et on place un arc d'un mot vers le suivant dans le texte. On peut mettre un sommet par mot (si le mot apparait plusieurs fois on ne le met qu'une seule fois) et mettre une arête entre deux sommets si les 2 mots sont voisins (avant ou après) dans le texte. On peut faire pareil avec les caractères (lettres + ponctuation). On peut séparer les types de mots (noms, verbes, adjectifs, etc.) et mettre des arcs s'ils se suivent dans le texte. ... Tous les graphes que je viens de décrire n'ont (a priori) AUCUN intérêt, ils sont "inutiles". Ce sont juste des graphes que l'on peut associer à un texte. La question est : associer un graphe à un texte : OK mais pour quoi faire ? Pour quel usage ? pour résoudre quel problème ? Pour analyser quoi ? pour faire quel traitement ? pour comprendre quoi ? Si l'objectif est de réduire la taille du texte sans perdre de l'information, le plus simple est d'utiliser un algorithme de compressions de données (type Huffman). Notez au passage que dans le bel algorithme de compression de Huffman il y a un graphe (un arbre) mais il 'est un peu difficile d'expliquer son usage dans un commentaire...

@samiotmani9092 5 жыл бұрын

L’intérêt serait de relier les concepts et idées d’un texte par une arrête qui serait un lien logique (cause-conséquence ...) . Le ou les sommets avec le plus d’arrêtes seraient alors les notions centrales à retenir. Dans le cadre d’étude en médecine, où par semaine il y peut y avoir plus de 300 pages à étudier, les graphes pourrait être un formidable moyen de hiérarchiser les informations en fonction de de leur importance. Ma question est , est ce que les graphes peuvent se prêter à ce genre d’utilisation ? Merci pour vos réponses et votre patience. Désolé si mes commentaires n’étaient pas clairs et si cette idée sort un peu des clous.

@a_la_decouverte_des_graphes 5 жыл бұрын

Ce genre de chose est probablement envisageable. MAIS ici les liens que vous envisagez se ferraient à partir de notions sémantiques (sur le sens des termes) et, à cause des ambiguïtés, des mots à sens multiples, du contexte dans lequel c'est employé, de la qualité du texte qui contient ces mots, etc. tout cela est TRES délicat à manipuler. Je suppose que les linguistes ont déjà des outils informatiques (sans doute +/- expérimentaux) pour ce genre de choses. Il est tout à fait possible que leurs outils qui analysent les textes sortent leurs résultats sous forme de graphe implicite (peu de gens connaissent la notion de graphes mais l'utilisent (souvent mal). D'où ma chaine...). Bref : + Je ne connais pas les travaux autour de tout ça (mais je pense qu'il y en a). + Ce n'est peut-être PAS la partie graphe qui est la plus compliquée mais bel est bien l'extraction du "contenu" sémantique du texte (à cause des points mentionnés plus haut). Si je vois des travaux, voire outils, autour de cette problématique, je laisserai un message... Bon courage pour vos études !