Marches aléatoires, arbres et optimalité d'algorithmes - Université de Lorraine Access content directly
Theses Year : 1999

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».
Fichier principal
Vignette du fichier
SCD_T_1999_0310_MARCKERT.pdf (3.8 Mo) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

tel-01747525 , version 1 (29-03-2018)

Identifiers

  • HAL Id : tel-01747525 , version 1

Cite

Jean-François Marckert. Marches aléatoires, arbres et optimalité d'algorithmes. Mathématiques générales [math.GM]. Université Henri Poincaré - Nancy 1, 1999. Français. ⟨NNT : 1999NAN10310⟩. ⟨tel-01747525⟩
72 View
41 Download

Share

Gmail Facebook X LinkedIn More