Stabilité

par **maxboubou** » 17 Oct 2007, 22:21

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 !)

par **Patastronch** » 18 Oct 2007, 02:50

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.

par **maxboubou** » 18 Oct 2007, 19:19

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...

par **Dominique Lefebvre** » 18 Oct 2007, 21:35

maxboubou a écrit: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"?

par **maxboubou** » 18 Oct 2007, 21:55

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)...

par **Patastronch** » 18 Oct 2007, 23:20

maxboubou a écrit: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.

par **Flodelarab** » 18 Oct 2007, 23:22

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.

par **bruce.ml** » 19 Oct 2007, 11:12

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.

par **Dominique Lefebvre** » 19 Oct 2007, 15:24

bruce.ml a écrit: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...

par **Chimomo** » 19 Oct 2007, 15:48

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).

par **Patastronch** » 19 Oct 2007, 16:18

bruce.ml a écrit: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

par **Patastronch** » 19 Oct 2007, 16:32

Chimomo a écrit: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

par **maxboubou** » 19 Oct 2007, 18:40

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...

par **Dominique Lefebvre** » 19 Oct 2007, 19:18

maxboubou a écrit: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 :-)

)

Stabilité

stabilité

Qui est en ligne