Marches aléatoires, arbres et optimalité d'algorithmes
Abstract
Non disponible / Not available
Cette thèse est corn posée de deux parties indépendantes. Dans la première partie composée de quatre chapitres, nous nous intéressons aux algorithmes de recherche du maximum et des zéros d'une marche aléatoire simple symétrique.
On exhibe des algorithmes optimaux en moyenne et pour l'ordre stochastique dans
ces deux cas. Comme application, on obtient les résultats suivants sur la structure
des arbres de Galton-Watson:
- le calcul des moments de la largeur des arbres de Cayley de taille n répondant ainsi
à une question d'Odlyzko & Wilf.
- un calcul simple de la limite en loi du couple hauteur-largeur dans les arbres binaires
de taille n.
- le calcul de la loi limite de la moyenne harmonique de la profondeur des noeuds
dans un arbre général de taille n.
Dans la deuxième partie, nous nous intéressons à un problème issu de l'intelligence
artificielle. Il consiste à construire de façon optimale un algorithme interruptible en
utilisant une suite d'algorithmes qui ne le sont pas. Ce problème nous amène à
chercher une suite de nombres positifs (Xi)i<:O maximisant la quantité puis à étudier les solutions de l'équation de Bellman ainsi que celle de l'équation différentielle non standard,
z'(a) = 1 + z'(a)z'(z(a))e-z{z{a)) + z'(a)e-z{z{a».
Origin | Files produced by the author(s) |
---|
Loading...