L'analyse lissée est-elle utilisée en dehors du milieu universitaire?

24

L' analyse lissée a- t-elle trouvé son chemin dans l'analyse principale des algorithmes? Est-il courant que les concepteurs d'algorithmes appliquent une analyse lissée à leurs algorithmes?

algorithms complexity-theory algorithm-analysis Gilles 'SO- arrête d'être méchant'
la source
11
Les gens appliquent-ils une sorte d'analyse de complexité à leurs algorithmes en dehors du monde universitaire?
Dave Clarke
2
Ce que dit @DaveClarke; peut-être devrait-il demander des analyses rigoureuses (ou non triviales). Je m'attends à ce que de nombreux praticiens regardent leurs algorithmes, comptent la profondeur d'imbrication des boucles et disent: "C'est !". O(n3)
Raphael
3
En recherchant toute utilisation d'une analyse lissée autre que Simplex, j'ai trouvé une liste organisée par l'un des gars qui a découvert la technique.
Raphael
1
@DaveClarke que diriez-vous des personnes travaillant chez IBM ou HP ou NTT? Ne devraient-ils pas utiliser ce genre d'analyse?
Marcos Villagra
1
@DaveClarke je fais.
Kevin

Réponses:

12

Je peux me tromper, mais je considère l'analyse lissée comme un moyen d' expliquer le comportement en pratique des algorithmes qui ont de mauvaises garanties théoriques (simplex, k-means, etc.). Je ne sais pas ce que cela signifierait d' utiliser analyse lissée dans la pratique, sauf pour justifier l'utilisation d'une heuristique particulière avec de mauvaises performances dans le pire des cas ("Mon heuristique a un comportement dans le pire des cas, mais une analyse lissée indique bien faire en pratique etc etc ")

Suresh
la source
2
Le problème est que jusqu'à présent, les grands succès de l'analyse lissée ont été d'expliquer la pratique actuelle, de sorte que les pratiquants pourraient simplement réagir en disant "c'est bien que tout ce que je fais puisse être prouvé". :). Je ne sais pas si quelqu'un a décidé d'utiliser une méthode heuristique jusqu'ici moins connue PARCE QUE l'analyse lissée.
Suresh
Une analyse formelle lissée est très difficile, il n'y a aucune raison que quiconque en théorie ne devrait pas trop la pratiquer. D'un autre côté, si vous le considérez comme une heuristique utilisée pour analyser un algorithme (à savoir, l'entrée est semi-aléatoire), alors elle est probablement utilisée tout le temps.
Yuval Filmus
3

La façon dont les gens analysent les algorithmes dans le monde réel est très différente de celle du milieu universitaire. Alors que dans le monde universitaire, le but est de trouver une limite supérieure prouvée correcte sur le temps de course, dans la vie réelle, le but est de comprendre comment l'algorithme fonctionne et quels ajustements peuvent améliorer le temps de course. Il existe deux méthodes principales interdites dans le monde universitaire mais utilisées dans la pratique:

  • La méthode d'approximation. Ici, vous utilisez beaucoup d'hypothèses simplificatrices pour essayer de prévoir le temps d'exécution d'un algorithme. Similaire à ce que les physiciens théoriques faisaient (autrefois).
  • Expérimentation. Vous exécutez votre algorithme et mesurez plusieurs statistiques - combien de temps est passé à chaque partie, combien de fois chaque fonction a été appelée, à quelle fréquence chaque branche a-t-elle été exécutée, etc. Ces informations peuvent être utilisées pour optimiser l'algorithme. L'expérimentation permet également de savoir si certaines approximations effectuées lors de l'analyse de l'algorithme fonctionnent en pratique ou non.

Cela dit, je ne pense pas qu'il soit très courant d'analyser un algorithme dans la pratique, à part ajouter du texte de remplissage dans une publication universitaire connexe. L'accent est mis sur le génie logiciel ou sur l'optimisation de bas niveau, selon le sujet.

Enfin, l'analyse lissée est une heuristique qui peut être utilisée pour expliquer pourquoi les algorithmes fonctionnent mieux en pratique que ne le suggérerait leur pire cas - à savoir que certaines entrées sont "aléatoires" dans un certain sens. Cette heuristique peut être utilisée pour approximer le comportement de l'algorithme si l'on utilise la méthode d'approximation.

Yuval Filmus
la source
"Dans le monde universitaire, le but est de trouver une limite supérieure prouvée correcte sur le temps de course" - c'est un but, pas le but. Il y a aussi beaucoup de travail sur l'analyse de cas moyenne, même si l'étudiant CS moyen peut ne pas en voir beaucoup (parce que c'est relativement difficile). "Comprendre comment fonctionne l'algorithme" est, sans doute, la base de toute l'algorithmique dans le monde universitaire.
Raphael