Sur un algorithme de recherche quasi-optimal et la fonction th\^eta de Jacobi

Odlyzko examine les performances de diverses strat\'egies de recherche de maximum ou de z\'ero en environnement inconnu. Il d\'ecrit un algorithme quasi-optimal en moyenne pour la recherche du maximum d'une marche al\'eatoire sur $n$ pas. Dans le m\^eme contexte, en utilisant un principe de d\'enombrement d\^u \`a Odlyzko, on d\'emontre que la loi limite du co\^ut de recherche est la m\^eme pour n'importe quel algorithme quasi-optimal. On caract\'erise cette loi successivement en terme - de la fonction th\^eta de Jacobi - du mouvement Brownien.

Travail commun avec Jean-Fran\c cois Marckert \& Marc Yor.