Répondre à la discussion
Affichage des résultats 1 à 17 sur 17

besoin d'aide a propos d'un petit algo



  1. #1
    boukmi34

    besoin d'aide a propos d'un petit algo


    ------

    Bonjour,
    jai besoin dun petit coup de pouce a propos dun algorithme.
    Dans un graphe on veut detecter si une arete est un "isthme" (arete indispensable pourla connexite du graphe) ou pas pour cela on utilise le theorem suivant:
    <si T est un arbre couvrant issu dun parcour en profondeur dun graphe connexe G alors {xy} avec date_visite[x]<date_visite[y] est un isthme si et seulement si {xy} est une arete de T et plus_bas[y]>date_viste[x]
    tel que plus_bas[y] est le minimum de:
    • date_visite[y].
    • date_visite[y] ou t est un sommet tel que {yt} est une arte de G mais pas de T
    • plus_bas[r] pour tout sommet r est un fils de y dans T

    je cherche un algorithme qui calclue l'entier plus_bas pour chake sommet...voila ce qujai fais mais je croi ke ce n'est pas correct:
    fonction plus_bas(s:sommet) : entier
    indice<-date_visite(s);
    H-difference__graphe(G,T); (T larbre issu du parcour en profondeur)
    fils,_sucesseurs(H,s);
    pour j allant de 0 a taille(fils)-1 faire
    si (date_visite(fils[j]) < indice) alors
    indice<-date_visite(fils[j]);
    finsi
    finpour
    fils<-successeurs(T , s);
    pour j allant de 0 a taille(fils)-1 faire
    si (indice > plus_bas(fils[j])) alors
    indice<-plus_bas(fils[j]);
    finsi
    finpour
    retourner indice


    merci davance.

    PS:c'est tres unrgent SVP

    -----

  2. Publicité
  3. #2
    ced-29

    Re : besoin d'aide a propos d'un petit algo

    Bonjour,
    Pour moi ce code a l'air de correspondre à ce que tu dis, qu'est-ce qui te fait penser qu'il n'est pas correct?


    Citation Envoyé par boukmi34 Voir le message
    • date_visite[y] ou t est un sommet tel que {yt} est une arte de G mais pas
    correction : tu veux dire date_visite[t].

  4. #3
    JPL
    Responsable des forums

    Re : besoin d'aide a propos d'un petit algo

    Petite remarque : si tu avais mis ton pseudo-code dans la balise Code tu aurais gardé l'indentation ce qui aurait été plus lisible.
    Rien ne sert de penser, il faut réfléchir avant - Pierre Dac

  5. #4
    boukmi34

    Re : besoin d'aide a propos d'un petit algo

    ouai ced-29 c'est ce que je voulais dire...en fait pour l'algo j'ai pas reussi à evaluer sa complexité en temps et c'est un problème car je sais pas commbien de temps il va mettre pour faire ses calculs sil sagit d'un nombre important de sommets.
    merci pour ta réponse

  6. A voir en vidéo sur Futura
  7. #5
    ced-29

    Re : besoin d'aide a propos d'un petit algo

    Oui c'est sûr que ton algo ne semble pas super optimisé.
    Il revient en fait à refaire un parcours en profondeur de T en testant a chaque fois si le sommet a un voisin dans G tel que l'indice du deuxième sommet soit inférieur à celui du premier.
    Je n'ai rien contre ça, mais je suis gêné par cette ligne :

    H-difference__graphe(G,T); (T larbre issu du parcour en profondeur)

    Je pense que ce calcul est très coûteux (je dirais avec du O(n), dis-moi si je me trompe), et le fait que tu le répêtes à chaque appel récursif le fait monter à O(n²).
    A ce prix là tu ferais mieux de faire le calcul sur successeurs(G,s), ou alors passer H en paramètre de ta fonction et le calculer une fois pour toutes.

  8. #6
    boukmi34

    Re : besoin d'aide a propos d'un petit algo

    Pour le probleme que je suis en train de resoudre les sommets sont stokes dans une pile avec leurs dates de visite dans l'acces a la date de visite d'un sommet se fait en temps constant.et je crois que tu as raison a propos de H et il vaut la definir comme variable globale avant la fonction plus_bas[s].
    Est ce qu'en faisant ca on diminue le temps de calcul ou pas?
    merci

  9. Publicité
  10. #7
    ced-29

    Re : besoin d'aide a propos d'un petit algo

    Citation Envoyé par boukmi34 Voir le message
    Pour le probleme que je suis en train de resoudre les sommets sont stokes dans une pile avec leurs dates de visite dans l'acces a la date de visite d'un sommet se fait en temps constant.et je crois que tu as raison a propos de H et il vaut la definir comme variable globale avant la fonction plus_bas[s].
    Est ce qu'en faisant ca on diminue le temps de calcul ou pas?
    merci
    Bien oui c'est exactement ce que j'ai dit ^^.
    Pour un nombre très important de sommets je pense que la différence au temps d'exécution sera très perceptible.
    Mais je me demande si ce ne serait pas encore plus simple de savoir si c'est un isthme en faisant une méthode légèrement modifiée de ta méthode de calcul d'arbre couvrant...

  11. #8
    boukmi34

    Re : besoin d'aide a propos d'un petit algo

    je connais pas d'autre methode qui permettent de detecter les isthme...ca m'enerve..
    Si tu tombe sur une autre methode merci de me tenir au courant.
    Cordialement

  12. #9
    boukmi34

    Re : besoin d'aide a propos d'un petit algo

    je crois qu'on peut utiliser cette proposition:
    u est un isthme <==> u n'appartient a aucun cycle
    qu'est ce que t'en penses?

  13. #10
    ced-29

    Re : besoin d'aide a propos d'un petit algo

    Eh bien moi ce que je disais c'est que ça me parait plus simple de partir de l'algo de parcours en profondeur, tu pars de s dans G, tu marque les deux sommets de l'isthme présumé comme déjà vus, et tu parcoures ensuite en profondeur jusqu'à ce que tous les sommets soient marqués ou que tu trouve un sommet y tel que date_visite[y]<dateVisite[s].

    Qu'est-ce que tu en penses?

  14. #11
    ced-29

    Re : besoin d'aide a propos d'un petit algo

    Citation Envoyé par boukmi34 Voir le message
    je crois qu'on peut utiliser cette proposition:
    u est un isthme <==> u n'appartient a aucun cycle
    qu'est ce que t'en penses?
    Ca revient au même, ta fonction précédente part aussi de ce principe. Mais en fait tu exploites le fait que tes sommets sont numérotés lors de la création de ton arbre. ça te simplifie la tâche car tu cherche un sommet z tel que date_visite[z]<dateVisite[x] au lieu de chercher à retrouver x absolument, ce qui sera plus long.
    Dernière modification par ced-29 ; 01/09/2007 à 14h45.

  15. #12
    ced-29

    Re : besoin d'aide a propos d'un petit algo

    Citation Envoyé par ced-29 Voir le message
    un sommet y tel que date_visite[y]<dateVisite[s].
    oui j'aurais dû dire un sommet z tel que date_visite[z]<date_visite[x] mais je me suis un peu embrouillé entre la notation de ton code et de ton énoncé

  16. Publicité
  17. #13
    boukmi34

    Re : besoin d'aide a propos d'un petit algo

    cette algorithme c'est pour detecter les cycles non?

  18. #14
    ced-29

    Re : besoin d'aide a propos d'un petit algo

    Tout ce qu'on écrit depuis le début a pour but d'identifier un cycle passant par l'arête {xy}. C'est le seul moyen d'identifier un isthme.

  19. #15
    boukmi34

    Re : besoin d'aide a propos d'un petit algo

    ok
    merci pour ton aide

  20. #16
    boukmi34

    Re : besoin d'aide a propos d'un petit algo

    Bonjour,
    est ce que tu peux detailler ton idée encore plus stp?
    Cordialement

  21. #17
    ced-29

    Re : besoin d'aide a propos d'un petit algo

    Code:
    fonction estUnIsthme(x,y : sommet) retourne booleen
    
    pour tout sommet s de G faire
       marqué[s] <- faux
    fin pour
    
    aTraiter <- vide
    
    si date_visite[x] < date_visite[y] faire
       aTraiter.empile(y);
    sinon faire
       aTraiter.empile(x);
    fin si
    
    marqué[x] <- vrai
    marqué[y] <- vrai
    trouve <- faux
    
    tant que nonVide(aTraiter) et trouve = faux faire
       z <- aTraiter.depile()
       marqué[z] <- vrai
       pour tout voisin v de z dans G  et tant que trouve = faux faire
          si date_visite[v] < date_visite[y] faire
             trouve <- vrai
          sinon si marqué[v] = faux faire
             marqué[v] <- vrai
             aTraiter.empile[v]
          fin si
       fin pour
    fin tant que
    
    retourner trouve
    Voilà ce que ça donne en détaillé ^^
    Qu'est-ce que tu en dis?

Discussions similaires

  1. [Microbiologie] besoin d'aide a propos de la culture des champignons microscopique
    Par microbio12 dans le forum Biologie
    Réponses: 1
    Dernier message: 14/11/2007, 12h57
  2. Besoin d'aide à propos de la thalidomide
    Par titilde21 dans le forum Chimie
    Réponses: 18
    Dernier message: 25/10/2007, 19h43
  3. j'ai besoin d'aide à propos du LM741
    Par Mister Viet dans le forum Électronique
    Réponses: 2
    Dernier message: 12/01/2007, 19h39
  4. Besoin d'un petit peu d'aide
    Par vino dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 29/01/2006, 16h29
  5. Besoin d'aide à propos de DELs (ou LEDs)
    Par Mimini dans le forum Électronique
    Réponses: 7
    Dernier message: 22/05/2005, 14h41
Découvrez nos comparatifs produits sur l'informatique et les technologies.