Séminaire interne du LIX
Année 03-04

Autumn 2003

• November 11, 2003
  Speaker: Behshad Behzadi
  Title: The Transformation Distance
  Abstract
  Evolution acts in several ways on biological sequences: either by mutating an element, or by inserting, deleting or copying a segment of the sequence. Varr'e et al. defined a transformation distance for the sequences, in which the evolutionary operations are copy, reverse copy and insertion of a segment. They also proposed an algorithm to calculate the transformation distance. This algorithm is O(n^4) in time and O(n^4) in space, where $n$ is the size of the sequences. In this work, we propose an improved algorithm which costs O(n^2) in time and O(n^2) in space. Furthermore, we extend the operation set by adding point deletions. We present an algorithm which is O(n^3) in time and O(n^2) in space for this extended case.
  

• October 29, 2003
  Speaker: Michel Nguyên Thê
  Title: Aire et autres fonctionnelles du mouvement brownien par fonctions génératrices
  Abstract
  La distribution de fonctionnelles du mouvement brownien telles que l'aire ou le moment d'inertie a bien été étudiée en probabilités, à base de mathématiques du continu, dont notamment la formule de Feynman-Kac à partir des années 40. Plus récemment divers types de mouvement brownien ont été étudiés, comme le pont brownien, le méandre ou l'excursion. Le théorème de Louchard en particulier permet de passer de la double transformée de Laplace d'une fonctionnelle du pont brownien vers celle de l'excursion.

  Nous montrerons ainsi à titre d'exemple comment trouver la distribution de l'intégrale du carré du pont brownien, pour en déduire celle de l'excursion.

  Nous montrerons ensuite comment retrouver l'aire des divers types de mouvement brownien cités en étudiant d'abord leurs équivalents discrets à l'aide des séries génératrices, puis en pompant les moments de la distribution limite suivant une méthodologie mise au point par Takács, dans le cadre de l'étude de la longueur de cheminement des arbres de Catalan.

  En généralisant la méthode à plusieurs variables, nous sommes capables d'une part de trouver des récurrences permettant de calculer rapidement les moments joints entre deux fonctionnelles monomiales, et d'autre part de retrouver des formules du type théorème de Louchard pour des fonctionnelles polynomiales.

  On notera que le calcul de moments joints se fait a priori beaucoup moins aisément en utilisant des objets continus, car on fait intervenir des intégrales multiples avec un nombre croissant de signes intégration.
  

• October 15, 2003
  Speaker: Moez Draief
  Title: Files d'attente, marches aléatoires et algorithme RSK
  Abstract
  Si X est une marche aléatoire et si M est son maximum, alors le processus 2M-X a la même loi que X+conditionnée à rester positive. Ce résultat a été prouvé par Pitman pour le mouvement brownien. Je présenterai une +version discrète de ce résultat et en proposerai une généralisation multidimentionnelle. La preuve est basée sur un résulat +classique en théorie des files d'attente: Théorème de Burke. Cette version multidimentionnelle fait appel à un opérateur (min, max, +) qui est étroitement lié +à la correspondance RSK. Ceci permet en outre de donner une interprétation de l'algorthme RSK en terme de file d'attente. Par +ailleurs, en exploitant le lien entre tableau de Young et fonction de Schur on mettra l'accent sur une propriété de symétrie des +files d'attente. Enfin, je décrirai comment d'autres résultats classiques en théorie des files d'attente permettent+de déterminer le comportement asymptotique d'un modèle de percolation dirigée.