Collecter un nombre inconnu de coupons

Dans les algorithmes de cartographie d'Internet, l'un des problemes cles a resoudre est celui de la decouverte des differentes interfaces de sortie d'un routeur en cas d'equilibrage de charge: combien de sondes doit-on envoyer tester la connexion pour etre raisonnablement certain d'avoir decouvert toutes les interfaces ? Une des solutions existantes est une variante du probleme du collecteur de coupons, qui consiste a associer a chaque nombre d'interfaces decouvertes un nombre de sondes au-dela duquel on considere que l'on peut s'arreter. Dans cet article, nous donnons une formule close pour l'association et prouvons sa quasi-optimalite.ne formule close pour l'association et prouvons sa quasi-optimalite.