Discussion :

[Kenshin01]

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é

[tbc92]

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é

[Kenshin01]

C'est un exercice que je dois faire absolument sur cette algorithme je ne comprends pas tres bien?
Cordialement

[WhiteCrow]

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 ?
3. …

[Kenshin01]

Bah j'imagine que si le graphe n'est pas planaire l'algorithme s'arrêtera ?

[WhiteCrow]

bah il aura du mal à s'arrêter avec une boucle comme tant que G n’est pas planaire faire.