Discussion :

[dark_falcon]

Bonjour,

dans le cadre d'un projet informatique je dois pouvoir détecter les boucles infines dans un programme java.

Si quelqu un pourrais me renseigner sur une méthode de détéction ,
ça me dépannerais beaucoup

merci

[kissmytoe]

Une boucle doit toujours avoir une condition de sortie.

C'est de vérifier toutes les boucles une par une pour vérifie qu'elles possèdent toutes une condition de sortir SUR pour empecher une boucle sans fin.

Tu pourrais aussi faire un bout de code du genre

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
if (i > 300) 
{
    (boite de dialogue) boucle infini?
    conditionSortie = true
}
i++

[TabrisLeFol]

Pourrait tu preciser un peu? Avant compilation ou après? Qu'est ce que tu compte faire?
Lors de l'utilisation d'une variable locale test un while(test) en boucle sans fin est assez facile à reconnaitre mais sinon... Je ne vois pas trop comment on pourrait faire la difference entre une boucle très grande, une boucle sans fin...
Le mieu serait d'utiliser des algorithmes prouvables, si des commentaires sont bien ecrits (utilisant toujours une meme synthaxe) il doit etre possible de realiser un robot de verification... mais c'est compliqué...

[dark_falcon]

pour mon projet je dois analyser un programme java pour voir si il comporte des boucles infinies( avant compilation). Je pense qu une analyse statique du code en étudiant le graphe de controle du programme serait le plus adapté mais je ne sais pas comment je peux le construire (je travaille en java).Alors il suffirait de faire la couverturte du graphe pour voir si celui-ci ce déroule de manière "normal".(me dire si je me trompe),

merci d avance

[Gfx]

Tu peux jeter un oeil au projet PMD par exemple. C'est open source, en Java et cela fait ce que tu veux. Ca pourrait te donner des idees.

[tralloc]

Oui je crois qu'il y a pas mal de gens qui se sont cassés la tête sur ce problème.
La seule chose que j'imagine, analyser dans le programme s'il y a des conditions de sorties, et si ces conditions de sorties peuvent être atteintes quelles que soient les valeus d'entrée...

Entre autres termes il s'agit d'un casse tête mathématique.

[anykeyh]

On ne peut pas utiliser les assertion pour ça? (Je suis pas sur de ce que je dit hein!)

[Hervé Saladin]

On ne peut pas utiliser les assertion pour ça? (Je suis pas sur de ce que je dit hein!)

C'est ce que j'aurais dit moi aussi.
JUnit (et les tests unitaires en général) est fait expres pour tester ton code et vérifier si il est solide, tu devrais te pencher la-dessus, c'est assez facile à faire en plus
Le principe est le suivant : tu écris des methodes en java chargées de tester ton code. Tu part du prncipe que l'execution de ce code doit avoir tel ou tel effet, tu l'execute et tu teste si il a bien eu l'effet attendu (assertion).
Je sais ca a pas l'air clair expliqué comme ca, mais tu verra c'est vraiment pas sorcier.
Bon courage, a+.

[herve91]

La théorie dit qu'il n'existe pas d'algorithme permettant de savoir si un programme se termine dans un temps fini ou non

[anykeyh]

Si tu te sent grand, beau et fort (), je te conseil de coder un parser qui verifiera les contraintes de ta boucle et grace a un puissant algorithme de retropropagation te sortira les ensemble possible pour chaque variable de tes contraintes, et finira par travailler sur ceux-ci afin de te dire si oui ou non ta boucle peu etre infini...
Mais tu peu aussi le faire de tete dans certains cas... (Methode conseillée...)

Exemple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
while (a<10)
{
 a++;
}

Logiquement, a tend vers +infini si ta boucle tend vers +infini, or +infini>10, donc ta boucle ne peu pas etre infini

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
while (a<10)
{
a*=5;
}

A ce moment la, si dans l'entrée de la boucle a<=0 alors ta boucle sera infini. Donc il faut remonter au dessus de ta boucle voir quel valeur elle peu prendre et s'assurer qu'elle ne peu pas prendre une valeur <= 0

Enfin apres, en pratique, je sais pas si en java l'overflow de variable leve une exception ou comme en c reinitialise la variable a son minimum (0x11111111 - 1 = 0x0111111 avec le dernier bit de signe )

[TabrisLeFol]

La théorie dit qu'il n'existe pas d'algorithme permettant de savoir si un programme se termine dans un temps fini ou non

Un programme "brute" je suis bien d'accord, ou en tout cas je ne vois pas comment on pourait etre sur qu'il s'arrete.
Par contre si on utilise des algorithmes prouvables,il doit y avoir moyen. Par contre je ne sais pas s'il existe de programmes permettant de verifier à 100% qu'un algorithme prouvable est juste...
Justement dans le cas d'un programme brute, serait il possible d'extraire l'algorithme et de le prouver?
(Je sais que je fais un peu dérivé le sujet, mais bon... )

[anykeyh]

http://fr.wikipedia.org/wiki/Coq_%28logiciel%29

Cela sort de Java, mais d'apres ce que j'ai compris ça sert à ça...
Mais bon, a moins que tu developpe des logiciels pour des fusée, satellite, avion ou tout autre systeme que ne doit absolument pas planter, je conseil la bonne vieille methode du "bon bah sa a l'air de marcher là"

[herve91]

Est-ce que ce programme se termine (conjecture de Syracuse) ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
public void syracuse(int n) {
   while (n != 1) {
      if ((n % 2) == 0) {
         n = n / 2;
      } else {
         n = 3 * n + 1;
      }
   }
   System.out.println("ouf je me termine !");
}

[anykeyh]

1) La boucle continue tant que n!=1
donc pour n=1l e programme se termine...

2)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
if((n%2)==0) //-> nombre pair
{
 n = n / 2  //-> nombre impair
} else 
{ 
/* Le programme peu s'arreter uniquement si n==1
    Or pour cela il faut soit:
    n = 3 * n + 1 Ce qui est impossible avec un entier naturel superieur à 1
    ET
    n = n / 2 est possible si n = 2 car (2%2)==0
*/ 
 n = 3 * n + 1
}

Donc si jme suis pas louper: le programme s'arrette pour tout nombre entre 0 et n (entier non signé) pour n = {1, 2}

Edit: Je viens de voir sur wikipedia, zero pointée huhuhu

[anykeyh]

En fait je dirai qu'il suffit qu'à n'importe quel moment n soit un multiple de 2 (2^n) pour que la suite se termine.

[herve91]

En fait je dirai qu'il suffit qu'à n'importe quel moment n soit un multiple de 2 (2^n) pour que la suite se termine.

Malgré de fortes suspicions, on n'a pas encore prouvé qu'on retombe toujours sur 1 pour tout n... d'où le terme de conjecture. Comme quoi même avec des calculs tout bêtes, il peut être bien difficile (voire impossible) de déterminer si la boucle est finie ou non.

[TabrisLeFol]

Avec n entier naturel different de 0. La conjecture est que cela se termine pour tout nombre?

En tout cas les 1 000 000, premiers nombres fonctionnent.

[herve91]

Avec n entier naturel different de 0. La conjecture est que cela se termine pour tout nombre?

Oui

En tout cas les 1 000 000, premiers nombres fonctionnent.

Tu as vérifié
Alors tu aurais pu aller jusqu'à 3,2×10^16, après on ne sait pas...

[Albator5151]

Bonjour,

Pour complèter le sujet et peut -etre pour commencer par des choses simples existe-t-il des classes java agissant sur du code source java permettant de savoir quels sont toutes les variables utilisés dans le programmes sans forcément savoir leur valeur.

Merci.

[Albator5151]

Bonjour,

Toujours à propos du problème de départ quels sont les librairies à utiliser pour récupérer tel ou tel caractère dans du code java. Par exemple je voudrais récupérer toutes les lignes ou un while apparait.

Merci

PS:Surtout si vous avez des idées pour récupérer toutes les valeurs de telle ou telle variable dans un programme, genre avec du découpage avant ou arrière. J'ai aussi entendu parler du logiciel bandera.