Publicité
+ Répondre à la discussion
Affichage des résultats 1 à 9 sur 9
  1. #1
    Modérateur
    Avatar de PRomu@ld
    Homme Profil pro Romuald Perrot
    Ingénieur de Recherche
    Inscrit en
    avril 2005
    Messages
    4 160
    Détails du profil
    Informations personnelles :
    Nom : Homme Romuald Perrot
    Âge : 29
    Localisation : France

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

    Informations forums :
    Inscription : avril 2005
    Messages : 4 160
    Points : 5 585
    Points
    5 585

    Par défaut [Algorithme] Contribuez à la page sources.

    Bonjour,

    Nous mettons en place une page source pour la rubrique algorithme et nous avons besoin de votre participation.

    Cette page contient des algorithmes en pseudo-code uniquement, les implémentations n'ont pas leur place ici !

    SI vous désirez contribuer, sachez que nous organisons les sources algo comme ceci :

    Entrée :
    Code :
    1
    2
    On présente ce que l'on donne à l'algorithme (un tableau, un arbre, ...)
    Sortie :
    Code :
    1
    2
    On indique ce que doit nous retourner le tableau (le tableau trié par ex.)
    Pseudo-Code:
    Complexité :
    Code :
    1
    2
    On indique une complexité ( mini , moy , max ).
    Merci à tous ceux qui participeront.


    La page source est accessible ici : http://algo.developpez.com/sources/
    http://rperrot.developpez.com
    http://phos-graphein.fr

    Vous désirez contribuer à la rubrique algorithmique, n'hésitez pas à me contacter.

  2. #2
    Rédacteur/Modérateur

    Avatar de millie
    Profil pro
    Inscrit en
    juin 2006
    Messages
    6 945
    Détails du profil
    Informations personnelles :
    Localisation : Luxembourg

    Informations forums :
    Inscription : juin 2006
    Messages : 6 945
    Points : 8 774
    Points
    8 774

    Par défaut

    les implémentations n'ont pas leur place ici
    Le problème est que parfois, la complexité dépend de l'implémentation que l'on donne aux types abstraits. Donc j'imagine que dans ce cas il faut préciser ?

  3. #3
    Modérateur
    Avatar de PRomu@ld
    Homme Profil pro Romuald Perrot
    Ingénieur de Recherche
    Inscrit en
    avril 2005
    Messages
    4 160
    Détails du profil
    Informations personnelles :
    Nom : Homme Romuald Perrot
    Âge : 29
    Localisation : France

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

    Informations forums :
    Inscription : avril 2005
    Messages : 4 160
    Points : 5 585
    Points
    5 585

    Par défaut

    la complexité dépend de l'implémentation
    En fait, si la complexité dépend de l'implémentation, celà veut dire que ton algo en est aussi dépendant donc ça apparaît aussitôt, il n'y a donc pas forcément besoin de le préciser. Mais si pour une application spécifique tu juges qu'il est bon de le préciser, fait-le.
    http://rperrot.developpez.com
    http://phos-graphein.fr

    Vous désirez contribuer à la rubrique algorithmique, n'hésitez pas à me contacter.

  4. #4
    Membre habitué

    Homme Profil pro Matthias
    Inscrit en
    septembre 2005
    Messages
    36
    Détails du profil
    Informations personnelles :
    Nom : Homme Matthias
    Âge : 29
    Localisation : France, Maine et Loire (Pays de la Loire)

    Informations forums :
    Inscription : septembre 2005
    Messages : 36
    Points : 123
    Points
    123

    Par défaut

    Q: Comment parcourir un graphe en largeur d'abord?

    R:

    Pour parcourir un graphe en largeur d'abord, nous utiliserons une file dans laquelle on placera les différents sommets.

    Idée générale:
    1. On part avec une file contenant le noeud de départ
    2. On défile le premier noeud pour le traiter
    3. On place les voisins non marqués de ce noeud en bout de file, après les avoir marqué
    4. Si la file n'est pas vide, on revient à l'étape 2

    Algorithme:

    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    Entree: 
        Graphe G
        Noeud S  //noeud initial du parcours
    
    Parcours_en_largeur(G,S)
        File F = FileVide();
        Enfiler(F, S);
        Marquer(S);
        tantque NON FileVide(F) faire
            Noeud N = Défiler(F);
            pour tout Noeud X dans Fils(N) faire
                si NonMarqué(X) alors 
                      Marquer(X);
                      Enfiler(F, X);
                finsi
           finpourtout
        fintantque

  5. #5
    Modérateur
    Avatar de PRomu@ld
    Homme Profil pro Romuald Perrot
    Ingénieur de Recherche
    Inscrit en
    avril 2005
    Messages
    4 160
    Détails du profil
    Informations personnelles :
    Nom : Homme Romuald Perrot
    Âge : 29
    Localisation : France

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

    Informations forums :
    Inscription : avril 2005
    Messages : 4 160
    Points : 5 585
    Points
    5 585

    Par défaut

    Le parcours en profondeur de graphe éxiste déjà dans la liste des sources :

    http://algo.developpez.com/sources/?...aphe#graph_dfs
    http://rperrot.developpez.com
    http://phos-graphein.fr

    Vous désirez contribuer à la rubrique algorithmique, n'hésitez pas à me contacter.

  6. #6
    Membre habitué

    Homme Profil pro Matthias
    Inscrit en
    septembre 2005
    Messages
    36
    Détails du profil
    Informations personnelles :
    Nom : Homme Matthias
    Âge : 29
    Localisation : France, Maine et Loire (Pays de la Loire)

    Informations forums :
    Inscription : septembre 2005
    Messages : 36
    Points : 123
    Points
    123

    Par défaut

    en effet mais il s'agit d'un parcours recursif...

  7. #7
    Modérateur
    Avatar de PRomu@ld
    Homme Profil pro Romuald Perrot
    Ingénieur de Recherche
    Inscrit en
    avril 2005
    Messages
    4 160
    Détails du profil
    Informations personnelles :
    Nom : Homme Romuald Perrot
    Âge : 29
    Localisation : France

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

    Informations forums :
    Inscription : avril 2005
    Messages : 4 160
    Points : 5 585
    Points
    5 585

    Par défaut

    D'accord. N'oublie pas de traiter le cas où on a un graphe non connexe.
    http://rperrot.developpez.com
    http://phos-graphein.fr

    Vous désirez contribuer à la rubrique algorithmique, n'hésitez pas à me contacter.

  8. #8
    Rédacteur/Modérateur

    Avatar de millie
    Profil pro
    Inscrit en
    juin 2006
    Messages
    6 945
    Détails du profil
    Informations personnelles :
    Localisation : Luxembourg

    Informations forums :
    Inscription : juin 2006
    Messages : 6 945
    Points : 8 774
    Points
    8 774

    Par défaut

    Citation Envoyé par PRomu@ld
    D'accord. N'oublie pas de traiter le cas où on a un graphe non connexe.
    Je ne vois pas le problème si le graphe n'est pas connexe. Il fait un parcours à partir d'un sommet particulier, donc si le graphe a plusieurs composantes connexes, toutes les composantes qui ne correspondent pas à la composante du sommet S (de départ) ne seront jamais vu. Non ?
    Je ne répondrai à aucune question technique en privé

  9. #9
    Modérateur
    Avatar de PRomu@ld
    Homme Profil pro Romuald Perrot
    Ingénieur de Recherche
    Inscrit en
    avril 2005
    Messages
    4 160
    Détails du profil
    Informations personnelles :
    Nom : Homme Romuald Perrot
    Âge : 29
    Localisation : France

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

    Informations forums :
    Inscription : avril 2005
    Messages : 4 160
    Points : 5 585
    Points
    5 585

    Par défaut

    Oui, dans ce cas, c'est un parcours de composante connexe en profondeur, pas un parcours de graphe en profondeur (c'est comme ça que je le vois). Un parcours d'une structure de donnée générique doit passer en revue tous les objets de cette structure de donnée (un parcours, je le vois comme une sorte d'énumération des élements de la structure)

    C'est juste une question d'application ou de définition, c'est pas bien grave.
    http://rperrot.developpez.com
    http://phos-graphein.fr

    Vous désirez contribuer à la rubrique algorithmique, n'hésitez pas à me contacter.

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •