Séminaire Algorithmique : « Génération aléatoire des graphes de Git », Julien Courtiel (GREYC)
Sciences 3- S3 351Vous développez pour un logiciel de gestions de versions, tel Mercurial ou Git ? Et en plus vous aimeriez avoir un moyen de tester vos programmes via des graphes de projet tirés aléatoirement ? Incroyable, cet exposé est fait pour vous ! (et bravo d'exister.) Nous nous intéressons ici à une famille de graphes qui … Continue reading Séminaire Algorithmique : « Génération aléatoire des graphes de Git », Julien Courtiel (GREYC)
Séminiare Algorithmique « Sous-shifts au langage stable », Samuel Petite (LAMFA, Univ. Picardie)
Sciences 3- S3 351Les sous-shifts au langage stable forment une classe de sous-shifts qui a été récemment introduite par V. Cyr et B. Kra. Cette famille contient de nombreux exemples classiques de sous-shifts, de diverses complexités allant des systèmes d’entropie strictement positive, comme les sous-shifts de type fini, aux systèmes de faible complexité, comme les sous-shifts de complexité … Continue reading Séminiare Algorithmique « Sous-shifts au langage stable », Samuel Petite (LAMFA, Univ. Picardie)
Séminaire Algorithmique : « StarMalloc : un allocateur de mémoire moderne renforcé formellement vérifié », Antonin Reitz (équipe Prosecco, INRIA Paris)
Sciences 3- S3 351Malgré la popularisation de langages modernes qui permettent une gestion sûre de la mémoire, C et C++ restent des langages de choix pour le développement de nombreux logiciels très couramment utilisés. Si ces langages permettent d'obtenir de bonnes performances, ils sont particulièrement vulnérables aux attaques par corruption mémoire. Des études récentes estiment que des erreurs … Continue reading Séminaire Algorithmique : « StarMalloc : un allocateur de mémoire moderne renforcé formellement vérifié », Antonin Reitz (équipe Prosecco, INRIA Paris)
Séminaire Algorithmique : « Combinatoire de mots, musiques traditionnelles et improvisation avec ordinateur », Marc Chemillier (EHESS, Paris)
Sciences 3- S3 351En informatique théorique, la combinatoire des mots consiste à étudier des séquences de symboles appelées des mots sur un alphabet. Ce concept est bien adapté à la description de la succession d’événements à l’intérieur d’une séquence musicale. Nous l’avons utilisé pour étudier certains rythmes dans les musiques africaines de la forme 3 2n 3 2 n+1 (pour n = 0 … Continue reading Séminaire Algorithmique : « Combinatoire de mots, musiques traditionnelles et improvisation avec ordinateur », Marc Chemillier (EHESS, Paris)
Séminaire Algorithmique : « Classes de sous-shifts définis par des formules logiques », Rémi Pallen (ENS Paris Saclay)
Sciences 3- S3 351Une configuration est un coloriage du plan Z². Habituellement, les ensembles de configurations étudiés sont ceux définis par un ensemble de motifs “interdits” n’apparaissant dans aucune des configurations de l’ensemble. De tels ensembles sont appelés sous-shifts. Dans ce séminaire, on définit les ensembles de configurations grâce à la logique Monadique du Second Ordre (MSO), et … Continue reading Séminaire Algorithmique : « Classes de sous-shifts définis par des formules logiques », Rémi Pallen (ENS Paris Saclay)
Séminaire Algorithmique : « Random Deterministic Automata With One Added Transition », Cyril Nicaud (LIGM, Univ. Paris-Est)
Sciences 3- S3 351Every language recognized by a non-deterministic finite automaton can be recognized by a deterministic automaton, at the cost of a potential increase of the number of states, which in the worst case can go from n to 2^n. In this talk, we investigate this classical result in a probabilistic setting where we take a random … Continue reading Séminaire Algorithmique : « Random Deterministic Automata With One Added Transition », Cyril Nicaud (LIGM, Univ. Paris-Est)
Séminaire Algorithmique : « Planar or almost planar graphs: topology to the rescue of algorithms », Arnaud de Mesmay (LIGM, Univ. Paris-Est)
Sciences 3- S3 351Many graphs encountered in practice have a particular structure. For example, road networks have few or no intersections when drawn in a plane. We will see how this type of property interacts with the combinatorics of graphs, and often leads to the development of algorithms that are more efficient than in the general case. This … Continue reading Séminaire Algorithmique : « Planar or almost planar graphs: topology to the rescue of algorithms », Arnaud de Mesmay (LIGM, Univ. Paris-Est)
Séminaire Algorithmique : « Combinatoire énumérative et bijective de différentes familles de chemins de Dyck avec trous d’air », Rémi Maréchal (GREYC, Caen)
Sciences 3- S3 351Cet exposé se situe dans le cadre de la combinatoire des chemins sur réseau. On introduit ici une généralisation des chemins de Dyck (dits “avec trous d’air”), avant de se pencher sur diverses questions classiques à leur sujet : énumération, distributions de motifs, étude de sous-ensembles, etc. Ce faisant, des suites d’entiers positifs (connues dans … Continue reading Séminaire Algorithmique : « Combinatoire énumérative et bijective de différentes familles de chemins de Dyck avec trous d’air », Rémi Maréchal (GREYC, Caen)
Séminaire Algorithmique : « Un cafard sous le chapeau », Victor Luftalla (LIS, Univ. Aix-Marseille)
Sciences 3- S3 351En 2023 Smith, Myers, Kaplan et Goodman-Strauss ont découvert le chapeau : une monotuile apériodique du plan euclidien. C’est-à-dire que l’on peut paver le plan euclidien avec des copies (à isométrie près) du chapeau, mais qu’il est impossible de faire un pavage périodique. Simultanément, Greenfeld et Tao ont prouvé l’existence d’un groupe finiment présenté (Z2×H où H est … Continue reading Séminaire Algorithmique : « Un cafard sous le chapeau », Victor Luftalla (LIS, Univ. Aix-Marseille)
Séminaire Algorithmique : Nicolas Ollinger (LIFO, Univ. Orléans)
Sciences 3- S3 351séminaire algorithmique : « Un Panorama des Modes de Mises à Jour des Réseaux d’Automates Booléens », Athénaïs Vaginay (GREYC)
Sciences 3- S3 351Abstract: Boolean automata networks are used as discrete models of biological systems. They consist of a generalization of cellular automata, where the grid is replaced by a directed graph, and each node has its own transition function. Automata change status over time, according to a chosen update mode, for example: synchronous, asynchronous, general-asynchronous, and the recently … Continue reading séminaire algorithmique : « Un Panorama des Modes de Mises à Jour des Réseaux d’Automates Booléens », Athénaïs Vaginay (GREYC)
Séminaire Algorithmique : Abdallah Saffidine (Univ. South New Wales, Sydney, Australie), « Generalizing Roberts’ characterization of unit interval graphs? How not to do it! »
Sciences 3- S3 351A celebrated result by Roberts establishes that an interval graph can be represented by unit-length intervals on the real line if and only if no vertex has three non-adjacent neighbors. In 2016, Durán et al. conjectured a generalization of this result, which we recently investigated. We ran an industrial mixed integer programming (MIP) solver on … Continue reading Séminaire Algorithmique : Abdallah Saffidine (Univ. South New Wales, Sydney, Australie), « Generalizing Roberts’ characterization of unit interval graphs? How not to do it! »