Évènements

Elastic degenerate strings provide a flexible framework for representing sequences with structured variability, generalizing classical string models while preserving algorithmic tractability. In this talk, we present a comprehensive framework for indexing such objects, culminating in the construction of an FM-index that supports efficient pattern matching. We begin by revisiting the notion of elastic degeneracy and … Continue reading Séminaire Algorithmique : « From Elastic Degenerate Strings to Full-Text Indexing: Suffix Sorting, BWT, and FM-Index Construction and Search », Francesco Pio Marino (Univ. Catane, Italie)

Au début des années 2000, Okhotin a introduit deux familles de grammaires formelles, les grammaires conjonctives et les grammaires booléennes, qu’il présente comme “le véritable cas général des grammaires sans contexte”. Ces grammaires enrichissent les grammaires algébriques par l’ajout d’une opération de conjonction pour les grammaires conjonctives et de la négation en plus de la … Continue reading Séminaire Algorithmique : « Un automate pour les caractériser tous », Théo Grente (GREYC)

In their book “Analytic Combinatorics”, Flajolet and Sedgewick describe a general approach that starts from a combinatorial description, translates this description into equations satisfied by generating functions, views these generating functions as analytic functions and exploits their singular behavior to deduce asymptotic properties of the combinatorial objects when their size becomes large. With Bruno Salvy, … Continue reading Séminaire Algorithmique : « Effective Asymptotics of Combinatorial Systems », Carine Pivoteau (LIGM, Univ. Paris-Est Marne la Vallée)

Le but de cet exposé est d’introduire les deux fondements de l’analyse calculable : la théorie des espaces représentés et ses liens avec la topologie, et la réduction de Weihrauch. J’insisterai en particulier sur le fait que la réduction de Weihrauch est définie grâce à une notion de multifonction continue que l’on ne peut définir … Continue reading Séminaire Algorithmique : « Weihrauch et la topologie », Emmanuel Rauzy (LACL, Univ. Paris-Est Créteil)

Dans cet exposé nous présenterons le système de représentation RNS utilisé pour l’arithmétique des grands entiers. Nous nous intéresserons en particulier à la multiplication modulaire en RNS et son application en cryptographie. Les algorithmes de Montgomery et de Barrett sont les plus couramment utilisés pour la multiplication modulaire. En RNS c’est l’approche de Montgomery qui … Continue reading Séminaire Algorithmique : « Multiplication modulaire dans le système de représentation Residue Number System », Christophe Nègre (GREYC, Caen)

Il y a fort longtemps (en l’an 2018), dans un bureau fort lointain (le S3-354), le jeune Matthieu Dien et ma modeste personne se sont lancés dans une quête : un problème qui ne prendrait que “10 minutes à résoudre”. Il aura fallu 8 ans, et l’aide du chevaleresque Paul Dorbec, pour qu’un article ait … Continue reading Séminaire Algorithmique : « One-two trees, let’s twist! », Julien Courtiel (GREYC, Caen)

Codd’s Theorem, a fundamental result of database theory, asserts that relational algebra and relational calculus have the same expressive power on relational databases. We explore Codd’s Theorem for databases over semirings and establish two different versions of this result for such databases: the first version involves the five basic operations of relational algebra, while in … Continue reading Séminaire Algorithmique : « Codd’s Theorem for Databases over Semirings », Guillermo Badia (University of Queensland, Australie)

Titre et résumé à venir.