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 :

Question sur la complexité d'un algorithme en théorie des graphes


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre averti
    Homme Profil pro
    Étudiant
    Inscrit en
    Avril 2021
    Messages
    51
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 26
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2021
    Messages : 51
    Par défaut Question sur la complexité d'un algorithme en théorie des graphes
    Bonjour je vous contacte par rapport à un exercice que je trouve dur au niveau de la compléxité

    Soit l’algorithme de construction de graphe planaire suivant
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
     
    fonctionG = planaire(G)
          tant que G n’est pas planaire faire
                      pour tout x sommet de G faire
                              V = liste des voisins de x
                              M = barycentre des sommets de V
                              si on diminue le nombre d’intersections d’arcs
                                     alors placer x en M
                      fin si
          fin faire
    fin faire
    Les questions sont les suivantes : Quelle est la complexité de cet algorithme ? Finit-il toujours ?

    En espérant être aidé

  2. #2
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    Décembre 2013
    Messages
    4 215
    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 215
    Par défaut
    J'essaie de réfléchir, je n'ai pas la réponse.

    Déjà, j'ai envie d'inverser les questions.
    La complexité d'un algorithme, c'est en gros calculer le nombre d'opérations que le programme va effectuer.
    Si dans certains cas l'algorithme ne finit pas (il tourne en boucle de façon infinie), ça veut dire que l'algorithme est de complexité infinie.

    Du coup si on commence par répondre à la 1ère question en disant que l'algorithme est en n^5 ou même n^10 ... par exemple, alors ça y est, on a répondu à la 2ème question, l'algorithme se finit forcément.

    Pour la complexité de l'algorithme, on peut déjà commencer par le 'coeur' du programme.

    Il y a un test dans ton algorithme : si on diminue le nombre d’intersections d’arcs alors

    Tu peux déjà essayer d'évaluer la complexité de ce test

    Accessoirement, oublions l'exercice.
    Ceci est un exercice, ou un besoin perso ?
    J'étais tombé sur un jeu qui correspond exactement à cet algorithme, j'adorais ce jeu. on avait un graphe, non planaire, et il fallait déplacer des points jusqu'à obtenir un graphe planaire. Le graphe était conçu de façon à ce qu'il y ait toujours une solution.
    Je ne trouve plus le lien vers ce jeu. Si tu as ça, je suis très intéressé

  3. #3
    Membre averti
    Homme Profil pro
    Étudiant
    Inscrit en
    Avril 2021
    Messages
    51
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 26
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2021
    Messages : 51
    Par défaut
    C'est un exercice que je dois faire absolument sur cette algorithme je ne comprends pas tres bien?
    Cordialement

  4. #4
    Membre émérite
    Homme Profil pro
    Chef de projet NTIC
    Inscrit en
    Juillet 2020
    Messages
    352
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Chef de projet NTIC

    Informations forums :
    Inscription : Juillet 2020
    Messages : 352
    Par défaut
    Bonjour,

    techniquement un algo doit terminer … mais passons ce petit abus de langage.
    La complexité de ton algo va dépendre des primitives que tu emploies comme «est planaire» (l. 3) par exemple.
    Mais ton algo ne se termine pas dans tous les cas de figures … que se passe-t-il si :
    1. le graphe que tu dois dessiner n'est pas planaire ?
    2. tous les nœuds de ton graphe sont aux mêmes coordonnées ?

  5. #5
    Membre averti
    Homme Profil pro
    Étudiant
    Inscrit en
    Avril 2021
    Messages
    51
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 26
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2021
    Messages : 51
    Par défaut
    Bah j'imagine que si le graphe n'est pas planaire l'algorithme s'arrêtera ?

  6. #6
    Membre émérite
    Homme Profil pro
    Chef de projet NTIC
    Inscrit en
    Juillet 2020
    Messages
    352
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Chef de projet NTIC

    Informations forums :
    Inscription : Juillet 2020
    Messages : 352
    Par défaut
    bah il aura du mal à s'arrêter avec une boucle comme tant que G n’est pas planaire faire.

Discussions similaires

  1. Des questions sur la complexité asymptotique et uniforme
    Par Karimce dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 28/03/2016, 11h17
  2. Algorithme théorie des Graphes - trouver l'itinéraire entre un arrêt A et un arrêt B
    Par domino313131 dans le forum Intelligence artificielle
    Réponses: 4
    Dernier message: 20/03/2011, 03h39
  3. Réponses: 0
    Dernier message: 21/06/2009, 22h06
  4. question sur la complexité d'un algorithme?
    Par logo98 dans le forum Mathématiques
    Réponses: 5
    Dernier message: 29/03/2009, 16h54
  5. Réponses: 5
    Dernier message: 15/09/2007, 00h02

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