Existe-t-il une méthode pour une analyse automatique d'exécution des algorithmes?

Je me demande, existe-t-il une méthode d'analyse automatique de l'exécution qui fonctionne au moins sur un sous-ensemble pertinent d'algorithmes (algorithmes pouvant être analysés)?

Je googlé « Analyse de l' algorithme automatique » qui m'a donné ce mais il est MATHY aussi. Je veux juste un exemple simple en pseudo-code que je peux comprendre. Peut-être trop précis, mais je pensais que ça valait le coup.

L' outil COSTA fait exactement cela, bien qu'il échoue dans de nombreux cas, comme vous pouvez l'imaginer, en raison de problèmes de calculabilité . Il existe de nombreux articles à ce sujet; L'analyse des coûts du bytecode Java par E. Albert, P. Arenas, S. Genaim, G. Puebla, D. Zanardini est un bon point de départ.

L'approche adoptée consiste à déduire une récurrence d'exécution à partir du code Javabyte, puis à la convertir en un formulaire fermé. L'outil calcule également les limites d'utilisation de l'espace.

Aucun algorithme ne peut décider si un algorithme donné s'arrête ou non, donc en particulier aucun algorithme ne peut analyser de manière précise la complexité d'un algorithme donné.

Je connais une approche de l'analyse de cas moyenne (semi-) automatisée, à savoir MaLiJAn ¹. Il ressemble étroitement au type d'analyse que Knuth utilise dans TAoCP. L'idée centrale est de

• modéliser le programme (flux) comme chaîne de Markov,
• $n$
• $n$
• utiliser l'algèbre informatique pour dériver le coût moyen (par rapport à ces fonctions).

Notez que seules les mesures de coût additives (par exemple, les comparaisons, le "temps") fonctionnent et que seule la valeur attendue est exacte (en supposant des fonctions de probabilité parfaites), des moments plus élevés ne peuvent pas être dérivés.

Toutes les étapes, à l'exception de l'extrapolation, sont rigoureuses [2] et il a été démontré que la méthode reproduit des résultats bien connus avec une grande précision - avec des entrées d'échantillons aléatoires appropriées, bien sûr. S'il n'y a pas de preuve ni même de garantie d'approximation sur les résultats (l'étape d'extrapolation est jusqu'à présent purement heuristique) les résultats obtenus avec l'outil permettent bien d'expérimenter des algorithmes difficiles à analyser et de formuler des hypothèses [3,4].

1. Divulgation complète: je faisais partie de ce groupe de recherche et j'avais participé au développement de l'outil.
2. Analyse de maximum de vraisemblance des algorithmes et des structures de données par U. Laube et M. Nebel (2010) [ préimpression ]
3. Ingénierie Quicksort Dual Pivot de Java 7 à l'aide de MaLiJAn par S. Wild et al (2012) [ préimpression ]
4. Analyse de maximum de vraisemblance de la méthode Ford – Fulkerson sur des graphiques spéciaux par U. Laube et M. Nebel (2015) [ préimpression ]

Bien sûr, comme l'a noté Yuval Filmus, il ne faut pas s'attendre à une solution générale à ces problèmes. Mais comme c'est généralement le cas, des solutions peuvent être trouvées pour des sous-ensembles intéressants du cas général.

Je ne suis en aucun cas un expert, ni même des connaissances significatives dans ce domaine, car il se trouve que je connais des travaux de ce genre. Il s'agit de l'analyse automatique de la complexité moyenne, et le travail a été réalisé par Philippe Flajolet et ses collègues.

$\lambda\acute\upsilon\omega$

Un article que j'ai trouvé sur le Web est un article de 1990: Analyse automatique des cas moyens d'algorithmes par Philippe Flajolet, Paul Zimmermann et Bruno Salvy .

Je m'attendrais à ce que des articles ultérieurs aient étendu ce travail, mais je ne sais pas vraiment. Le travail a été assez abondamment cité et sa recherche sur le Web devrait produire des travaux plus récents sur le même sujet.

Maintenant, j'ai peur que le travail de Flajolet et de ses collègues soit très mathématique, et je ne m'attendrais pas à une lecture facile.