Répondre à la discussion
Page 1 sur 2 1 DernièreDernière
Affichage des résultats 1 à 30 sur 41

Classe des problèmes algorithmiques



  1. #1
    ABN84

    Classe des problèmes algorithmiques

    Bonjour,
    me réferent à ce lien sur la théorie de la complexité http://fr.wikipedia.org/wiki/Th%C3%A...es_algorithmes
    2 classes de problèmes sont identifées:
    - décision
    - recherche de solution
    Je trouve qu'il manque une classe:
    ex:
    Q: existe-t-il une solution pour x^2<-1?
    R: non
    --> problème de décision
    Q: trouver une solution à x^2<1
    R: 0.5 R:0 R:-0.8...
    --> problème de recherche de solution
    Q: trouver toutes les solutions de x^2<1
    R:]-1,1[
    --> problème de ?

    -----

    "Engineering is the art of making what you want from what you get"

  2. Publicité
  3. #2
    gg0

    Re : Classe des problèmes algorithmiques

    Bonsoir.

    C'est un problème de recherche de solutions (les solutions étant des intervalles ou des réunions d'intervalles). Les logiciels de calcul formel travaillent ainsi.

    Cordialement.

  4. #3
    ABN84

    Re : Classe des problèmes algorithmiques

    Bonsoir,
    J'associe la recherche de solution unitaire(dans la sens "trouver une solution") aux algorithmes d'optimisation de type: Newton, Simplex, nelder-mead, pso, genetique, grogrammation dynamique, LMI...
    en gros des algorithmes qui cherchent un zéro ou un minimum d'une fonction.
    Quel type d'algo est associé à la recherche d'intervalle?
    "Engineering is the art of making what you want from what you get"

  5. #4
    gg0

    Re : Classe des problèmes algorithmiques

    Tout dépend de la typologie.

    Si les types sont peu nombreux et très stricts, de nombreux algorithmes ne sont d'aucun type.
    Je ne vois pas trop l'intérêt de cette question ...

  6. #5
    ABN84

    Re : Classe des problèmes algorithmiques

    Bonjour,
    Citation Envoyé par gg0 Voir le message
    Tout dépend de la typologie.

    Si les types sont peu nombreux et très stricts, de nombreux algorithmes ne sont d'aucun type.
    Je n'ai rien compris de cette réponse
    Je ne vois pas trop l'intérêt de cette question ...
    je cherche de la littérature pour résoudre un problème d’ingénierie auquel je suis confronté.
    Le plus souvent mes problèmes sont du type:
    trouver la commande qui minimise la consommation d'energie d'une batterie sous la contrainte [...], ce qui pour moi se traduit par une recherche de minimum d'une fonction de pénalité sous certaines contraintes sous forme d'inéquations. Si j'ai l'expression analytique de la fonction de pénalité, de son gradient et de son hessien, j'utilise la méthode de Newton, dans le cas contraire, j'utilise soit la programmation dynamique soit un algorithme évolutionnaire basé populations (génétiques, ou essaim particulaire).
    Une autre classe de problème aux quels je suis confronté est de type: trouver un x tel que f(x)<a, dans ce cas, si ça peut s'ecrire sous forme de LMI linéaire, les algorithmes pour résoudre des LMI existent sinon, je fais tourner un algo d'otim (Newton ou Metaheuristique) sur f et j'utilise comme fonction d'arrêt f(x)<0
    Ces deux types de problèmes sont des choses aux quelles je suis habitué. Actuellement, je suis confronté à un problème de type trouver tous les x qui respectent f(x)<a, f pouvant avoir plusieurs minimas.
    Je n'ai jamais répondu à ce type de problèmes précedemment, et je cherche des mots clés pour commencer à chercher sur ieeexplore
    "Engineering is the art of making what you want from what you get"

  7. A voir en vidéo sur Futura
  8. #6
    gg0

    Re : Classe des problèmes algorithmiques

    Ok !

    Dans ton premier message, tu as présenté (sans le vouloir) un problème très différent (*). Je ne suis pas spécialiste du sujet, mais "résolution d'inéquation" me semble approprié. Un forum d'informatique sera sans doute plus précis.

    Cordialement.

    (*) trouver parmi deux classes d'algorithmes où placer un problème.

  9. Publicité
  10. #7
    ABN84

    Re : Classe des problèmes algorithmiques

    En utilisant des outils de calcul formel (Maple, Mupad...), on peut résoudres des inéquations simples.
    Mais dès que celles-ci deviennent complexes et non linéaires, ils n'y arrivent plus.
    De la même façon que la méthode de Newton-Raphson (et analogues) permet de donner une solution approchée de la solution d'une équation non linéaire, je voudrais savoir s'il existe un équivalent pour les inéquations
    "Engineering is the art of making what you want from what you get"

  11. #8
    12Pierre44

    Re : Classe des problèmes algorithmiques

    Bonjour,
    J'ai suivi avec intérêt ce sujet depuis le début.
    Avez-vous consulté les études réalisées par J.Jacquelin ?
    D'autre part, l'outil informatique ne peut que calculer ce qu'un utilisateur lui demande. En d'autres termes, si vous savez résoudre un certain problème, alors vous pouvez faire le module qui fera le calcul à votre place. Les logiciels dont vous parlez ne sont que des boites à outils. Soit l'outil dont vous avez besoin existe, mais apparemment ce n'est pas le cas, soit il n'existe pas mais ces logiciels ont les outils capables de le fabriquer, enfin, dernière hypothèse, ces outils-là n'existe pas.
    Dans tous les cas, si vous pouvez décrire le problème et sa solution, c'est à dire écrire l'algorithme pour faire le module, alors, il peut être réalisé avec des langages de bas niveau.
    Mais à mon avis, aucun langages ne pourra résoudre un problème s'il n'a pas été résolu formellement par l'auteur du logiciel.

  12. #9
    mike.p

    Re : Classe des problèmes algorithmiques

    Bonjour,

    Citation Envoyé par ABN84 Voir le message
    Ces deux types de problèmes sont des choses aux quelles je suis habitué. Actuellement, je suis confronté à un problème de type trouver tous les x qui respectent f(x)<a, f pouvant avoir plusieurs minimas.
    En fait, tout dépend des relations dont vous disposez pour améliorer votre position après des tests. Un préalable intéressant , dans ce cas , serait de savoir le nombre de minima et tout ce qui génère des conditions d'arrêt local. Arrangez pour converger vers un petit nombre d'options à explorer complètement.
    Si vous n'en avez pas, je ne vois rien d'autre à faire que tout tester. Il n'y a pas de solution universelle miracle ; beaucoup de ces problèmes sont NP complets.
    Dernière modification par mike.p ; 27/08/2013 à 18h50.

  13. #10
    ABN84

    Re : Classe des problèmes algorithmiques

    Dans tous les cas, si vous pouvez décrire le problème et sa solution, c'est à dire écrire l'algorithme pour faire le module, alors, il peut être réalisé avec des langages de bas niveau.
    Ma question concerne l'existance de travaux sur ce type d'algorithmes.
    Pour être concrêt:
    imaginons:
    f=x^4-15*x^2+5*x-20;

    on calcule la jacobienne de f:
    J=4*x^3 - 30*x + 5;

    si je veux trouver une solution pour f(x)=0, un algorithme possible est:
    Code:
    x=x0;
    
    for i=1..100
    
         x=x-f(x)/J(x);
    end
    selon la valeur de x0, la réponse sera soit 3.88 soit -4.16

    Je voudrais savoir s'il existe un algorithme qui puisse à partir de l'expression de f résoudre f<0
    la réponse attendue est ]-4.16,3.88[
    "Engineering is the art of making what you want from what you get"

  14. #11
    12Pierre44

    Re : Classe des problèmes algorithmiques

    D'abord, je crois qu'il faut préciser le sens d'algorithme.
    Un algorithme est une suite d'ordres logiques qui comporte un début et une fin.
    Ce terme n'a rien à voir avec l'informatique.
    Par contre, si on doit faire un traitement informatique, on commence par écrire une algorithme : je fais ci, je fait ça, si il y a tel cas, je ferai ceci, sinon, je ferai cela.
    Ensuite, naturellement, on va le traduire en code suivant le langage que l'on préfère et qui semble le plus adapté.
    Il y a lieu de préciser que l'algorithme est souvent (ou quelque-fois) difficile à faire, l'écriture du code n'est qu'une traduction dans un langage compréhensible par une machine.
    Avec l'exemple que vous donnez, l'algorithme est vraiment facile à faire et le code ne serait qu'une simple traduction.
    Et comme dit Mike.p, il n'y a pas de solution miracle, il faut savoir résoudre le problème pour pouvoir demander à la machine de faire le calcul.

  15. #12
    ABN84

    Re : Classe des problèmes algorithmiques

    D'abord, je crois qu'il faut préciser le sens d'algorithme.
    Un algorithme est une suite d'ordres logiques qui comporte un début et une fin.
    Ce terme n'a rien à voir avec l'informatique.
    A aucun moment, je n'ai parlé d'Informatique, je parle d'algo au sens mathématique du terme.
    L'algorithme que j'ai présenté est l'algorithme de Newton basique ( http://en.wikipedia.org/wiki/Newton%27s_method ) qui sert à résoudre des équations non linéaires.
    il n'y a pas de solution miracle, il faut savoir résoudre le problème pour pouvoir demander à la machine de faire le calcul.
    Non!
    L’existence même d'algorithmes comme celui de Newton est la preuve du contraire, il existe certaines fonctions pour lesquelles on ne peut pas trouver de solutions analytiques. alors que par un algorithme comme celui de Newton-Raphson, on peut approcher très fidèlement la solution.
    J'aimerais si vous voulez bien revenir à ma question initiale:
    existe-t-il des travaux sur des algorithmes de résolution numérique approchée d'inéquations.
    Mon exemple précédent est simple à comprendre.
    "Engineering is the art of making what you want from what you get"

  16. Publicité
  17. #13
    ABN84

    Re : Classe des problèmes algorithmiques

    Citation Envoyé par mike.p Voir le message
    Bonjour,



    En fait, tout dépend des relations dont vous disposez pour améliorer votre position après des tests. Un préalable intéressant , dans ce cas , serait de savoir le nombre de minima et tout ce qui génère des conditions d'arrêt local. Arrangez pour converger vers un petit nombre d'options à explorer complètement.
    Ce dont vous parlez c'est le problème de convergence locales et globale de l'algorithme. c'est un vrai problème mais prématuré par rapport à mon besoin, vue que pour le moment,je ne connait aucune classe d'algo pour résoudre des inéquations, une fois j'en aurais identifié un ou plisieurs il conviendra d'en étudier la convergence.
    Si vous n'en avez pas, je ne vois rien d'autre à faire que tout tester. Il n'y a pas de solution universelle miracle ; beaucoup de ces problèmes sont NP complets.
    encore une fois, votre message me fait croire que vous pensez que je parle d'algorithmes d'optimisations.
    "Engineering is the art of making what you want from what you get"

  18. #14
    obi76

    Re : Classe des problèmes algorithmiques

    Bonjour,

    Citation Envoyé par ABN84 Voir le message
    Ma question concerne l'existance de travaux sur ce type d'algorithmes.
    Pour être concrêt:
    imaginons:
    f=x^4-15*x^2+5*x-20;

    on calcule la jacobienne de f:
    J=4*x^3 - 30*x + 5;[...]

    la réponse attendue est ]-4.16,3.88[
    oui ça existe, j'ai déjà vu ça quelque part (je ne me rappelle plus du terme)... Il existe un nombre caractéristique d'un polynôme qui permet de savoir le nombre de changement de signe dans un intervalle donné. En utilisant ça on peut remonter à la solution que vous cherchez, c'est pas forcément très simple mais c'est faisable.

    EDIT : trouvé : http://fr.wikipedia.org/wiki/Th%C3%A...%A8me_de_Sturm
    Dernière modification par obi76 ; 27/08/2013 à 20h22.
    Paradoxalement, ce sont les débats stériles qui se reproduisent le plus.

  19. #15
    mike.p

    Re : Classe des problèmes algorithmiques

    OK ! écartons l'optimisation et la recherche de minima

    Supposez vous avoir l'algorithme pour résoudre f(x) = 0 ?

    Si oui, c'est trivial ; il vous suffit de segmenter votre ensemble de départ par les 0 de f et de tester un ( seul ) élément de chaque segment pour en déduire le signe

  20. #16
    obi76

    Re : Classe des problèmes algorithmiques

    Citation Envoyé par mike.p Voir le message
    Si oui, c'est trivial ; il vous suffit de segmenter votre ensemble de départ par les 0 de f et de tester un ( seul ) élément de chaque segment pour en déduire le signe
    Non, il peut y avoir un nombre pair de changements de signe dans l'intervalle, dans ce cas votre algorithme les ignorera. Il faut passer par ce que j'ai dit.
    Paradoxalement, ce sont les débats stériles qui se reproduisent le plus.

  21. #17
    gg0

    Re : Classe des problèmes algorithmiques

    Heu ...

    Des changements de signe entre deux zéros pour une fonction continue ? peu probable

    A noter : Si f n'est pas un polynôme, l'algorithme de Sturm ne s'applique plus. C'est pour cela que les logiciels formels ont des incapacités : pas de méthode pour trouver les zéros, pas de résolution d'inéquations.

  22. #18
    obi76

    Re : Classe des problèmes algorithmiques

    Non, enfin ce que je veux dire c'est que pour trouver vos intervalles de départ, il faut partir de l'hypothèse que dans chaque intervalle, il n'y a qu'un zéro. Pour en être sur, il faut passer par ce que j'ai dit
    Paradoxalement, ce sont les débats stériles qui se reproduisent le plus.

  23. Publicité
  24. #19
    ABN84

    Re : Classe des problèmes algorithmiques

    Bonjour,
    Pour OBI, le lien que vous avez présenté traite des fonctions polynomiales, les fonctions non linéaires auxquelles je peux être confronté on souvent des expressions en exp, sin/cos et tanh, donc non couvertes par la démarche présentée. ma fonction illustrative n'est qu'un exemple simple pour comprendre la problèmatique, en réalité, les fonctions que je traite sont non linéaires et multi arguments.
    Pour Mike,
    contre exemple:
    f=x^2+y^2;
    resoudre par newton f=1 me donnera un couple de points x,y se trouvant sur le cercle décrit par x^2+y^2=1; par exemple [1,0],[sqrt(2)/2,-sqrt(2)/2]... tout dépendra du point de départ [x0,y0]
    comment à partir de cette seule info, pouvez vous sortir le domaine dans lequel f<1?


    la solution analytique de f<1, est qqch de type: x=[-1,1], y=[-(1 - x^2)^(1/2), (1 - x^2)^(1/2)]

    c'est ce type de solutions que je cherche, mais non pas par des outils de calcul formel (car ils ne pourront pas résoudre les inéquations non linéaires) mais avec une methode de calcul numérique analogue à Newton
    Dernière modification par ABN84 ; 28/08/2013 à 09h25.
    "Engineering is the art of making what you want from what you get"

  25. #20
    obi76

    Re : Classe des problèmes algorithmiques

    Si ce sont pour des fonctions quelconques, alors il faut trouver un moyen de trouver le nombre de changement de signes dans un intervalle.
    Paradoxalement, ce sont les débats stériles qui se reproduisent le plus.

  26. #21
    gg0

    Re : Classe des problèmes algorithmiques

    Ah, nouvelle information : Il s'agit de fonctions de plusieurs variables.

    Là, je crains qu'il ne faille t'adresser à des spécialistes (qui généralement n'ont pas le temps de fréquenter des forums). En calcul formel (exact) le problème d'obtenir des algorithmes effectifs est ouvert (non résolu). En calcul approché, dès qu'il y a du non linéaire à beaucoup de variables, la stabilité des algorithmes est douteuse. Avec 2 ou 3 variables, il y a sans doute des outils connus (des spécialistes).
    Pour ton exemple, la logique est la même : Une fois défini l'ensemble des solutions, il partitionne le plan en plusieurs zones où le signe est constant. Il suffit de tester un point de chaque zone. Pour une fonction simple, on peut trouver des points dans les différentes zones, pour une fonction très compliquée, il devient difficile de savoir même combien il y a de zones.

    Cordialement.

  27. #22
    obi76

    Re : Classe des problèmes algorithmiques

    Citation Envoyé par gg0 Voir le message
    Ah, nouvelle information : Il s'agit de fonctions de plusieurs variables.
    et il sagit aussi de fonctions non forcément polynomiales, alors dans ce cas...

    Pour ton exemple, la logique est la même : Une fois défini l'ensemble des solutions, il partitionne le plan en plusieurs zones où le signe est constant. Il suffit de tester un point de chaque zone.
    Sauf que pour garantir que le signe est constant dans une zone, il faut de toute façons trouver une méthode qui à un intervalle donné te donnent le nombre de zéros de cette fonction (j'insiste sur ce point). Tester si un point dans la zone est d'un certain signe ne peut pas te garantir qu'ils ont tous le même signe dans cet intervalle.
    Dernière modification par obi76 ; 28/08/2013 à 09h31.
    Paradoxalement, ce sont les débats stériles qui se reproduisent le plus.

  28. #23
    toothpick-charlie

    Re : Classe des problèmes algorithmiques

    pour une fonction de plusieurs variables, l'ensemble des zéros est en général infini non dénombrable, selon la "lisseur" de la fonction cet ensemble sera plus ou moins simple, mais il me semble difficile qu'un algorithme numérique donne des solutions approchées de tous les zéros.

  29. #24
    gg0

    Re : Classe des problèmes algorithmiques

    @ Obi76 :

    pour une fonction simplement continue, il peut être extrêmement difficile de définir les zones (il n'y a plus de question d'intervalle), mais si elle est suffisamment "lisse", on ne passe pas d'une zone strictement positive à une zone strictement négative sans passer par 0 (couper la frontière des zones). Donc le signe sur une zone est parfaitement déterminé par la valeur en un point.
    Par exemple, pour résoudre y-x sin(x)<1, on remarque que y-x sin(x)=1 est une courbe continue du plan, qui définit deux zones : Zone 1 : Celle qui contient l'origine; zone 2 : celle qui contient le point de coordonnées (0,2).
    0-0 sin(0) <1
    2-0 sin(0) >1
    Donc les solutions sont les couples de coordonnées des points de la zone 1.
    Remarque : On est bien avancés ! On a trouvé que les solutions sont les (x,y) tels que x est quelconque et y>x sin(x)+1.

    En général, les "résolutions" d'inéquations à plusieurs variables sont assez décevantes. Le contre exemple d'ABN84 le montre aussi, car c'est une réécriture de l'inéquation.

    Cordialement.

  30. Publicité
  31. #25
    obi76

    Re : Classe des problèmes algorithmiques

    Citation Envoyé par gg0 Voir le message
    @ Obi76 :

    pour une fonction simplement continue, il peut être extrêmement difficile de définir les zones (il n'y a plus de question d'intervalle),
    C'est pour ça que dans le cas de polynomes, passer par le théorème de Sturm me paraissait la bonne solution. Maintenant si on complexifie le problème de départ, on va rapidement arriver dans un mur, si ce n'est pas déjà le cas...
    Paradoxalement, ce sont les débats stériles qui se reproduisent le plus.

  32. #26
    mike.p

    Re : Classe des problèmes algorithmiques

    Salut Obi76


    entre 2 zéros ? et alors qu'on ne présume pas de l'alternance des signes mais qu'on effectue un test à chaque intervalle ?!?!

    pourtant le signe ne peut changer qu'après un zéro ( on est implicitement dans le continu ) et donc entre 2 zéros le signe est unique.

    je dois rater quelque chose ... vos explications sont les bienvenues

  33. #27
    mike.p

    Re : Classe des problèmes algorithmiques

    mais les intervalles sont des segments dont les bornes sont les zéros ...

  34. #28
    toothpick-charlie

    Re : Classe des problèmes algorithmiques

    le problème c'est que si tu utilises un algorithme itératif qui trouve des zéros de la fonction, comment être sûr qu'entre deux zéros qu'il a trouvés il n'y en pas d'autres?

  35. #29
    mike.p

    Re : Classe des problèmes algorithmiques

    Citation Envoyé par ABN84 Voir le message
    contre exemple:
    f=x^2+y^2;
    Bonjour,

    mais ce n'est pas une fonction ...

    vous voulez l'intervalle des x dont l'image a un certain signe. Donc on devrait avoir une fonction de x qui rende y. Ca n'a plus de sens si un x rend un positif ET un négatif

    je vous rappelle que la particularité d'une fonction est d'associer une valeur unique Une équation de cercle n'est pas une fonction

  36. #30
    gg0

    Re : Classe des problèmes algorithmiques

    @ Mike.p :

    f: (x,y) -->x²+y² est bien une fonction.

    Cordialement.

Sur le même thème :

Page 1 sur 2 1 DernièreDernière

Discussions similaires

  1. Classe gauche vs classe de conjugaison
    Par nico3004 dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 26/12/2011, 21h57
  2. Classe Cn
    Par guy_flavien dans le forum Mathématiques du supérieur
    Réponses: 7
    Dernier message: 03/11/2010, 10h51
  3. Classe ATS
    Par Neil.daf dans le forum Orientation après le BAC
    Réponses: 2
    Dernier message: 15/08/2010, 13h52
  4. classe prepa/classe prepa integree
    Par adr101 dans le forum Orientation après le BAC
    Réponses: 2
    Dernier message: 04/01/2007, 12h26
  5. Classe AB?
    Par flyingman dans le forum Électronique
    Réponses: 2
    Dernier message: 14/01/2005, 15h39