BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//wp-events-plugin.com//7.2.3.1//EN
TZID:Europe/Paris
X-WR-TIMEZONE:Europe/Paris
BEGIN:VEVENT
UID:7931@i2m.univ-amu.fr
DTSTART;TZID=Europe/Paris:20160113T110000
DTEND;TZID=Europe/Paris:20160113T120000
DTSTAMP:20241120T205608Z
URL:https://www.i2m.univ-amu.fr/evenements/complexite-moyenne-d-algorithme
 s-de-pattern-matching-et-optimalite/
SUMMARY: (...): Complexité moyenne d'algorithmes de pattern matching et op
 timalité
DESCRIPTION:: Nous étudions la vitesse asymptotique d'algorithmes de patte
 rn matching cherchant un motif $w$ dans un texte aléatoire Bernoulli. La 
 vitesse asymptotique est définie comme la limite\, quand $n$ tend vers l'
 infini\, de l'espérance du rapport de $n$ par le nombre d'accès en lectu
 re effectués pour un texte aléatoire de taille $n$. L'étude est limité
 e aux algorithmes qui\, à chaque itération et à partir de la position c
 ourante\, lisent une position relative déterminée par leur état interne
  et\, selon la lettre lue\, changent d'état interne\, incrémentent (ou p
 as) la position courante et\, le cas échéant\, signalent un match (a pri
 ori tous les algorithmes usuels peuvent être codés sous cette forme). É
 tant donné $w$\, l'ordre d'un algorithme est la plus grande position\, re
 lativement à la position courante\, qu'il lit en cherchant $w$ (général
 ement $|w|-1$ ou $|w|$). Nous montrons que si un texte est Bernoulli alors
  la séquence des états internes d'un algorithme est une chaîne de Marko
 v à états cachés dont on sait expliciter les probabilités de transitio
 n\, ce qui permet d'en calculer la vitesse asymptotique.Notre résultat pr
 incipal est\, qu'étant donnés un motif $w$\, un entier $k\\geq |w|-1$ et
  un modèle Bernoulli\, il existe\, parmi les algorithmes d'ordre $k$\, un
  algorithme de vitesse asymptotique maximale dont l'ensemble des états in
 ternes est en bijection avec un sous-ensemble des fonctions partielles $f$
  de $\\{0\, \\ldots\, n\\}$ vers $\\alp$ telles que\, pour tout $i
CATEGORIES:Séminaire,Mathématiques-Évolution-Biologie
END:VEVENT
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:STANDARD
DTSTART:20151025T020000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
END:STANDARD
END:VTIMEZONE
END:VCALENDAR