BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Normastic - ECPv6.15.18//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-ORIGINAL-URL:https://www.normastic.fr
X-WR-CALDESC:Évènements pour Normastic
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Europe/Paris
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
DTSTART:20150329T010000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:20151025T010000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
DTSTART:20160327T010000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:20161030T010000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
DTSTART:20170326T010000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:20171029T010000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20160519T140000
DTEND;TZID=Europe/Paris:20160519T180000
DTSTAMP:20260411T123819
CREATED:20160513T135408Z
LAST-MODIFIED:20250708T114220Z
UID:13420-1463666400-1463680800@www.normastic.fr
SUMMARY:Satellite AlgoComb de la journée Maths-STIC (20/05/2016)
DESCRIPTION:Satellite AlgoComb de la journée Maths-STIC du 20 mai 2016\nUne journée de l’axe  Algorithmique et Combinatoire est organisée le 19 mai de 14H à 18H\, veille de la Journée Maths-Stic. \nSalle de séminaire du Département d’Informatique\nUFR de Sciences & Technologies\nSite du Madrillet\nUniversité de Rouen.\n\nProgramme:\n\n\n 14h-14h45 : Nicolas Bedon: Le complémentaire du langage d’un automate branchant est encore le langage d’un automate branchant.\n\nLes automates traditionnels (automates de Kleene) sont un modèle naturel et simple pour représenter des programmes séquentiels: les mots reconnus peuvent être vus comme des traces d’exécution de programmes séquentiels. Dans cet exposé nous nous intéressons aux automates branchants\, définis et étudiés par Lodaya & Weil il y a une quinzaine d’années. Les automates branchants sont une extension des automates de Kleene avec deux nouvelles catégories de transitions permettant de mettre en parallèle des chemins de l’automate. Les étiquettes des chemins ne sont plus alors des mots (ordres totaux)\, mais des pomsets (ordres partiels)\, qui peuvent aussi être vus comme des traces d’exécution de programmes concurrents. Le complémentaire du langage d’un automate de Kleene est encore le langage d’un automate de Kleene\, et ce dernier se calcule effectivement (et facilement) à partir du premier. Ce calcul peut être réalisé par plusieurs constructions bien connues. L’une d’entre elles repose sur une construction algébrique\, réalisable car l’algèbre associée à un automate est finie. Nous verrons que cette construction se généralise aux automates branchants\, mais elle est plus difficile\, car cette fois-ci les algèbres associées aux automates peuvent être infinies.\n\n14h45-15h30: Florent Madelaine: Complexité du model checking paramétré par la structure.\n\nLa conjecture de la dichotomie énoncée il y a bientôt 25 ans par Feder et Vardi stipule que tout problème de contraintes est soit dans P\, soit NP-complet. Ces problèmes peuvent être formulés comme des problèmes de model checking paramétrés par la structure où la logique considérée est un certain fragment de la logique du premier ordre : la formule représente la partie syntaxique d’une instance du problème de contrainte (c’est-à-dire les variables et les contraintes imposés entre ces variables) et la structure décrit la nature même de ces contraintes\, c’est-à-dire les combinaisons de valeurs autorisées. Dans le cas booléen\, qui correspond à une variante du problème SAT\, la conjecture est supportée par le théorème de Schaefer\, dont la preuve repose sur une machinerie algébrique proposée par Post. Cette machinerie peut être adaptée pour résoudre des problèmes  de model checking différents. Dans cet exposé\, je me propose de présenter une introduction vulgarisée à cette problématique puis de commenter quelques résultats de classification. \n\n\n15h30-15h45: Pause\n15h45-16h30: Thierry Lecroq: La transformée dans l’ordre des blocs binaires.\n(Travail commun avec Jackie Daykin\, Richard Groult\, Yannick Guesnet\, Arnaud Lefebvre\, Martine Léonard et Elise Prieur-Gaston) \nDans cet exposé\, nous présentons une transformée bijective de type Burrows-Wheeler pour les mots binaires. La méthode originale par Burrows et Wheeler est basée sur l’ordre lexicographique pour les alphabets généraux. La transformation d’un mot est donc définie comme étant la dernière colonne de la matrice constituée par les conjugués du mot triés dans l’ordre croissant. Notre nouvelle approche applique l’ordre des blocs binaires\, appelé B-ordre\, ce qui\, en fait\, donne non pas une\, mais deux transformées : une basée sur des mots de Lyndon\, l’autre sur une répétition de mots de Lyndon. Ces transformées sont construites pour les B-mots qui sont des analogues aux mots de Lyndon (plus petits conjugués dans l’ordre considéré). Un calcul clé dans ces transformations est l’application d’une technique de tri des suffixes en temps linéaire. De plus\, nous montrons que le calcul des inverses de ces transformées peut se faire en temps linéaire en utilisant des arguments combinatoires simples.\n\n16h30-17h15: Brigitte Vallée: Fonction de récurrence d’un mot sturmien aléatoire\n(Travail commun avec Pablo Rotondo)\n \n\nLes mots sturmiens sont intensément étudiés\,  car ce sont  (informellement) les mots les plus simples non ultimement périodiques.  Nous  adoptons ici un point de vue  peu  classique\,  et nous nous intéressons à l’étude d’un mot sturmien aléatoire.  Il est bien connu que tout mot sturmien est défini par son angle $\alpha$\, qui est un irrationnel de l’intervalle $]0\, 1[$.    Il est donc naturel   de travailler dans un modèle aléatoire où  l’angle $\alpha$  est uniforme dans l’intervalle $]0\, 1[$. Nous étudions ainsi  la fonction de récurrence $(\alpha\, n)  \mapsto R_\alpha (n)$   qui  décrit le temps d’attente nécessaire pour obtenir tous les facteurs de longueur donnée $n$ du mot sturmien $S_\alpha$\, où  l’angle $\alpha$ est uniforme dans $]0\, 1[$  et la longueur $n$  uniforme dans $[1..N]$\, quand la borne $N$ tend vers $\infty$. Je présenterai les résultats obrenus\, et  je chercherai aussi à relier cette étude aléatoire avec des préoccupations  sturmiennes rouennaises (Lecroq\, Lefevre et Prieur-Gaston). Ces derniers  étudient  l’indice d’un mot sturmien\, qui  décrit la périodicité locale du mot\, et surtout la version abélienne  de ce paramètre. \n\n\n17h15-18h: Discussions sur l’axe.\n\n\n\n 
URL:https://www.normastic.fr/event/satellite-algocomb-de-la-journee-maths-stic-du-20-mai-2016/
LOCATION:Site du Madrillet\, 685 Avenue de l’Université\, Saint Etienne du Rouvray\, 76801
CATEGORIES:Algorithmique et Combinatoire
END:VEVENT
END:VCALENDAR