Répondre à la discussion
Page 1 sur 2 1 DernièreDernière
Affichage des résultats 1 à 30 sur 46

Complexité algo recherche degré de connexité...



  1. #1
    djar

    Complexité algo recherche degré de connexité...


    ------

    Bonjour à tous !

    Voila... Je suis en L3 info, et nous avons eu des rattrapages en maths. Parmi ces rattrapages figurait un cour de maths sur les graphes. A un moment, le professeur nous a parlé d'un problème qui m'a fortement interessé:

    Comment determiner le minimum des points a supprimer dans un graphe connexe pour que celui ne le soit plus ?

    Il a ajouté que c'était un problème très complexe au sens algorithmique et que rien n'avait été trouvé qui soit rapide.

    Avec mon culot d'éléphant , je me suis dit bon... On va trouver un algorithme alors... Et j'ai trouvé, preuve à l'appui.

    Il y a donc maintenant deux possibilités:
    1. - Je me suis trompé...
    2. - Ce n'est pas un problème compliqué...

    Pour le 1), j'ai vérifié et revérifié (je ne demande à personne de vérifier), ça fonctionne théoriquement.
    Mais c'est le 2. qui m'amène a vous demander si vous connaitriez le meilleur algorithme qui fasse ceci en un temps optimal ?...

    Merci à celui qui m'aidera parce que je ne trouve rien sur Internet...

    -----

  2. #2
    martini_bird

    Re : Complexité algo recherche degré de connexité...

    Salut,

    je ne saurais pas répondre à ta question, mais as-tu aussi considéré les graphes en dimension quelconque ? (Un maillage du tore ou plus généralement d'une surface de genre p par exemple.)

    Cordialement.
    « Angle éternel, la terre et le ciel, pour bissectrice, le vent. » Garcia Lorca

  3. #3
    djar

    Re : Complexité algo recherche degré de connexité...

    Tous les graphes sont adaptés à mon algorithme, et la preuve n'utilise aucune contrainte.

    Mais cependant, si tu as un graphe à me faire tester (pas trop gros parce que sinon à la main, j'en aurai pour longtemps !), je suis particulièrement ouvert !

  4. #4
    djar

    Re : Complexité algo recherche degré de connexité...

    Ca y est, il semblerait que j'ai trouvé...
    Je crois que c'est le même problème que de trouver la fiabilité d'un réseau...

    et les amis... C'est un problème NP-Complet...
    que je le résous en temps polynomial si mes calculs sont bons.
    Ca, c'est très sympa ...


    http://en.wikipedia.org/wiki/List_of...plete_problems
    Section Network design->Cuts and connectivity->Network reliability

    Ne nous réjouissons pas trop vite... Je vais encore vérifier tout.

  5. A voir en vidéo sur Futura
  6. #5
    Sylvestre

    Re : Complexité algo recherche degré de connexité...

    Citation Envoyé par djar Voir le message
    C'est un problème NP-Complet...Ne nous réjouissons pas trop vite... Je vais encore vérifier tout.
    Je crois que tu fais bien de tout vérifier. Ce n'est pas que je remette en question tes capacités, mais cela m'est aussi arrivé de croire que j'avais trouvé cela. Il m'a suffit de discuter avec mon collègue pour me faire démonter en 30 secondes...

  7. #6
    djar

    Re : Complexité algo recherche degré de connexité...

    Tu comprendras que je ne veuille pas donner l'algo tout de suite...

    Mais faisons un test ! Donne moi un graphe fortement connexe et je te dirais quels points supprimer pour le rendre non connexe le plus rapidement... Le problème, c'est que j'ai pas encore programmé l'algo sur ordi donc je suis obligé de le faire à la main: je risque de faire des erreurs de calcul, mais je ferais attention...

  8. #7
    Sylvestre

    Re : Complexité algo recherche degré de connexité...

    Citation Envoyé par djar Voir le message
    Tu comprendras que je ne veuille pas donner l'algo tout de suite...

    Mais faisons un test ! Donne moi un graphe fortement connexe et je te dirais quels points supprimer pour le rendre non connexe le plus rapidement... Le problème, c'est que j'ai pas encore programmé l'algo sur ordi donc je suis obligé de le faire à la main: je risque de faire des erreurs de calcul, mais je ferais attention...
    Jusqu'à combien de sommets veux-tu aller ?

    Si tu me dis n, je te concocterai un autre graphe de taille n+1 et on regardera comment varie le temps de calcul.

  9. #8
    djar

    Re : Complexité algo recherche degré de connexité...

    Je suis vraiment tenté de te dire n, mais j'ai pas encore programmer l'algo et j'ai des partiels à préparer ! Mais disons n = 10 pour commencer (et c'est déjà grand) puis n=11, je ne tricherais pas et je te dirais le temps que j'ai mis à la main... Qui risque d'être grand ! Mais si déjà je met moins de quinze minutes à la main, ça veut dire que ça devrait prendre quelques millieme de secondes sur un ordinateur classique...

    Je ferais tout mon possible pour te faire l'algo sur ordi en deux semaines, comme ça on verra le temps réel ! Et on pourra tester avec n=1000 et n=1001 !

    Merci de m'aider en tout cas !

  10. #9
    Sylvestre

    Re : Complexité algo recherche degré de connexité...

    Ok,

    je vais te donner un graphe de 10 sommets bientôt. Mais comme je n'ai pas non plus trop de temps, je te prie de m'excuser si cela attends ce soir. Ceci dit, je ne connais pas bien le problème et je ne sais pas quel graphe sont difficiles pour ce problème. Je vais donc certainement te donner un graphe aléatoire de densité 1/2.

  11. #10
    djar

    Re : Complexité algo recherche degré de connexité...

    okidok', mais le probleme, je te l'avoue, c'est que si tu génére un graphe aléatoire, tu risques d'avoir du mal à vérifier la réponse que je vais te donner...

  12. #11
    skydancer

    Re : Complexité algo recherche degré de connexité...

    Effectivement c'est un probleme interressant.

    Il existe plusieurs familles d'algorithmes qui résolvent ce probleme. Pour résumer il y a deux grandes familles :
    - les algorithmes à base de flot. pâr éxemple la recherche des coupes minimales entre chaque paire de noeud d'un graphe
    - les algorithmes dits aléatoires, qui malgré leurs noms fournissent des résultats exacts. exemple marche aléatoire sur un graphe...

    Je n'en connais pas la complexité algorithmique....

  13. #12
    djar

    Re : Complexité algo recherche degré de connexité...

    Interessant, je vais chercher des infos dans cette direction...

    Mon algorithme est déterministe.
    J'ai pas internet chez moi, mais seulement à la fac donc demain soir , je testerais le programme et après demain, je vous filerais les résultats...

  14. #13
    Sylvestre

    Re : Complexité algo recherche degré de connexité...

    Citation Envoyé par djar Voir le message
    okidok', mais le probleme, je te l'avoue, c'est que si tu génére un graphe aléatoire, tu risques d'avoir du mal à vérifier la réponse que je vais te donner...
    Tu as raison, je vais te préparer un graphe ce soir pour lequel je connais la réponse.
    Mais peut-être qu'en faisant cela, je vais rendre le problème plus simple qu'il ne l'est. Mais bon, au cas où, on fera plusieurs essais.

  15. #14
    Sylvestre

    Re : Complexité algo recherche degré de connexité...

    Essaie avec ça :

    2-8
    2-10
    2-4
    8-10
    8-1
    4-10
    1-4
    8-5
    8-7
    7-1
    1-5
    3-7
    3-6
    5-6
    9-5
    9-6

  16. #15
    skydancer

    Re : Complexité algo recherche degré de connexité...

    Pour trouver des algos , tu peux chercher "vertex connectivity"

    Un petit détail, pour graphe complet (c'est à dire qur tout les sommets du graphe sont liés à tout les autres), il faudrait enlever tout les sommets pour le rendre non-connexe. C'est le genre de points particuliers que tu peux tester avec ton algorithme.

  17. #16
    djar

    Re : Complexité algo recherche degré de connexité...

    Comme je n'ai pas Internet chez moi, je resous les cas avec du retard... Je vais tester le tiens ce soir !

    Mais hier, j'etais trop impatient donc j'ai code mon algo. 2h apres, je fesais un test avec 13 vertices. Resultat tres remarquable: 15ms en moyenne et parfois, c'est mon chronometre qui n'etait pas assez precis et qui m'affichait 0ms !! J'ai donc suivi ce que tu m'as dit de faire: augmenter de 1 le nombre de vertices. Resultat avec 14 vertices: toujours 15ms, le chronometre n'est pas assez precis car la difference est inferieur a 1ms !!! C'est plutot bien je pense...
    J'ai jamais fait un algo aussi puissant !

    A bientot !

  18. #17
    Sylvestre

    Re : Complexité algo recherche degré de connexité...

    Ok,

    dans ce cas, il va falloir faire des tests avec plus de sommets, genre 50, et regarder le comportement du temps de calcul.
    Si c'est vraiment polynomial, alors tu es millionnaire !
    (désolé, mais j'ai encore des doutes, cela semble trop beau)

  19. #18
    djar

    Re : Complexité algo recherche degré de connexité...

    En fait, j'ai transforme la complexite temporelle en complexite spatiale, meme si cela reste faisable du fait de l'utilisation de deux petites astuces mathematiques que je ne dirais pas (tout de suite)...

    Je teste ton graphe et ensuite on verra avec 50 points !
    Note: normalement, je dis bien normalement, 50 points et 51 points ne devrait pas trop deranger mon algo... Si mes calculs sont bons...

    C'est tellement interessant !!!
    Dernière modification par djar ; 17/10/2006 à 09h45.

  20. #19
    Sylvestre

    Re : Complexité algo recherche degré de connexité...

    Citation Envoyé par djar Voir le message
    En fait, j'ai transforme la complexite temporelle en complexite spatiale, meme si cela reste faisable du fait de l'utilisation de deux petites astuces mathematiques que je ne dirais pas (tout de suite)...

    Je teste ton graphe et ensuite on verra avec 50 points !
    Note: normalement, je dis bien normalement, 50 points et 51 points ne devrait pas trop deranger mon algo... Si mes calculs sont bons...

    C'est tellement interessant !!!
    Je me demande : Combien de temps met ton algorithme pour donner la réponse si je te donne une clique à n sommets ?

  21. #20
    invite986312212
    Invité

    Re : Complexité algo recherche degré de connexité...

    Citation Envoyé par Sylvestre Voir le message
    Si c'est vraiment polynomial, alors tu es millionnaire !

    je ne connais pas bien cette question de P=NP mais si j'ai bien compris, si c'est vrai pour un problème, c'est vrai pour tous ceux d'une certaine classe(?) est-ce que ça signifie qu'on sait déduire un algoritme pour tous les problèmes de cette classe à partir d'un seul? par exemple, supposons que l'algoritme de Djar permette de trouver un ensemble minimal de sommets déconnectant un graphe en un temps polynomial, est-ce qu'on peut en déduire un algoritme polynomial pour le problème du représentant de commerce? ou bien on sait juste qu'un tel algoritme existe?

  22. #21
    djar

    Re : Complexité algo recherche degré de connexité...

    Par contre, j'ai oublie de preciser que je n'ai demontre ma formule seulement pour des graphes non orientes. Mais normalement, ca fonctionne aussi bien. Dois-je considerer que ton graphe est oriente ?

  23. #22
    djar

    Re : Complexité algo recherche degré de connexité...

    Citation Envoyé par ambrosio Voir le message
    je ne connais pas bien cette question de P=NP mais si j'ai bien compris, si c'est vrai pour un problème, c'est vrai pour tous ceux d'une certaine classe(?) est-ce que ça signifie qu'on sait déduire un algoritme pour tous les problèmes de cette classe à partir d'un seul? par exemple, supposons que l'algoritme de Djar permette de trouver un ensemble minimal de sommets déconnectant un graphe en un temps polynomial, est-ce qu'on peut en déduire un algoritme polynomial pour le problème du représentant de commerce? ou bien on sait juste qu'un tel algoritme existe?
    Si un probleme NP complet tombe, tous les autres tombent...
    Mais ca ne veut pas dire que mon algo "serait" une solution a tous les autres. Ca veut simplement dire qu'il existe une solution polynomiale pour tous les problemes NP Complets...

    Bon je retourne en cours moi ! A bienvite !

  24. #23
    djar

    Re : Complexité algo recherche degré de connexité...

    Citation Envoyé par Sylvestre Voir le message
    Je me demande : Combien de temps met ton algorithme pour donner la réponse si je te donne une clique à n sommets ?
    J'ai calcule ca, mais mauvaise nouvelle: c'est pas genial a cause d'un petit truc que je dois optimiser.

    La complexite est: n! + n2

    Le petit truc a optimiser est: comment savoir le nombre de chaines simples issues d'un vertex x ?

  25. #24
    Sylvestre

    Re : Complexité algo recherche degré de connexité...

    Citation Envoyé par djar Voir le message
    La complexite est: n! + n2
    Le petit truc a optimiser est: comment savoir le nombre de chaines simples issues d'un vertex x ?
    C'est quoi une chaîne simple ?

  26. #25
    djar

    Re : Complexité algo recherche degré de connexité...

    Citation Envoyé par Sylvestre Voir le message
    C'est quoi une chaîne simple ?
    C'est un "chemin" qui te permet d'aller du sommet x a un autre y sans passer deux fois par le meme.

  27. #26
    Sylvestre

    Re : Complexité algo recherche degré de connexité...

    Citation Envoyé par djar Voir le message
    Le petit truc a optimiser est: comment savoir le nombre de chaines simples issues d'un vertex x ?
    En quoi le fait de savoir ceci te permettrait d'aller plus vite ? Dans le cas d'une clique tu vas trouver (n-1)! pour chaque sommet.

  28. #27
    djar

    Re : Complexité algo recherche degré de connexité...

    Citation Envoyé par Sylvestre Voir le message
    En quoi le fait de savoir ceci te permettrait d'aller plus vite ? Dans le cas d'une clique tu vas trouver (n-1)! pour chaque sommet.
    Mon algo repose la dessus...

  29. #28
    djar

    Re : Complexité algo recherche degré de connexité...

    Ha ! J'ai peut etre trouve une idee de super optimisation !

    Hehe, j'ai plus d'un tour dans mon sac ! Bon je vais ameliorer ca.

  30. #29
    Sylvestre

    Re : Complexité algo recherche degré de connexité...

    Citation Envoyé par djar Voir le message
    Ha ! J'ai peut etre trouve une idee de super optimisation !

    Hehe, j'ai plus d'un tour dans mon sac ! Bon je vais ameliorer ca.
    Bravo, mais à mon avis tu ferais mieux de prouver que ce que tu as déjà est polynomial dans tous les cas de figures. Cela suffit amplement pour devenir très célèbre.

  31. #30
    djar

    Re : Complexité algo recherche degré de connexité...

    Attends... Tu veux dire que meme si j'ai une factorielle, ce n'est pas si grave ? Cela veut dire que ce serait polynomial quand meme ?!!? Ce serait super parce que la demo est deja faite !

Page 1 sur 2 1 DernièreDernière

Discussions similaires

  1. besoin d'aide a propos d'un petit algo
    Par boukmi34 dans le forum Logiciel - Software - Open Source
    Réponses: 16
    Dernier message: 02/09/2007, 17h17
  2. Chercher Algo
    Par yacine1 dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 15/03/2007, 17h24
  3. transformée de Fourier (algo numérique)
    Par Heimdall dans le forum Mathématiques du supérieur
    Réponses: 8
    Dernier message: 07/03/2007, 04h52
  4. Retrouver algo à partir de résultats
    Par Delfart dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 26/02/2007, 20h30
  5. Graphes:lien entre connexite et degre
    Par Suzanna dans le forum Mathématiques du supérieur
    Réponses: 6
    Dernier message: 25/02/2006, 16h22