Julien David (LIPN, Université Paris Nord)

L’étude théorique des algorithmes est très souvent limitée à l’analyse de la complexité dans le pire des cas. Il existe pourtant de nombreuses notions de complexité qui apportent des informations essentielles à la bonne compréhension de l’efficacité des algorithmes. Parmi celles-ci, la complexité en moyenne consiste à supposer une distribution de probabilité sur les entrées (on prendra le plus souvent la distribution uniforme), et d’évaluer l’espérance du nombre de fois où une opération donnée sera effectuée.



Parmi les critiques les plus récurrentes sur l’analyse théorique des algorithmes, on retrouve les suivantes:


  • l’analyse dans le pire des cas n’est pas représentative de l’efficacité d’un algorithme, car bien souvent, ce pire des cas ne se produit que sur un ensemble d’entrées très restreint alors que l’algorithme semble avoir un bon comportement “en pratique”.

  • l’analyse en moyenne n’apporte pas d’information sur ce qui se passe “en pratique”, car elle suppose souvent des distributions de probabilité qui correspondent pas “à la réalité”.

Dans cet exposé, nous discuterons de cette seconde critique. Puis un outil sera proposé pour faciliter l’étude du comportement des algorithmes, mêlant des techniques de génération aléatoire à des techniques de fouille de données. Enfin, une famille de générateurs aléatoires sera proposée.