Discussion :

[membreComplexe12]

Salut tous,

je voudrais savoir comment on demontre la vitesse de convergence des algorithmes ? j'ai par exemple entendu que newton à une vitesse quadratique, la dichotomie logarithmique...

pourriez vous me dire comment faire pour demontrer ceci et eventuellement me donner un exemple pour les methodes que j'ai cité ci dessus ?

je vous remercie d'avance pour votre aide

[Franck Dernoncourt]

http://fr.wikipedia.org/wiki/Algorit...de_convergence ?

[membreComplexe12]

en fait je n'ai pas vraiment compris ces notions et sur wiki je trouve que c'est un peu compliqué pour un débutant...

1°) par exemple on a pour la dichotomie:

Xn+1 - Xn = ecartOrigine/2^n

J'ai bien compris comment obtenir ceci mais j'ai pas trop compris pourquoi on dit que la convergence est lineaire ?

par le "n" n'a pas de puissance ?


2°) pour newton:

pour newton on dit que la convergence est quadratique car le "n" est au carré dans la relation donnée par Xn+1 - Xn ??

[davly]

je n'ai pas étudier la vitesse de convergence des algo, mais leur complexité,
il est vrai de dire que la dichotomie est logarithmique et que l'algo de newton quadratique.

j'ai l'impression que tu peux donc lié cela a la compléxité moyenne de l'algo.
La compléxité moyenne correspond à l’ordre de grandeur des itérations de ton algo.

- si t'a un tableau de n élément avec des indices, tu as un indices, tu sais donc ou le récupérer c'est de compléxité 1.

- maintenant si tu n'as pas l'indice, tu dois le parcourir entièrement, on parlera ici de compléxité linéaire, compléxité n.

- si maintenant tu fais une recherche par dichotomie (en supposant que ton tableau est trié bien sur), tu vas couper le tableau autant de fois que possible en 2 jusqu’à avoir l’élément, t'aura moins que le linéaire.. compléxité logarithmique.

- si tu veux trier ton tableau, l’algorithme glouton est quadratique, tu fais un double parcour pour tout ranger.. compléxité n².

c'était des exemple pour illustrer maintenant pour démontrer, je me rappelle plus trop de formules, c'est long et pénible a lire, essaye de voir ce que tu peux avoir sur le net.

j’espère que ça pourra t'aider à comprendre le principe.

[membreComplexe12]

oui ça à l'air lié ces choses...

je vais voir sur le net ce que je trouve là dessus.


merci en tout cas :-)

[Franck Dernoncourt]

oui ça à l'air lié ces choses...

Heu, pas tellement :

• la complexité computationnelle se penche sur l'ordre de grandeur du nombre d'unités de calcul à réaliser pour arriver à la fin d'un algorithme ;
• la vitesse de convergence étudie l'évolution d'une suite (au sens mathématique).

Dans certains cas particuliers, l'étude de la vitesse de convergence peut certes éclairer la complexité computationnelle, mais c'est rare ! Et le calcul de la complexité computationnelle ne sert à rien pour déterminer la vitesse de convergence.

[membreComplexe12]

franck aurais tu un lien pas mal qui explique pour un debutant toutes ces notions depuis zero ?

[Franck Dernoncourt]

• Vitesse de convergence : http://en.wikipedia.org/wiki/Rate_of_convergence
• Complexité computationnelle : http://lapoire.developpez.com/algorithmique/initiation/

Ce sont les liens les moins compliqués que je connaisse... il y a peut-être de meilleurs liens !

[FR119492]

Salut!
Il faut être conscient que la complexité ne donne parfois pas une idée exacte du temps de calcul en fonction de la taille du problème. Je te donne deux exemples:

1. Tu veux remplir un tableau de dimension n*n. Tu peux le faire ligne par ligne ou colonne par colonne. De toute évidence, la complexité est la même dans les deux cas. Or, pour de grandes valeurs de n, le temps de calcul est différent: en Fortran, c'est plus rapide colonne par colonne et en C, ligne par ligne.
2. Tu veux résoudre des systèmes linéaires d'ordre n. La complexité te dit que le temps de calcul est un polynôme de degré 3 en n. Or si tu traces le graphe du temps de calcul en fonction de n, tu constateras qu'il présente une discontinuité lorsque la taille de ta matrice dépasse la place disponible en mémoire vive et que ton ordinateur doit multiplier les transferts ver son disque dur.

Alors, je pense qu'une approche "expérimentale" est plus fiable que l'étude de la complexité: on essaie et on observe.
Jean-Marc Blanc

[membreComplexe12]

merci pour ces éléments !

ps : Jean Marc comment montre t on que ça evolue comme un polynome de degres 3 ?

[Franck Dernoncourt]

Alors, je pense qu'une approche "expérimentale" est plus fiable que l'étude de la complexité: on essaie et on observe.

Disons que cela dépend des objectifs visés.

Si cela intéresse 21did21 ou d'autres visiteurs de ce thread, plus d'info sur ce sujet : http://www.developpez.net/forums/d11...le-algorithme/

[membreComplexe12]

merci pour ces compléments

[FR119492]

Salut!

Jean Marc comment montre t on que ça evolue comme un polynome de degres 3

En fait, on n'a plus besoin de le montrer, parce qu'on le sait déjà. Mais, si tu veux le vérifier, il y a plusieurs approches possibles:

1. Tu essaies avec diverses valeurs de n, tu chronomètres et tu représentes la fonction T(n), ainsi que T(n)/n, T(n)/n^2 et T(n)/n^3. En fait, ça n'est pas très précis, parce que ton ordinateur fait un tas d'autres choses en même temps.
2. Dans ton programme, tu ajoutes 2 compteurs, l'un pour les additions et soustractions, l'autre pour les multiplications et divisions, puis tu procèdes comme ci-dessus, mais avec les valeurs obtenues par les compteurs, à la place du temps de calcul.
3. Tu décortiques ton algorithme et tu regardes le nombre de boucles imbriquées.

Jean-Marc Blanc