IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Quand utiliser les files ?


Sujet :

Algorithmes et structures de données

  1. #1
    Nouveau membre du Club Avatar de bj303931
    Femme Profil pro
    Étudiant
    Inscrit en
    Février 2016
    Messages
    75
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Février 2016
    Messages : 75
    Points : 27
    Points
    27
    Par défaut Quand utiliser les files ?
    Bonjour, quand et pourquoi utiliser une file? Une Pile?

    Par exemple, dans les algorithmes de parcours de graphe (Dijkstra...) il y a une file et je ne comprends pas pourquoi...
    Pourriez-vous m'aider, s'il vous plaît?
    Grand merci à vous.

  2. #2
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    Août 2008
    Messages
    26 609
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : Août 2008
    Messages : 26 609
    Points : 188 580
    Points
    188 580
    Par défaut


    Une file est une structure de données FIFO : le premier élément arrivé sera le premier élément sorti. Au contraire, la pile fonctionne dans l'ordre inverse, LIFO : le premier élément arrivé dans la pile sera le dernier que tu pourras récupérer.

    Pour Dijkstra, tu effectues un parcours en largeur de ton graphe : le nœud de départ, puis tous ses voisins, puis tous les voisins de ces voisins, etc. (Au contraire, un parcours en profondeur continue à s’éloigner, à parcourir d'abord les enfants du nœud courant.) Pour ce parcours en largeur, tu dois utiliser une file : quand tu commences au niveau de ta source, tu explores un voisin, puis tu stockes les autres voisins pour exploration immédiate dans une file. Chaque fois que tu vois un nœud, tu places tous ses voisins pas déjà explorés à la fin de la file. Ainsi, tu parcourras bien tous les nœuds du graphe "en largeur".
    Vous souhaitez participer aux rubriques Qt (tutoriels, FAQ, traductions) ou HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  3. #3
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    Décembre 2013
    Messages
    4 038
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : Décembre 2013
    Messages : 4 038
    Points : 9 347
    Points
    9 347
    Par défaut
    Les expressions 'en largeur' et 'en profondeur' sont claires, mais j'ai bien peur que notre ami ne les comprenne pas.

    Quand on parcours un arbre en largeur, on va recenser tous les points qui sont à une distance de 1 du point de départ, puis tous les points qui sont à une distance de 2 du point de départ, puis tous les points ç une distance de 3 , etc, etc, etc,
    Alors que dans un parcours en profondeur, on va parcourir une branche, et on va aller jusqu'au bout de cette branche, et quand on en aura fini avec cette branche, on attaquera une autre branche.
    Par exemple, si on prend un cas classique : sur un damier 8x8, avec des cases notées de A1 à H8, on part de la case A1, et on veut 'visiter' chaque case.
    On va forcément commencer par dire que les 2 voisins de A1 sont les cases A2 et B1. on va donc mettre ces 2 cases dans une file ou dans une pile.
    file = {(B1, 1);(A2,1)} : Dans ma file, je donne la case visitée, et la distance par rapport à la case A1.
    à l'étape suivante, on va avoir : file = {(A2,1);(B2,2);(C1,2)}
    Et à la 3ème étape, on va avoir : file = {(B2,2);(C1,2);(A3,2)} On parcourt en largeur, on a tous les éléments à 1 pas de l'origine, puis tous les éléments à 2 pas de l'origine ... ...

    Dans le cas d'un parcours en profondeur, on va avoir :
    pile = {(B1, 1);(A2,1)}
    Puis pile = {(B1,1);(B2,1);(A3,2)}
    Puis pile = {(B1,1);(B2,1);(B2,3);(A3,3)} : à chaque nouveau mouvement, on prend la dernière case recensée, et on recherche ses voisins.
    Puis pile = {(B1,1);(B2,1);(B2,3);(B3,4);(A4,4)} : On a dans notre recensement des points à une distance de 1 de l'origine, et aussi des points à une distance de 2, ou de 3 ou même de 4 !
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  4. #4
    Nouveau membre du Club Avatar de bj303931
    Femme Profil pro
    Étudiant
    Inscrit en
    Février 2016
    Messages
    75
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Février 2016
    Messages : 75
    Points : 27
    Points
    27
    Par défaut
    Où peut-on utiliser les files encore?

  5. #5
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    Août 2008
    Messages
    26 609
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : Août 2008
    Messages : 26 609
    Points : 188 580
    Points
    188 580
    Par défaut
    Une file d'attente à un guichet (ou pour accéder à une ressource partagée, en général ; dans le même genre, le traitement des événements comme des clics qui arrivent à une application), un système peu efficace de gestion des caches (dès qu'il est rempli, on élimine la première entrée arrivée ; voir anomalie de Bellady pour l'efficacité moyenne).
    Vous souhaitez participer aux rubriques Qt (tutoriels, FAQ, traductions) ou HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

Discussions similaires

  1. Quand utiliser les requêtes imbriquées ?
    Par yann18 dans le forum Débuter
    Réponses: 2
    Dernier message: 29/06/2011, 22h11
  2. [EJB3] Quand utiliser les ejb ?
    Par tastika dans le forum Java EE
    Réponses: 5
    Dernier message: 04/03/2009, 17h57
  3. Quand utiliser les pointeurs ?
    Par kedare dans le forum Qt
    Réponses: 4
    Dernier message: 22/08/2007, 12h50
  4. [POO] Quand utiliser les Exceptions?
    Par ChriGoLioNaDor dans le forum Langage
    Réponses: 2
    Dernier message: 20/06/2007, 09h40
  5. quand utiliser les modules de classe
    Par borislotte dans le forum Access
    Réponses: 3
    Dernier message: 02/03/2007, 15h56

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo