Marches aléatoires, arbres et optimalité d'algorithmes - Université de Lorraine Accéder directement au contenu
Thèse Année : 1999

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

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

  • HAL Id : tel-01747525 , version 1

Citer

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⟩
73 Consultations
45 Téléchargements

Partager

Gmail Facebook X LinkedIn More