stabilité

(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)





Posted by: maxboubou

bonjour a tous !!
voila,je n'arrive pas a convaincre mon prof que la notion de stabilité est reliée aux algorithmes deterministes (enfin,tout dépend de la définition qu'on en donne).
peut-on dire qu'un algorithme deterministe est stable ? si oui, dans quel sens ?
(le sujet de tipe cette année c'est limite ,stabilité,variabilité...j'ai deja pas mal bossé sur cette idée,et voila qu'il me dit que ca colle pas !)


Posted by: Patastronch

Qu'appelles-tu stable ?

Tu parles de stabilité au voisinage d'une valeur ? Dans ce cas la rien à voir avec le déterminisme.
Tu parles de stabilité numérique ? Dans ce cas la rien à voir avec le déterminisme.
Tu parles de robustesse ? Dans ce cas la rien a voir avec le déterminisme.
Tu parles de la stabilité algorithmique qui peut se vulgariser comme : Si l'algorithme renvoie la solution optimale a dans un ensemble de solution A alors l'algorithme renverra toujours la solution a pour tout ensemble A privé d'un (ou plusieurs) éléments de A différent a. Si tu parles de cette stabilité, alors rien a voir avec le déterminisme.

Enfin bon tout ca pour dire que stabilité ca a pas de sens, ou plutot trop de sens selon le contexte dans lequel il est employé. Et ca va etre dur de te répondre si tu précises pas de quelle notion de stabilité tu parles.


Posted by: maxboubou

oui,en effet...
mais le theme du TIPE de prépa cette année c'est limite,stabilité,variabilité...la definition de stabilité est alors laissée aux candidats, je pense,et je voulais savoir justement si on pouvait trouver une notion pertinente de stabilité qui colle avec les algorithmes deterministes...


Posted by: Dominique Lefebvre

Citation:
Posté par maxboubou
oui,en effet...
mais le theme du TIPE de prépa cette année c'est limite,stabilité,variabilité...la definition de stabilité est alors laissée aux candidats, je pense,et je voulais savoir justement si on pouvait trouver une notion pertinente de stabilité qui colle avec les algorithmes deterministes...


Peux-tu nous donner un exemple de ce que tu appelles "un algorithme déterministe"?


Posted by: maxboubou

par exemple,des algorithmes de jeu (puissance 4,morpion par exemple)
en effet,les techniques de programmation permettent aujourd'hui de mettre en place des algorithmes qui permettent a l'ordinateur d'evaluer tous les coups possibles du jeu,et donc de choisir le coup optimal (l'ordi devient donc pratiquement imbattable)...


Posted by: Patastronch

Citation:
Posté par maxboubou
par exemple,des algorithmes de jeu (puissance 4,morpion par exemple)
en effet,les techniques de programmation permettent aujourd'hui de mettre en place des algorithmes qui permettent a l'ordinateur d'evaluer tous les coups possibles du jeu,et donc de choisir le coup optimal (l'ordi devient donc pratiquement imbattable)...


Premiere chose, si l'ordinateur énumère toutes les possibilités, alors ce n'est pas les technique de programmations qui sont mises en avant mais la capacité de ta machine surtout. Quant au déterminisme il me semble que tu as pas vraiment capté la notion exact. Si tu veux vriament comprendre de quoi il s'agit, va voir ce qu'est une machine de turing déterministe et une machine de turing non déterministe. Si tu veux approfondir la notion hésite pas a lire des bouquins de complexité et notemment Computers and Intractability de Michael R. Garey et David S. Johnson, (c'est la référence dans le domaine).

Sinon pour vulgariser, un algorithme sera dit déterministe pour une classe de complexité s'il peut etre résolu en temps contraint pas la classe de compléxité sur une machine déterministe.

Dans la pratique tous les algorithme sont déterministe ! Ce n'est pas parceque mon probleme appartient a NP que l'algorithme que je vais pondre n'est pas déterministe, ca voudra juste dire quemon algo ne peut s'executer en temps polynomial sur une machine déterministe (si on suppose P différent de NP) mais qu'a la fois il peut s'executer en temps polynomial sur une machine non déterministe. Mais ton ordinateur est une machine déterministe par définition ! Donc ton algorithme est forcément programmé de maniere déterministe mais ne s'executera pas en temps polynomial.

Je sais pas si j'ai été tres clair, mais je te conseille fortement d'etudier la théorie de la compléxité si tu veux etre a l'aise avec cette notion.


Posted by: Flodelarab

Le déterminisme réside uniquement dans le déterminisme de l'évaluation des branches d'un arbre.

Il me semble qu'on cache le problème.
Il me semble aussi que dans une partie d'échecs, l'arbre est considéré infiniment grand.... on se leurre.


Posted by: bruce.ml

Je ne suis pas d'accord avec cette notion de déterminisme, c'est bien plus simple que ça : un algorithme est determinite s'il retourne toujours la même réponse.


Posted by: Dominique Lefebvre

Citation:
Posté par bruce.ml
Je ne suis pas d'accord avec cette notion de déterminisme, c'est bien plus simple que ça : un algorithme est determinite s'il retourne toujours la même réponse.


Tu veux dire, si les données d'entrée sont strictement identiques...


Posted by: Chimomo

Je pense que la notion de déterminisme initialement évoquée n'était en effet pas celle liée aux classes de complexité mais une notion fondée sur la certitude de la validité du résultat renvoyé.

Par exemple, est algorithme qui test les divisions d'un entier par tous les entiers premiers inférieurs à sa racine carré est un test déterministe de primalité. Un algorithme probabiliste basé sur le théorème de Fermat (qui fait un grand nombre de test de Fermat pour des nombres grands et aléatoires) ne sera pas déterministe, puisqu'il se pourrait qu'il déclare un nombre premier alors que le nombre ne l'était pas (si c'était par exemple un nombre de Carmichael).


Posted by: Patastronch

Citation:
Posté par bruce.ml
un algorithme est determinite s'il retourne toujours la même réponse.


Ok rien a voir avec la compléxité en effet, c'est la définition classique j'aurais du y penser. Faut me comprendre je suis dans un département RO :)


Posted by: Patastronch

Citation:
Posté par Chimomo
Je pense que la notion de déterminisme initialement évoquée n'était en effet pas celle liée aux classes de complexité mais une notion fondée sur la certitude de la validité du résultat renvoyé.

Par exemple, est algorithme qui test les divisions d'un entier par tous les entiers premiers inférieurs à sa racine carré est un test déterministe de primalité. Un algorithme probabiliste basé sur le théorème de Fermat (qui fait un grand nombre de test de Fermat pour des nombres grands et aléatoires) ne sera pas déterministe, puisqu'il se pourrait qu'il déclare un nombre premier alors que le nombre ne l'était pas (si c'était par exemple un nombre de Carmichael).


Ok je vois ce que tu veux dire. Un algorithme déterministe par opposition a un algorithme stochastique. Par exemple un algo génétique n'est pas considéré comme déterministe puisque certaines de ses action seront aléatoires. Cependant précisons que le random d'un ordinateur est une fonction déterministe dans l'absolue :)


Posted by: maxboubou

merci de toutes vos reponses...
en effet,l'objectif d mon tipe serait de partir d'algorithmes deterministes (qui,a partir d'une situation donnée renvoient le meme resultat),et d'enchainer en mettant en evidence le fait que tous les jeux ne peuvent pas etre programmés ainsi (exemple du jeu de go ou autre,qui introduit une grande part de hasard dans ses algorithmes).
pour moi le lien avec le sujet "limite,variabilité,stabilité" est clair...
j'aimerais connaitre votre avis,avant de vraiment me lancer dans quelque chose d'hors sujet...


Posted by: Dominique Lefebvre

Citation:
Posté par maxboubou
pour moi le lien avec le sujet "limite,variabilité,stabilité" est clair...
j'aimerais connaitre votre avis,avant de vraiment me lancer dans quelque chose d'hors sujet...


Je ne suis pas sur de voir le lien entre le sujet "limite, variabilité, stabilité" et les algorithmes déterministes tels que tu les présentes.
Par exemple, qu'est-ce que serait la limite d'un algo déterministe? Et sa variabilité? Et bien sur, sa stabilité? Comment définir ces trois caractéristiques à propos d'un algorithme?

Ces trois notions me font plutôt penser à un système dynamique, mais cela doit être une déformation professionnelle :-))










-