Inscription / Connexion Nouveau Sujet
Niveau algorithmique
Partager :

Invariant de boucle

Posté par
samihormi
01-10-18 à 13:51

Bonjour à tous :

Voila mon probleme,  j'ai l'algorithme suivant

fonction somme(a,b):
Entree: deux entiers a et b, avec a ≤ b
Sortie : la somme de a, a+1, …, et b.

solution ← a
Nombre_suivant ← a
Tant que (Nombre_suivant < b):
    Nombre_suivant  ← Nombre_suivant  + 1
    solution ← solution + Nombre_suivant
rendre solution

Je doit d'abord exhiber et prouver "l'invariant de boucle".
Puis ensuite en me basant sur se resultat prouver, la correction de cet algorithme.

En faisant quelques iterations j'ai obtenu les resultas suivant :
Initialisation: i = 0 , Nombre_suivant = x, solution = x

Iteration 1i = 1 , Nombre_suivant = x+1, solution = x+(x+1)=2x+1
Iteration 2i = 2 , Nombre_suivant = x+2, solution = (x+1)+(2x+1)=2x+1
Iteration 3i = 3 , Nombre_suivant = x+3, solution = (2x+1)+(3x+3)=3x+3
etc

Mon problème débute ici je n'arrive pas à trouver l'invariant de boucle bien que j'aie essayé avec sigma i= x jusqu'a y mais je ne trouve pas la formule avec laquelle la remplir .
Merci d'avance pour votre aide

Posté par
flight
re : Invariant de boucle 01-10-18 à 17:05

salut

pour ce que tu veux faire pourquoi ne pas utiliser une boucle toute simple du genre

z = 0 'variable cumulative
a = 2
b = 7
i = 0
While Val(a) + i <> Val(b)
z = z + (Val(a) + i)
i = i + 1
Wend
MsgBox z + (Val(a) + i)  ' --> donne la valeur attendue
End Sub

Posté par
carpediem
re : Invariant de boucle 01-10-18 à 20:11

salut

c'est quoi un invariant de boucle ?

Posté par
lafol Moderateur
re : Invariant de boucle 01-10-18 à 23:26

Bonjour
tes quelques itérations sont pour le moins surprenantes ...

Posté par
samihormi
re : Invariant de boucle 02-10-18 à 09:19

Re bonjour

Un invariant de boucle est une proposition qui est vrai avant la boucle et qui demeure vrai apres chaque iteration.

En quoi mes iterations sont-elles surprenantes ? Vous semble t-elle fausses ?

Posté par
lafol Moderateur
re : Invariant de boucle 02-10-18 à 10:19

déjà les x, on se demande d'où ils sortent
ensuite tes sommes déraillent à partir de l'itération 2

Posté par
luzak
re : Invariant de boucle 02-10-18 à 13:13

Bonjour !
Je n'ai pas répondu parce qu'il y a deux hypothèses :
1. L'algorithme (incorrect) a été fourni par le professeur qui souhaite qu'on trouve la faute par examen d'invariant de boucle.
2. La faute est celle d'une recopie hâtive ce qui explique que les "essais" déraillent.

@samihormi
Tu as un invariant simple, en notant k le nombre d'itérations, à savoir "Nombre_suivant-k".
Mais si l'énoncé n'est pas l'original je te signale qu'il ne fera pas la somme voulue faute d'une initialisation correcte.
Il est facile de voir que si a>b on n'entrera pas dans la boucle.

Posté par
samihormi
re : Invariant de boucle 02-10-18 à 14:52

@luzak

L'algorithme est correct, c'est une certitude.
En effet les "x" sont en réalité les "a", d'ou l'originalité de mes itérations , de plus ils existaient  quelques erreurs de calculs.
Voici les véritables itérations que j'ai obtenu :

Iteration 1, i = 1 , Nombre_suivant = a+1, solution = a+(a+1)=2a+1
Iteration 2, i = 2 , Nombre_suivant = a+2, solution = (a+2)+(2a+1)=3a+3
Iteration 3, i = 3 , Nombre_suivant = a+3, solution = (a+3)+(3a+3)=4a+6
Iteration 4, i = 4 , Nombre_suivant = a+4, solution = (a+4)+(4a+6)=5a+10
Iteration 5, i = 5 , Nombre_suivant = a+5, solution = (a+5)+(5a+10)=6a+15
etc

En ce qui concerne l'avancement de la trouvaille de l'invariant de boucle :

J'estime que la partie de "solution" avec "a",
A savoir = (a,2a,3a,4a,5a,6a,...) peu être obtenu avec allant de i=a juqu'a y (lorsque la boucle s'arrête),
Par contre je n'arrive pas à introduire la partie entiere de "solution" à savoir = (0,1,3,6,10,15,...)

Merci d'avance pour vos pistes

Posté par
luzak
re : Invariant de boucle 02-10-18 à 15:44

Pourquoi appeler "somme(a,b)" un algorithme qui ne calcule PAS a+b .
Parce que franchement trouver 6a+15 au bout de 5 itérations et persister à croire que tu as la somme a+b !

encore une fois, d'où vient l'algorithme ?
Est-il donné comme ça ? Est-ce celui que tu proposes pour résoudre un problème ? Et quel problème ? Il faudrait le détailler si tu veux qu'on t'aide.

Posté par
luzak
re : Invariant de boucle 02-10-18 à 16:10

En fait, tu as un algorithme qui calcule (au bout de n itérations) le réel (n+1)a+\dfrac{n(n+1)}2.
Donc, au bout de b itérations tu auras (b+1)(a+\dfrac b2)

Si c'est ton intention, parfait !
Mais pour appeler ça le calcul d'une somme il faut un certain nombre de contorsions !

Posté par
lafol Moderateur
re : Invariant de boucle 02-10-18 à 17:06

son intention était annoncée là :

samihormi @ 01-10-2018 à 13:51

Bonjour à tous :

Voila mon probleme, j'ai l'algorithme suivant

fonction somme(a,b):
Entree: deux entiers a et b, avec a ≤ b
Sortie : la somme de a, a+1, …, et b.



si j'ai bien compris, la fonction somme(a,b) doit calculer si a est un entier inférieur ou égal à un entier b la somme \sum_{k=a}^b k

Posté par
samihormi
re : Invariant de boucle 02-10-18 à 17:52

@lafol
Exactement !!
Mais il me faut la formule a l'intérieur de sigma pour ensuite prouver par récurrence que l'algorithme est vrai .

@luzak

L'algorithme nous est donné comme ça (je vous avoue que le manque d'indication est également problématique pour moi).
Je doit trouver une formule qui est vrai avant la boucle et après chaque itération de la boucle , c'est l'invariant de boucle.
Une fois trouvé je vais démontrer par récurrence (avec k comme en Terminale) que l'invariant de boucle demeure vrai pour toute valeur.
Puis enfin, je pourrais ainsi en conclure que l'algorithme est correcte.

Toutefois je ne comprend aucune de vos 2 formules j' ai essayé tant bien que mal mais toujours rien.

Posté par
alb12
re : Invariant de boucle 02-10-18 à 17:59

salut,
si j'ai bien compris ton invariant de boucle est a+(a+1)+(a+2)+ ... +(a+i)= ???

Posté par
alb12
re : Invariant de boucle 02-10-18 à 18:12

j'ai poste avant d'avoir lu ton message, je maintiens ma proposition.

Posté par
samihormi
re : Invariant de boucle 03-10-18 à 05:59

@alb12

Non, ta formule est valable pour la variable 'Nombre_suivant':
Mon invariant de boucle est la variable 'solution'

Posté par
carpediem
re : Invariant de boucle 03-10-18 à 08:11

j'avoue que je n'ai toujours pas vraiment compris ce qu'est un invariant de boucle ... et à quoi ça sert ... mais d'après ta réponse à 09h19 alors je plussoie à la proposition de alb12

solution = \sum_0^i (a + i)

...

Posté par
luzak
re : Invariant de boucle 03-10-18 à 08:12

Bonjour alb12 !
Quelle différence entre ta relation et ce que j'avais indiqué  le 02-10 à 16:10 ?

@samihormi
La formule donnée est bien la variable "solution".

Posté par
alb12
re : Invariant de boucle 03-10-18 à 08:52

"Toutefois je ne comprend aucune de vos 2 formules j' ai essayé tant bien que mal mais toujours rien." avait dit samihormi
c'est pourquoi j'ai reformule.
On pourrait meme dire que l'invariant de boucle est:
solution=somme de i=0 à i=k des a+i et k<b

Posté par
carpediem
re : Invariant de boucle 03-10-18 à 09:07

luzak : ton invariant de boucle est le résultat final donc une constante !! ... c'est donc évidemment un invariant de boucle

mais d'après ce que je comprends on veut un invariant qui dépende du compteur utilisé dans la boucle (le compteur est nombre_suivant ... que j'ai noté i comme alb12)

et à chaque boucle on a bien la formule de alb12

enfin tu le dis bien dans ta deuxième ligne mais en utilisant la variable b ... qui a déjà un rôle ...

ce me semble-t-il ...

Posté par
alb12
re : Invariant de boucle 03-10-18 à 10:08

@samihormi
la formule que tu cherches est solution=a+(a+1)+ ... +(a+k)
mais c'est à toi de trouver cette formule ! suite arithmetique ?

Posté par
luzak
re : Invariant de boucle 03-10-18 à 10:40

On peut voir comme ça mais, pour moi, n était le compteur d'itérations...

Posté par
carpediem
re : Invariant de boucle 03-10-18 à 10:47

ha d'accord : ton n est notre i

un entier n est moins complexe qu'un entier i effectivement !!

Posté par
samihormi
re : Invariant de boucle 03-10-18 à 15:44

Merci à tous pour votre précieuse aide:

J'ai finalement trouvé l'invariant de boucle ...

Posté par
carpediem
re : Invariant de boucle 03-10-18 à 16:20

qui est donc ?

Posté par
samihormi
re : Invariant de boucle 04-10-18 à 11:09

L'invariant de boucle est de i = x a y de (i+1)x + combinason avec n = i+1 et r = 2

Posté par
alb12
re : Invariant de boucle 04-10-18 à 11:34

autant lancebroquer dans une calebasse

Posté par
lafol Moderateur
re : Invariant de boucle 04-10-18 à 13:30

samihormi @ 04-10-2018 à 11:09

L'invariant de boucle est de i = x a y de (i+1)x + combinason avec n = i+1 et r = 2


tu m'en diras tant ....

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !