Marches aléatoires, arbres et optimalité d'algorithmes

Non disponible / Not availableCette 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 dansces deux cas. Comme application, on obtient les résultats suivants sur la structuredes 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 binairesde taille n.- le calcul de la loi limite de la moyenne harmonique de la profondeur des noeudsdans un arbre général de taille n.Dans la deuxième partie, nous nous intéressons à un problème issu de l'intelligenceartificielle. Il consiste à construire de façon optimale un algorithme interruptible enutilisant 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»